Какво трябва да знаем:    
Двоична аритметика   Бройни системи  

Научнопопулярно списание "Аз - Ижица"
Алгоритми

Код на Хеминг – описание и примери

Ричард Уесли Хеминг (1915 –1998) започва изследователската си кариера в лабораторията на Бел, където открива коригиращия грешките код, носещ неговото име.
Фотографията е заимствана от http://cm.bell-labs.com/cm/cs/alumni/hamming/index.html

Хеминг с котката

Трябва да изпратим съобщение, състоящо се от последователност от четири нули или единици. Предполагаме, че при изпращането на съобщение с дължина 20 или по-малко нули и единици е възможно на едно единствено място да се получи грешка. Нулата да бъде заменена с единица и обратно. Изключваме възможността за две и повече грешки.
Въпросът е: Можем ли да допълним четери-символното съобщение с допълнителна информация , която да покаже има ли грешка и ако има – да я поправи.”
Един от възможните начини за решение е да изпратим съобщението с дължина 4 три пъти.

Информативна част на съощението

Изпратено кодирано съобщение

Полученото съобщение е с дължина 12 и в него е възможна една грешка. Да предположим, че тя е в в девета позиция.


Как да я поправим? Разделяме съобщението на три части и ги подреждаме една под друга.


Ако в една позиция има 3 еднакви символа считаме че при нея няма грешка. Ако два от символите съвпадат а третия се различава,както е в първа позиция, то при нея е допусната грешка при предаването. За правилен приемаме символът който се среща два пъти – в случая нула.
Но въпросът, който е решил Хеминг е каква е минималната дължина на съобщението, което трябва да изпратим за да се открият и коригират грешките при условие, че информативната част на съощението е с дължина 4?
Постъпва се така: Докато информативната част на съобщението е с дължина 4, изпратеното съобщение е с дължина 7.
Позициите с номера, които не са степени на две (3, 5, 6 , 7) са за самото съобщение а позициите с номера степените на двойката (1, 2 , 4) са служебни.
Да попълним позициите за съобщението а служебните да оставим свободни:


Построява се матрица,


представляваща числата от 1 до 7 в двоична бройна система. Това са трибуквени думи от азбуката {0,1} , подредени лексикографски (както в речника). Номерата на редовете са отдясно. Редът с номер 1 е равен на сумата от трите реда с номера 3 , 5 и 7 , което ще означаваме така:
[1]=[3]+[5]+[7], защото (001)= (011)+ (101)+ (111).

Тук се има предвид двоичната аритметика, при която 0+0=0 0+1=1+0=1 и 1+1=1

По подобен начин се установяват равенствата
[2]=[3]+[6]+[7]
[4]=[5]+[6]+[7]
Да проверим:
[1]=[3]+[5]+[7] ⇔ (001)= (011)+ (101)+ (111)
[2]=[3]+[6]+[7] ⇔ (010)= (011)+ (110)+ (111)
[4]=[5]+[6]+[7] ⇔ (100)= (101)+ (110)+ (111)
Сега служебната позиция с номер 1 , по подобие на равенството [1]=[3]+[5]+[7] се попълва със сумата от числата, стоящи на позиции 3 , 5 и 7:


0+1+1=0


Позицията с номер 2 , по подобие на равенството [2]=[3]+[6]+[7] се попълва със сумата от числата, стоящи на позиции 3 , 6 и 7: 0+1+1=0


Позицията с номер 4 , по подобие на равенството [4]=[5]+[6]+[7] да попълним със сумата от числата, стоящи на позиции 5 , 6 и 7: 1+1+1=1


Това е кодираното съобщение. Изпращаме го.
При получаването му извършваме проверка по правилата
[1]=[3]+[5]+[7]         [2]=[3]+[6]+[7]         [4]=[5]+[6]+[7]
за контролните позиции и ако и трите равенства са изпълнени кодираното съобщение е прието вярно.
Но интересното е че ако не е така можем да намерим позицията в която има грешка.
Да предположим, че сме получили съобщението
Извършваме проверка на контролните позиции по познатото правило.
Намираме сумата на съдържанията на получените контролни позиции и изчислените по правилата на двоичната аритметика.
Обръщаме получените цифри( в случая ще се получи същото) – 101 и това е номерът на сгрешената позиция в двоична бройна система.
101(2) = 5(10) .
Сбърканата позиция е с номер 5 и информативното съобщение не е 0011 а 0111.
Още един пример

Получено съобщение и изчислени контролни суми


Сума от съдържанията на контролните позиции

Обърнатото число е 110 а това е 6 в десетична бройна система.
Там е грешката и информативното съобщение е 0111.
Това е направил Ричард Уесли Хеминг!