3.3. Линейные блоковые коды

Как уже упоминалось выше, построение хорошего кода озна­чает поиск вV₂подмножества элементов в наибольшей степе­ни удаленных друг от друга. Это очень трудная задача. Более того, если даже это сделано, то остается неясным как назна­чить кодовые слова информационным сообщениям.

Линейный код (т.е. множество кодовых слов) является век­торным подпространством в пространствеV₂. Это означает, что операция кодирования может быть представлена умножением на матрицу. В терминах цифровой электроники простое коди­рующее устройство может быть построено на элементах «исключающее ИЛИ», «И» и триггерах типа D. В этой главе операциями сложения и умножения в двоичном векторном пространстве являются «исключающее ИЛИ» (сложение по модулю 2) и «И», соответственно. Таблицы сложения и умно­жения двоичных элементов имеют следующий вид:

a	b	a+b	аb
0	0	0	0
0	1	1	0
1	0	1	0
1	1	1	1

3.4. Порождающая и проверочная матрицы. Кодирование с помощью матриц g и н

Пусть С двоичный линейный (п, к, d_min)код. Так как С есть k-мерное подпространство, то оно имеет базис, например, (v₀, v,,..., v_k-1)такой, что любое кодовое слово v С может быть за­писано как линейная комбинация элементов этого базиса:

(3.7)

где Уравнение (3.7) может быть записано в матричной форме через порождающую матрицуGи вектор-сообщение

(3.8)

где

(3.9)

Так как С является k-мерным векторным пространством вV₂, то существует (п-к)-мерное дуальное пространство (dualspace), которое порождается строками матрицы Н, называемой проверочной матрицей (parity-checkmatrix) ,такой, что , где через обозначена транспонированная матрица Н. Заме­тим, в частности, что любое кодовое слово удовлетворяет условию

(3.10)

Уравнение (3.10) является фундаментальным для декодирования линейных кодов.

Линейный код , который генерируется матрицей Н, яв­ляется двоичным линейным (п, п — k, )кодом, который называют обычно дуальным коду С.

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

(3.11)

где

(3.12)

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

(3.13)

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

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

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

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

В дальнейшем будет использовано обозначение для информационного сообщения и обозначение для соответствующего кодового слова кода С.

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

(3.14)

где представляет проверочную часть кодового слова.

Однако, если к > (п - к) или к/п> 1/2, тогда кодирование с помощью проверочной матрицы Н требует меньшего коли­чества вычислений. Этот вариант кодирования основан на уравнении (3.14) . Проверочные позиции вычисляются следующим образом:

(3.15)

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

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

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