Построение кода Хэмминга

Построение кода Хэмминга происходит в несколько этапов.

I. Нахождение числа k контрольных разрядов.

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

Первый вариант сообщения на выходе канала связи не содержит искажений, остальные – по одному искажению разряда. Таким образом, число вариантов равно .

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

Содержимое контрольных разрядов – двоичное слово длины k. Для однозначного соответствия этим словам различных вариантов передачи сообщения, очевидно, должно выполняться условие:

(2.6)

Отсюда определяется k как наименьшее целое, удовлетворяющее этому условию . Преобразуем неравенство (2.6). Учитывая, что и подставляя разность в (2.6), получаем

(2.7)

Отсюда при известном значении m можно выбрать как наименьшее целое, удовлетворяющее (2.7), а затем вычислить . Ясно, что при этом должна быть уверенность, что передача кода длины l не вызовет искажения более одного разряда.

II. Выделение из отрезка натуральных чисел k последовательностей.

Пусть V – натуральное число из отрезка и – его двоичная запись, т.е. . Поскольку число изображается в двоичной системе счисления записью 10…0, содержащей 1 только в - м разряде, то отсюда и из условия (1.6) следует, что любое число из отрезка в двоичном представлении имеет не более k разрядов.

1) В первую последовательность включим все натуральные числа V из отрезка , в двоичном представлении которых первый разряд равен 1, т.е. . Этими числами являются

Нижняя строка содержит двоичные числа указанных чисел.

2) Во вторую последовательность включаются все числа V, второй разряд, равный 1, т.е. :

3) В третью последовательность включаются числа с :

………………………………………………………………..

k) B k- последовательности все числа имеют

Первыми членами этих последовательностей являются степени двойки: . Те разряды набора , у которых индекс I является степенью двойки, являются контрольными, остальные – информационными. Контрольных разрядов будет ровно k, информационных .

III. Определение содержимого информационных разрядов.

В информационные разряды (разряды с номерами, не являющимися степенью двойки) записываются последовательно двоичные символы сообщения :

и т. д.

IV. Определение содержимого контрольных разрядов.

Содержимое контрольных разрядов определяется по формулам:

(2.8)

Таким образом, есть сумма по модулю 2 содержимого всех разрядов с номерами, принадлежащим первой последовательности, кроме ее первого члена, есть аналогичная сумма по второй последовательности и т. д.

Все разряды, указанные в правой части равенств являются информационными. Их содержимое определено ранее.

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

В этом случае проверочными соотношениями являются:

(2.9)

Первое равенство в (2.9) получается из первого равенства (2.8), если прибавить по модулю 2 слева и справа элемент , второе — получается из второго равенства в (2.8), если прибавить слева и справа и т. д.

Пример 1. Пусть известно, что l =7.

I.Из (2.6) получим, что k =3, а m = l - k =4. Определим, какой код будет

иметь, например, сообщение .

II.Получим три последовательности:

1, 3, 5, 7 — первая последовательность,

2, 3, 6, 7 — вторая последовательность,

4, 5, 6, 7 — третья последовательность.

III.Заполняем информационные разряды коды (рис.2.16)

Рис.2.16

IV. Определяем содержимое контрольных разрядов согласно (2.8):

– суммирование по первой найденной

последовательности,

– суммирование по второй найденной

последовательности

– суммирование по третьей найденной

последовательности

Заполняя контрольные разряды, получаем код (рис. 2.17).

Рис.2.17

Пример 2. Определим код Хэмминга для слова .

I. С помощью (2.7) подбираем l =9, тогда k =9-5=4. Контрольными разрядами являются в коде, остальные – информационные.

II. Выделенные последовательности имеют вид:

1, 3, 5, 7, 9 – первая последовательность,

2, 3, 6, 7 – вторая последовательность,

4, 5, 6, 7 – третья последовательность,

8,9 – четвертая последовательность.

III. После заполнения информационных разрядов имеем (рис.2.18):

Рис.2.18

IV. Подсчитываем содержимое контрольных разрядов:

После заполнения контрольных разрядов имеем код .

Поиск по сайту: