Коды Хемминга
Американский ученый Р. Хемминг предложил способ кодирования информации, позволяющий не только обнаруживать, но и исправлять ошибки при передаче одиночного слова любой разрядности. Эти коды – систематические. Пусть разрядность слова равна m. Для контроля информации требуется k дополнительных разрядов. Число k выбирается согласно следующим правилам.
1. Контролирующее число k выбирается так, чтобы оно имело количество комбинаций, достаточное для распознавания одной из m+k позиций или для сигнализации отсутствия ошибки. Полученное таким образом число описывает n=m+k+1 событий. Следовательно, необходимо, чтобы выполнялось неравенство 2k≥(m+n+1).
2. (m+k)-разрядные позиции нумеруются от единицы до (m+k), начиная от младшей значащей. Контрольные разряды k обозначаются P0, P1, P2, …,Pk-1 и помещаются в разряды, имеющие номера 1,2,4,8, …,2k-1 (m+k)-разрядного числа. Остальные m разрядов могут быть размещены в любом порядке между контрольными разрядами.
3. Контрольные разряды P0, P1, P2, …,Pk-1 выбраны таким образом, чтобы для определенных разрядов слова служить в качестве контрольных избыточных разрядов.
| Проверка | Проверяемые разряды | |||||||||||||||
| … | ||||||||||||||||
| … | ||||||||||||||||
| … | ||||||||||||||||
| … | ||||||||||||||||
| … | . | . | . |
P0 выбрано с таким расчетом, чтобы в позициях 1, 3, 5, 7, 9, 11 … число единиц каждого слова было четным, P1 выбрано для того, чтобы выполнялось условие четности в разрядах 2, 3, 6, 7, 10, 11, 14, 15 …, аналогично P2 контролирует позиции 4,5,6,7,12,13,14,15,20… и P3 − для разрядов 8, 9,10,11,12,13, 14,15,24,25… .
На основании рассмотренных правил в табл. 6 показаны семиразрядные коды. Контрольные разряды обозначены P0, P1 и P2 и помещены в позициях 1, 2 и 4.
Операция обнаружения и исправления ошибок выполняется путем нахождения k-разрядного контрольного числа. При этом младший значащий разряд контрольного числа находится посредством проведения контроля на четность над разрядами 1,3,5,7,9… . Если контроль показывает правильность передачи, то пишется нуль, иначе − единица. Следующий разряд контрольного числа
Таблица 6
| Разряды | |||||||||
| Число | |||||||||
| A | B | C | P2 | D | P1 | P0 | |||
определяется путем проверки на четность разрядов 2,3,7,10,11,14,15,… . Остальные разряды контрольного числа находятся аналогично.
Если контрольное число равно нулю, то это означает, что при передаче информации ошибка не произошла. Если же контрольное число не равно нулю, то оно указывает на тот разряд числа, где зафиксирована ошибка, которую необходимо исправить.
Пусть, например, передается число шесть 0110011, а принимается в виде 0110111, то есть произошла ошибка в третьем разряде. Выполняя контроль на четность с помощью разрядов P0, P1 и P2, находим:
Контрольное число
P0 (1, 3, 5, 7) = (1, 1, 1, 0) нечетность 1
P1 (2, 3, 6, 7) = (1, 1, 1, 0) нечетность 1
P2 (4, 5, 6, 7) = (0, 1, 1, 0) четность 0
Полученное контрольное число равно 011, что соответствует ошибке в третьем разряде.
Таким образом, дополнительный разряд Pi выбран так, чтобы проверять четность той совокупности разрядных позиций, чьи контрольные числа содержат единицу в позиции 2i.