Hamming-kood: vigade tuvastamine ja parandamine näidetega

Mis on viga?

Edastatud andmed võivad side ajal rikkuda. Tõenäoliselt mõjutavad seda väline müra või muud füüsilised rikked. Sellises olukorras ei saa sisendandmed olla samad, mis väljundandmed. Seda mittevastavust nimetatakse veaks.

Andmevead võivad põhjustada oluliste või turvaliste andmete kadumise. Suurem osa andmeedastusest digitaalsüsteemides toimub bitiedastuse vormis. Isegi väike muudatus võib mõjutada kogu süsteemi jõudlust. Kui andmejadas muudetakse 1 väärtuseks 0 või 0 muudetakse 1-ks, nimetatakse seda "bitivigaks".

Vigade tüübid

Andmete edastamisel saatjalt vastuvõtjale esineb peamiselt kolme tüüpi bitivigasid.

• Ühebitised vead
• Mitu bitivigu
• Sarivõtte vead

Ühebitised vead

Kogu andmejadas ühes bitis tehtud muudatust nimetatakse "Ühe biti veaks". Ühebitise vea esinemine pole aga nii tavaline. Pealegi ilmneb see viga ainult paralleelses sidesüsteemis, kuna andmeid edastatakse bittide kaupa ühel real. Seetõttu on suurem tõenäosus, et üks rida võib olla mürarikas.

Mitu bitivigu

Andmejada puhul nimetatakse seda, kui saatja ja vastuvõtja andmejada kahes või enamas bitis toimub muutus, seda nimetatakse mitmebitiseks veaks.

Seda tüüpi tõrkeid esineb enamasti nii jada- kui ka paralleeltüüpi andmesidevõrkudes.

Sarivõtte vead

Bittide komplekti muutmist andmejadas tuntakse kui "Burst error". Seda tüüpi andmeviga arvutatakse alates esimese biti muutusest kuni viimase biti muudatuseni.

Mis on vigade tuvastamine ja parandamine?

Digitaalses sidesüsteemis kandub viga ühest sidesüsteemist teise. Kui neid vigu ei avastata ega parandata, lähevad andmed kaotsi. Tõhusaks suhtluseks tuleks süsteemiandmeid edastada suure täpsusega. Selleks tuleb esmalt tuvastada vead ja need parandada.

Vigade tuvastamine on andmesidesüsteemi saatjalt vastuvõtjale edastatavates andmetes esinevate vigade tuvastamise meetod.

Siin saate nende vigade leidmiseks kasutada koondamiskoode, lisades andmetele, kui need allikast edastatakse. Neid koode nimetatakse "koodide tuvastamise veaks".

Kolme tüüpi veatuvastuskoode on:

• Pariteedi kontroll
• Tsükliline koondamise kontroll (CRC)
• Pikisuunaline koondamise kontroll (LRC)

Pariteedi kontroll

• Seda tuntakse ka kui pariteedikontrolli.
• Sellel on kulutõhus mehhanism vigade tuvastamiseks.
• Selles tehnikas nimetatakse üleliigset bitti paarsusbitiks. See lisatakse iga andmeühiku kohta. Ühiku 1-de koguarv peaks muutuma paariks, mida nimetatakse paarsusbitiks.

Pikisuunalise koondamise kontroll

Selles veatuvastustehnikas korraldatakse bitiplokk tabelivormingus. LRC meetod aitab teil arvutada iga veeru paarsusbiti. Selle paarsuse komplekt saadetakse ka koos algandmetega. Pariteedi plokk aitab teil koondamist kontrollida.

Tsüklilise koondamise kontroll

Tsükliline liiasuse kontroll on üleliigse jada, mis tuleb lisada seadme lõppu. Sellepärast peaks saadud andmeüksus olema jagatav teise, ettemääratud kahendarvuga.

