Изменения

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

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