Hammingi kood: vigase biti asukoht näitab, mida parandada

Määra neli andmebitti ja muuda kanalis soovitud bitte, kasutades nuppe või klõpsates joonisel. Dekooder teeb kolm paarsuskontrolli uuesti, loeb ebaõnnestunud kontrollid kahendarvuks ja muudab vastava biti tagasi. Vaata protsess üks kord sammhaaval läbi, seejärel proovi kahte viga.

Näidisarvutus — Hammingi kood: vigase biti asukoht näitab, mida parandada

Saadetud: kontrollbitid	0110011
Vastu võetud	0110111
Sündroom	1012
Väljastatud andmed	1011
Koodikiirus, andmebitte saadetud biti kohta	57,1%

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Hammingi kood: vigase biti asukoht näitab, mida parandada

Hammingi kood lisab andmetele kontrollbitid, et ühe muutunud biti saaks üles leida ja tagasi muuta. Iga kontrollbitt tagab, et valitud asukohtades on paarisarv ühtesid; seda nimetatakse paarsuskontrolliks. Dekooder kordab saabunud sõna kontrolle. Ebaõnnestunud kontrollide muster ehk sündroom annab kahendarvuna vigase biti asukoha, kus 0 tähendab, et viga pole. Kontrollnumber saab üksnes näidata, et midagi on valesti; Hammingi kood näitab ka vea asukohta. Laiendatud kood lisab biti, mis muudab kogu sõna paariseks. See parandab iga üksiku vea ning tuvastab kaks viga neid parandamata: SECDED.

Mida iga sümbol tähendab

dᵢ: neli andmebitti asukohtades 3, 5, 6 ja 7
p₁, p₂, p₄: kontrollbitid, igaüks oma indeksiga tähistatud asukohas; p₀ on laiendatud koodi üldine paarsusbitt
s: sündroom 4s₄ + 2s₂ + s₁, kus s_k on 1, kui ringis k on saabumisel paaritu arv ühtesid
P: laiendatud koodi kõigi kaheksa vastuvõetud biti paarsus: 1 tähendab paaritut arvu vigu
p: bitiveamäär ehk tõenäosus, et üks bitt muutub, sõltumatult kõigist teistest

Eeldab: Iga bitt muutub teistest sõltumatult ja sama tõenäosusega p. Tegelikes kanalites ja mäludes esineb ka purskevigu, mille korral muutuvad korraga mitu kõrvutist bitti. Selline purse ongi mitme biti viga, millega need koodid kõige halvemini toime tulevad.
Ei kehti, kui: Kolme vea korral. Laiendatud kood peab kolme viga üheks, sest üldine paarsuskontroll on paaritu, ning muudab seni õiget bitti. Kõigi vigade tabel näitab, et kõik 896 kolme veaga juhtu väljastavad valed andmed ilma märguandeta.

Paarituks muutunud ringide summa näitab vigase biti asukohta 🖖

Vajuta Üks viga. Kanalis muutub bitt 5. Ringides 1 ja 4 on nüüd paaritu arv ühtesid, ring 2 jääb paariseks: 1 + 4 = 5. Tulemus ei sõltu sobivalt valitud näitest. Ring k kontrollib täpselt neid asukohti, mille kahendkujus on k-le vastav järk 1. Seetõttu muudab asukohas i olev vigane bitt paarituks just need ringid, mille summa on i. Biti koht joonisel on ühtlasi selle aadress. Hamming otsis 1950. aastal „kontrollarvu”, mis annaks iga üksiku vea asukoha ja mille nullväärtus tähendaks vea puudumist. Kolm kontrolli annavad kaheksa võimalikku tulemust. Seitsmebitisel sõnal on vaja täpselt kaheksat: seitse asukohta ja „viga pole”. Ühtki tulemust ei jää üle. Kõigist 128 seitsmebitisest sõnast on 16 koodisõnad; ülejäänud 112 erinevad täpselt ühest koodisõnast ühe biti võrra. Diagrammi all olev tabel dekodeerib kõik 112 õigesti. Kontrollbittide paiknemine asukohtades 1, 2 ja 4 on lihtsa põhjusega. Nende arvude kahendkujus on ainult üks 1, mistõttu kuulub iga kontrollbitt vaid ühte ringi ja selle väärtuse saab määrata vastava kontrolli järgi. Just nii põhjendas valikut ka Hamming.

Kahe vea korral rikub dekooder veel kolmandagi biti 🖖

Vajuta Kaks viga. Bitid 3 ja 5 muutuvad. Ring 1 sisaldab mõlemat, saab kaks korda mõjutatud ja jääb paariseks; ringid 2 ja 4 muutuvad paarituks. Sündroom on 6, täiesti kehtiv asukoht. Dekooder muudab seni õiget bitti 6. Saabumisel olid valed kaks andmebitti, pärast parandamist on valed kolm. Ruudustik näitab sama iga paari kohta: kõik 21 paari ja seega kõik 336 kahe veaga juhtu 16 andmesõna seas väljastavad valed andmed ilma märguandeta. Vajuta Ainult kontrollbitid. Asukohad 1 ja 2 ei kanna andmeid, nii et andmed saabusid tervena, kuid sündroom 3 käsib dekoodril rikkuda biti d₁. Seejärel vajuta Laiendatud, kaks viga. Kaheksas bitt teeb kõigi kaheksa biti kogumi paariseks. Üks viga muudab üldise paarsuskontrolli alati paarituks, kaks viga jätavad selle paariseks. Kui dekooder näeb mittenullist sündroomi kõrval paarist üldkontrolli, märgistab ta sõna ega muuda midagi. Nii juhtub kõigi 448 kahe veaga juhu korral. Neid pole võimalik parandada, sest nii asukohad 3 ja 5 kui ka 1 ja 7 annavad sündroomiks 6. Hamming alustaski märguandest. Tema 1950. aasta artikkel algab kahe releearvutiga, mille Bell Labs ehitas Aberdeen Proving Groundile. Need ei lasknud ühtki releeriket märkamata läbi. Algusaastatel esines 8,900 relee seas umbes kaks või kolm riket päevas ning öösiti ja nädalavahetustel järelevalveta töötanud masinad jäid seetõttu sageli seisma.

