5.4. Линейные блочные коды

5.4.1. Система передачи дискретных сообщений

При передаче информации по каналам связи возможны ошибки вследствие помех и искажений сигналов. Для обнаружения и исправления возникающих ошибок используются помехоустойчивые коды. Упрощенная схема системы передачи информации при помехоустойчивом кодировании показана на рис. 5.3.

Кодер служит для преобразования поступающей от источника сообщений последовательности из  информационных символов в последовательность из  символов кодовых комбинаций (или кодовых слов). Совокупность кодовых слов образует код.

Множество символов, из которых составляется кодовое слово, называется алфавитом кода, а число различных символов в алфавите – основанием кода. В дальнейшем вследствие их простоты и наибольшего распространения рассматриваются главным образом двоичные коды, алфавит которых содержит два символа: 0 и 1.

Правило, по которому информационной последовательности сопоставляется кодовое слово, называется правилом кодирования. Если при кодировании каждый раз формируется блок  из  информационных символов, превращаемый затем в -символьную кодовую комбинацию , то код называется блочным. При другом способе кодирования информационная последовательность на блоки не разбивается, и код называется непрерывным.

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

Дискретный канал связи – это совокупность технических средств вместе со средой распространения радиосигналов, включенных между кодером и декодером для передачи сигналов, принимающих конечное число разных видов. Для описания реальных каналов предложено много математических моделей, с разной степенью детализации отражающих реальные процессы. Ограничимся рассмотрением простейшей модели двоичного канала, входные и выходные сигналы которого могут принимать значения 0 и 1.

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

.

(5.14)

Таким образом, компонента вектора ошибки  указывает на то, что 2-й символ принят правильно (), а компонента  указывает на ошибку при приеме ().Поэтому важной характеристикой вектора ошибки является число  ненулевых компонентов, которое называется весом или кратностью ошибки. Кратность ошибки – дискретная случайная величина, принимающая целочисленные значения от 0 до .

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

Для симметричного стационарного канала распределение вероятностей векторов ошибки кратности  является биноминальным:

,

где    – число сочетаний из  элементов по .

Вероятность искажения конкретных  символов (или вероятность появления одной конфигурации  вектора ошибки веса ) определяется по формуле

,

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

Декодирующее устройство (декодер) предназначено оценить по принятой последовательности  значения информационных символов . Из-за действия помех возможны неправильные решения. Процедура декодирования включает решение двух задач: оценивание переданного кодового слова и формирование оценок информационных символов.

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

Наибольшую трудность представляет первая задача декодирования. При равновероятных информационных последовательностях ее оптимальное решение дает метод максимального правдоподобия. Функция правдоподобия как вероятность получения данного вектора  при передаче кодовых слов ,  на основании (5.14) определяется вероятностями появления векторов ошибок:

,

где     – вес вектора

Очевидно, вероятность  максимальна при минимальном . На основании принципа максимального правдоподобия оценкой  является кодовое слово, искажение которого для превращения его в принятое слово  имеет минимальный вес, т. е. в симметричном канале является наиболее вероятным (НВ):

.

Если несколько векторов ошибок  имеют равные минимальные веса, то наивероятнейшая ошибка  определяется случайным выбором среди них.

В качестве расстояния между двумя кодовыми комбинациями принимают так называемое расстояние Хэмминга, которое численно равно количеству символов, в которых одна комбинация отлична от другой, т.е. весу (числу ненулевых компонентов) разностного вектора. Расстояние Хэмминга между принятой последовательностью  и всеми возможными кодовыми словами 5, есть функция весов векторов ошибок :

.

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

Таким образом, оптимальная процедура декодирования для симметричного канала может быть описана следующей последовательностью операций. По принятому вектору  определяется вектор ошибки с минимальным весом , который затем вычитается (в двоичном канале - складывается по модулю 2) из :

.

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

Широко распространены линейные коды, называемые так потому, что их кодовые слова образуют линейное подпространство над конечным полем. Для двоичных кодов естественно использовать поле характеристики . Принадлежность принятой комбинации  известному подпространству является тем признаком, по которому выносится решение об отсутствии ошибок ().

Так как по данному коду все пространство последовательностей длины  разбивается на смежные классы (см. 5.3.2), то для каждого смежного класса можно заранее определить вектор ошибки минимального веса, называемый лидером смежного класса. Тогда задача декодера состоит в определении номера смежного класса, которому принадлежит , и формировании лидера этого класса.