Например, для кода (7, 4) порождающая матрица имеет вид 1,ф-ла (5.23)
G
. (6,а.4)
2.5 Процесс декодирования включает в себя вычисление синдрома, который в матричной форме записывается как :
H
= C,
(6,а.5)
где H – проверочная матрица размером rn.
– матрица – столбец размера n , соответствующая принятой из канала кодовой комбинации;
C –матрица – столбец размера r.
Из соотношения 6,а.5) следует, что вычисление синдрома сводится к r проверкам
i
= 1, 2, …, r, (6,а.6)
т.е. i-ая проверка определяется элементами i-ой строки проверочной матрицы.
2.6 Проверочная матрица строится следующим образом 2, с. 88. В начале строится матрица, транспонированная по отношению к матрице- дополнению, а затем к ней справа приписывается единичная матрица:
H
. (6,а.7)
Например, для кода (7.4) с порождающей матрицей (6,а.4) проверочная матрица имеет вид:
H
, (6,а.8)
и проверки декодера сводятся к следующим выражениям:
с1
=
,
с2
=
,
с3
=
.
На основе (6,а.9) легко составить таблицу ненулевых синдромов (табл. 6,а.1).
Таблица 6,а.1 – Ненулевые синдромы кода Хэмминга (7, 4)
-
Синдром с1с2с3
100
010
001
110
101
011
111
Ошибочный символ
Последние четыре колонки табл. 6,а.1 указывают, как по виду синдрома определяется номер ошибочного символа (дополнительные символы не подлежат исправлению, так как после выполнения проверок (6,а.9) они не используются).
2.7 Правило формирования дополнительных символов (6,а.3) является основой алгоритма работы кодера:
1. На вход кодера поступают k информационных символов в параллельном коде либо в последовательном коде (в последнем случае требуется регистр сдвига длиной k).
2. Вычисляются r = n – k дополнительных символов с помощью сумматоров по модулю r.
3. k информационных и r дополнительных символов поступают на выход кодера в параллельном либо последовательном коде (в последнем случае требуется преобразователь параллельного кода в последовательный).
На рис. 6,а.1 приведена функциональная схема кодера кода (7, 4) с порождающей матрицей (6,а.4). Символы входной и выходной кодовых комбинаций представлены в параллельном коде.
2.8 Алгоритм работы декодера следующий:
1. На вход декодера поступает n символов принятой кодовой комбинации.
2. На основе соотношения (6,а.6) вычисляется синдром.
3. Анализатор синдрома, построенный на основе таблицы синдромов, формирует сигналы для исправления ошибочных информационных символов.
4.
Производится исправление ошибочных
символов, состоящее в их инверсии и
выполняемое путем сложения по модулю
2 исправляемого символа с единицей
(пусть
–
некоторый символ, тогда
1 =
).
5. На выход декодера после исправления ошибки поступает комбинация простого кода из k символов.
На рис. 6,а.2 приведена функциональная схема декодера кода (7, 4), построенная на основе проверочной матрицы (6,а.8). Символы входной и выходной кодовых комбинаций представлены в параллельном коде. Анализатор синдрома реализует следующую функциональную зависимость (табл. 6,а.2), построенную на основе таблицы синдромов (табл. 6,а.1).
Таблица 6,а.2 – Функциональная зависимость анализатора синдрома
-
Входы
Выходы
С1
С2
С3
1
2
3
4
1
1
0
1
0
0
0
0
1
1
0
1
0
0
1
1
1
0
0
1
0
1
0
1
0
0
0
1
2.9 Код, кодер и декодер которого строятся на многовходных сумматорах по модулю 2, называют кодом Хэмминга или кодами с проверками на четность. Основы построения кодеров и декодеров кодов Хэмминга рассмотрены выше и иллюстрированы на примере кода (7, 4). Используя изложенные принципы можно построить кодер и декодер при других значениях n и k.