Hamming-kood: veakorrigeeriv plokk-kood — definitsioon ja näited

Hamming-kood on veakorrigeeriv plokk-kood. Kood on saanud oma nime Richard Hammingi järgi, kes töötas selle välja 1950. aastatel. Tollal kasutas Hamming masinate vigade parandamiseks augukaarte ja nende tükelduste töötlemiseks releed, mistõttu tekkis vajadus automaatse vea tuvastamise ja parandamise järele.

Hammingi koodid on laialdaselt kasutusel nii digitaalses signaalitöötluses kui ka telekommunikatsioonis ja mujal, kus oluline on andmete usaldusväärsus. Hamming-koodid genereeritakse kindlate reeglite järgi: need lisavad andmesõnale mitmeid pariteedibitte. Pariteedibitt näitab, kas teatud bittide rühm sisaldab paarisarvulist või paarituarvulist ühete arvu. Iga andmebitt Hamming-koodis on "kaetud" mitme pariteedibitiga, mis võimaldab tuvastada ja enamasti ka parandada ühe-bitilisi vead (üksikisikute bittide süstemaatiline pööramine). Hamming-koodid kasutavad sisemist redundantsi, st andmete külge lisatakse lisabitte.

Hammingi koodi parameetreid tähistatakse tavaliselt paariga (N, n), kus N on koodisõna kogupikkus (andmebittide + pariteedibittide arv) ja n on kasutajaandmete bittide arv. Kui pariteedibittide arv on k, siis täiskoodi pikkus, mida nimetatakse täiuslikuks Hammingi koodiks, on 2 k - 1 {\displaystyle 2^{k}-1} (sest k on pariteedibittide arv). Sel juhul jääb andmebittide arvuks n = 2^k - 1 - k. Näiteks k = 3 korral on N = 7 ja n = 4, seega (7,4)-kood.

Kuidas Hamming-kood töötab

Kõige levinum lihtne versioon on Hamming(7,4), mis kasutab kolme pariteedibitti (positsioonidel 1, 2 ja 4) ning neli andmebitti (positsioonidel 3, 5, 6 ja 7). Pariteedibitide positsioonid valitakse tavaliselt kui kaks astet (1, 2, 4, 8 jne), sest iga pariteedibitt kontrollib neid koodi positsioone, mille positsiooni binaarkujutisel on vastavas kohal 1. Täpsemalt:

• Pariteedibitt p1 kontrollib positsioone 1, 3, 5, 7, ... (binaari LSB = 1).
• Pariteedibitt p2 kontrollib positsioone 2, 3, 6, 7, ... (järgmine binaarkoht = 1).
• Pariteedibitt p4 kontrollib positsioone 4, 5, 6, 7, ... (järgmisel binaarkohal = 1).

Pariteedid arvutatakse tavaliselt nii, et iga kontrollgrupi bittide summa oleks kas paaris (even parity) või paaritu (odd parity). Kui iga pariteedigrupi pariteet on paika pandud, siis satuvad iga võimalikud ühebittilised vead unikaalsele vektorile (nn. sündroomile), mis osutab vigasele positsioonile. Kui kõik pariteedid on õiged, on sündroom null ja viga ei ilmne.

Näide: Hamming(7,4) kodeerimine ja vea parandamine

Kodeerime andmebitsid d1 d2 d3 d4 = 1 0 1 1, paigutades need positsioonidele 3, 5, 6 ja 7 vastavalt tavamärgistusele. Algne paigutus (positsioonid 1..7) enne pariteedibittide arvutamist on:

• 1: p1 (pariteet)
• 2: p2 (pariteet)
• 3: d1 = 1
• 4: p4 (pariteet)
• 5: d2 = 0
• 6: d3 = 1
• 7: d4 = 1

Arvutame pariteedid (kasutame siin paarispariteeti):

