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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
м (Второй пункт доказательства корректности : веткора -> вектора)
 
(не показана 31 промежуточная версия 6 участников)
Строка 1: Строка 1:
[[Файл:chain4.png|thumb|right|Цепной код для двоичного вектора длиной 4]]'''Цепной код''' — это код, каждый следующий столбец которого получается из предыдущего циклическим сдвигом вверх.
+
[[Файл:Chain4.png|right]]
 +
'''Цепной код''' (англ. ''chain code'') — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из <tex>2^n \times n</tex> элементов) получается из предыдущего циклическим сдвигом вверх.
  
== Алгоритм получения цепного кода для двоичного вектора ==
+
Цепной код позволяет исправить все одиночные ошибки при условии, что между любыми двумя ошибочно принятыми имеется по крайней мере три правильно принятых сигнала. Часто используется при передаче данных: видео, мобильной связи.
# Берем в качестве первого слова слово из 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>. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.
# Если получено слово из n нулей, то код полностью записан, иначе возвращаемся к шагу 2  
+
 
====Доказательство корректности====
+
При таком построении видно, что элементы таблицы <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
 +
 
 +
==Доказательство корректности==
 
Разобьем доказательство на две части:
 
Разобьем доказательство на две части:
# Доказательство того, что одно и то же слово встречается в коде не более одного раза.
+
# Доказательство того, что один и тот же вектор встречается в коде не более одного раза.
# Доказательство того, что код перебирает все возможные слова прежде, чем получит слово из n нулей.
+
# Доказательство того, что алгоритм перебирает все возможные вектора прежде, чем получит вектор из <tex>n</tex> нулей.
  
 
===Доказательство первого пункта===
 
===Доказательство первого пункта===
Покажем, что в этом алгоритме никогда не будет ситуации, когда нам надо образовать новое слово, а оба возможных вариантов (добавление нуля или единицы) уже были использованы. Рассмотрим первое такое противоречие, то есть уже было два слова, которые начинались таким же набором единиц и нулей и отличались только в последнем разряде. Но они были получены из двух слов, которые отличаются только в первом разряде, значит, мы должны были столкнуться с данной ситуацией на шаг раньше, но мы предполагали, что это первый подобный случай и пришли к противоречию. Следовательно, мы не можем столкнуться с данной ситуацией.
+
Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из <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> нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.
 +
 
 +
Во второй ситуации каждому из векторов <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>. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.
 +
 
 
===Доказательство второго пункта===
 
===Доказательство второго пункта===
Покажем, что невозможно вернуться к слову из всех нулей, пока не переберем все <math>2^n</math> слов, где n — длина слова. Допустим, мы всё же получили слово из всех нулей раньше, чем перебрали все слова. Тогда разобьём слова, которые не попали в код на две группы: кончающиеся на единицу и кончающиеся на ноль. Докажем, что второй группы группы нет. Рассмотрим слово {abc..yz}0, не попавшее в код, где {abc..yz} — некоторая последовательность единиц и нулей. Заметим, что слово {bc..yz}00 также не в коде. Оно могло быть получено из слов 1{bc..yz}0 и 0{bc..yz}0, одно из которых есть рассматриваемое {abc..yz}0. Но если другое слово и встретилось в коде, то мы бы получили из него {bc..yz}01, следуя алгоритму (причем это слово точно встретится в первый раз). Таким образом, слово {bc..yz}00 точно не в коде. Такую же цепочку рассуждений можно провести и для слова {c..yz}000, и так далее. На n-ом шаге мы бы получили утверждение, что слова из n нулей тоже нет в коде, и пришли бы к противоречию. Заметим, что исходя из третьего и четвертого шагов, все слова вида {abc..yz}1 встречаются строго раньше {abc..yz}0, которые точно записаны в код. Таким образом, слов, не попавших в код, нет.
+
 
 +
Покажем, что до генерации вектора из <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> уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида <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]
 +
 
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 
 +
[[Категория: Комбинаторика ]]

Текущая версия на 13:45, 24 июня 2019

Chain4.png

Цепной код (англ. chain code) — это такое упорядочивание двоичных векторов одной длины, каждый следующий столбец которого (можно рассматривать как таблицу из [math]2^n \times n[/math] элементов) получается из предыдущего циклическим сдвигом вверх.

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

Алгоритм получения цепного кода для двоичных векторов[править]

