Цепные коды

Цепной код — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из [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]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, которые точно записаны в код. Таким образом, слов, не попавших в код, нет.