Код на Хамминг: дефиниция и принцип на корекция на грешки

Научете всичко за кодовете на Хамминг: дефиниция, принцип на откриване и корекция на грешки, примери (7,4) и практическо приложение в телекомуникациите.

Кодът на Хаминг е блоков код за коригиране на грешки. Кодът е кръстен на Ричард Хаминг, който го разработва през 50-те години на миналия век. По онова време Хаминг работи с машини, които имат релета и използват перфокарти за четене на данните. Тъй като са били много използвани, перфокартите често са имали грешки, които е трябвало да бъдат коригирани от служителите.

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

Хаминг кодът използва излишък. При k бита за четност общата дължина на кодовата дума при класическия (пълнофункционален) Хаминг е 2^k − 1. Това е записано като:

2 k - 1 {\displaystyle 2^{k}-1}

Например, ако има три бита за четност (k = 3), кодовата дума има дължина 7, което оставя 4 бита потребителски данни — това е добре познатият (7,4) Хаминг код. Общата нотация за код е (N,n), където N е общата дължина на кодовата дума, а n е броят на битовете полезни данни; примерът по-горе е (7,4).

Разположение на битовете за четност и данните

В класическия (7,4) Хаминг код позициите на битовете са номерирани от 1 до 7. Битовете на позиции, които са степени на 2 (1, 2, 4, ...), се отделят за четност (първични битове за проверка). Останалите позиции съдържат битовете данни.

• Позиция 1 (p1) — проверява позиции 1,3,5,7,...
• Позиция 2 (p2) — проверява позиции 2,3,6,7,...
• Позиция 4 (p4) — проверява позиции 4,5,6,7,...

Така всеки бит данни попада под контрола на комбинация от битове за четност, което позволява при получаване на кодова дума да се установи коя конкретна позиция (ако има такава) е повредена.

Кодиране — пример за (7,4)

Да разгледаме конкретен пример. Нека данните да са 4 бита d1..d4 = 1,0,1,1. Те се разполагат на позиции 3,5,6,7:

• позиция 1: p1
• позиция 2: p2
• позиция 3: d1 = 1
• позиция 4: p4
• позиция 5: d2 = 0
• позиция 6: d3 = 1
• позиция 7: d4 = 1

Ако използваме четна паритетна проверка, стойностите на битовете за четност се изчисляват така, че сумата (по модул 2) на покритите бита да бъде 0 (четен брой единици):

• p1 = d1 ⊕ d2 ⊕ d4 = 1 ⊕ 0 ⊕ 1 = 0
• p2 = d1 ⊕ d3 ⊕ d4 = 1 ⊕ 1 ⊕ 1 = 1
• p4 = d2 ⊕ d3 ⊕ d4 = 0 ⊕ 1 ⊕ 1 = 0

Кодовата дума става: 0 1 1 0 0 1 1 (поредността: p1 p2 d1 p4 d2 d3 d4).

Декодиране и корекция на грешки (синдром)

При получаване на кодова дума декодерът пресмята отново същите паритети и сравнява с получените parитет-битове. Разликата се представя чрез синдром (битов вектор), който указва позицията на грешката (ако има единична грешка). Синдромът се образува от битовете s1, s2, s4 (проверки за p1, p2, p4). Ако синдромът е нулев (000), няма открита грешка; ако е различен от нула, неговата стойност (като двоично число s4 s2 s1) дава индекса на позицията с грешка.

Пример: ако при предаването битът на позиция 5 (d2) се обърне от 0 на 1, получената дума ще бъде 0 1 1 0 1 1 1. При проверка:

• s1 = r1 ⊕ r3 ⊕ r5 ⊕ r7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1
• s2 = r2 ⊕ r3 ⊕ r6 ⊕ r7 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0
• s4 = r4 ⊕ r5 ⊕ r6 ⊕ r7 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1

Синдромът s4 s2 s1 = 1 0 1 (двоично) = 5 → грешката е на позиция 5. Декодерът обръща бита на тази позиция и възстановява оригиналните данни.

Възможности и ограничения

• Корекция: Класическият Хаминг код има минимално Хаминг разстояние 3 и може да коригира всяка единична битова грешка (Single Error Correction, SEC).
• Откриване: Без допълнителен общ паритет кодът може да открие, но не винаги да разпознае двойни грешки. За да се добави възможност за откриване на двойни грешки, се използва разширен Хаминг код (SECDED) — Single Error Correction, Double Error Detection — чрез добавяне на един общ паритетен бит.
• Ефективност: Хаминг кодовете са икономични при ниска честота на грешки и са лесни за хардуерна реализация. При по-висока грешност се използват по-сложни кодове (Reed–Solomon, LDPC и др.).
• Общо правило: за да се поддържат m битове данни с k бита за четност, трябва да се изпълнява условието 2^k ≥ m + k + 1 (за да бъдат различими всички възможни позиции на евентуална грешка и случаят без грешка).

Приложения

Кодовете на Хаминг се използват в памети с достъп на произволни позиции (RAM), при предаване на контролни данни в комуникационни канали, в сателитни и други вградени системи, където еднократните грешки са по-чести от множество едновременни грешки. Комбинацията от простота и ефективност ги прави удобни за реализация както в хардуер, така и в софтуер.

Кратко обобщение: Хаминг кодовете осигуряват лесен и бърз начин за откриване и корекция на единични битови грешки чрез добавяне на няколко бита за четност, поставени на позиции степен на две. Разширеният вариант (SECDED) добавя допълнителен бит за откриване на двоични грешки.

Въпроси и отговори

В: Какво представлява кодът на Хаминг?

В: Как работи кодът на Хамминг?

Въпрос: Кой е изобретил кода на Хаминг?

В: За какво е използвал Ричард Хаминг своето изобретение?

Въпрос: Какво се записва като (N,n), когато говорим за код на Хаминг?

Въпрос: Кой е най-краткият възможен код на Хаминг?

Търсене по буква