41. Самокорректирующиеся коды (коды Хэмминга), метод построения.

Кодом исходного сообщения может быть любое m-разрядное словов алфавите {0,1}. Множество всех таких слов образуетm-разрядный линейный код мощности 2^m. В реальных системах при передаче информации по каналам связи в силу разных причин может происходить искажение сигналов. В результате отдельные разряды передаваемых кодовых слов могут измениться, т.е. ноль может превратиться в единицу, а единица – в ноль. Если искажению подвергся только один разряд передаваемого слова (называется одиночной ошибкой).

В коде Хэмминга используется несколько контрольных разрядов, каждый из них заполняется таким образом, чтобы анализ их содержимого в случае одиночной ошибки позволил точно определить, в каком именно разряде произошло искажение.

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

Также имеет место формула: , гдеm– длина кодового слова,k– число контрольных разрядов.

Для удобства будем нумеровать контрольные разряды в кодовом слове слева направо степенями двойки, т.е. числами 1,2,4,8,…, 2^k−1. Остальные позиции содержат информационные разряды. На рисунке изображено кодовое слово с 6 информационными и 4 контрольными разрядами. Все разряды пронумерованы числами от 1 до 10, а контрольные разряды выделены темным цветом.

1

2

3

4

5

6

7

8

9

10

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

Эту последовательность множеств можно продолжать бесконечно, используя следующую закономерность. Во-первых, номера множеств V_i– это степени двойки. Во-вторых, минимальное число во множествеV_iравноi. В-третьих, множествоV_iсодержит те, и только те натуральные числа, в разложении которых по различным степеням двойки 1,2,4,8,…,i,…, 2^k─1слагаемоеiвходит с коэффициентом 1.

При заполнении контрольных разрядов кодового словаиспользуются следующие равенства:,,и т.д.

Код Хэмминга позволяет проверять правильность передачи кодовых слов по каналу связи и в случае возникновения одиночной ошибки точно определять её местоположение. Для этого используются так называемые контрольные суммы. У кода Хэмминга с kконтрольными разрядами имеется ровноkконтрольных сумм. Обозначим их черезS_i, где номерiявляется степенью двойки, т.е. принимает значения 1, 2, 4, 8,…, 2^k─1. При вычислении каждой контрольной суммы складывается содержимое одного из контрольных и нескольких информационных разрядов, а именно:,,и т.д.

Указанное правило вычисления контрольных сумм гарантирует, что при передаче кодового слова без искажений все контрольные суммы будут равны нулю. Если же во время передачи кодового слова случится одиночная ошибка, то номер искаженного разряда можно будет легко определить с помощью контрольных сумм. Для этого достаточно вычислить все контрольные суммы (т.е. проверить их на четность) и сложить номера контрольных сумм, отличных от нуля.

Пример 1. Исходные словаимеют длину 5. Требуется выяснить, какую длину будут иметь кодовые слова кода Хэмминга.

По условию задачи m= 5. Поэтому определим число контрольных разрядовkиз неравенства (52), переписав его в следующем виде:. Последовательно подставляя вместоkчисла 1,2,3 и т.д., выясняем, что наименьшее допустимое значениеkравно 4. Значит, кодовые слова кода Хэмминга в данном случае имеют длинуn = m + k= 9.

Пример 2. Требуется построить кодовое слово кода Хэмминга, соответствующее исходному слову.

0

0

1

0

1

1

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

Теперь в соответствии с указанным выше правилом заполним контрольные разряды:

, ,,.

В итоге получаем искомое кодовое слово .

Пример 3. На выходе канала связи получили кодовое слово кода Хэмминга. Требуется выяснить, какое словобыло отправлено.

Найдем контрольные суммы. Их будет столько же, сколько и контрольных разрядов, т.е. четыре. Получим

, ,,.

Отличными от нуля оказались контрольные суммы S₂иS₄. Складывая их номера, узнаём, что одиночная ошибка произошла в шестом разряде слова. Исправив в этом разряде единицу на ноль, получим отправленное слово.