• p1 kontrollib positsioone 1,3,5,7 → p1 + 1 + 0 + 1 peab olema paaris ⇒ teadaolevate bittide summa = 2 (paaris) ⇒ p1 = 0.
• p2 kontrollib positsioone 2,3,6,7 → p2 + 1 + 1 + 1 peab olema paaris ⇒ teadaolevate bittide summa = 3 (paaritu) ⇒ p2 = 1.
• p4 kontrollib positsioone 4,5,6,7 → p4 + 0 + 1 + 1 peab olema paaris ⇒ teadaolevate bittide summa = 2 (paaris) ⇒ p4 = 0.

Saame koodisõna: 0 1 1 0 0 1 1 ehk 0110011.

Kui ülekanne tekitab ühe-bitilise vea, näiteks bitis positsioonil 6 muutub 1 → 0, siis vastuvõtja saab sõna 0 1 1 0 0 0 1. Kontrollides pariteete üle saadakse sündroomi bittide kombinatsioon:

• s1 = pariteet(1,3,5,7) = 0
• s2 = pariteet(2,3,6,7) = 1
• s4 = pariteet(4,5,6,7) = 1

Nende sündroomibittide binaarkodeering (s4 s2 s1) = 110₂ = 6 näitab, et viga on positsioonil 6. Selle positsiooni bit pööratakse tagasi ja andmed on taastatud.

Omadused, piirangud ja laiendused

• Hamming-koodid on võimelised parandama ühte bitiviga ja tuvastama enamasti ka ühe bitiviga. Neid iseloomustab minimaalse Hamming'i kaugusena 3.
• Hammingi klassikaline konstruktsioon annab "täiusliku" koodiperekonna, kus N = 2^k - 1 ja n = 2^k - 1 - k. See tähendab, et kõik võimalikud sündroomid (sh nullsündroom) kaardistavad kas vea positsiooni või vea puudumise.
• Kui lisada ülejäänud pariteedibitt (näiteks kogu koodisõna paarispariteet), tekib laiendatud Hamming-kood (näiteks (8,4)). See suudab ühtlasi tuvastada kahe-bitilisi vigu (kuid neid ei paranda). Selline lisapariteet võimaldab eristada olukorda "kahe-bitiline viga" ja "üks-bitiline viga".
• Hammingi kood ei paranda rohkem kui ühte üksikbitti (välja arvatud keerukamad mitmetasandilised skeemid või lisapariteedid). Kui mitme-bitiline viga tekib, võib sündroom anda eksitava positsiooni ning vale paranduse viia väljaveale.

Praktilistes süsteemides kombineeritakse Hamming-kood sageli teiste veakontrolli ja korrigeerimise tehnikatega (nt krüpteeritud kanali koodid, korrigeerivad plokid või järjepidevuse kontrollid), et saavutada suurem veakindlus ja tuvastatavus. Hamming-kood on tänini enimkasutatav elementaarne skeem tänu oma lihtsusele ja tõhususele väikse arvutus- ja salvestuskulu juures.

Lühim võimalik Hammingi kood on (3,1) — ühe andmebiti kohta kasutatakse 2 pariteedibitti. Sellel koodil on kaks kehtivat "täissõna" 000 ja 111. Kui ülekandes tekivad vead, näiteks saadud sõnad 001, 010 või 100, neid tõlgendatakse lähemal olevana kehvale koodisõnale 000, ja sõnad 011, 101 või 110 vastavad koodile 111. See illustreerib lihtsustatult ideed, et iga võimalik vealine sõna kaardistub lähimale kehtivale koodisõnale.

Küsimused ja vastused

K: Mis on Hammingi koodeks?

K: Kuidas Hammingi kood töötab?

K: Kes leiutas Hammingi koodi?

K: Milleks kasutas Richard Hamming oma leiutist?

K: Mida kirjutatakse (N,n), kui räägitakse Hamming-koodist?

Küsimus: Milline on lühim võimalik hamming-kood?

Otsing