Hammingov kód: definícia, princíp opravy chýb a príklady

Princíp a základné vlastnosti

Hammingove kódy sú príkladom lineárnych blokových kódov, ktoré vkladajú do dát niekoľko paritných bitov (redundanciu) podľa pevného pravidla. Paritný bit kontroluje sudosť (alebo nepárnosť) určitej podmnožiny bitov kódového slova. V Hammingovom kóde je každý dátový bit "pokrývaný" viacerými paritnými bitmi tak, aby porušenie jedného bitu spôsobilo jednoznačnú zhodu paritných kontrol — tzv. syndróm — ktorý indikuje polohu chyby.

Vlastnosti, ktoré Hammingov kód typicky poskytuje:

• Minimálna Hammingova vzdialenosť 3 medzi platnými kódy — umožňuje opravu jedného bitu (single-error correction, SEC).
• Detekcia dvoch nesúladiacich bitov (dvojité chyby) je vo väčšine základných verzií čiastočne možná (s určitými obmedzeniami), ale na spoľahlivé zistenie dvojitej chyby sa pridáva rozšírený paritný bit (SECDED — Single Error Correction, Double Error Detection).

Počet paritných a dátových bitov

Ak použijeme k paritných bitov, maximálna dĺžka kódového slova pre klasický (plný) Hammingov kód je 2^k − 1. Počet dátových bitov je teda 2^k − 1 − k. V článku bol uvedený príklad pre k = 3, kedy platí:

2 k - 1 {\displaystyle 2^{k}-1} , pre k ako počet paritných bitov.

Pre k = 3 teda total = 2³ − 1 = 7 bitov a dátových bitov je 7 − 3 = 4, čo sa obvykle zapisuje ako (7,4). Všeobecné kritérium, ktoré musí platiť, je 2^k ≥ n + 1, kde n je celkový počet bitov (dáta + parita).

Umiestnenie paritných bitov a výpočet

Pri bežnej konštrukcii Hammingovho kódu sú paritné bity umiestnené na pozíciách ...1, ...2, ...4, ...8 (t. j. na indexoch, ktoré sú mocninami dvoch: 1, 2, 4, 8, ...). Dátové bity sa vkladajú do ostatných pozícií. Paritné bity potom kontrolujú všetky pozície, ktorých binárne indexy majú príslušný bit nastavený na 1.

Konkrétne pre (7,4) sú pozície nasledovné:

• p1 → pozícia 1 (kontroluje bity 1,3,5,7)
• p2 → pozícia 2 (kontroluje bity 2,3,6,7)
• p4 → pozícia 4 (kontroluje bity 4,5,6,7)
• dátové bity sú na pozíciách 3,5,6,7

Paritný bit sa nastaví tak, aby súčet (mod 2) všetkých bitov v jeho kontrolovanej množine (vrátane paritného bitu) bol 0 pri použitej even-parity (sudá parita). Pri odd-parity sa postup upraví analogicky.

Príklad kódovania a opravy (7,4)

Nech sú dátové bity (v poradí d1,d2,d3,d4) = 1,0,1,1. Umiestnime ich do pozícií 3,5,6,7:

• pozícia 3 = d1 = 1
• pozícia 5 = d2 = 0
• pozícia 6 = d3 = 1
• pozícia 7 = d4 = 1

Vypočítame paritné bity (sudá parita):

• p1 (pozícia 1) kontroluje 1,3,5,7 → p1 ⊕ d1 ⊕ d2 ⊕ d4 = sudá → p1 = parity(d1,d2,d4) = parity(1,0,1) = 0
• p2 (pozícia 2) kontroluje 2,3,6,7 → p2 = parity(d1,d3,d4) = parity(1,1,1) = 1
• p4 (pozícia 4) kontroluje 4,5,6,7 → p4 = parity(d2,d3,d4) = parity(0,1,1) = 0

Výsledné kódové slovo (pozície 1..7) je: 0 1 1 0 0 1 1 (t. j. 0110011).

Ak počas prenosu dôjde k jednému prevrátenému bitu — napr. bit na pozícii 6 sa zmení z 1 na 0 — prijímač spočíta tri paritné kontroly (tzv. syndróm):

• s1 = kontrola množiny pre p1 (pozície 1,3,5,7)
• s2 = kontrola množiny pre p2 (pozície 2,3,6,7)
• s4 = kontrola množiny pre p4 (pozície 4,5,6,7)

Tieto bity sa zložia ako binárne číslo s najnižším významným bitom s1 a najvyšším s4. V uvedenom príklade sa vypočíta syndróm 110 (binárne) = 6, čo jednoznačne ukazuje, že chybný bit je na pozícii 6. Prijímač potom invertuje bit na pozícii 6 a takto sa chyba opraví.

Najmenší Hammingov kód (3,1)

Najkratší možný Hammingov kód je (3,1) — dva paritné bity a jeden dátový bit. Platné kódové slová sú 000 a 111 (pri použití sudých parít). Jednobitové chyby ako 001, 010, 100 sú v poradí najbližšie k 000 a budú korektne opravené na 000; podobne 011, 101, 110 sa opraví na 111.

Rozšírené verzie a praktické použitie

Základný Hammingov kód (napr. (7,4)) opravi jeden bit, ale nemusí spoľahlivo rozlíšiť všetky dvojité chyby. Preto sa často používa rozšírený Hammingov kód s jedným ďalším celočíselným paritným bitom (tzv. SECDED) — ten umožní opraviť jeden bit a zároveň detegovať výskyt dvoch bitových chýb.

Hammingove kódy sa dnes používajú v digitálne spracovanie signálov, v telekomunikáciách, v pamäťových moduloch (niekedy v jednoduchej forme) či v iných aplikáciách, kde je potrebné relatívne lacné a efektívne zabezpečiť opravu jedného bitu chyby.

Zhrnutie

• Hammingov kód pridáva paritné bity podľa pravidla založeného na mocninách dvoch.
• Pre k paritných bitov je maximálna dĺžka kódového slova 2^k − 1 a počet dátových bitov je 2^k − 1 − k.
• Kód má Hammingovu vzdialenosť 3 — opraví jednu chybu a (v rozšírenej verzii) dokáže detegovať dve chyby.