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

Первые коды были изобретены Ричардом Хэммингом (1950 г.). Они предназначены для исправления одиночных ошибок в кодовых словах. Следовательно, для этих кодов разреженность d^∗ ≥ 3.Если H — проверочная матрица кода K c d^∗ ≥ 3, то любые два столбца в H линейно независимы, т. е. они ненулевые и не пропорциональны. При q = 2 пропорциональность столбцов с элементами из F_q означает просто их совпадение, и, следовательно,

- 10 -

H должна состоять из некоторого множества различных ненулевых столбцов.

Заметим, что для любого m ∈ N существует точно 2^m − 1 ненулевых столбцов длины m над F₂.

Определение 1. Бинарным кодом Хэмминга называется линейный код K над F₂, проверочная матрица которого при некотором натуральном m ≥ 2 состоит из всех 2^m − 1 ненулевых столбцов длины m.

Таким образом, бинарный код Хэмминга имеет параметры: n = 2^m−1, k = n−m = 2^m−m−1. Число m = n − k называется числом проверочных символов кода.

Теорема 1. Пусть K — бинарный код Хэмминга с m проверочными символами (в частности, K ⊆ V (2^m −1, F₂)). Тогда его разреженность d^∗ = 3 и шары радиуса 1 с центрами в кодовых словах попарно не пересекаются и покрывают все пространство V (2^m − 1, F₂).

Доказательство.Пусть H — проверочная матрица кода K. Ее размеры: m × n, где n =2^m − 1. Любые два столбца в ней линейно независимы по определению кода, но следующие три столбца в H, очевидно, линейно зависимы:

1 0 1

0 1 1

0 0 0

. , . , .

. . .

. . .

0 0 0

Они всегда есть, так как m ≥ 2. Следовательно, d^∗ = 3 и шары радиуса 1 с центрами в кодовых словах не пересекаются. Число таких шаров равно |K|=2^n−m, а число слов в каждом шаре равно 1+n = 2^m. В объединении всех шаров содержится, следовательно, 2^n−m2^m = 2ⁿ слов, а это есть число всех слов пространства V (n, F₂) = V (2^m − 1, F₂).

Определение 2. Кодом Хэмминга над F_q называют линейный код над F_q, проверочная матрица которого для некоторого натурального числа m ≥ 2 состоит из максимально возможного числа попарно не пропорциональных столбцов длины m.

- 11 -

Заключение.

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

- 12 -

Список литературы.

Учебное пособие «Теория кодирования» В.А. Белоногов.

dic.academic.ru

- 13 -