26. Декодирование принятых комбинаций кода Хэмминга.
Декодирование принятых комбинаций кода Хэмминга и исправление одиночных искажений производится в соответствии со следующими преобразованиями.
1. Определение элементов синдрома e
,
e
,
e
,
e
e = u1 u3 u5 u7 u9
(28)
e = u4 u5 u6 u7
e = u8 u9 u10
2. Восстановление искаженной принятой кодовой комбинации кода Хэмминга. Пример: передается разрешенная комбинация кода Хэмминга 1001001101 в исходной информационной двоичной комбинации произошло искажение в третьем (слева направо) разряде искажение и на приемник поступил код 1011001101. Каждый разряд слева направо обозначается буквами u1u2u3u4u5u6u7u8u9u10. Декодирование осуществляется по системе уравнений (28):
e = 1 1 0 1 0 =1
e = 0 1 0 1 1 =1
e = 1 0 0 1 =0
e = 1 0 1 =0
Синдром в этом случае равен 0011, что при переводе в десятичное число означает цифру 3, т.е. 0011 3, это указывает на искажение третьего элемента в принятой кодовой комбинации, который и подлежит исправлению с 1 на 0, что в свою очередь и приводит к восстановлению искаженной кодовой комбинации.
27. Алгоритм декодирования принятых комбинаций систематического кода.
-
b11 b21 ... bk1 10 ... 0(22)
b12 b22 ... bk2 01 ... 0................................
b1r b2r ... bkr 00 ... 1
10000 |
0011 |
(20)
G9,5 = |
0101 |
00100 |
0110 |
00010 |
0111 |
00001 |
1001 |
На основании проверочной матрицы Hn,r (22) формируется алгоритм кодирования и декодирования систематического кода.
В качестве примера построим на основании производящей матрицы (20) проверочную матрицу H9,4.
-
a1
a2
a3
a4
a5
b1
b2
b3
b4
(23)
0
0
0
0
1
1
0
0
0
H9,4
=
0
1
1
1
0
0
1
0
0
1
0
1
1
0
0
0
1
0
1
1
0
1
1
0
0
0
1
По полученной проверочной матрице H9,4 определяются проверочные элементы b1, b2, b3, b4 на основании следующих уравнений:
b1 = a5
b2 = a2 a3 a4
(24)
b4 = a1 a2 a4 a5
Следовательно, любая кодовая комбинация систематического кода определяется из Np=2k исходных комбинаций. Например, если на вход кодирующего устройства поступает исходная информационная кодовая комбинация 11001, то на его выходе образуется разрешенная кодовая комбинация систематического кода
a1=1; a2=1; a3=0; a4=0; a5=1.
b1=1; b2=1; b3=1; b4=1.
11001 11001 1111.
При исходной комбинации 10101 кодовая комбинация систематического кода определится как
a1=1; a2=0; a3=1; a4=0; a5=1.
b1=1; b2=1; b3=0; b4=0.
10101 10101 1100.
При декодировании принятых комбинаций, т.е. обработки систематического кода приемным устройством, алгоритм распознавания искаженной кодовой комбинации определяется в соответствии со следующими уравнениями:
b =b1 a5
(25)
b =b3 a1 a3 a4
b =b4 a1 a2 a4 a5
Например при передаче разрешенной комбинации 110011111 произошло искажение в пятом разряде и принята комбинация 110001111 (искажение в 5 разряде, передана 1, а принят 0).
Если при проверке приемным устройством разрешенной комбинации систематического кода окажется, что хотя бы одно из уравнений (25) не будет равно 0, то в кодовой комбинации произошли ошибки. В приведенном примере принятая кодовая комбинация 110001111 по уравнениям (25) при a1=1, a2=1, a3=0, a4=0, a5=0, b1=1, b2=1, b3=1, b4=1 оценивается как:
b =1 0 =1
(26)
b =1 1 0 0=0
b =1 1 1 0 0=0
Равенство 1 первого и четвертого уравнений говорит о возникшем искажении кодовой комбинации и если стоит задача только оценки правильности приема кодовой комбинации, то по рассмотренному примеру формируется команда сигнализации об искажении принятой кодовой комбинации, принимается решение либо о перезапросе кодовой комбинации или об отказе ее обработке приемными устройствами.
Если же предусмотрена операция исправлений искажений, то необходимо провести дальнейший анализ уравнений (25).
Так например, наличие 1 в первом и четвертом уравнениях говорит о том, что искаженным может быть один из элементов разрешенной кодовой комбинации систематического кода b1, b4, a1, a2, a4, a5.
Наличие 0 во втором и третьем уравнениях означает, что элементы b2, b3, a1, a2, a3, a4 приняты без искажений. Исключая правильно принятые элементы из первого и четвертого уравнений определяют потенциально искаженные элементы. Таким искаженным элементом в рассматриваемом примере может быть один из b1, b4, a5, но элемент a5 входит и в первое и во второе уравнения, следовательно искажен он.
Заменив в принятой кодовой комбинации в элементе 5 значение 0 на 1, восстанавливается искаженная кодовая комбинация. Результаты проверок правильности принятых кодовых комбинаций по уравнениям (25) называют синдромом (синдром-определитель), так же называется и программно-аппаратный модуль приемного устройства.