Изменения

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

Цепной код позволяет исправить все одиночные ошибки при условии, что между любыми двумя ошибочно принятыми имеется по крайней мере три правильно принятых сигнала. Часто используется при передаче данных: видео, мобильной связи. == Алгоритм получения цепного кода для двоичного вектора двоичных векторов ==# Берем в В качестве первого слова слово вектора берём вектор из <tex>n </tex> нулей.# Делаем циклический сдвиг предыдущего слова влево с потерей первого разрядаЧтобы получить следующий вектор, берём последний добавленный вектор, пусть <tex>a_1\dots a_n</tex>.# Приписываем к полученному слову Если в конец единицукоде до этого не встречался вектор <tex>a_2\dots a_n 1</tex>, то добавляем его. Проверяем, встречалось ли это слово Иначе проверяем на наличие в коде ранеевектора <tex>a_2\dots a_n 0</tex>.# Если неттакой не встречался, то записываем добавляем его в код. Если вектор уже встречался, значит, иначе последнюю единицу заменяем на ноль и записываем слово в кодгенерация кода закончена.# Если получено слово из При таком построении видно, что элементы таблицы <tex> a_1^i\dots a_1^{i+n}</tex> равны элементам <tex> a_1^i\dots a_n^i</tex> == Псевдокод алгоритма ==* <tex>\mathtt {current}</tex> — последний добавленный битовый вектор* <tex>\mathtt {result}</tex> — список битовых векторов  '''string[]''' chain_code('''int''' n): current = '0' * n нулей, то код полностью записан, иначе возвращаемся к шагу result = [current] '''while''' ''true'' prefix = current[2 ..n] '''if''' prefix + '1' '''not in''' result current =prefix + '1' '''else''' prefix + '0' '''not in''' result current =prefix + '0' '''else''' '''break''' result.append(current) '''return''' result ==Доказательство корректности====

# Доказательство того, что одно один и то тот же слово вектор встречается в коде не более одного раза.# Доказательство того, что код алгоритм перебирает все возможные слова вектора прежде, чем получит слово вектор из <tex>n </tex> нулей.

Покажем, что в этом алгоритме никогда не будет ситуацииединственная ситуация, когда нам надо образовать новое словотребуется сгенерировать новый вектор, а оба возможных вариантов варианта (добавление нуля или единицы) уже были использованыдобавлены — сгенерирован вектор из <tex>n</tex> нулей. Рассмотрим первое такое противоречие: последним добавлен вектор <tex>a_1 a_2 \dots a_n</tex>, то вектора <tex>a_2 \dots 1</tex> и <tex>a_2 \dots a_n 0</tex> уже присутствуют в коде. Далее есть уже было два слова, которые начинались таким же набором единиц и две возможных ситуации: вектор <tex>a_2 \dots a_n 0</tex> состоит из <tex>n</tex> нулей и отличались только или предшествовал другому вектору в последнем разрядекоде. В первой ситуации алгоритм завершает работу. Но они были получены  Во второй ситуации каждому из двух слов, которые отличаются только векторов <tex>a_2 \dots a_n 1</tex> и <tex>a_2 \dots a_n 0</tex> предшествовали некоторые вектора в первом разрядекоде, значитпусть <tex>B_1 = b_1 a_2 \dots a_n</tex> и <tex>B_2 = b_2 a_2 \dots a_n</tex>. Так как мы рассматриваем первое противоречие, мы должны были столкнуться то <tex>b_1 \neq b_2</tex>. Но в таком случае вектор <tex>a_1 a_2 \dots a_n</tex> совпадает с данной ситуацией на шаг раньшеодним из векторов <tex>B_1</tex> или <tex>B_2</tex>. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, но мы предполагалиследовательно, что это реализуется только первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуациейвариант ситуации. 

Покажем, что невозможно вернуться к слову до генерации вектора из всех нулей, пока не переберем все <mathtex>2^n</mathtex> слов, где n — длина слованулей генерируются все остальные битовые вектора. Допустим, мы всё же получили слово вектор из всех нулей раньше, чем перебрали все словавектора. Тогда разобьём словарассмотрим множество векторов <tex>Z</tex>, которые не попали в код на две группы: кончающиеся на единицу были сгенерированы алгоритмом и кончающиеся оканчиваются на ноль. Пусть <tex>a_1 a_2 \dots a_{n - 1} 0 \in Z</tex>. Докажем, что второй группы группы нет. Рассмотрим слово <tex>a_2 \dots a_{abc..yzn - 1}0, не попавшее в код, где {abc.0 \in Z</tex>.yz} — некоторая последовательность единиц и нулей. ЗаметимОт противного, что слово пусть вектор <tex>a_2 \dots a_{bc..yz}00 также не в коде. Оно могло быть получено из слов n - 1{bc..yz}0 и 0</tex> был сгенерирован. Тогда ему предшествовал вектор <tex>b_1 a_2 \dots a_{bc..yzn - 1}0</tex>. Так как по предположению <tex>b_1 \neq a_1</tex>, одно из которых есть рассматриваемое то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только <tex>a_2 \dots a_{abc..yzn - 1}01</tex>. Но  Значит, если другое слово и встретилось в кодемножество <tex>Z</tex> непусто, то мы бы получили оно содержит вектор из него {bc<tex>n</tex> нулей.Но это противоречит тому, что вектор из <tex>n</tex> нулей был сгенерирован.yz}01Следовательно, следуя алгоритму (причем это слово точно встретится предположение не верно и все вектора с нулём в первый раз)последней позиции были сгенерированы. Таким образом, слово  Пусть был сгенерирован вектор <tex>a_1 \dots a_{bc..yzn - 1}00 точно не в коде0</tex>. Такую же цепочку рассуждений можно провести и для слова Ему предшествовал некоторый вектор <tex>b_1 a_1 \dots a_{c..yzn - 1}000, и так далее</tex>. На Так как алгоритм сначала пытается поместить в код вектор <tex>a_1 \dots a_{n-ом 1} 1</tex>, то на этом шаге мы бы получили утверждение, что слова из вектор <tex>a_1 \dots a_{n нулей тоже нет - 1} 1</tex> уже присутсовал в коде, и пришли бы к противоречию. ЗаметимПредыдущее рассуждение показывает, что исходя из третьего и четвертого шагов, все слова всякий вектор вида <tex>a_1 \dots a_{abc..yz}n - 1 встречаются строго раньше {abc..yz}0</tex> был добавлен в код, которые точно записаны а значит, и вектор вида <tex>a_1 \dots a_{n - 1} 1 </tex> также был добавлен в код. Таким образом, слов, не попавших все двоичные вектора присутсвуют в код, нетсгенерированном коде. == См. также == *[[Коды Грея]]*[[Коды антигрея]]*[[Коды Грея для перестановок]] == Источники информации ==*[http://en.wikipedia.org/wiki/Chain_code Wikipedia {{---}} Chain code]  [[Категория: Дискретная математика и алгоритмы]] [[Категория: Комбинаторика ]]