ГЛАВА 5. ВАЖНЕЙШИЕ ЛИНЕЙНЫЕ КОДЫ

В данной главе описаны некоторые двоичные коды, которые были хорошо известны еще до создания теории циклических кодов. Среди них наиболее известен код Хэмминга,

5.1. Коды Хэмминга

Двоичный код Хэмминга удобнее всего задавать при помощи его проверочной матрицы. Рассмотрим матрицу И из нулей и единиц, содержащую строк и столбцов, причем столбцами являются все ненулевые двоичные последовательности длины Над полем из двух элементов любые два вектора, дающие в сумме 0, должны совпадать. Поэтому сумма любых двух столбцов из этой матрицы не равна 0, и поскольку единственным отличным от нуля скаляром является 1, то не существует ни одной нулевой линейной комбинации из двух столбцов матрицы И. Следовательно, нулевое пространство этой матрицы имеет минимальный вес, равный 3, и является кодом, исправляющим все одиночные ошибки. Длина кодовых векторов равна число проверочных символов равно следовательно, число информационных символов равно

Поскольку все векторов, задающих одиночные ошибки, принадлежат различным смежным классам, то этими смежными классами и кодовым пространством исчерпываются все смежных классов. Поэтому образующими смежных классов для этого кода являются нулевой вектор и все векторы одиночных ошибок, причем других векторов среди образующих нет, так что код Хэмминга является примером совершенного кода. Можно построить код Хэмминга любой длины если матрицу И строить для наименьшего значения удовлетворяющего условию а затем просто отбросить все лишние столбцы, оставив столбцов. Независимо от того, какие именно столбцы отбрасываются, минимальный вес кода будет все еще равен 3. Можно выбрать столбцы таким образом, чтобы получился квазисовершенный код. (См. задачи 5.1 и 5.3.) Итак, для любого существует код Хэмминга, исправляющий все одиночные ошибки, который является оптимальным для двоичного симметричного канала.

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

ошибка, и содержащий 0 на всех остальных местах. Синдром равен

так как — кодовый вектор и поэтому принадлежит нулевому пространству матрицы И. Но поскольку это вектор, содержащий единственную единицу на месте, соответствующем ошибке, то синдром равен как раз той строке матрицы которая соответствует ошибке. Таким образом, сравнивая синдром с матрицей можно найти положение ошибки и исправить ее, просто заменив соответствующий символ на правильный. Особенно удобно это делать, если использовать в качестве столбца матрицы двоичное представление числа Тогда для каждой отдельной одиночной ошибки синдром является двоичным представлением номера компоненты, в которой произошла ошибка. Это расположение первоначально использовано Хэммингом.

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

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

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

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

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

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

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

1. Если синдром равен 0, то предполагается, что ошибок не было.

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

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

Можно доказать, что код Хэмминга с расстоянием, равным 4, является квазисовершенным. (Задача 5.2.) И в этом случае можно отбросить некоторые столбцы проверочной матрицы, так чтобы получился код с минимальным расстоянием, равным 4, для любой длины

На первый взгляд может показаться, что для того чтобы обобщить код Хэмминга на случай, когда символы кода принадлежат некоторому полю с элементами, необходимо только выбрать в качестве проверочной матрицы И матрицу размерности столбцами которой являются все возможные различные последовательности длины Однако это не так, поскольку теперь некоторые нетривиальные линейные комбинации двух столбцов будут равны 0. Например, над полем из 3 элементов сумма векторов (2,1) и (1,2) равна (0,0). Затруднение возникает потому, что векторы (1,2) получаются умножением вектора (2,1) на скаляр. В случае двоичного кода единственный скаляр тривиален.

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

доли всех последовательностей первый ненулевой символ равен 1, максимальное число столбцов матрицы И равно поэтому

Пример. В поле из трех элементов код с тремя проверочными символами является нулевым пространством матрицы

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

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

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

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

Кодом, двойственным к двоичному коду Хэмминга, исправляющему все одиночные ошибки, является код Макдональда. Двойственным к коду Хэмминга с расстоянием, равным 4, является код Макдональда или эквивалентный ему код Рида — Маллера первого порядка.