В качестве первого вектора берём вектор из [math]n[/math] нулей. Чтобы получить следующий вектор, берём последний добавленный вектор, пусть [math]a_1\dots a_n[/math]. Если в коде до этого не встречался вектор [math]a_2\dots a_n 1[/math], то добавляем его. Иначе проверяем на наличие в коде вектора [math]a_2\dots a_n 0[/math]. Если такой не встречался, добавляем его. Если вектор уже встречался, значит, генерация кода закончена.

При таком построении видно, что элементы таблицы [math] a_1^i\dots a_1^{i+n}[/math] равны элементам [math] a_1^i\dots a_n^i[/math]

Псевдокод алгоритма[править]

  • [math]\mathtt {current}[/math] — последний добавленный битовый вектор
  • [math]\mathtt {result}[/math] — список битовых векторов
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

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

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

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

Доказательство первого пункта[править]

Покажем, что единственная ситуация, когда требуется сгенерировать новый вектор, а оба возможных варианта (добавление нуля или единицы) уже добавлены — сгенерирован вектор из [math]n[/math] нулей. Рассмотрим первое такое противоречие: последним добавлен вектор [math]a_1 a_2 \dots a_n[/math], вектора [math]a_2 \dots 1[/math] и [math]a_2 \dots a_n 0[/math] уже присутствуют в коде.

Далее есть две возможных ситуации: вектор [math]a_2 \dots a_n 0[/math] состоит из [math]n[/math] нулей или предшествовал другому вектору в коде. В первой ситуации алгоритм завершает работу.

Во второй ситуации каждому из векторов [math]a_2 \dots a_n 1[/math] и [math]a_2 \dots a_n 0[/math] предшествовали некоторые вектора в коде, пусть [math]B_1 = b_1 a_2 \dots a_n[/math] и [math]B_2 = b_2 a_2 \dots a_n[/math]. Так как мы рассматриваем первое противоречие, то [math]b_1 \neq b_2[/math].

Но в таком случае вектор [math]a_1 a_2 \dots a_n[/math] совпадает с одним из векторов [math]B_1[/math] или [math]B_2[/math]. Это противоречит предположению о том, что рассмотренная конфликтная ситуация является первой, следовательно, реализуется только первый вариант ситуации.

Доказательство второго пункта[править]

Покажем, что до генерации вектора из [math]n[/math] нулей генерируются все остальные битовые вектора. Допустим, мы всё же получили вектор из всех нулей раньше, чем перебрали все вектора. Тогда рассмотрим множество векторов [math]Z[/math], которые не были сгенерированы алгоритмом и оканчиваются на ноль.

Пусть [math]a_1 a_2 \dots a_{n - 1} 0 \in Z[/math]. Докажем, что [math]a_2 \dots a_{n - 1} 0 0 \in Z[/math]. От противного, пусть вектор [math]a_2 \dots a_{n - 1} 0 0 [/math] был сгенерирован. Тогда ему предшествовал вектор [math]b_1 a_2 \dots a_{n - 1} 0[/math]. Так как по предположению [math]b_1 \neq a_1[/math], то в коде может быть только один вектор такого вида, а в таком случае алгоритм может сгенерировать только [math]a_2 \dots a_{n - 1} 0 1[/math].

Значит, если множество [math]Z[/math] непусто, то оно содержит вектор из [math]n[/math] нулей. Но это противоречит тому, что вектор из [math]n[/math] нулей был сгенерирован. Следовательно, это предположение не верно и все вектора с нулём в последней позиции были сгенерированы.

Пусть был сгенерирован вектор [math]a_1 \dots a_{n - 1} 0[/math]. Ему предшествовал некоторый вектор [math]b_1 a_1 \dots a_{n - 1}[/math]. Так как алгоритм сначала пытается поместить в код вектор [math]a_1 \dots a_{n - 1} 1[/math], то на этом шаге вектор [math]a_1 \dots a_{n - 1} 1[/math] уже присутсовал в коде. Предыдущее рассуждение показывает, что всякий вектор вида [math]a_1 \dots a_{n - 1} 0[/math] был добавлен в код, а значит, и вектор вида [math]a_1 \dots a_{n - 1} 1 [/math] также был добавлен в код. Таким образом, все двоичные вектора присутсвуют в сгенерированном коде.

См. также[править]

Источники информации[править]