Совершенные и квазисовершенные коды

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

Свойства совершенного кода2:

Для совершенного -кода, исправляющего все ошибки веса, не большего , выполняется соотношение . Верно и обратное утверждение;

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

Таблица декодирования совершенного кода, исправляющего все ошибки в не более чем позициях, имеет в качестве лидеров все строки, содержащие не более единиц. Верно и обратное утверждение.

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

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

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

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

Действительно, .

Порядок построения кода Хэмминга следующий:

Выбираем целое положительное число . Сообщения будут словами длины , а кодовые слова - длины ;

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

Строится матрица из строк и столбцов. В -ой строке стоят цифры двоичного представления числа . Матрицы для r=2, 3 и 4 таковы:

Записывается система уравнений , где - матрица из предыдущего пункта. Система состоит из уравнений. Например, для :

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

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

Пример. -код Хэмминга имеет в качестве одного из кодовых слов . Матрица приведена на шаге 3 хода построения кода Хэмминга. Ясно, что . Добавим к строку ошибок . Тогда и , т.е. ошибка находится в третьей позиции. Если , то и позиция ошибки - и т.п. Если ошибка допущена в более чем в одной позиции, то декодирование даст неверный результат.