Цепные коды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Доказательство корректности)
(Доказательство второго пункта)
Строка 40: Строка 40:
  
 
===Доказательство второго пункта===
 
===Доказательство второго пункта===
Покажем, что невозможно вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на единицу и кончающиеся на ноль. Докажем, что второй группы группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность единиц и нулей. Заметим, что слово {bc..yz}00 также не в коде. Оно могло быть получено из слов 1{bc..yz}0 и 0{bc..yz}0, одно из которых есть рассматриваемое {abc..yz}0. Но если другое слово и встретилось в коде, то мы бы получили из него {bc..yz}01, следуя алгоритму (причем это слово точно встретится в первый раз). Таким образом, слово {bc..yz}00 точно не в коде. Такую же цепочку рассуждений можно провести и для слова {c..yz}000, и так далее. На n-ом шаге мы бы получили утверждение, что слова из n нулей тоже нет в коде, и пришли бы к противоречию. Заметим, что исходя из третьего и четвертого шагов, все слова вида {abc..yz}1 встречаются строго раньше {abc..yz}0, которые точно записаны в код. Таким образом, слов, не попавших в код, нет.
+
 
 +
Покажем, что до генерации веткора из <tex>n</tex> нулей генерируются все остальные битовые вектора. Допустим, мы всё же получили вектор из всех нулей раньше, чем перебрали все вектора. Тогда рассмотрим множество векторов <tex>Z</tex>, которые не были сгенерированы алгоритмом и оканчиваются на ноль.
 +
 
 +
Пусть <tex>a_1 a_2 \cdots a_{n - 1} 0 \in Z</tex>. Докажем, что <tex>a_2 \cdots a_{n - 1} 0 \in Z</tex>. От противного, пусть вектор <tex>a_2 \cdots a_{n - 1} 0 0 </tex> был сгенерирован. Тогда ему предшествовал вектор <tex>b_1 a_2 \cdots a_{n - 1} 0</tex>. Так как по предположению <tex>b_1 \neq a_1</tex>, то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только <tex>a_2 \cdots a_{n - 1} 0 1</tex>.
 +
 
 +
Значит, если множество <tex>Z</tex> непусто, то оно содержит вектор из <tex>n</tex> нулей. Но это противоречит тому, что вектор из <tex>n</tex> нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы.
 +
 
 +
Пусть был сгенерирован вектор <tex>a_1 \cdots a_{n - 1} 0</tex>. Ему предествовал некоторый вектор <tex>b_1 a_1 \cdots a_{n - 1}</tex>. Так как алгоритм сначала пытается поместить в код вектор <tex>a_1 \cdots a_{n - 1} 1</tex>, то на этом шаге вектор <tex>a_1 \cdots a_{n - 1} 1</tex> уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида <tex>a_1 \cdots a_{n - 1} 0</tex> был добавлен в код, а значит, и вектор вида <tex>a_1 \cdots a_{n - 1} 1 </tex> также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде.

Версия 22:08, 12 января 2012

Цепной код — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из [math]2^n \times n[/math] элементов) получается из предыдущего циклическим сдвигом вверх.

Алгоритм получения цепного кода для двоичных векторов

В качестве первого вектора берём вектор из [math]n[/math] нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, пусть [math]a_1\cdots a_n[/math]. Если в коде до этого не встречатся вектор [math]a_2\cdots a_n 1[/math], то добавляем его. Иначе проверяем на наличие в коде вектора [math]a_2\cdots a_n 0[/math]. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.

Псевдокод алгоритма

chain_code(n):
  current = string('0', n)
  result = [current]
  while (true):
    prefix = current.substring(2, n)
    if concat(prefix, '1') not in result:
      current = concat(prefix, '1')
    else concat(prefix, '0') not in result:
      current = concat(prefix, '0')
    else:
      break
    result.append(current)
  return result

В приведённом выше псевдокоде:

  • current — последний добавленный битовый вектор
  • result — список битовых векторов

Доказательство корректности

Разобьем доказательство на две части:

  1. Доказательство того, что один и тот же вектор встречается в коде не более одного раза.
  2. Доказательство того, что алгоритм перебирает все возможные вектора прежде, чем получит вектор из [math]n[/math] нулей.

Доказательство первого пункта

Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из [math]n[/math] нулей. Рассмотрим первое такое противоречие: последним добавлен вектор [math]a_1 a_2 \cdots a_n[/math], вектора [math]a_2 \cdots 1[/math] и [math]a_2 \cdots a_n 0[/math] уже присутствуют в коде.

Далее есть две возможных ситуации: вектор [math]a_2 \cdots a_n 0[/math] состоит из [math]n[/math] нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.

Во второй сутиации каждому из векторов [math]a_2 \cdots a_n 1[/math] и [math]a_2 \cdots a_n 0[/math] предшествовали некоторые вектора в коде, пусть [math]B_1 = b_1 a_2 \cdots a_n[/math] и [math]B_2 = b_2 a_2 \cdots a_n[/math]. Так как мы рассматриваем первое противоречие, то [math]b_1 \neq b_2[/math].

Но в таком случае вектор [math]a_1 a_2 \cdots a_n[/math] совпадает с одним из векторов [math]B_1[/math] или [math]B_2[/math]. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.

Доказательство второго пункта

Покажем, что до генерации веткора из [math]n[/math] нулей генерируются все остальные битовые вектора. Допустим, мы всё же получили вектор из всех нулей раньше, чем перебрали все вектора. Тогда рассмотрим множество векторов [math]Z[/math], которые не были сгенерированы алгоритмом и оканчиваются на ноль.

Пусть [math]a_1 a_2 \cdots a_{n - 1} 0 \in Z[/math]. Докажем, что [math]a_2 \cdots a_{n - 1} 0 \in Z[/math]. От противного, пусть вектор [math]a_2 \cdots a_{n - 1} 0 0 [/math] был сгенерирован. Тогда ему предшествовал вектор [math]b_1 a_2 \cdots a_{n - 1} 0[/math]. Так как по предположению [math]b_1 \neq a_1[/math], то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только [math]a_2 \cdots a_{n - 1} 0 1[/math].

Значит, если множество [math]Z[/math] непусто, то оно содержит вектор из [math]n[/math] нулей. Но это противоречит тому, что вектор из [math]n[/math] нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы.

Пусть был сгенерирован вектор [math]a_1 \cdots a_{n - 1} 0[/math]. Ему предествовал некоторый вектор [math]b_1 a_1 \cdots a_{n - 1}[/math]. Так как алгоритм сначала пытается поместить в код вектор [math]a_1 \cdots a_{n - 1} 1[/math], то на этом шаге вектор [math]a_1 \cdots a_{n - 1} 1[/math] уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида [math]a_1 \cdots a_{n - 1} 0[/math] был добавлен в код, а значит, и вектор вида [math]a_1 \cdots a_{n - 1} 1 [/math] также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде.