4 Методы помехоустойчивого кодирования в системах пдс

Коды Хэмминга являются:

1 Блочными, поскольку каждому сообщения соответствует блок некоторого числа разрядов.

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

3 Разделимыми, так как содержат информационные и проверочные разряды, расположенные на определенных местах.

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

Пример 4.1.Построим образующую матрицу кода Хэмминга (7,4) вида а₁ а₂ а₃ а₄ b₁ b₂ b₃, у которого а₁ а₂ а₃ а₄ – информационная группа, b₁ b₂ b₃ – проверочная группа, старшие разряды информационной и проверочной групп расположены слева. Проверочные разряды вычисляются следующим образом:

;

; (10)

,

В рассматриваемом коде длина (количество разрядов) всей КК n=7, длина информационной группы к=4, длина проверочной группы r=n-к=3. Искомая образующая матрица G_(7,4) размерности (7х4) состоит из двух подматриц: единичной – размерности кхк (4х4) и проверочной – размерности rхк (3х4):

G_(7,4)=

(11) 1	0	0	0	0	1	1	а1
0	1	0	0	1	0	1	а2
0	0	1	0	1	1	0	а3
0	0	0	1	1	1	1	а4
а1	а2	а3	а4	b1	b2	b3

В проверочной подматрице, расположенной в правой части образующей матрицы (11), единицам соответствуют номера информационных разрядов а_i, входящих в алгоритмы (10).

Кодовым расстоянием d между двумя кодовыми комбинациями называется количество разрядов, которыми они отличаются. Для определения этого расстояния нужно сложить по модулю 2 две кодовые комбинации (КК) и подсчитать число единиц в полученной сумме, которое называется весом кодовой комбинации. Для помехоустойчивых кодов интерес представляет минимальное кодовое расстояние или расстояние Хэмминга – d₀. Коды Хэмминга относятся к линейным систематическим кодам с d₀=3 и d₀=4.

Кратностью ошибки называется количество ошибочных разрядов КК. Корректирующие свойства помехоустойчивых кодов характеризуются кратностью гарантированно обнаруживаемых t₀ и исправляемых t_и ошибок. Соотношения, устанавливающие связь между кратностью гарантированно обнаруживаемых и исправляемых ошибок и минимальным кодовым расстоянием, выглядят следующим образом:

t₀d₀-1.

(12)

, для нечетных значений d₀

, для четных значений d₀

Обнаружение и исправление ошибок в коде Хэмминга осуществляется на основе определения и последующего анализа синдрома. Под синдромом понимается кодовая комбинация c_1, c_{2 ……..} c_r, которая получается суммированием по модулю 2 принятых проверочных разрядов b^*_1, b^*_{2 ……..} b^*_r и вычисленных проверочных разрядов b^{`</sup><sub>1,</sub> b<sup>`}_{2 ……..} b^`_r по принятым информационным разрядам с использованием одних и тех же алгоритмов вычисления на передаче и приеме. Если все разряды синдрома представлены нулями, то ошибки нет или она не обнаруживается. Наличие хотя бы одной единицы в составе синдрома указывает на обнаружение ошибки и, кроме того, на основе анализа синдрома можно осуществить исправление ошибок. Поскольку код Хэмминга имеет d₀=3 или d₀=4,то в соответствии с (12) он исправляет однократные ошибки на основе таблицы, устанавливающей соответствие между видом синдрома и номером ошибочного разряда.

Для вышеупомянутого кода Хэмминга (7,4) эта таблица имеет вид:

Таблица 1

Ошибочный разряд	Синдром
	С1	С2	С3
a1	0	1	1
a2	1	0	1
a3	1	1	0
a4	1	1	1
b1	1	0	0
b2	0	1	0
b3	0	0	1

Пример 4.2. Исходная кодовая комбинация примитивного кода 0110. Требуется построить разрешенную кодовую комбинацию кода (7,4) и убедиться, что исправляется однократная ошибка.

В данном случае а₁ =0, а₂=1, а₃=1, а₄=0. Воспользовавшись (10) определим проверочные элементы: b₁=0, b₂=1, b₃=1.

Следовательно, разрешенная комбинация имеет вид 0110011. Допустим, что произошла ошибка в а₃ , т.е. принята комбинация 0100011. Вычислим по принятым информационным разрядам а₁₌0_, а_{2 =}1, а₃=0, а₄=0, проверочные разряды b_1, b_{2 ,} b₃ на основе соотношений (10):

b^{`</sup><sub>1</sub>=1, b<sup>`}₂=0, b^`₃=1.

Вычислим синдром:

b^*₁ b^*₂ b^*₃ 0 1 1

b^{`</sup><sub>1</sub> b<sup>`}₂ b^`_{3 =} 1 0 1

c₁ c₂ c₃ 1 1 0

Согласно таблице1нужно исправить а₃, т.е. действительно тот разряд, в котором произошла ошибка.