Изменения

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

== Алгоритм получения цепного кода для двоичного вектора ==\itemБерем в качестве первого слова слово из n нулейЦепной код позволяет исправить все одиночные ошибки при условии, что между любыми двумя ошибочно принятыми имеется по крайней мере три правильно принятых сигнала. Часто используется при передаче данных: видео, мобильной связи.

Делаем циклический сдвиг предыдущего слова влево с потерей В качестве первого разрядавектора берём вектор из <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>. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.

Если нет, то записываем его в код, иначе последнюю единицу заменяем на ноль и записываем слово в код '''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

Если получено слово из n нулей, то код полностью записан, иначе возвращаемся к шагу 2 ====Доказательство корректности=первого пункта===Требуется доказатьПокажем, что алгоритм не повторит 2 слова единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из <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> нулей или 1) уже были использованы.Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только предшествовал другому вектору в последнем разрядекоде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуациейВ первой ситуации алгоритм завершает работу.

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