Iga biti kahekordne saatmine nõuab sama kaheksat bitti, kuid ei paranda midagi 🖖

Nii iga biti kahekordne saatmine kui ka laiendatud kood kasutavad nelja andmebiti jaoks kaheksat bitti. Kui kaks koopiat erinevad, on selge, et midagi läks valesti, kuid pole teada, kumb koopia on õige. Vastuvõtja saab ploki üksnes märgistada. Kui p = 0,01, juhtub see 7,69×10⁻² plokkidest ning 3,77×10⁻⁴ pääseb valena läbi, sest ühe biti mõlemad koopiad muutuvad korraga. Laiendatud Hammingi kood parandab iga üksiku vea, märgistab 2,64×10⁻³ ja laseb valena läbi 5,34×10⁻⁵ plokkidest. Sama bitieelarve juures tähendab see 29 korda vähem märgistusi ja 7 korda vähem valesid plokke. Katkend- ja pidevjoon näitavad selle paremust mõlema näitaja järgi, kuni p ületab 0,066. Sellises kanalis muutub üks bitt viieteistkümnest. Iga biti kolmekordne saatmine edestab liuguri kõigil p väärtustel seitsmebitist koodi ploki kohta: siin 1,19×10⁻³ võrreldes 2,03×10⁻³-ga. See vajab aga 12 bitti 7 asemel, mistõttu on õiglane võrdlus kaheksabitiste lahenduste vahel.

Ülesanne täielikult lahendatud

Mitu kontrollbitti vajab 64-bitine sõna? 4 sammu
Kaitse samal viisil 64 andmebitti. Vajuta Laiendatud, üks viga: nelja andmebiti kohta kasutatakse nelja kontrollbitti ja koodikiirus on 50,0%. Leia, mitu kontrollbitti vajab üks 64-bitine sõna sama tagatise jaoks, et iga üksik viga parandatakse ja iga kahe veaga juht märgistatakse. Arvuta ka pikema sõna hind selle eelseadistuse väärtusel p = 0,001.

Ava see ülesanne tööriistas
1. Kui kontrolle on r, saab sündroomil olla 2^r väärtust. Üks väärtus peab tähendama vea puudumist ning iga m + r asukoht vajab oma väärtust, seega 2^r ≥ m + r + 1. Lehel on m = 4 ja r = 3 rahuldab tingimuse täpselt, ilma ühegi üleliigse väärtuseta.
  
  $2^{r} \geq m + r + 1, m = 4 : 2^{3} = 8 = 4 + 3 + 1$
2. Kui m = 64, annavad kuus kontrolli 64 väärtust, kuid vaja on 71; seitse annavad 128 väärtust, millest piisab 72 jaoks. Niisiis parandab 71-bitine sõna iga üksiku vea.
  
  $m = 64 : 2^{6} = 64 < 71, 2^{7} = 128 \geq 72 \Rightarrow r = 7, n = 71$
3. Ühe üldise paarsusbiti lisamisel saadakse 72 bitti. Neist 8 on kontrollbitid ning koodikiirus on 88,9%, võrreldes lehel oleva 50,0%-ga.
  
  $n = 64 + 7 + 1 = 72, \frac{64}{72} = 88 . 9%$
4. Pikemasse sõnasse koguneb sagedamini kaks viga ja SECDED ei suuda kahte viga enam parandada. Ühe 8-bitise sõna puhul saadakse see tõenäosus lehel oleva kahe näitaja liitmisel.
  
  $P_{\geq 2} (n) = 1 - q^{n} - n p q^{n - 1}, P_{\geq 2} (8) = 2.78 \times 1 0^{- 5} + 5.57 \times 1 0^{- 8} = 2.79 \times 1 0^{- 5}$
Vastus

Kaheksa kontrollbitti, 72-bitine sõna, koodikiirus 88,9%. Kui p = 0,001, sisaldab see kaht või enamat viga tõenäosusega 2,44×10⁻³. Kui samad 64 bitti saadetakse kuueteistkümne 8-bitise sõnana, lähevad need kaotsi niipea, kui üks sõna kaob; selle tõenäosus on 4,46×10⁻⁴. Pika sõna korral on 64 biti kaotsimineku tõenäosus umbes 5,5 korda suurem, kuid kontrollbitte kulub kaheksa korda vähem.

$P_{\geq 2} (72) = 2.44 \times 1 0^{- 3}, 1 - (1 - P_{\geq 2} (8))^{16} = 4.46 \times 1 0^{- 4}, \frac{2 . 44}{0 . 446} \approx 5.5$

Õpitee

Miks on algoritm õige

Allikad (2)

The code itself, the requirement that the checking number give the position of any single error, the check positions 1, 2, 4 and the reason for them, the extended code that adds double-error detection, and the relay computers that motivated it: R. W. Hamming, "Error Detecting and Error Correcting Codes." Bell System Technical Journal 29(2), April 1950, pp. 147-160. DOI 10.1002/j.1538-7305.1950.tb00463.x
How Hamming told the story in his later course: a relay computer that could detect an error, retried three times and then dropped the problem, and the question that followed: R. W. Hamming, The Art of Doing Science and Engineering: Learning to Learn, Session 12, "Error-Correcting Codes". Lecture slides, Naval Postgraduate School, Monterey (course delivered 1995).

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.