20
правок
Изменения
Нет описания правки
[[Файл:chain4.png|thumb|right|Цепной код для двоичного вектора длиной 4]]'''Цепной код''' — код, состоящий из n-разрядных слов. Следующее слово кода получается из предыдущего сдвигом на один разряд влево с отбрасыванием первого разряда и добавлением нуля или единицы в конец. Другое определение цепного кода — это код, каждый следующий столбец которого есть циклический сдвиг получается из предыдущего циклическим сдвигом вверх на 1 разряд.
== Алгоритм получения цепного кода для двоичного вектора ==
\itemБерем в качестве первого слова слово из n нулей.
'''Шаг 2'''
Делаем циклический сдвиг предыдущего слова влево с потерей первого разряда.
'''Шаг 3'''
Приписываем к полученному слову в конец единицу. Проверяем, встречалось ли это слово в коде ранее.
Если нет, то записываем его в код, иначе последнюю единицу заменяем на ноль и записываем слово в код.
'''Шаг 4'''
====Доказательство корректности====
Требуется доказать, что алгоритм не повторит 2 слова в коде до того, как закончит цикл и то, что он переберет все возможные варианты.