Код на Хеминг: Откриване и коригиране на грешки с примери

Какво е грешка?

Предадените данни могат да бъдат повредени по време на комуникация. Вероятно е да бъде повлиян от външен шум или други физически повреди. В такава ситуация входните данни не могат да бъдат същите като изходните данни. Това несъответствие е известно като „Грешка“.

Грешките в данните могат да доведат до загуба на важни или защитени данни. По-голямата част от трансфера на данни в цифровите системи ще бъде под формата на „битов трансфер“. Дори малка промяна може да повлияе на работата на цялата система. В поредица от данни, ако 1 се промени на 0 или 0 се промени на 1, това се нарича „Битова грешка“.

Видове грешки

Има основно три вида битови грешки, които възникват при предаване на данни от подателя към получателя.

• Единични битови грешки
• Множество битови грешки
• Burst грешки

Единични битови грешки

Промяната, направена в един бит в цялата последователност от данни, е известна като „Грешка с един бит“. Появата на еднобитова грешка обаче не е толкова често срещана. Освен това тази грешка възниква само в паралелна комуникационна система, тъй като данните се прехвърлят побитово в един ред. Следователно има повече шансове една линия да бъде шумна.

Множество битови грешки

В последователност от данни, ако има промяна в два или повече бита от последователност от данни на предавател към приемник, това е известно като „Множество битови грешки“.

Този тип грешки възникват най-вече както в серийни, така и в паралелни мрежи за предаване на данни.

Burst грешки

Промяната на набора от битове в последователността от данни е известна като „Burst error“. Този тип грешка в данните се изчислява от първата битова промяна до последната битова промяна.

Какво е откриване на грешки и коригиране на грешки?

В цифровата комуникационна система грешката ще се прехвърля от една комуникационна система в друга. Ако тези грешки не бъдат открити и коригирани, данните ще бъдат загубени. За ефективна комуникация системните данни трябва да се прехвърлят с висока точност. Това ще стане, като първо идентифицирате грешките и ги коригирате.

Откриването на грешки е метод за откриване на грешки, които присъстват в данните, предавани от предавател към приемник в система за предаване на данни.

Тук можете да използвате кодове за излишък, за да намерите тези грешки, като добавите към данните, когато се предават от източника. Тези кодове се наричат ​​„Кодове за откриване на грешки“.

Три вида кодове за откриване на грешки са:

• Проверка на паритета
• Cyclic Redundancy Check (КРС)
• Продължителна проверка на излишъка (LRC)

Проверка на паритета

• Известен е също като проверка на паритета.
• Има рентабилен механизъм за откриване на грешки.
• При тази техника излишният бит е известен като паритетен бит. Добавя се към всяка единица данни. Общият брой единици в единицата трябва да стане четен, което е известно като паритетен бит.

Надлъжна проверка на излишъка

При тази техника за откриване на грешки блок от битове е организиран в табличен формат. Методът LRC ви помага да изчислите бита за паритет за всяка колона. Комплектът от този паритет също се изпраща заедно с оригиналните данни. Блокът за паритет ви помага да проверите излишъка.

Проверка на цикличността

Cyclic Redundancy Check е поредица от излишни, които трябва да бъдат добавени към края на модула. Ето защо получената единица данни трябва да се дели на второ, предварително определено двоично число.

В дестинацията входящите данни трябва да бъдат разделени на същото число. В случай, че няма остатък, тогава единицата данни се приема за правилна и се приема. В противен случай това показва, че блокът данни е повреден при предаване и следователно трябва да бъде отхвърлен.

В кода на Хеминг източникът кодира съобщението чрез добавяне на излишни битове в съобщението. Тези излишни битове се вмъкват и генерират най-вече на определени позиции в съобщението, за да се извърши процеса на откриване и коригиране на грешки.

История на кода на Хеминг

• Кодът на Hamming е техника, изградена от RWHamming за откриване на грешки.
• Кодът на Хеминг трябва да се прилага към единици данни с всякаква дължина и използва връзката между данните и излишните битове.
• Той работи върху проблема с метода за коригиране на грешки и разработва все по-мощен набор от алгоритми, наречен код на Хеминг.
• През 1950 г. той публикува кода на Хеминг, който днес се използва широко в приложения като ECC памет.

Приложение на кода на Хеминг

Ето някои общи приложения за използване на код на Hamming:

• Сателитите
• Компютърна памет
• модеми
• PlasmaCAM
• Отворени конектори
• Екранираща тел
• Вграден процесор

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

• Методът на кода на Хеминг е ефективен в мрежи, където потоците от данни са дадени за еднобитови грешки.
• Кодът на Hamming не само осигурява откриването на битова грешка, но също така ви помага да отстъпите грешка, съдържаща бит, така че да може да бъде коригирана.
• Лекотата на използване на кодовете на Хеминг ги прави най-подходящи за използване в компютърна памет и корекция на единични грешки.

Недостатъци на кода на Хеминг

