Понятие синдрома

Обнаружение и исправление ошибок кодом Хэмминга сводится к определению и последующему анали­зу синдрома.

Синдромом называется совокупность элемен­тов, которые получены суммированием по модулю 2 принятых про­верочных элементов и проверочных элементов, вычисленных по принятым информационным элементам. Вычисление производится по тому же правилу, кото­рое применяется для их определения на передающей стороне.

Для определения проверочных элементов b₁, b₂,…, b_r на передающей стороне пользу­ются операторами R₁, ..., R_r, b_i=R_i{a_j}, где а_j - множество ин­формационных элементов данной кодовой комбинации. На прием­ной стороне по принятой совокупности информационных элемен­тов { а_j *} вычисляются с помощью тех же операторов R_i (они должны быть обязательно известны и на приемной стороне) новые проверочные элементы b'_i= R_i{a_j*} (знак * означает принятые элементы кодовой комбинации, которые из-за ошибок в канале могут отличаться от переданных). Далее принятые проверочные элементы (т.е. имеющиеся в принятой кодовой комбинации) b₁*, b₂*,…, b_r* складываются по модулю 2 с вычислен­ными проверочными элементами b'₁, b'₂, ..., b'_r:

В результате сложения получается некоторая кодовая комби­нация, которую называют синдромом или вектором ошибки.

Допустим, что все информационные элементы кодовой комбинации приня­ты верно, тогда {а_j} = {а_j*} и, значит, {b_i*} = {b_i}, т. е. проверочные элементы, вычисленные по {а_j*}, такие же, как на передающей стороне. Если при приеме проверочных элементов также не произошло ошибок, то

В этом случае все разряды синдрома будут представлены нулями:

С₁С₂…С_r 00…0.

Если где-то произошла ошибка, то в составе синдрома появятся единицы. Это и есть способ обнаружения ошибок кодом Хэммин­га. Поскольку код Хэмминга имеет минимальное кодовое расстоя­ние do=3, то это означает, что код может исправлять одну ошибку, т. е. указать номер позиции в кодовой комбинации, где произош­ла ошибка (что для двоичных кодов достаточно, т.к. в этом случае кодовый элемент на указанной позиции просто меняется на противоположный). В одном из вариантов кода Хэмминга между видом синдрома и номером ошибоч­ного разряда имеется однозначное соответствие: двоичное число синдрома представляет собой условный номер (в десятичной си­стеме) того разряда в кодовой комбинации, где произошла ошиб­ка.

Построение кода Хэмминга

Рассмотрим пример построения кода Хэмминга, в котором между видом синдрома и номером ошибоч­ного разряда имеется однозначное соответствие: двоичное число синдрома представляет собой условный номер (в десятичной си­стеме) того разряда в кодовой комбинации, где произошла ошиб­ка.

Для этого, сопоставляя двоичное число, которое представляет синдром, с номером позиции элементов множеств {а_j} и {b_i}, в которых произошла ошибка (учитываем, что ошибка может произойти и в информационном, и в проверочном разрядах), найдем вид операторов {R_i}.

Предположим, что требуется сформировать код при условии, что кодовая комбинация содержит 5 информационных символов (k=5) и код должен исправлять однократную ошибку, т.е. ошибку в одном разряде (t_И=1). Определим требуемое расстояние Хэмминга и число проверочных разрядов:

Будем считать, что d₀=3. Найдем число проверочных разрядов:

Получили, что для обеспечения требуемого расстояния Хэмминга d₀=3 кодовая комбинация должна содержать 4 проверочных элемента (элементы b₁b₂b₃b₄), т.е. код вида (9,5).

Появление единицы в синдроме происходит следую­щим образом:

Если синдром имеет такой вид, то кодовая комбинация не имеет ошибки ни в одном разряде. Если синдром имеет вид 0001, то будем считать, что произошла ошибка в первом разряде в проверочном элементе b₄^′. Синдром вида 0010 свяжем с ошибкой во втором разряде в проверочном элементе b₃^′. Синдром вида 0100 свяжем с ошибкой в четвертом разряде в проверочном элементе b₂^′ (т.к. в десятичном коде 0100 соответствует числу 4). Синдром вида 1000 свяжем с ошибкой в восьмом разряде в проверочном элементе b₁^′ (т.к. в десятичном коде 1000 соответствует числу 8). Т.о. одна единица в синдроме соответствует ошибке в одном из проверочных элементов, а проверочные элементы будут располагаться в 1, 2, 4 и 8 разрядах кодовой комбинации.

Появление большего числа единиц в синдроме будет свя­зано с ошибками в информационных элементах {а_j}. Информационные элементы кодовой комбинации будут располагаться в 3, 5, 6, 7, 9 разрядах.

Запишем вид синдрома, соответствующий ошибке в каждом разряде кодовой комбинации в виде таблицы:

Число, соответствующее синдрому в десятичном коде	Элементы синдрома				Элементы кодовой комбинации с ошибками
	С1	С2	С3	С4
1	0	0	0	1	b4
2	0	0	1	0	b3
3	0	0	1	1	a1
4	0	1	0	0	b2
5	0	1	0	1	a2
6	0	1	1	0	a3
7	0	1	1	1	a4
8	1	0	0	0	b1
9	1	0	0	1	a5
10	1	0	1	0	a6
11	1	0	1	1	a7
12	1	1	0	0	a8
13	1	1	0	1	a9
14	1	1	1	0	a10
15	1	1	1	1	a11

Т.о. всем элементам кодовой комбинации поставлено в соответствие значение синдрома, которое при переводе в десятичный код, соответствует номеру разряда этого элемента. Таблица составлена до 15 разряда, т.к. именно это число позволяет записать двоичная комбинация из 4-х элементов. Т.к. в примере кодовая комбинация состоит из 9 элементов будем пользоваться первыми девятью строками таблицы.

Теперь определим {R_i} — операторы фор­мирования проверочных элементов по информационным элементам. При этом учтем, что единственное линейное преобразование, которое можно совершать над информационными элементами, - это суммирование (в данном случае суммирование по модулю 2).

Построим ал­горитм оператора R₁ так, чтобы он включал в себя информационные элемен­ты, ошибка в которых приводила бы к появлению единицы «1» в младшем разряде синдрома (С₄). Наличие «1» в млад­шем разряде С₄ соответствует проверочному элементу b₄. Кроме того, эта «1» есть в синдромах с номерами 3, 5, 7, 9, 11, 13, 15, что соответствует информационным элементам а₁, а₂, a₄, a₅, a₇, а₉, a₁₁. Таким образом,

Для девятиразрядной кодовой комбинации

Если в одном из этих элементов произойдет ошибка, то это неиз­бежно приведет к изменению b₄.

Для формирования проверочного элемента b₃, в синдроме ко­торого единица стоит на второй позиции (второй разряд), отби­раем информационные элементы, имеющие «1» во втором разря­де своих синдромов, т. е. a₁, а₃, а₄, а₆, а₇, а₁₀, а₁₁:

Для девятиразрядной кодовой комбинации

Для формирования проверочного элемента b₂, в синдроме ко­торого единица стоит на третьей позиции (третий разряд), отби­раем информационные элементы, имеющие «1» в третьем разря­де своих синдромов, т. е. a₂, а₃, а₄, а₈, а₉, а₁₀, а₁₁:

Для девятиразрядной кодовой комбинации

Для формирования проверочного элемента b₁, в синдроме ко­торого единица стоит на четвертой позиции (четвертый разряд), отби­раем информационные элементы, имеющие «1» в четвертом разря­де своих синдромов, т. е. a₅, а₆, а₇, а₈, а₉, а₁₀, а₁₁:

Для девятиразрядной кодовой комбинации

Пример

Имеется комбинация информационных элементов 11001. Для кода Хэмминга построить разрешенную комбинацию кода (9,5) и показать, что данный код исправляет однократную ошибку.

Воспользуемся проверочной матрицей приведенной выше. Имеем:

Разрешенная комбинация имеет вид 11001 1111.

Пусть произошла ошибка в элементе а₃, т. е. приняли комбинацию 11101 1111. Проверим, исправляется ли ошибка. Для этого вычис­лим по информационной части принятой кодовой комбинации новые провероч­ные разряды:

Найдем синдром

0110 – в десятичной системе есть число 6. На 6-м условном номере согласно таблице стоит инфор­мационный элемент а₃. Следовательно, значение принятого элемента а'₃ нужно исправить: вместо «1» поставить «0». В результате кодовая комбинация принята правильно: 11001.