3.10. Код Хэмминга

Одним из наиболее распространенных систематических кодов является код Хэмминга [132].

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

(r - количество проверочных разрядов). Из этого неравенства получаем

Формулу (3.29) можно привести к следующему виду:

где количество информационных разрядов. Это неравенство позволяет определить длину кода при заданном числе информационных разрядов. В табл. 21 приведены параметры некоторых кодов Хэмминга.

Таблица 21 (см. скан)

Характерной особенностью проверочной матрицы кода с является то, что ее столбцы представляют собой любые различные ненулевые комбинации длиной Например, при т. е. для кода (15,11), проверочная матрица может иметь следующий вид:

Перестановкой столбцов, содержащих одну единицу, данную матрицу можно привести к виду

Использование такого кода позволяет исправить любую одиночную ошибку или обнаружить произвольную ошибку кратности два.

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

где « проверочные разряды; информационные разряды.

В том случае, когда при передаче кодового слова возникает одиночная ошибка, окажутся невыполненными те проверочные соотношения, в которые входит значение ошибочного разряда. Например, если ошибка возникла в пятом информационном разряде, окажутся невыполнимыми первое и четвертое уравнения, т. е. синдром равен 1001 (совпадает с пятым столбцом матрицы Я). Отсюда получаем алгоритмы определения места одиночной ошибки: местоположение столбца матрицы , совпадающего с вычисленным синдромом, указывает место ошибки. Ясно, что вычисленное значение синдрома обязательно совпадает с одним из столбцов матрицы , так как в качестве столбцов выбраны все возможные двоичные -разрядные числа.

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

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

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

Следовательно, и закодированное сообщение имеет вид 1010101. Предположим, что шестой символ принят ошибочно, тогда будет получено сообщение 1010111. Синдром в этом случае имеет вид т. е. двоичное представление числа 6.

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

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

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

Таблица 22 (см. скан)

Проверочная матрица для -кода с может иметь вид

Дополнительное проверочное соотношение, вводимое для увеличения минимального расстояния кода Хэмминга, представим так: Учитывая (3.31), получаем

Система уравнений (3.31) и последнее соотношение для позволяет записать проверочную матрицу для кода (16, 11):

Иногда при практическом использовании кода встречается задача получения укороченного кода с заданным минимальным расстоянием или 4). В этом случае строится проверочная матрица для неукороченного кода с наименьшим значением удовлетворяющим следующим условиям:

Во втором случае число проверочных разрядов кода равно Затем в полученной матрице отбрасываются все лишние столбцы подматрицы

Пример. Построить проверочную матрицу для кода Хэмминга с содержащего информационных разрядов. Наименьшее значение которое удовлетворяет неравенству (3.34), равно 4.

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

Проверочная матрица укороченного кода (15, 10) в этом случае имеет вид

При использовании табл. 21 очень просто определяем, для какого из неукороченных кодов Хэммиига необходимо построить проверочную матрицу, по которой строится проверочная матрица укороченного кода. Например, если необходимо строить проверочную матрицу для кода, с т. е. кода (63, 57), и затем вычеркнуть из подматрицы двадцать семь столбцов.

Весовую характеристику кода Хэмминга удобно находить с помощью функции позволяющей определить число кодовых векторов с различными весами 193].

Для кода с

Для кода с

В формулах (3.35), (3.36) число кодовых векторов веса со равно значению коэффициентов многочлена, стоящих перед

Пример. Пусть задай код Хэмминга о Определить коэффициенты ложных переходов. Для этого кода согласно формуле (3.35) имеем

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

Поэтому втот код обнаруживает все одно-, дву-, пяти-, шестикратные ошибки, 80% трехкратных и четырехкратных.