Префиксные коды

Рассмотренный выше код, казалось бы, можно было бы оптимизировать, например, присвоить командам коды, представленные в таблице 3.4.

Таблица 3.4

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

K₁, K₄, K₃, K₄, K₁, K₁, K₂, K₁, ……

Закодированные команды будут выглядеть следующим образом:

Легко видеть, что произойдет, если мы попытаемся однозначно дешифрировать это код в команды. Путаница начинается со второго бита, так это может быть и команда K_2, и команда K₃ , и команда K₄.

Посмотрим на частоту использования букв русского языка и ограничим их количество до 32 букв, считая, что буквы «е», «ё», это одна буква.

Код Хаффмена

Часть 3.

Избыточная передача информации и методы исправления ошибок

Код с повторениями

Код с проверкой на четность

Циклические коды

Коды Хэмминга

Коды Хэмминга.

Возьмем некоторую последовательность двоичных разрядов:

λ ₁ λ₂ λ₃ λ₄ λ₅ λ₆ λ₇ λ₈ λ₉ λ₁₀ λ₁₁ λ₁₂ λ₁₃ λ₁₄ λ₁₅ λ₁₆ λ₁₇ λ₁₈ λ₁₉ λ₂₀ λ₂₁ λ₂₂ λ₂₃ λ₂₄ λ₂₅ λ₂₆

где λ_i- значение 0 или 1 в i – разряде двоичного числа (можно последовательность продолжить и дальше).

Добавим контрольные разряды:

К ₁ К ₂ К ₃ К ₄ К ₅

(добавим для данного случая, именно такое количество контрольных разрядов, в дальнейшем станет понятно почему).

В результате сформируем последовательность, вид которой определяется в соответствии с описанием, которое будет определено ниже:

К ₁ К _{2 λ1} К ₃ λ₂ λ₃ λ₄ К ₄ λ₅ λ₆ λ₇ λ₈ λ₉ λ₁₀ λ₁₁ К ₅ λ₁₂ λ₁₃ λ₁₄ λ₁₅ λ₁₆ λ₁₇ λ₁₈ λ₁₉ λ₂₀ λ₂₁ λ₂₂ λ₂₃ λ₂₄ λ₂₅ λ₂₆

Данная последовательность будет обладать свойством исправления одиночной ошибки при условии формирования значения контрольных разрядов в соответствии с описанием, основанным на структуре решетки по Таблице 1. Построим следующую таблицу, где для последовательности, состоящей из какого-то количества разрядов, номер разряда представим в двоичном виде и развернем в колонку, в которой младший разряд находится внизу, а старшие выше. Ниже волнистой черты, двигаясь в обратном порядке, пометим крестиками разряды, появившиеся в нижней строке над волной (т.е. для 1 разряда), затем во второй строке тоже самое действие произведем для второй строки над волной (2 разряд) и так далее. А в колонках, номер которых является степенью двойки, вместо креста поставим символ К _i, где i соответствует этой степени.

Получаем таблицу, похожую на решетку, к которой сверху добавлен десятичный номер (в колонку) соответствующего разряда в порядке возрастания слева направо, и чуть ниже звездочками (*) отмечены номера колонок (разрядов) кратных степени двойки.

К ₁ К _{2 λ1} К ₃ λ₂ λ₃ λ₄ К ₄ λ₅ λ₆ λ₇ λ₈ λ₉ λ₁₀ λ₁₁ К ₅ λ₁₂ λ₁₃ λ₁₄ λ₁₅ λ₁₆ λ₁₇ λ₁₈ λ₁₉ λ₂₀ λ₂₁ λ₂₂ λ₂₃ λ₂₄ λ₂₅ λ₂₆

1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3

1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

* * * * *

_ _ _ _ ____ ____________ __ ___ _ __ _ __ _ _ __ _ _ _ _ _

Р. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Р. 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

Р. 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

Р. 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

Р. 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

S1 К ₁ 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х

