3.5. Декодирование по стандартной таблице

В этом разделе представлена процедура декодирования, кото­рая находит кодовое слово ,ближайшее к принятому с иска­жениями слову , где вектор ошибок создан двоичным симметричным каналом (ДСК) в процессе передачи кодового слова. Модель ДСК показана на Рисунке 5. По пред­положению переходная вероятность р (или параметр ДСК) меньше 1/2.

Стандартной таблицей (или стандартной расстановкой) [Sle] для двоичного линейного (n,k, d_min)кода С называется таблица всех возможных принятых из канала векторов , организованная таким образом, что может быть найдено ближай­шее к кодовое слово .

Рис. 3.3. Модель двоичного симметричного канала

Стандартная таблица содержит 2^n-kстрок и2^k+ 1 столбцов. Правые 2^к столбцов таблицы содержат все вектора из прост­ранстваV₂= {0, 1}^л.

Для описания процедуры декодирования необходимо вве­сти понятие синдрома. Определение синдрома произвольного слова изV₂следует из уравнения (3.10),

(3.16)

где Н проверочная матрица кода С. Покажем, что синдром яв­ляется индикатором вектора ошибок. Предположим, что кодо­вое слово , переданное по ДСК, принято как . Синдром принятого слова равен

(3.17)

Таким образом, вычисление синдрома можно рассматривать как линейное преобразование вектора ошибок.

Таблица 3.1

Стандартная таблица двоичного линейного блоко­вого кода

s	u0=0	u1
0	v0	v0
s1	e1	e1+ v1
s2	e2	e2+ v1

Процедура построения стандартной таблицы

1. Правые столбцы первой строки заполним кодовыми слова­ми кода С, начиная с нулевого кодового слова. В первую ячейку первого столбца запишем нулевой синдром. Поло­жимj= 0.

2. Дляj= j+ 1, найдем слово минимального веса Хемминга, не являющееся кодовым и не включенное в предыдущие строки таблицы. Соответствующий синдром запишем в первый (крайний левый) столбец j-ой строки. В оставшиеся 2^к ячеек этой строки запишем сум­мы и содержимого первой строки (т.е. кодового слова).

3. 3. Повторяем шаг 2 процедуры, пока все вектора изV₂не ока­жутся включенными в таблицу. Эквивалентно, повторяем шаг 2 покаj<2^п-к, иначе Стоп.

Пример 5. Стандартная таблица двоичного линейного (4,2,2) кода:

s	00	01	10	11
00	0000	0110	1011	1101
11	1000	1110	0011	0101
10	0100	0010	1111	1001
01	0001	0111	1010	1100

Декодирование с помощью стандартной таблицы выпол­няется следующим образом. Пусть г = v+е принятое слово. Найдем это слово в таблице и возьмем в качестве результата де­кодирования сообщение u, записанное в верхней (первой) ячейке того столбца, в котором лежит принятое слово г. По идее, этот процесс требует хранения в памяти всей таблицы и поиска в ней заданного слова.

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

Синдром всех элементов i-ой строки равен

(3.18)

и не зависит от конкретного значения кодового слова . Упрощенная процедура декодирования состоит в следующем: вычислить синдром принятого слова

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

Таким образом, вместо таблицы п× 2ⁿ бит для декодирова­ния достаточно использовать таблицу лидеров смежных клас­сов п × 2^n-kбит.

Пример 6. Снова рассмотрим двоичный линейный (4, 2, 2) код из Примера 3. Положим, что передано было кодовое слово (0110), а принято слово (0010). Тогда синдром равен

Находим в стандартной таблице лидер смежного класса (0100) и получаем декодированное кодовое слово (0010)+(0100)=(0110). Одиночная ошибка в слове исправлена! Это может показаться странным, так как минимальное кодо­вое расстояние равно 2 и, согласно условию, исправление однократных ошибок невозможно. Однако объяснение этому может быть найдено в стандартной таблице (Пример 5). Заме­тим, что третья строка таблицы содержит два различных дво­ичных вектора веса 1. Это означает, что только три из возмож­ных четырех одиночных ошибок могут быть исправлены. В Примере 6 дана одна из исправляемых ошибок.

Оказывается, что данный (4, 2, 2) код является простей­шим примером линейного кода с неравной защитой от ошибок {linearunequalerrorprotection— LUEPкод) [Wv, Van], Данному LUEPкоду соответствует разделяющий вектор (3,2), который показывает, что минимальное кодовое расстояние равно трем, если различаются первые биты сообщений и равно двум, если различаются вторые биты сообщений.

В случае систематического кодирования рассмотренная выше процедура находит оценку переданного сообщения на первых k позициях декодированного слова. Это может быть одной из возможных причин применения систематического кодирования.