Коды Хэмминга. Кодами Хэмминга обычно называют групповые кода

Кодами Хэмминга обычно называют групповые кода:

· с кодовым расстоянием, исправляющие одиночные ошибки;

· с кодовым расстоянием, исправляющие одиночные и обнаруживающие тройные ошибки.

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

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

Кроме этого общего требования, для кодов Хэмминга является обязательным, чтобы результат проверок на четность при декодировании искаженного кодового слова указывал также номер разряда, в котором расположен искаженный символ. Этот номер представляется числом, которое образуется при записи результатов 1-ой, 2-ой,... -ой проверок в двоичной системе счисления ().

Обозначим разряды кодового слова кода Хэмминга в виде последовательности,,,...,..., где I, 2, 3,... k..., - натуральные числа, представляющие собой номера разрядов. Следовательно, первая проверка должна охватывать те нечётные символы, при записи номеров которых в двоичной системе счисления обязательно имеется единица в первом разряде двоичного числа, то есть,,,, и так далее;

.

Вторая и последующие проверки строятся следующим образом

,

,

. (1.36)

Проверочные символы располагаются в тех разрядах, которые участвуют только в одной проверке. Такими разрядами являются 1-ый 2, 4, 8, 16 и так далее.

Необходимое число проверочных разрядов в кодовом слове определяется выражением (1.29), которое для кодов Хэмминга () удобнее использовать в виде

ПРИМЕР. Необходимо закодировать кодом Хэмминга ()комбинацию из пяти информационных символов 10011.

Определяем необходимое число проверочных разрядов: 2⁵£ 2ⁿ/ n откуда. Принимаем,.

Проверочные символыы должны занять I, 2, 4 и 8 разряды кода, а информационные 3(1), 5(0), 6(0), 7(1) и 9(1) разряды (в скобках указаны значения символов). Определяем значения проверочных символов согласно уравнениям (1.36):

,

,

,

.

Таким образом, передаваемое кодовое слово кода Хэмминга имеет вид 101100111.

Пусть в канале связи символ, находящийся в 5-ом разряде, был искажен и кодовое слово приняло вид 101110111. В приемнике в процессе декодирования производятся проверки согласно уравнениям (1.36):

,

,

,

.

Записываем результат проверки в виде, что равно десятичному числу 5, которое указывает номер искаженного разряда. Следовательно, в 5-ом разряде необходимо изменить 1 на 0.

После исправления искаженного символа в информационных разрядах получим последовательность символов 10011, которая совпадает с переданной комбинацией информационных символов.

5.Вопросы:

1. Типы дискретного канала.

2. Классификация корректирующих кодов.

3. Коды с чётным числом единиц.

4. Коды с постоянным весом.

5. Инверсный код.

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