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

 

Рассмотрим двоичный линейный код, сконструированный следующим образом. Выпишем все различные ненулевые –разрядные двоичные числа ( –компонентные вектора) и используем полученные вектора в качестве столбцов проверочной матрицы, располагая их в порядке возрастания. Построенная таким образом матрица имеет размерность . Принимая во внимание, что число столбцов проверочной матрицы определяет длину кода , а число строк – количество проверочных символов , то число информационных символов в кодовом слове будет . Таким образом, с помощью подобной проверочной матрицы будет сконструирован линейный код. Кроме того, поскольку все столбцы проверочной матрицы различны, то любая пара столбцов матрицы линейно независима, тогда как каждый из столбцов всегда может быть представлен в виде линейной комбинации двух других. Следовательно, на основании теоремы 6.4.1 можно утверждать, что кодовое расстояние построенного кода , и он может исправить любую однократную ошибку.

Линейные коды, обладающие параметрами

, (6.9)

называются кодами Хэмминга.

На основании предшествующего рассмотрения можно сформулировать следующую теорему:

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

Пример 6.6.1. Пусть , тогда существует (7,4) код Хэмминга, столбцами проверочной матрицы которого являются числа от 1 до 7, записанные в двоичной форме 3–х компонентными векторами:

.

В том случае, когда существует необходимость построения кода Хэмминга в систематической форме, единственное, что необходимо сделать – это определенным образом упорядочить столбцы исходной проверочной матрицы, выделив в явном виде единичную матрицу, как составную часть проверочной. Из полученной таким способом матрицы легко построить и каноническую порождающую матрицу. Иллюстрацией описанного алгоритма могут служить матрицы и , представленные ниже, основой для получения которых послужила матрица (7,4) кода Хэмминга.

Значения параметров первых двоичных кодов Хэмминга, определяемые соотношениями (6.9), представлены в таблице 6.4.

Таблица 6.4.

n						∙∙∙
k						∙∙∙
n-k						∙∙∙
R=k/n	4/7	11/15	26/31	57/63	120/127	∙∙∙

 

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

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

.