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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
== Алгоритм получения цепного кода для двоичного вектора ==
 
== Алгоритм получения цепного кода для двоичного вектора ==
 
# Берем в качестве первого слова слово из n нулей.
 
# Берем в качестве первого слова слово из n нулей.
 
+
# Делаем циклический сдвиг предыдущего слова влево с потерей первого разряда.
'''Шаг 2'''
+
# Приписываем к полученному слову в конец единицу. Проверяем, встречалось ли это слово в коде ранее.
 
+
# Если нет, то записываем его в код, иначе последнюю единицу заменяем на ноль и записываем слово в код.
Делаем циклический сдвиг предыдущего слова влево с потерей первого разряда.
+
# Если получено слово из n нулей, то код полностью записан, иначе возвращаемся к шагу 2  
 
 
'''Шаг 3'''
 
 
 
Приписываем к полученному слову в конец единицу. Проверяем, встречалось ли это слово в коде ранее.
 
 
 
Если нет, то записываем его в код, иначе последнюю единицу заменяем на ноль и записываем слово в код.
 
 
 
'''Шаг 4'''
 
 
 
Если получено слово из n нулей, то код полностью записан, иначе возвращаемся к шагу 2  
 
 
====Доказательство корректности====
 
====Доказательство корректности====
Требуется доказать, что алгоритм не повторит 2 слова в коде до того, как закончит цикл и то, что он переберет все возможные варианты.
+
Разобьем доказательство на две части:
 +
# Доказательство того, что одно и то же слово встречается в коде не более одного раза.
 +
# Доказательство того, что код перебирает все возможные слова прежде, чем получит слово из n нулей.
  
Во-первых, в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление 0 или 1) уже были использованы.
 
Допустим, мы наткнулись на эту ситуацию в первый раз, то есть уже было 2 слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
 
  
Во-вторых, мы не сможем снова вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова.
+
# Покажем, что в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление нуля или единицы) уже были использованы. Рассмотрим первое такое противоречие, то есть уже было два слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на 1 и кончающиеся на 0.
+
# Заметим, что невозможно вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на 1 и кончающиеся на 0. Докажем, что 2-й группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность 1 и 0. Рассмотрим два слова, которые могут быть от него образованы: {bc..yz}01 и {bc..yz}00. Они могли быть получены из слов {abc..yz}0 и {(not a)bc..yz}0. Но даже если второе слово встречается в коде, то в коде не может быть более одного из рассматриваемых слов, значит аторого не может быть вообще (так как алгоритм по возможности добавляет 1, а не 0). То есть слово {bc..yz}00 тоже нет в коде. Так эту цепочку можно продолжить до слова 00..000 и прийти к противоречию. А раз 2-й группы нет, то не может быть и 1-й, так как если в коде есть слово, кончающееся на 0, то мы не можем получить его, если не было слова с таким же началом, но с единицей в конце.
Докажем, что 2-й группы нет.
 
Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность 1 и 0. Рассмотрим два слова, которые могут быть от него образованы: {bc..yz}01 и {bc..yz}00. Они могли быть получены из слов {abc..yz}0 и {(not a)bc..yz}0. Но даже если второе слово встречается в коде, то в коде не может быть более одного из рассматриваемых слов, значит аторого не может быть вообще (так как алгоритм по возможности добавляет 1, а не 0). То есть слово {bc..yz}00 тоже нет в коде. Так эту цепочку можно продолжить до слова 00..000 и прийти к противоречию.
 
А раз 2-й группы нет, то не может быть и 1-й, так как если в коде есть слово, кончающееся на 0, то мы не можем получить его, если не было слова с таким же началом, но с единицей в конце.
 

Версия 01:42, 27 ноября 2010

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

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

  1. Берем в качестве первого слова слово из n нулей.
  2. Делаем циклический сдвиг предыдущего слова влево с потерей первого разряда.
  3. Приписываем к полученному слову в конец единицу. Проверяем, встречалось ли это слово в коде ранее.
  4. Если нет, то записываем его в код, иначе последнюю единицу заменяем на ноль и записываем слово в код.
  5. Если получено слово из n нулей, то код полностью записан, иначе возвращаемся к шагу 2

Доказательство корректности

Разобьем доказательство на две части:

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


  1. Покажем, что в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление нуля или единицы) уже были использованы. Рассмотрим первое такое противоречие, то есть уже было два слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
  2. Заметим, что невозможно вернуться к слову из всех нулей, пока не переберем все [math]2^n[/math] слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на 1 и кончающиеся на 0. Докажем, что 2-й группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность 1 и 0. Рассмотрим два слова, которые могут быть от него образованы: {bc..yz}01 и {bc..yz}00. Они могли быть получены из слов {abc..yz}0 и {(not a)bc..yz}0. Но даже если второе слово встречается в коде, то в коде не может быть более одного из рассматриваемых слов, значит аторого не может быть вообще (так как алгоритм по возможности добавляет 1, а не 0). То есть слово {bc..yz}00 тоже нет в коде. Так эту цепочку можно продолжить до слова 00..000 и прийти к противоречию. А раз 2-й группы нет, то не может быть и 1-й, так как если в коде есть слово, кончающееся на 0, то мы не можем получить его, если не было слова с таким же началом, но с единицей в конце.