S2 0 К ₂ х 0 0 х х 0 0 х х 0 0 х х 0 0 х х 0 0 х х 0 0 х х 0 0 х х

S3 0 0 0 К ₃ х х х 0 0 0 0 х х х х 0 0 0 0 х х х х 0 0 0 0 х х х х

S4 0 0 0 0 0 0 0 К ₄ х х х х х х х 0 0 0 0 0 0 0 0 х х х х х х х х

S5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 К ₅ х х х х х х х х х х х х х х х

S6...................................................................................... ……......

К ₁ К _{2 λ1} К ₃ λ₂ λ₃ λ₄ К ₄ λ₅ λ₆ λ₇ λ₈ λ₉ λ₁₀ λ₁₁ К ₅ λ₁₂ λ₁₃ λ₁₄ λ₁₅ λ₁₆ λ₁₇ λ₁₈ λ₁₉ λ₂₀ λ₂₁ λ₂₂ λ₂₃ λ₂₄ λ₂₅ λ₂₆

Основанием для построения таблицы является следующий факт: Если пронумеровать все разряды передаваемого кода с учетом длины (в таблице это колонки слева направо), а номер разряда в десятичной форме выразить в двоичном виде, то для первого разряда наличие единицы появляется в номере через разряд, для второго разряда повторение единички идет со скважностью через два и так далее. Скважность определяется числом, полученным возведением основания два в степень, определяемая номером разряда минус один, то есть 2^{i - 1}. В числах нумерующих номер колонки, являющихся степенью двойки, как мы видим, один разряд. Именно этот разряд и рассматривается в качестве контрольного разряда. Этот разряд будет являться суммой по модулю два всех разрядов соответствующей строки, которые входят в двоичный номер колонок нумерующих разряды.

К ₁ = λ₁ + λ₂+ λ₄ + λ₅ + λ₇ + λ₉ + λ₁₁ + λ₁₂ + λ₁₄ + λ₁₆ + λ₁₈ + λ₂₀ + λ₂₂ + λ₂₄ + λ₂₆

К ₂ = λ₁ + λ₃+ λ₄ + λ₆ + λ₇ + λ₁₀ + λ₁₁ + λ₁₃ + λ₁₄ + λ₁₇ + λ₁₈ + λ₂₁ + λ₂₂ + λ₂₅ + λ₂₆

К ₃ = λ₂ + λ₃+ λ₄ + λ₈ + λ₉ + λ₁₀ + λ₁₁ + λ₁₅ + λ₁₆ + λ₁₇ + λ₁₈ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

К ₄ = λ₅ + λ₆+ λ₇ + λ₈ + λ₉ + λ₁₀ + λ₁₁ + λ₁₉ + λ₂₀ + λ₂₁ + λ₂₂ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

К ₅ = λ₁₂+ λ₁₃+ λ₁₄+λ₁₅ +λ₁₆+ λ₁₇ + λ₁₈ + λ₁₉ + λ₂₀ + λ₂₁ + λ₂₂ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

…………

Отсюда, сумма значений разрядов в соответствующей строке с включением контрольного разряда по модулю два для всех строк должна быть равна нулю, а именно для S1, S2, …. Sk.

S1= К ₁+λ₁ + λ₂+ λ₄ + λ₅ + λ₇ + λ₉ + λ₁₁ + λ₁₂ + λ₁₄ + λ₁₆ + λ₁₈ + λ₂₀ + λ₂₂ + λ₂₄ + λ₂₆

S2 =К ₂+λ₁+ λ₃+ λ₄ + λ₆ + λ₇ + λ₁₀ + λ₁₁ + λ₁₃ + λ₁₄ + λ₁₇ + λ₁₈ + λ₂₁ + λ₂₂ + λ₂₅ + λ₂₆

S3 = К ₃+λ₂ + λ₃+ λ₄ + λ₈ + λ₉ + λ₁₀ + λ₁₁ + λ₁₅ + λ₁₆ + λ₁₇ + λ₁₈ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

