Необходимое число дополнительных разрядов для корректирующего кода
|
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
1 |
2 |
3 |
4 |
4 |
5 |
6 |
|
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
Определим теперь позиции, которые надлежит проверить в каждой из проверок. Если ошибок нет, то на всех проверяемых позициях будет 0, если в низшем разряде числа стоит 1, то это значит, что в результате первой проверки обнаружена ошибка.
При первой проверке проверяются те номера позиций, двоичные представления которых имеют в самом правом разряде единицы:
1
1,
3
11,
5
101,
7
111,
9
1001
и т.д.
Таким образом, первая проверка охватывает позиции 1, 3, 5, 7, 9.
Для второй проверки выбирают такие позиции, двоичные представления которых имеют единицу во втором с конца разряде:
2 10, 3 11, 6 110, 7 111, 10 1010.
Аналогично проводим третью проверку в третьем с конца разряде:
4 100, 5 101, 6 110, 7 111, 12 1100, 13 1101.
Такой выбор проверяемых позиций дает возможность определить позиции, в которых произошла одиночная ошибка. Напомним, что при каждой проверке сумма единиц должна быть четной.
Пример 1. Пусть произошла ошибка в одной из позиций первой проверки, тогда в проверочном числе в низшем (правом) разряде появится единица. Дальнейшую расшифровку проверочного числа дает вторая проверка: если среди всех позиций второй проверки ошибок нет, то появится нуль. Если на третьей позиции произошла ошибка, нарушившая четность как в первой, так и во второй проверке, то после двух проверок в двух низших разрядах появятся единицы. В третьей и следующих проверках третья позиция уже отсутствует. Таким образом, в нашем примере проверочное число равно 0011=3, что и дает номер позиции, на которой произошла ошибка. Аналогично можно убедиться, что любая одиночная ошибка на любой позиции может быть устранена проверками, дающими проверочное число, равное номеру позиции, на которой произошла ошибка. Определим теперь, какие позиции следует использовать для проверочных символов. Если выбрать для проверки позиции 1, 2. 4, 8,… , то при каждой проверке будет участвовать хотя бы одна из этих позиций, и это позволит независимо от знаков передаваемого числа получит при каждой проверке четное число единиц. Соответствующие проверяемые разряды, как было показано выше, образуют таблицу 4.5.
Таблица 4.5
Проверяемые разряды
Номер проверки |
Проверяемые разряды |
1 |
1, 3, 5, 7, 9, 11, 13, … |
2 |
2, 3, 6, 7, 10, 11, 14, … |
3 |
4, 5, 6, 7. 12, 13, … |
Пример
2. Построим
код Хемминга для
,
,
.
Для передачи проверочных символов будут
использоваться разряды 1, 2, 4 (эти разряды
выделены заливкой), остальные разряды
будут использоваться для передачи
информации, в них разместим двоичные
коды чисел от 0 до 15. В результате получим
кодовые комбинации, приведенные в
таблице 3.6. Как видно, построенный код
допускает передачу 16 сообщений, при
этом
комбинаций не используются.
Пример 3. Проиллюстрируем работу построенного кода. Рассмотрим комбинацию 0110011, которая соответствует числу 11 в таблице 4.6. Допустим, сто при передаче произошла ошибка, и символ в пятой позиции сменился на противоположный. Получилась комбинация 0110111. Определим ошибку по изложенной выше методике.
Первая проверка (сумма разрядов 1, 3, 5, 7 нечетная) дает 1.
Вторая проверка (сумма разрядов 2, 3, 6, 7 четная) дает 0
Третья проверка (сумма разрядов 4, 5, 6, 7 нечетная) дает 1
В итоге получаем проверочное число (101)2 = 5. Следовательно, на пятой позиции произошла ошибка, и знак в этой позиции необходимо заменить на обратный (1 на 0). В результате восстановится правильная комбинация 0110011.
Корректирующую
способность кода можно повышать и
дальше: строить коды для обнаружения
-
кратной и исправления
-
кратной ошибок. Конечно, при этом будет
расти количество дополнительных знаков
и общая длина кодовой комбинации при
неизменном размере полезного кода. Эти
вопросы рассматриваются в теории
помехоустойчивого кодирования [9, 10].
Таблица 4.6
Код Хэмминга для передачи 4-х разрядных двоичных слов
с обнаружением и исправлением одиночной ошибки
Разряды передаваемого кода |
Десятичное представление передаваемого сообщения |
||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
2 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
3 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
4 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
5 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
6 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
7 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
8 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
9 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
10 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
11 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
12 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
13 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
14 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
15 |