• Еднобитов код за откриване и коригиране на грешки. Въпреки това, ако множество битове са основана грешка, тогава резултатът може да доведе до друг бит, който трябва да бъде правилен, за да бъде променен. Това може да доведе до допълнителни грешки в данните.
• Алгоритъмът на кода на Хеминг може да реши проблеми само с единични битове.

Как да кодирате съобщение в Hamming Code

Процесът, използван от подателя за кодиране на съобщението, включва следните три стъпки:

• Изчисляване на общия брой излишни битове.
• Проверка на позицията на излишните битове.
• И накрая, изчисляване на стойностите на тези излишни битове.

Когато горните излишни битове са вградени в съобщението, то се изпраща на потребителя.

Стъпка 1) Изчисляване на общия брой излишни битове.

Да предположим, че съобщението съдържа:

• n– брой битове данни
• p – брой излишни битове, които се добавят към него, така че np да може да посочи поне (n + p + 1) различни състояния.

Тук (n + p) изобразява местоположението на грешка във всяка от (n + p) битови позиции и едно допълнително състояние показва липса на грешка. Тъй като p бита могат да показват 2^p щати, 2^p трябва да е поне равно на (n + p + 1).

Стъпка 2) Поставяне на излишните битове в правилната им позиция.

P излишните битове трябва да бъдат поставени на битови позиции на степени на 2. Например 1, 2, 4, 8, 16 и т.н. Те се наричат ​​p₁ (на позиция 1), стр₂ (на позиция 2), стр₃ (на позиция 4) и т.н.

Стъпка 3) Изчисляване на стойностите на излишния бит.

Излишните битове трябва да бъдат битове за паритет, което прави броя на 1s четен или нечетен.

Двата вида паритет са ?

• Общият брой битове в съобщението е четен, се нарича четен паритет.
• Общият брой битове в съобщението, които са направени нечетни, се нарича нечетен паритет.

Тук целият излишен бит, p1, трябва да се изчисли като паритет. Той трябва да покрива всички битови позиции, чието двоично представяне трябва да включва 1 в 1-ва позиция, с изключение на позицията на p1.

P1 е битът за четност за всеки бит с данни в позиции, чието двоично представяне включва 1 в по-малко важната позиция, без да включва 1 Like (3, 5, 7, 9, ….)

P2 е битът за паритет за всеки бит данни в позиции, чието двоично представяне включва 1 в позиция 2 отдясно, без да включва 2 като (3, 6, 7, 10, 11,…)

P3 е битът за паритет за всеки бит в позиции, чието двоично представяне включва 1 в позиция 3 отдясно, без да включва 4 Като (5-7, 12-15,…)

Дешифриране на съобщение в код на Хеминг

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

Процесът на преизчисляване се извършва в следните стъпки:

• Преброяване на броя на излишните битове.
• Правилно позициониране на всички излишни битове.
• Проверка на паритета

Стъпка 1) Преброяване на броя на излишните битове

Можете да използвате същата формула за кодиране, броят на излишните битове

2^p ? n + p + 1

Тук броят на битовете данни и p е броят на излишните битове.

Стъпка 2) Правилно позициониране на всички излишни битове

Тук p е излишен бит, който се намира на битови позиции на степени на 2, например 1, 2, 4, 8 и т.н.

Стъпка 3) Проверка на паритета

Паритетните битове трябва да се изчислят на базата на битове данни и излишни битове.

p1 = паритет (1, 3, 5, 7, 9, 11…)

p2 = паритет (2, 3, 6, 7, 10, 11…)

p3 = паритет (4-7, 12-15, 20-23…)

Oбобщение

• Предадените данни могат да бъдат повредени по време на комуникация
• Три вида битови грешки са 1) Единични битови грешки 2) Множествени битови грешки 3) Бурст битови грешки
• Промяната, направена в един бит в цялата последователност от данни, е известна като „Грешка с един бит“.
• В последователност от данни, ако има промяна в два или повече бита от последователност от данни на предавател към приемник, това е известно като „Множество битови грешки“.
• Промяната на набора от битове в последователността от данни е известна като „Burst error“.
• Откриването на грешки е метод за откриване на грешки, които присъстват в данните, предавани от предавател към приемник в система за предаване на данни
• Три вида кодове за откриване на грешки са 1) Проверка на паритета 2) Проверка на циклично излишък (CRC) 3) Проверка на надлъжно излишък (LRC)
• Кодът на Hamming е линеен код, който е полезен за откриване на грешки до две непосредствени битови грешки. Способен е на еднобитови грешки.
• Кодът на Hamming е техника, изградена от RWHamming за откриване на грешки.
• Често срещани приложения за използване на код на Hamming са сателитна компютърна памет, модеми, вграден процесор и др.
• Най-голямото предимство на метода на кода на Хеминг е ефективно в мрежи, където потоците от данни се дават за еднобитови грешки.
• Най-големият недостатък на метода на кода на Хеминг е, че може да реши проблеми само с единични битове.
• Можем да извършим процеса на криптиране и декодиране на съобщението с помощта на код на Хеминг.