Изменения

'''Цепной код''' (англ: . ''chain code'') — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из <tex>2^n \times n</tex> элементов) получается из предыдущего циклическим сдвигом вверх. Цепной код позволяет исправить все одиночные ошибки при условии, что между любыми двумя ошибочно принятыми имеется по крайней мере три правильно принятых сигнала. Часто используется при передаче данных: видео, мобильной связи.

В качестве первого вектора берём вектор из <tex>n</tex> нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, пусть <tex>a_1\cdots dots a_n</tex>. Если в коде до этого не встречатся встречался вектор <tex>a_2\cdots dots a_n 1</tex>, то добавляем его. Иначе проверяем на наличие в коде вектора <tex>a_2\cdots dots a_n 0</tex>. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена. При таком построении видно, что элементы таблицы <tex> a_1^i\dots a_1^{i+n}</tex> равны элементам <tex> a_1^i\dots a_n^i</tex>

'''string[]''' chain_code('''int''' n): current = string('0', * n)

'''while (''' ''true):'' prefix = current[2..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'''

'''return ''' result В приведённом выше псевдокоде:* current — последний добавленный битовый вектор* result — список битовых векторов

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

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

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

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

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

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

Пусть был сгенерирован вектор <tex>a_1 \cdots dots a_{n - 1} 0</tex>. Ему предествовал предшествовал некоторый вектор <tex>b_1 a_1 \cdots dots a_{n - 1}</tex>. Так как алгоритм сначала пытается поместить в код вектор <tex>a_1 \cdots dots a_{n - 1} 1</tex>, то на этом шаге вектор <tex>a_1 \cdots dots a_{n - 1} 1</tex> уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида <tex>a_1 \cdots dots a_{n - 1} 0</tex> был добавлен в код, а значит, и вектор вида <tex>a_1 \cdots dots a_{n - 1} 1 </tex> также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде. == См. также == *[[Коды Грея]]*[[Коды антигрея]]*[[Коды Грея для перестановок]] == Источники информации ==*[http://en.wikipedia.org/wiki/Chain_code Wikipedia {{---}} Chain code]