Sihtkohas tuleb sissetulevad andmed jagada sama arvuga. Kui jääki pole, siis loetakse andmeüksus õigeks ja aktsepteeritakse. Vastasel juhul näitab see, et andmeüksus on edastamisel kahjustatud ja seetõttu tuleb see tagasi lükata.

Hammingi koodis kodeerib allikas sõnumi, lisades sõnumisse üleliigseid bitte. Need üleliigsed bitid sisestatakse ja genereeritakse enamasti sõnumi teatud kohtades, et viia läbi vigade tuvastamise ja parandamise protsess.

Hammingi koodi ajalugu

• Hammingi kood on RWHammingu loodud tehnika vigade tuvastamiseks.
• Hamming-koodi tuleks rakendada mis tahes pikkusega andmeühikutele ja see kasutab andmete ja liiasusbittide vahelist suhet.
• Ta tegeles veaparandusmeetodi probleemiga ja töötas välja üha võimsama algoritmide massiivi, mida nimetatakse Hammingi koodiks.
• 1950. aastal avaldas ta Hammingi koodi, mida kasutatakse tänapäeval laialdaselt sellistes rakendustes nagu ECC mälu.

Hammingi koodi rakendamine

Siin on mõned Hammingi koodi kasutamise levinumad rakendused:

• Satelliidid
• Arvutimälu
• modemid
• PlasmaCAM
• Avage pistikud
• Varjestustraat
• Embedded protsessor

Hammingi koodi eelised

• Hamming-koodi meetod on efektiivne võrkudes, kus andmevood antakse ühebitiste vigade jaoks.
• Hamming-kood ei võimalda mitte ainult bitiviga tuvastamist, vaid aitab teil ka viga sisaldavat bitti taande teha, et seda saaks parandada.
• Hammimiskoodide kasutusmugavus muudab need kõige paremini sobivaks arvutimälus kasutamiseks ja ühe vea parandamiseks.

Hammingi koodi puudused

• Ühebitine veatuvastus- ja paranduskood. Kui aga mitme biti alusviga on, võib tulemuseks olla veel üks bitt, mida tuleks muuta õigeks. See võib põhjustada andmete täiendavaid vigu.
• Hamming-koodi algoritm suudab lahendada ainult üksikute bittide probleeme.

Sõnumi kodeerimine Hammingi koodis

Protsess, mida saatja kasutab sõnumi kodeerimiseks, sisaldab järgmist kolme sammu.

• Üleliigsete bittide koguarvu arvutamine.
• Üleliigsete bittide asukoha kontrollimine.
• Viimaseks nende üleliigsete bittide väärtuste arvutamine.

Kui ülaltoodud üleliigsed bitid on sõnumisse manustatud, saadetakse see kasutajale.

Step 1) Üleliigsete bittide koguarvu arvutamine.

Oletame, et sõnum sisaldab:

• n– andmebittide arv
• p – üleliigsete bittide arv, mis sellele lisatakse nii, et np saab näidata vähemalt (n + p + 1) erinevaid olekuid.

Siin (n + p) kujutab vea asukohta igas (n + p) bitipositsioonis ja üks lisaolek näitab, et viga pole. Nagu p bitid võivad tähistada 2^p osariigid, 2^p peab olema vähemalt võrdne (n + p + 1).

Step 2) Üleliigsete bittide paigutamine õigesse kohta.

P üleliigsed bitid tuleks asetada bitipositsioonidele, mille võimsus on 2. Näiteks 1, 2, 4, 8, 16 jne. Neid nimetatakse p-ks.₁ (positsioonil 1), lk₂ (positsioonil 2), lk₃ (positsioonil 4) jne.

Step 3) Üleliigse biti väärtuste arvutamine.

Üleliigsed bitid peaksid olema paarsusbitid, mis muudab 1-de arvu paaris või paaritu.

Kaks pariteedi tüüpi on ?

