Самокорректирующийся код

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

Рассмотрим равномерное кодирование, при котором длина каждого кодового слова равна , а алфавит . Будем предполагать, что помехи, во-первых, не меняют длину кодовых слов, во-вторых, в каждом кодовом слове происходит не более ошибок типа замещения, то есть 0 меняется на 1, а 1 меняется на 0.

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

Хэмминг подробно описал код, корректирующий одну ошибку, именно его мы и рассмотрим.

Пусть кодовое слово , где каждое , и – минимальное натуральное число, такое что .

Тогда все числа от 1 до можно закодировать -разрядными двоичными числами, если , то его можно записать

.

В множестве чисел введем подмножества , тогда

,

,

,

.

Эти подмножества пересекаются, но не совпадают, причем среди чисел есть такие, которые попадают ровно в одно подмножество. Такими числами будут степени числа два: и так далее, так как в их двоичном представлении присутствует всего одна 1.

Определение. Кодом Хэмминга длины называется множество слов , удовлетворяющих следующим условиям:

, (9)

где означает сумму по модулю 2.