Часть I: Глава 1. Линейные коды

1.1. ЛИНЕЙНЫЕ КОДЫ

Коды были придуманы для того, чтобы исправлять ошибки в каналах связи с шумом. Предположим, что имеется телеграфная линия из Бостона в Нью-Йорк, по которой можно посылать 0 и 1. Обычно при посылке 0 принимается также 0, но иногда 0 может быть принят как 1 или 1 принята как 0. Будем считать, что в среднем один из каждых 100 символов будет ошибочным. Это означает, что для каждого символа имеется вероятность того, что в канале произойдет ошибка. Описанная модель называется двоичным симметричным каналом (рис. 1.1).

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

Мы хотим закодировать эти сообщения, чтобы как-то защитить их от ошибок в канале. Блок из символов сообщения будет кодироваться в кодовое слово или 1), где (рис. 1.2); эти кодовые слова образуют код.

Рис. 1.1. Двоичный симметричный канал с вероятностью ошибки (в общем случае

Рис. 1.2 Кодирование сообщения

Метод кодирования, который мы сейчас собираемся описать, порождает код, называемый линейным кодом. Первая часть кодового слова состоит из символов самого сообщения:

за которым следуют проверочных символов Проверочные символы выбраны так, чтобы кодовые слова удовлетворяли уравнению

где — матрица называемая проверочной матрицей кода, имеет вид

Здесь А — некоторая фиксированная - матрица из 0 и 1, а

— единичная матрица размера Все операции в уравнении (1.1) выполняются по модулю 2, т. е. Мы будем называть это двоичной арифметикой. Пример. Код Проверочная матрица

определяет код с Для этого кода

Сообщение кодируется в кодовое слово которое начинается с самого сообщения:

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

Если сообщение то и проверочные символы легко определяются:

так что кодовое слово

Уравнения (1.4) называются уравнениями проверки на четность или проверками на четность для кода. Первое уравнение проверки на четность говорит, что 2, 3 и 4-й символы каждого кодового слова должны в сумме давать 0 по модулю 2, т. е. их сумма должна быть четной (откуда и название!).

Так как каждый из трех символов сообщения равен О или 1, то в этом коде имеется всего кодовых слов. Эти слова:

В коде в общем случае имеется кодовых слов.

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

Мы примем условие (1.1) как общее определение.

Определение. Пусть — любая двоичная матрица. Линейный код с проверочной матрицей состоит из всех векторов таких, что (все операции производятся по модулю 2).

Удобно, но не очень существенно, если имеет вид, приведенный в (1.2) и (1.3), когда первые символов каждого кодового слова являются символами сообщения, или информационными символами, а последние символов — проверочными.

Линейные коды наиболее важны для практических применений и просты для понимания. Нелинейные коды будут введены в гл. 2.

Пример. Код код с повторением. Код с и с проверочной матрицей

Каждое кодовое слово содержит только один символ сообщения . Проверочные уравнения имеют вид

т. е. Таким образом, имеются всего два кодовых слова: 00000 и 11111. Передаваемый символ просто повторяется 5 раз; поэтому такой код называется кодом с повторением.

Пример. Код код из всех слов четного веса. Код с и с проверочной матрицей Каждое кодовое слово содержит три информационных символа и один

проверочный символ Кодовыми словами, число которых являются последовательности все возможные векторы длины 4 с четным числом единиц.

Упражнения. (1). Код имеет проверочную матрицу

Выписать все кодовые слова. Проделать то же самое для матрицы

Как связаны эти коды?

(2). Код имеет проверочную матрицу

Выписать все кодовые слова.

(3). Показать, что при переименование на рис. 1.1 принятых символов преобразует этот канал в двоичный симметричный канал с Показать, что при связь невозможна.