S4= К ₄+λ₅ + λ₆+ λ₇ + λ₈ + λ₉ + λ₁₀ + λ₁₁ + λ₁₉ + λ₂₀ + λ₂₁ + λ₂₂ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

S ₅=К₅+ λ₁₂+ λ₁₃+ λ₁₄+λ₁₅ +λ₁₆+ λ₁₇+ λ₁₈+ λ₁₉ + λ₂₀ + λ₂₁ + λ₂₂ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

……………..

Исходя из логики построения, те суммы, в которые входит разряд с одиночной ошибкой, будут иметь значение - отличное от нуля, а в совокупности будут представлять номер ошибочного разряда. Это хорошо видно из таблицы.

И так общий алгоритм получения контрольных разрядов и их проверки состоит в следующем:

1. В коде, который предполагаете закодировать кодом Хемминга, вместо разрядов, номера которых являются числами 2 в степени n, где n≥ 0 и целое, вставляются контрольные разряды. В таблице сверху эти разряды отмечены звездочками (*), а в масках, по которым образуются контрольные суммы буквой к.

2. Маски отмечены крестиками (х) одного цвета для каждой контрольной суммы в соответствующих строках и удваиваются при переходе от строчки к строчке начиная с единицы.

3. Промежутки между масками отмеченные нулями полностью соответствуют количеству разрядов разрядам маски.

4. Каждое значение суммы по модулю 2 в каждой строке является суммой тех разрядов, которые встречаются в номерах соответствующих колонок таблицы. Например: Сумма S1 является суммой тех колонок, где в двоичном представлении номера колонки встречается первый разряд, т.е. это номера 1,3,5,7, и т.д.

Сумма S2 является суммой тех колонок, где в двоичном представлении номера колонки встречается второй разряд, т.е. это номера 2,3; 6,7; 10,11 и т.д.

Также сумма S3.

Также сумма S4.

Также сумма S5.

И т.д.

Из представления таблицы видно, что, если в каком то из разрядов, принимаемого сообщения, код примет противоположное значение, то это отразиться на тех суммах, в которых это разряд участвует при получении соответствующей суммы. А это будет представлять в совокупности номер того разряда, в котором произошел сбой, если суммы представлять как значение соответствующего разряда соответствующих сумм. Если все суммы нулевые, то все разряды переданы, верно.

Например: Если в 7 разряде произошел сбой, то это отразится на суммах S1, S2, S3, что хорошо видно из таблицы. Безусловно, другие разряды должны быть переданы правильно.

5. Таким образом, для примера представленного в таблице имеем

К ₁ = λ₁ + λ₂ + λ₄ + λ₅ + λ₇ + λ₉+ λ₁₁ + λ₁₂ + λ₁₄ + λ₁₆ + λ₁₈ + λ₂₀ + λ₂₂ + λ₂₄ + λ₂₆

К ₂ = λ₁ + λ₃ + λ₄ + λ₆ + λ₇ + λ₁₀+ λ₁₁+ λ₁₃ + λ₁₄ + λ₁₇ + λ₁₈ + λ₂₁ + λ₂₂ + λ₂₅ + λ₂₆

К ₃ = λ₂ + λ₃ + λ₄+ λ₈ + λ₉+ λ₁₀+ λ₁₁+ λ₁₅ + λ₁₆+ λ₁₇ + λ₁₈ + λ₂₃ + λ₂₄ + λ₂₅+ λ₂₆

К ₄ = λ₅+ λ₆ + λ₇+ λ₈+ λ₉+ λ₁₀ + λ₁₁+λ₁₉ + λ₂₀+ λ₂₁+ λ₂₂ + λ₂₃ + λ₂₄ + λ₂₅+ λ₂₆

К ₅ = λ₁₂+ λ₁₃+ λ₁₄+ λ₁₅+ λ₁₆+ λ₁₇+ λ₁₈+λ₁₉+ λ₂₀+ λ₂₁+ λ₂₂ + λ₂₃ + λ₂₄ + λ₂₅ + λ₂₆

Поиск по сайту: