Построить код Хемминга (7.4).

- Нарисовать структурную схему кодера и декодера, исправляющего ошибку.

- Определить проверочный код для передаваемой кодовой комбинации 1011.

- Исправить ошибку, допущенную в четвертом элементе принятой кодовой комбинации.

Построение кодов Хемминга базируется на принципе проверки на чётность веса W (числа единичных символов) в информационной группе кодового блока. Поясним идею проверки на чётность на примере простейшего корректи-рующего кода, который так и называется кодом с проверкой на чётность иликодом с проверкой по паритету (равенству).В таком коде к кодовым комбинациям безизбыточного первичного двоич-ного k - разрядного кода добавляется один дополнительный разряд (символпроверки на чётность, называемый проверочным, или контрольным). Если чис-ло символов “1” исходной кодовой комбинации чётное, то в дополнительномразряде формируют контрольный символ 0, а если число символов “1” нечёт-ное, то в дополнительном разряде формируют символ 1. В результате общеечисло символов “1” в любой передаваемой кодовой комбинации всегда будет чётным.Таким образом, правило формирования проверочного символа сводится кследующему:

r1 = i1 ⊕ i2 ⊕ ... ⊕ ik ,

где i - соответствующий информационный символ (0 или 1), k - общее их числоа под операцией "⊕" здесь и далее понимается сложение по mod2. Очевидно,что добавление дополнительного разряда увеличивает общее число возмож-ных комбинаций вдвое по сравнению с числом комбинаций исходного первич-ного кода, а условие чётности разделяет все комбинации на разрешённые инеразрешённые. Код с проверкой на чётность позволяет обнаруживать одиноч-ную ошибку при приёме кодовой комбинации, так как такая ошибка нарушаетусловие чётности, переводя разрешённую комбинацию в запрещённую.Критерием правильности принятой комбинации является равенство нулюрезультата S суммирования по mod 2 всех n символов кода, включая провероч-ный символ r1. При наличии одиночной ошибки S принимает значение 1:

S = r1 ⊕ i1 ⊕ i2 ⊕ . . . ⊕ ik =  0 - ошибки нет

1444424443 =  1 - однократная ошибка. n

Этот код является (k +1, k) - кодом, или (n, n -1) - кодом. Минимальное рас-стояние кода равно двум (d min = 2), и, следовательно, никакие ошибки не могутбыть исправлены. Простой код с проверкой на чётность может использоватьсятолько для обнаружения (но не исправления) однократных ошибок.Увеличивая число дополнительных проверочных разрядов и формируя поопределённым правилам проверочные символы r, равные 0 или 1, можно уси-лить корректирующие свойства кода так, чтобы он позволял не только обнару-живать, но и исправлять ошибки. На этом и основано построение кодов Хем-минга.Коды Хемминга. Рассмотрим эти коды, позволяющие исправлять одиноч-ную ошибку, с помощью непосредственного описания. Для каждого числа про-верочных символов r = 3,4,5… существует классический код Хемминга с марки-ровкой (n,k) = (2r–1, 2r–1 –r) , (3.20)

т.е. - (7,4), (15,11), (31,26) …

При других значениях числа информационных символов k получаются такназываемые усечённые (укороченные) коды Хемминга. Так, для международно-го телеграфного кода МТК-2 , имеющего 5 информационных символов, потре-буется использование корректирующего кода (9,5), являющегося усечённым отклассического кода Хемминга (15,11), так как число символов в этом кодеуменьшается (укорачивается) на 6. Для примера рассмотрим классический кодХемминга (7,4), который можно сформировать и описать с помощью кодера,представленного на рис.3.2. В простейшем варианте при заданных четырёх(k=4) информационных символах (i1, i2, i3, i4) будем полагать, что они сгруппиро-ваны в начале кодового слова, хотя это и не обязательно. Дополним эти ин-формационные символы тремя проверочными символами (r = 3), задавая ихследующими равенствами проверки на чётность, которые определяются соот-ветствующими алгоритмами [3,5]:

r1 = i1 ⊕ i2 ⊕ i3;

r2 = i2 ⊕ i3 ⊕ i4;

r3 = i1 ⊕ i2 ⊕ i4,

где знак ⊕ означает сложение по модулю 2.

В соответствии с этим алгоритмом определения значений проверочныхсимволов ri ниже выписаны все возможные 16 кодовых слов (7,4) - кода Хем-минга.

На рис. 3.3 приведена схема декодера для (7,4) - кода Хемминга, на входкоторого поступает кодовое слово

V = ( i1', i2', i3', i4', r1', r2', r3')

Апостроф означает, что любой символ слова может быть искажён помехой вканале передачи.

В декодере в режиме исправления ошибок строится последовательность:

s1 = r1' ⊕ i1' ⊕ i2' ⊕ i3';

s2 = r2' ⊕ i2' ⊕ i3' ⊕ i4';

s3 = r3' ⊕ i1' ⊕ i2' ⊕ i4'. Трёхсимвольная последовательность ( s1, s2, s3 ) называется синдромом.

Термин "синдром" используется и в медицине, где он обозначает сочетаниепризнаков, характерных для определённого заболевания. В данном случаесиндром S = (s1, s2, s3 ) представляет собой сочетание результатов проверкина чётность соответствующих символов кодовой группы и характеризует опре-делённую конфигурацию ошибок (шумовой вектор).

Кодовые слова (7,4) - кода Хемминга.

к = 4 r = 3

i1 i2 i3 i4 r1 r2 r3

0 0 0 0 0 0 0

0 0 0 1 0 1 1

0 0 1 0 1 1 0

0 0 1 1 1 0 1

0 1 0 0 1 1 1

0 1 0 1 1 0 0

0 1 1 0 0 0 1

0 1 1 1 0 1 0

1 0 0 0 1 0 1

1 0 0 1 1 1 0

1 0 1 0 0 1 1

1 0 1 1 0 0 0

1 1 0 0 0 1 0

1 1 0 1 0 0 1

1 1 1 0 1 0 0

1 1 1 0 1 1 1

Число возможных синдромов определяется выражением S = 2r. (3.21)

При числе проверочных символов r = 3 имеется восемь возможных син-дромов (2³ = 8). Нулевой синдром (000) указывает на то, что ошибки при приёмеотсутствуют или не обнаружены. Всякому ненулевому синдрому соответствуетопределённая конфигурация ошибок, которая и исправляется. Классическиекоды Хемминга (3.20) имеют число синдромов, точно равное их необходимомучислу, позволяют исправить все однократные ошибки в любом информативноми проверочном символах и включают один нулевой синдром. Такие коды назы-ваются плотноупакованными.Усечённые коды являются неплотноупакованными, так как число синдро-мов у них превышает необходимое. Так, в коде (9,5) при четырёх проверочныхсимволах число синдромов будет равно 2⁴ =16, в то время как необходимо все-го 10. Лишние 6 синдромов свидетельствуют о неполной упаковке кода (9,5).

Для рассматриваемого кода (7,4) в таблице 1 представлены ненулевыесиндромы и соответствующие конфигурации ошибок.

Таким образом, код (7,4) позволяет исправить все одиночные ошибки.Простая проверка показывает, что каждая из ошибок имеет свой единственныйсиндром. При этом возможно создание такого цифрового корректора ошибок(дешифратора синдрома), который по соответствующему синдрому исправляетсоответствующий символ в принятой кодовой группе. После внесения исправ-ления проверочные символы ri можно на выход декодера (рис.3.3) не выводить.Две или более ошибки превышают возможности корректирующего кода Хем-минга, и декодер будет ошибаться. Это означает, что он будет вносить не-правильные исправления и выдавать искажённые информационные символы.Идея построения подобного корректирующего кода, естественно, не меня-ется при перестановке позиций символов в кодовых словах. Все такие вариан-ты также называются (7,4) - кодами Хемминга