• Bitide koguarv sõnumis on tehtud paaris, nimetatakse paarispaarsuseks.
• Bitide koguarvu sõnumis, mis on tehtud paarituks, nimetatakse paarituks pariteediks.

Siin tuleb kogu liiasbitt p1 arvutada paarsusena. See peaks hõlmama kõiki bitipositsioone, mille binaarne esitus peaks sisaldama 1-t 1. positsioonis, välja arvatud p1 asukoht.

P1 on paarisbitt iga andmebiti jaoks positsioonides, mille binaarne esitus sisaldab 1-t vähemtähtsas positsioonis, mis ei sisalda 1 Like (3, 5, 7, 9, …. )

P2 on paarsusbitt iga andmebiti jaoks positsioonides, mille binaarne esitus sisaldab 1 positsioonis 2 paremalt, välja arvatud 2 Like (3, 6, 7, 10, 11,…)

P3 on paarsusbitt iga biti jaoks positsioonides, mille binaarne esitus sisaldab 1-t positsioonis 3 paremalt, mitte 4 Like (5-7, 12-15,… )

Sõnumi dekrüpteerimine Hammingi koodis

Vastuvõtja saab sissetulevad sõnumid, mis nõuavad vigade leidmiseks ja parandamiseks ümberarvutusi.

Ümberarvutusprotsess viiakse läbi järgmiste sammudega:

• Üleliigsete bittide arvu loendamine.
• Kõikide üleliigsete bittide õige positsioneerimine.
• Pariteedikontroll

Step 1) Üleliigsete bittide arvu loendamine

Kodeerimiseks võite kasutada sama valemit, üleliigsete bittide arvu

2^p ? n + p + 1

Siin on andmebittide arv ja p üleliigsete bittide arv.

Step 2) Kõigi üleliigsete bittide õige paigutamine

Siin on p üleliigne bitt, mis asub bitipositsioonidel astmetega 2, näiteks 1, 2, 4, 8 jne.

Step 3) Pariteedikontroll

Paarsusbitid tuleb arvutada andmebittide ja üleliigsete bittide põhjal.

p1 = paarsus(1, 3, 5, 7, 9, 11…)

p2 = paarsus(2, 3, 6, 7, 10, 11…)

p3 = paarsus(4-7, 12-15, 20-23…)

kokkuvõte

• Edastatud andmed võivad side ajal rikkuda
• Kolm tüüpi bitivigasid on 1) ühe biti vead 2) mitme biti vead 3) saribiti vead
• Kogu andmejadas ühes bitis tehtud muudatust nimetatakse "ühebitise veaks".
• Andmejada puhul nimetatakse seda, kui saatja ja vastuvõtja andmejada kahes või enamas bitis toimub muutus, seda nimetatakse mitmebitiseks veaks.
• Bittide komplekti muutmist andmejadas tuntakse kui "Burst error".
• Vigade tuvastamine on andmesidesüsteemi saatjalt vastuvõtjale edastatavates andmetes esinevate vigade tuvastamise meetod.
• Kolme tüüpi veatuvastuskoode on 1) paarsuskontroll 2) tsükliline koondamise kontroll (CRC) 3) pikisuunaline koondamise kontroll (LRC)
• Hamming-kood on lainerkood, mis on kasulik kuni kahe vahetu bitivea tuvastamiseks. See on võimeline ühebitiste vigade korral.
• Hammingi kood on RWHammingu loodud tehnika vigade tuvastamiseks.
• Levinud rakendused Hammingi koodi kasutamiseks on satelliitarvuti mälu, modemid, sisseehitatud protsessor jne.
• Hammingu koodi meetodi suurim eelis on efektiivne võrkudes, kus andmevood antakse ühebitiste vigade jaoks.
• Hamm-koodi meetodi suurim puudus on see, et see suudab lahendada ainult üksikute bittide probleeme.
• Sõnumi krüptimise ja dekodeerimise protsessi saame läbi viia hamming-koodi abil.