Цепные коды

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