Цепные коды — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
[[Файл:chain4.png|thumb|right|Цепной код для двоичного вектора длиной 3]]'''Цепной код''' — код, состоящий из n-разрядных слов. Следующее слово кода получается из предыдущего сдвигом на один разряд влево с отбрасыванием первого разряда и добавлением нуля или единицы в конец. Другое определение цепного кода — это код, каждый следующий столбец которого есть циклический сдвиг предыдущего вверх на 1 разряд.
+
[[Файл:chain4.png|thumb|right|Цепной код для двоичного вектора длиной 4]]'''Цепной код''' — код, состоящий из n-разрядных слов. Следующее слово кода получается из предыдущего сдвигом на один разряд влево с отбрасыванием первого разряда и добавлением нуля или единицы в конец. Другое определение цепного кода — это код, каждый следующий столбец которого есть циклический сдвиг предыдущего вверх на 1 разряд.
  
  
Строка 5: Строка 5:
 
Для получения цепного кода используется жадный алгоритм. Первон слово кода — слово, полностью состоящая из нулей. Образуя каждое следующее  слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль.
 
Для получения цепного кода используется жадный алгоритм. Первон слово кода — слово, полностью состоящая из нулей. Образуя каждое следующее  слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль.
 
====Почему алгоритм работает?====
 
====Почему алгоритм работает?====
Во-первых, в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление 0 или 1) уже были использованы.
+
[[Файл:chainend.png|thumb|left|последние n строк цепного кода]]Во-первых, в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление 0 или 1) уже были использованы.
 
Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
 
Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
  
 
Во-вторых, мы не сможем снова вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Чтобы снова получить эту строку, мы должны будем перебрать все строки, в которых есть 1, тк мы по возможности добавляем именно 1, а 0 только если такое число уже было
 
Во-вторых, мы не сможем снова вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Чтобы снова получить эту строку, мы должны будем перебрать все строки, в которых есть 1, тк мы по возможности добавляем именно 1, а 0 только если такое число уже было

Версия 02:57, 12 ноября 2010

Цепной код для двоичного вектора длиной 4
Цепной код — код, состоящий из n-разрядных слов. Следующее слово кода получается из предыдущего сдвигом на один разряд влево с отбрасыванием первого разряда и добавлением нуля или единицы в конец. Другое определение цепного кода — это код, каждый следующий столбец которого есть циклический сдвиг предыдущего вверх на 1 разряд.


Алгоритм получения цепного кода для двоичного вектора

Для получения цепного кода используется жадный алгоритм. Первон слово кода — слово, полностью состоящая из нулей. Образуя каждое следующее слово, мы сдвигаем предыдущее влево на один разряд, отбрасывая старший, затем добавляем в конец 1 и проверяем, не было ли такого слова раньше. Если было, то меняем последнюю единицу на ноль.

Почему алгоритм работает?

последние n строк цепного кода
Во-первых, в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление 0 или 1) уже были использованы.

Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.

Во-вторых, мы не сможем снова вернуться к слову из всех нулей, пока не переберем все [math]2^n[/math] слов, где n — длина слова. Чтобы снова получить эту строку, мы должны будем перебрать все строки, в которых есть 1, тк мы по возможности добавляем именно 1, а 0 только если такое число уже было