Hamming-kód (hibajavító blokkkód) — definíció, elv és példák

Ismerje meg a Hamming-kód definícióját, elvét és példáit: hibajavító blokkkódok, paritásbitek, kódszavak (n,k) szemléletes magyarázattal és számítási példákkal.

A Hamming-kód egy egyszeres hibajavításra képes hibajavító blokkkód, amelyet Richard Hamming fejlesztett ki az 1950-es években. Hamming akkoriban olyan gépekkel dolgozott, amelyek relékkel működtek, és lyukkártyákat használtak az adatok tárolására és olvasására. A lyukkártyák gyakori hibái miatt felmerült az igény a hibák automatikus felismerésére és javítására, és ennek eredménye lett a Hamming-kódcsalád.

Alapelvek röviden

A Hamming-kódokat gyakran alkalmazzák a digitális jelfeldolgozásban és a távközlésben. Lényege, hogy az adatbiteket több paritásbit fedi le, így egyetlen bit hibáját képesek felismerni és helyesen kijavítani. A paritásbit megadja, hogy az általa lefedett bitcsoportban páros vagy páratlan-e az 1‑esek száma. Egy adatbitnek több paritásbitje is lehet (átfedés), és az átfedéses struktúra teszi lehetővé a hibapozíció meghatározását.

A Hamming-kódoknál a paritásbitek száma legyen k. Ekkor a k paritásbit által felügyelt kódszó teljes hossza n = 2^k − 1. (A korábbi szövegben szereplő formula megjelenítése megmaradt alább.) Ha kódszónként például három paritásbit van, akkor a kódszónak 7 ( 2 k - 1 {\displaystyle 2^{k}-1} , mert k a paritásbitek száma) hosszúságúnak kell lennie. Így kódszavanként 4 bit felhasználói adat marad a példában. Általában ezt (N,n) alakban írják, ahol az első szám a kódszó teljes hossza, a második pedig a felhasználói adatok bitjeinek száma. A fenti példában (7,4).

Hol helyezkednek el a paritásbitek?

A paritásbitek pozíciói az n hosszú kódszóban a hatványkitevők (1, 2, 4, 8, ...), azaz 2^0, 2^1, 2^2, ... helyeken állnak. A többi pozíciót az adatbitekkel töltjük fel. Például a (7,4) Hamming-kódban a paritásbitek a 1., 2. és 4. pozíciókban vannak; az adatbiteket pedig a 3., 5., 6. és 7. helyeken tároljuk.

Kódolás (példa a (7,4) kódra)

Kódolás lépései (egyszerű, bináris, páros paritással):

• Megadjuk a 4 adatbitet, és elhelyezzük őket a 3., 5., 6., 7. pozíciókba (rendezés tetszőleges, de a dekódolásnál is ugyanazt a rendet használjuk).
• Kiszámoljuk a paritásbit értékét úgy, hogy az adott paritásbit által lefedett pozíciókban az 1-esek száma páros legyen (XOR művelettel összegzés).
• Az így kapott 7 bites kódszó kerül átviteli egységként továbbításra.

Konkrét példa: legyenek az adatbiteink (a 3.,5.,6.,7. pozíciókban) d3=1, d5=0, d6=1, d7=1. A paritásbitek (p1 a 1., p2 a 2., p4 a 4. pozíción):

• p1 (pozíció 1) lefedi a 1,3,5,7 pozíciókat → p1 = d3 ⊕ d5 ⊕ d7 = 1 ⊕ 0 ⊕ 1 = 0
• p2 (pozíció 2) lefedi a 2,3,6,7 pozíciókat → p2 = d3 ⊕ d6 ⊕ d7 = 1 ⊕ 1 ⊕ 1 = 1
• p4 (pozíció 4) lefedi a 4,5,6,7 pozíciókat → p4 = d5 ⊕ d6 ⊕ d7 = 0 ⊕ 1 ⊕ 1 = 0

Így a teljes kódszó (pozíciók 1-től 7-ig): 0 1 1 0 0 1 1 (p1 p2 d3 p4 d5 d6 d7).

Dekódolás és hibajavítás (szindróma számítás)

Átviteli hibák esetén a vevő újraszámolja a paritásokat ugyanazon szabály szerint, és megkap egy úgynevezett szindrómát (egy k-bites értéket). A szindróma megmutatja, hogy melyik pozícióban történt az egyetlen bit hiba (ha van egyetlen bit hiba). A szindróma számítása lényegében a paritásellenőrzés eredményeinek kombinációja (XOR).

Például, ha a 7 bites kódszó egy bitje megváltozik (pl. a 5. pozíció 0→1), a vevő kiszámítja a szindróma biteket s1, s2, s4 ugyanazokból a fedett csoportokból. A kapott három bites szindróma (s4 s2 s1) kettőskettes számként megadja az hibás pozíció számát. Ha a szindróma 000, akkor vagy nincs hiba, vagy páros számú hibák vannak (ez utóbbit a Hamming-kód nem javítja); bármely más érték az egyetlen hibás bit pozícióát adja, amelyet egyszerűen invertálva kijavítunk.

A korábbi példa folytatása: ha a 5. pozíció hibásan 1 lesz, akkor a szindróma s = 101₂ = 5, tehát a hibás bit az 5. pozícióban van — ezt a bitet visszafordítva helyreállítjuk az eredeti kódszót.

Műszaki jellemzők, korlátok és előnyök

• Hamming-kódok jellemzően egyszeres bithibát képesek javítani és kétszeres bithibát felismerni (de nem mindig kijavítani).
• Hatékonyság: a kódrátát általában n−k / n (adatbiteket / teljes kódszót hossz) módon mérjük; a Hamming-kódok alacsonyabb redundanciával adnak egyszeres hibajavítást, mint az egyszerű ismétlőkódok.
• Gyakorlati felhasználás: memóriavezérlőkben (pl. ECC RAM), kommunikációs rendszerekben és beágyazott eszközökben használják, ahol az egyszeres bithibák gyakoriak és fontos a gyors javítás.
• Matematikai formalizmus: a Hamming-kódokat paritásellenőrző (H) és generátor (G) mátrixokkal lehet pontosan leírni; a szindróma kiszámítása egy H • r^T szorzattal történik (minden művelet GF(2)-ben).

Külön megemlítendő: a legrövidebb Hamming-kód

A legrövidebb Hamming-kód az (3,1) kód (két paritásbit és egy adatbit). Ennél a kódnál a paritások kiszámítási módja miatt a lehetséges érvényes kódszavak 000 és 111. Ha az átvitelnél a vevő 001, 010 vagy 100 kódot kap, ezek mind az 000-hez lesznek rendelve (egy bit hiba javítása), míg 011, 101 és 110 a 111-re javulnak.

Összefoglalás

A Hamming-kód egyszerű és hatékony módszer a kis hibaarányú rendszerekben előforduló egybites hibák automatikus javítására. Könnyen megvalósítható logikai műveletekkel (XOR), ezért elterjedt beágyazott rendszerekben és memóriakezelésben. Hátránya, hogy többszörös bithibák esetén nem mindig képes helyes javításra; ilyen esetekre kiterjesztett vagy erősebb hibajavító kódokat alkalmaznak.

Kérdések és válaszok

K: Mi az a Hamming-kód?

K: Hogyan működik a Hamming-kód?

K: Ki találta fel a Hamming-kódot?

K: Mire használta találmányát Richard Hamming?

K: Mit írunk (N,n) alakban, amikor egy Hamming-kódról beszélünk?

Kérdés: Mi a legrövidebb hamming-kód?

Keresés betűvel