АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Бинарные деревья и бинарные префиксные коды.
  2. Бинарные деревья и бинарные префиксные коды.

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

 

K1 K2 K3 K4
       

Таблица 3.4

 

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

K1, K4, K3, K4, K1, K1, K2, K1, ……

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

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

 

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

Буква Частота Примечание
  А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Ь Ъ Э Ю Я 0,062 0,014 0,038 0,013 0,025 0,072 0,007 0,016 0,062 0,010 0,028 0,035 0,026 0,053 0,090 0,023 0,040 0,045 0,053 0,021 0,002 0,009 0,004 0,012 0,006 0,003 0,016 0,014 0,014 0,003 0,006 0,018  

Код Хаффмена

Часть 3.

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

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

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

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

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

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

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

λ 1 λ2 λ3 λ4 λ5 λ6 λ7 λ8 λ9 λ10 λ11 λ12 λ13 λ14 λ15 λ16 λ17 λ18 λ19 λ20 λ21 λ22 λ23 λ24 λ25 λ26

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

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

К 1 К 2 К 3 К 4 К 5

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

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

К 1 К 2 λ1 К 3 λ2 λ3 λ4 К 4 λ5 λ6 λ7 λ8 λ9 λ10 λ11 К 5 λ12 λ13 λ14 λ15 λ16 λ17 λ18 λ19 λ20 λ21 λ22 λ23 λ24 λ25 λ26

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

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

К 1 К 2 λ1 К 3 λ2 λ3 λ4 К 4 λ5 λ6 λ7 λ8 λ9 λ10 λ11 К 5 λ12 λ13 λ14 λ15 λ16 λ17 λ18 λ19 λ20 λ21 λ22 λ23 λ24 λ25 λ26

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 К 1 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х 0 х

S2 0 К 2 х 0 0 х х 0 0 х х 0 0 х х 0 0 х х 0 0 х х 0 0 х х 0 0 х х

S3 0 0 0 К 3 х х х 0 0 0 0 х х х х 0 0 0 0 х х х х 0 0 0 0 х х х х

S4 0 0 0 0 0 0 0 К 4 х х х х х х х 0 0 0 0 0 0 0 0 х х х х х х х х

S5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 К 5 х х х х х х х х х х х х х х х

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

К 1 К 2 λ1 К 3 λ2 λ3 λ4 К 4 λ5 λ6 λ7 λ8 λ9 λ10 λ11 К 5 λ12 λ13 λ14 λ15 λ16 λ17 λ18 λ19 λ20 λ21 λ22 λ23 λ24 λ25 λ26

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

К 1 = λ1 + λ2+ λ4 + λ5 + λ7 + λ9 + λ11 + λ12 + λ14 + λ16 + λ18 + λ20 + λ22 + λ24 + λ26

К 2 = λ1 + λ3+ λ4 + λ6 + λ7 + λ10 + λ11 + λ13 + λ14 + λ17 + λ18 + λ21 + λ22 + λ25 + λ26

К 3 = λ2 + λ3+ λ4 + λ8 + λ9 + λ10 + λ11 + λ15 + λ16 + λ17 + λ18 + λ23 + λ24 + λ25 + λ26

К 4 = λ5 + λ6+ λ7 + λ8 + λ9 + λ10 + λ11 + λ19 + λ20 + λ21 + λ22 + λ23 + λ24 + λ25 + λ26

К 5 = λ12+ λ13+ λ141516+ λ17 + λ18 + λ19 + λ20 + λ21 + λ22 + λ23 + λ24 + λ25 + λ26

…………

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

S1= К 11 + λ2+ λ4 + λ5 + λ7 + λ9 + λ11 + λ12 + λ14 + λ16 + λ18 + λ20 + λ22 + λ24 + λ26

S2 21+ λ3+ λ4 + λ6 + λ7 + λ10 + λ11 + λ13 + λ14 + λ17 + λ18 + λ21 + λ22 + λ25 + λ26

S3 = К 32 + λ3+ λ4 + λ8 + λ9 + λ10 + λ11 + λ15 + λ16 + λ17 + λ18 + λ23 + λ24 + λ25 + λ26

S4= К 45 + λ6+ λ7 + λ8 + λ9 + λ10 + λ11 + λ19 + λ20 + λ21 + λ22 + λ23 + λ24 + λ25 + λ26

S 55+ λ12+ λ13+ λ141516+ λ17+ λ18+ λ19 + λ20 + λ21 + λ22 + λ23 + λ24 + λ25 + λ26

……………..

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

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

 

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. Таким образом, для примера представленного в таблице имеем

К 1 = λ1 + λ2 + λ4 + λ5 + λ7 + λ9+ λ11 + λ12 + λ14 + λ16 + λ18 + λ20 + λ22 + λ24 + λ26

К 2 = λ1 + λ3 + λ4 + λ6 + λ7 + λ10+ λ11+ λ13 + λ14 + λ17 + λ18 + λ21 + λ22 + λ25 + λ26

К 3 = λ2 + λ3 + λ4+ λ8 + λ9+ λ10+ λ11+ λ15 + λ16+ λ17 + λ18 + λ23 + λ24 + λ25+ λ26

К 4 = λ5+ λ6 + λ7+ λ8+ λ9+ λ10 + λ1119 + λ20+ λ21+ λ22 + λ23 + λ24 + λ25+ λ26

К 5 = λ12+ λ13+ λ14+ λ15+ λ16+ λ17+ λ1819+ λ20+ λ21+ λ22 + λ23 + λ24 + λ25 + λ26


1 | 2 | 3 | 4 | 5 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)