ГЛАВА 3

ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

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

3.1. СТРУКТУРА ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ

Напомним, что векторное пространство GF" {q) представляет собой множество п-последовательностей элементов из GF (q) с покомпонентным сложением и умножением на скаляр. Наиболее важным частным случаем является GF" (2) - векторное пространство двоичных слов длины п, в котором при сложении двух векторов в каждой компоненте происходит сложение по модулю 2.

Определение 3.1.1. Линейный код есть подпространство в в GF" (q).

Таким образом, линейный код есть непустое множество п-последовательностей над GF (q), называемых кодовыми словами, такое, что сумма двух кодовых слов является кодовым словом, и произведение любого кодового слова на элемент поля также является кодовым словом. В любом линейном коде нулевое слово как начало координат векторного пространства всегда есть кодовое слово. Точнее, если с - кодовое слово, то - с также кодо-

62 гл. 3. ЛИНЕЙНЫЕ БЛОКОВЫЕ КОДЫ

вое слово и, следовательно, с -- (- с) тоже будет кодовым словом.

Каждое слово в линейном коде связано с остальными словами кода так же, как любое другое кодовое слово. Расположение соседних кодовых слов вокруг нулевого слова есть типичное расположение слов вокруг любого другого кодового слова. Например, предположим, что с -некоторое кодовое слово и с, -

кодовые слова, находящиеся на некотором расстоянии d от с; тогда с -с -нулевое слово и -с, -с, -

- с - кодовые слова, находящиеся на расстоянии d от нулевого слова. Таким образом, для определения минимального расстояния линейного кода достаточно определить расстояние между нулевым словом и ближайшим к нему другим кодовым словом.

Определение 3.1.2. Вес Хэмминга w (с) кодового слова с равен числу его ненулевыхкомпонент. Минимальный вес кода W* есть минимальный вес ненулевого кодового слова.

Теорема 3.1.3. Для линейного кода минимальное расстояние d* находится из равенства

d* = min w (с) = w*,

где минимум берется по всем кодовым словам, кроме нулевого. Доказательство.

d* = mm d{ci, c) = min d(0, Cj - Cj-) = min w(c).

C.,C.S C-, CjGS cS

iii 1Ф,- □

Следовательно, для нахождения линейного кода, исправляющего t ошибок, необходимо найти линейный код с минимальным весом, удовлетворяющим неравенству

W* 2t+ 1.

Изучение метрических свойств линейных кодов много проще, чем нелинейных.

3.2. МАТРИЧНОЕ ОПИСАНИЕ

ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ

Линейный код ё образует подпространство в GF" (q). Для изучения этих кодов будет полезна теория линейных пространств. Любое множество базисных векторов может быть использовано в качестве строк для построения (Хп)-матрицы G, которая называется порождающей матрицей кода. Пространство строк матрицы G есть линейный код W, любое кодовое слово есть линейная комбинация строк из G. Множество q кодовых слов называется линейным (п, )-кодом.

3.2. МАТРИЧНОЕ ОПИСАНИЕ 63

Строки матрицы G линейно независимы, и число строк k равно размерности подпространства. Размерность всего пространства GF" (q) равна п. Всего существует 9 кодовых слов, и q различных -последовательностей над GF (q) могут быть отображены на множество кодовых слов.

Любое взаимно однозначное соответствие й-последовательностей и кодовых слов может быть использовано для кодирования, но наиболее естественный способ кодирования использует отображение

c = iG,

где i - информационное слово, представляющее собой k-no-следовательность кодируемых информационных символов, а с -образующая кодовое слово «-последовательность. Задаваемое последним равенством соответствие между информационным и кодовым словами определяет кодер и зависит от выбора базисных векторов в качестве строк матрицы G; в то же время само множество кодовых слов не зависит от этого выбора.

В качестве простого примера двоичного блокового кода рассмотрим порождающую матрицу

10 0 10

О I О О I 0 0 111

в этом случае информационное слово

i = [О 1 1 ]

будет кодироваться в кодовое слово

10 0 10 с = [0 1 1] 0 10 0 1 0 0 111

= [01110].

Порождающая матрица является сжатым описанием линейного кода. Сравните двоичный линейный (100,50)-код, для описания которого требуется 100X50 = 5000 битов, определяющих элементы матрицы G, с произвольным (100, 50)-кодом, имеющим 2" кодовых слов и требующим для описания примерно 10* битов.

Поскольку ё является подпространством, оно имеет ортогональное дополнение?--, которое состоит из всех векторов, ортогональных к Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как код. Когда само рассматривается как код, оно называется кодом, дуальным к