1.3. Кодирование и декодирование линейных блоковых кодов

1.3.1. Кодирование с помощью матриц g и н

Равенство (1.10) определяет по существу правило кодирования для линейного блокового кода, которое может быть использовано непосредственно. Если кодирование должно быть систематическим, то произвольная порождающая матрица G линейного блокового (n, к, d_min) кода С может быть преобразована к систематической форме G_sys (иначе, к канонической форме) с помощью элементарных операций и перестановок столбцов матрицы. Матрица G_sys состоит из двух подматриц: k×k единичной матрицы, обозначаемой I_k, и k× (n-k) проверочной подматрицы Р. Таким образом,

(1.14)

где

(1.15)

Так как GH^T = 0, то отсюда следует, что систематическая форма проверочной матрицы имеет вид

(1-16)

Пример 3. Рассмотрим двоичный линейный (4,2,2) код с порождающей матрицей

Перестановкой второго и четвертого столбцов преобразуем эту матрицу в систематическую форму

Таким образом, проверочная подматрица равна

Интересно отметить, что в данном случае выполняется соотношение Р = Р^т. Из (1.16) следует, что систематическая форма проверочной матрицы имеет вид

В дальнейшем будет использовано обозначение u = (u₀, u₁,…,u_k-1) для информационного сообщения и обозначение v = (v₀, v_l,..., v_n-1) для соответствующего кодового слова кода С.

Если параметры С таковы, что k<(n- k) или, эквивалентно, скорость кода k/п < 1/2, то кодирование с помощью порождающей матрицы более экономно по числу логических операций.

В этом случае

(1.17)

где v_р = uP = (v_k,v_k+1,…,v_n-1) представляет проверочную часть кодового слова.

Однако, если k>(n-k) или k/n > 1/2, тогда кодирование с помощью проверочной матрицы Н требует меньшего количества вычислений. Этот вариант кодирования основан на уравнении (1.12) (u, v_p)H^T = 0. Проверочные позиции (v_k, v_k+1, …, v_n-1) вычисляются следующим образом:

(1.18)

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

Пример 4. Рассмотрим двоичный линейный (4,2,2) код из примера 3. Пусть сообщение и кодовые слова обозначены u = (u₀,u₁) и v = (v₀, v₁, v₂, v₃), соответственно. Из уравнения (1.18) получаем

v₂=u₀+ u₁,

^V3=u₀

Соответствие между 2² = 4 двух битными сообщениями и кодовыми словами имеет следующий вид:

(1-19)

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

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

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

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

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

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

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

(1-20)

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

(1.21)

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

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

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

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

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

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

Однако, возможно некоторое упрощение процедуры декодирования, если заметить, что все элементы одной и той же строки имеют один и тот же синдром. Каждая строка Row_i, 0 ≤i<2^n-k, этой таблицы представляет смежный класс кода С, а именно, Row_i = { e_i +v|vC}. Вектор е_i называется лидером смежного класса.

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

(1.22)

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

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

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

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

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

Оказывается, что данный (4, 2, 2) код является простейшим примером линейного кода с неравной защитой от ошибок (linear unequal error protection - LUEP код). Данному LUEP коду соответствует разделяющий вектор (3,2), который показывает, что минимальное кодовое расстояние равно трем, если различаются первые биты сообщений и равно двум, если различаются вторые биты сообщений.

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