Hamming CodeVirheiden havaitseminen ja korjaaminen esimerkkien avulla

Mikä on virhe?

TransmitSyötetty data voi vioittua tiedonsiirron aikana. Ulkoinen kohina tai muut fyysiset viat voivat vaikuttaa siihen. Tällaisessa tilanteessa syöttödata ei voi olla sama kuin lähtödata. Tätä ristiriitaa kutsutaan virheeksi.

Datavirheet voivat aiheuttaa tärkeiden tai suojattujen tietojen menetyksen. Suurin osa digitaalisten järjestelmien tiedonsiirrosta tapahtuu "bittisiirtona", ja pienikin yhden bitin muutos voi vaikuttaa koko järjestelmän suorituskykyyn. Jos datasekvenssissä 1 muuttuu arvoksi 0 tai 0 arvoksi 1, sitä kutsutaan "bittivirheeksi".

Virhetyypit

Dataa siirrettäessä esiintyy pääasiassa kolmenlaisia ​​bittivirheitä transmitlähettäjältä vastaanottajalle. Alla oleva kaavio havainnollistaa, miten kukin tyyppi vaikuttaa datasekvenssiin:

• Yhden bitin virheitä
• Useita bittivirheitä
• Pursotusvirheet

Yhden bitin virheet

Yhden bitin muutosta koko datasekvenssissä kutsutaan "yksibittiseksi virheeksi". Yksibittisen virheen esiintyminen ei ole kovin yleinen. Se tapahtuu enimmäkseen rinnakkaistietoliikennejärjestelmissä, koska data siirretään bitti kerrallaan erillisillä riveillä, joten on suurempi todennäköisyys, että yksi rivi muuttuu kohinaiseksi, kun taas muut pysyvät puhtaina.

Useita bittivirheitä

Kun kaksi tai useampi datajonon bitti muuttuu niiden välillä transmitja vastaanottimen välillä sitä kutsutaan "monibittiseksi virheeksi".

Tämän tyyppistä virhettä esiintyy sekä sarja- että rinnakkaistietoverkoissa.

Pursotusvirheet

Muutos joukkoon peräkkäisiä bittejä datajonossa tunnetaan nimellä "purskevirhe". Purskevirheen pituus mitataan ensimmäisestä muutetusta bitistä viimeiseen muuttuneeseen bittiin.

Mitä on virheiden havaitseminen ja virheenkorjaus?

Digitaalisessa viestintäjärjestelmässä virheitä voi syntyä datan siirtyessä laitteesta toiseen. Jos näitä virheitä ei havaita ja korjata, data menetetään. Tehokkaan viestinnän edellytyksenä on datan siirto suurella tarkkuudella, mikä saavutetaan tunnistamalla virheet ensin ja korjaamalla ne sitten.

Virheiden havaitseminen on menetelmä datassa olevien virheiden löytämiseksi transmitted jostakin transmitter vastaanottimelle a:ssa tietoliikenne järjestelmään.

Redundanssikoodeja käytetään näiden virheiden löytämiseen lisäämällä dataan ylimääräisiä bittejä, kun se on transmitlähteestä. Näitä ylimääräisiä bittejä kutsutaan "virheentunnistuskoodeiksi". Kolme yleisintä virheentunnistuskoodityyppiä ovat:

• Pariteetin tarkistus
• Cyclic Redundancy Check (CRC)
• Pituussuuntainen redundanssitarkistus (LRC)

Pariteetin tarkistus

• Se tunnetaan myös pariteettitarkistuksena.
• Se tarjoaa kustannustehokkaan mekanismin virheiden havaitsemiseen.
• Tässä tekniikassa jokaiseen datayksikköön lisättävää redundanttia bittiä kutsutaan pariteettibitiksi. Se asetetaan siten, että yksikön ykkösten kokonaismäärästä tulee parillinen (parillinen pariteetti) tai pariton (pariton pariteetti).

Pituussuuntainen redundanssin tarkistus

Tässä virheentunnistustekniikassa bittilohko järjestetään taulukkoon. LRC-menetelmä laskee pariteettibitin jokaiselle sarakkeelle, ja tämä pariteettibittijoukko lähetetään alkuperäisen datan mukana. Pariteettibittilohko auttaa vastaanottajaa tarkistamaan redundanssin ja havaitsemaan virheitä.

Syklinen redundanssitarkistus

Syklinen redundanssitarkistus liittää datayksikön loppuun sarjan redundantteja bittejä siten, että tuloksena oleva datayksikkö on täsmälleen jaollinen toisella, ennalta määrätyllä binääriluvulla.

Määränpäässä saapuva data jaetaan samalla luvulla. Jos jakojäännöstä ei ole, datayksikön oletetaan olevan oikea ja se hyväksytään. Muussa tapauksessa se osoittaa, että datayksikkö on vaurioitunut lähetyksessä, ja se on hylättävä.

Mikä on Hamming Code?

Hamming-koodi on lineaarinen koodi, joka on hyödyllinen jopa kahden välittömän bittivirheen havaitsemiseen ja yksittäisten bittien virheiden korjaamiseen. Tällainen virheenkorjaus toimii tyypillisesti tiedonsiirtokerroksella, jossa dataa kehystetään ja tarkistetaan sen eheys vierekkäisten solmujen välillä.

Hamming-koodissa lähde koodaa viestin lisäämällä redundantteja bittejä. Nämä redundanttiset bitit lisätään ja luodaan tiettyihin kohtiin viestissä virheiden havaitsemis- ja korjausprosessin suorittamiseksi.

Hammingin historia Code

• Hamming-koodi on RW Hammingin kehittämä tekniikka virheiden havaitsemiseksi ja korjaamiseksi.
• Sitä voidaan soveltaa minkä tahansa pituisiin datayksiköihin ja se hyödyntää databittien ja redundanssibittien välistä suhdetta.
• Hamming työskenteli virheenkorjauksen ongelman parissa ja kehitti yhä tehokkaamman joukon algoritmeja.
• Vuonna 1950 hän julkaisi Hamming-koodin, jota käytetään edelleen laajalti sovelluksissa, kuten ECC-muistissa.

Hammingin sovellukset Code

Tässä on joitakin Hamming-koodin yleisiä sovelluksia:

• satelliitit
• Tietokoneen muisti (ECC RAM)
• modeemit
• PlasmaCAM
• Avaa liittimet
• Suojattu lanka
• Sulautetut prosessorit

Hammingin edut Code

• Hamming-koodi on tehokas verkoissa, joissa datavirrat altistuvat yhden bitin virheille.
• Se ei ainoastaan ​​havaitse bittivirhettä, vaan auttaa myös tunnistamaan virheen sisältävän bitin, jotta se voidaan korjata.
• Hamming-koodien helppokäyttöisyys tekee niistä sopivia tietokoneen muistiin ja yksittäisten virheiden korjaukseen.

Hammingin haitat Code

• Se on yksibittinen virheentunnistus- ja korjauskoodi. Jos useissa biteissä havaitaan virheitä, tulos voi kääntää toisen, oikean bitin, mikä voi vääristää dataa entisestään.
• Hamming-koodin algoritmi pystyy ratkaisemaan vain yhden bitin ongelmia.

Kuinka koodata viesti Hammingissa Code

Lähettäjän viestin koodaamiseen käyttämä prosessi sisältää seuraavat kolme vaihetta:

• Laske redundanttien bittien kokonaismäärä.
• Määritä redundanttien bittien sijainti.
• Laske jokaisen redundantin bitin arvo.

Kun redundantit bitit on upotettu viestiin, koko koodisana lähetetään vastaanottajalle.

Vaihe 1) Laske redundanttien bittien kokonaismäärä.

Oletetaan, että viesti sisältää n databittejä ja p redundantit bitit, lisätty siten, että 2^p voi osoittaa ainakin (n + p + 1) eri tilaa.

Tässä (n + p) kuvaa virheen sijaintia kussakin (n + p) bittipaikassa, ja yksi ylimääräinen tila tarkoittaa, ettei virhettä ole. Koska p pariteettibittiä voi ilmaista 2^p osavaltiot, 2^p on oltava vähintään yhtä suuri kuin (n + p + 1).

Vaihe 2) Aseta ylimääräiset osat oikeille paikoilleen.

P redundanttia bittiä sijoitetaan bittipaikoille, jotka ovat luvun 2 potensseja – esimerkiksi 1, 2, 4, 8 ja 16. Niitä kutsutaan p:ksi₁ (paikassa 1), s₂ (paikassa 2), s₃ (sijalla 4) ja niin edelleen.

Vaihe 3) Laske kunkin redundantin bitin arvo.

Jokainen redundantti bitti on pariteettibitti, joka tekee sen ryhmässä olevien ykkösten lukumäärästä joko parillisen tai parittoman. Pariteettityyppejä on kaksi:

• Parillinen pariteetti: Peitettyjen positioiden ykkösten kokonaismäärästä tehdään parillinen.
• Pariton pariteetti: Peitettyjen paikkojen ykkösten kokonaismäärästä tehdään pariton.

Jokainen pariteettibitti kattaa tietyn joukon positioita, jotka määräytyvät positionumeroiden binääriesityksen perusteella:

• p₁ tarkistaa kaikki paikat, joiden binääriarvon vähiten merkitsevässä bitissä on 1 – paikat 1, 3, 5, 7, 9, 11 ja niin edelleen.
• p₂ tarkistaa kaikki paikat, joiden binääriarvon toisessa bitissä oikealta on 1 – paikat 2, 3, 6, 7, 10, 11 ja niin edelleen.
• p₃ tarkistaa kaikki paikat, joiden binääriarvon kolmannessa bitissä oikealta on luku 1 – paikat 4–7, 12–15 ja niin edelleen.

Työesimerkki (7,4): Tarkastellaan neljää databittiä 1011Kolme pariteettibittiä vaaditaan (2³ = 8 ≥ 4 + 3 + 1), jolloin saadaan seitsemänbittinen koodisana, joka on esitetty muodossa p₁ p₂ d₁ p₃ d₂ d₃ d₄Datan sijoittelu asettaa paikat 3, 5, 6, 7 = 1, 0, 1, 1. Käyttämällä parillista pariteettia: p₁ kattaa paikat 1, 3, 5, 7 (bitit 1, 0, 1 → p₁ = 0); s₂ kattaa bitit 2, 3, 6, 7 (bitit 1, 1, 1 → p₂ = 1); s₃ kattaa bitit 4, 5, 6, 7 (bitit 0, 1, 1 → p₃ = 0). transmitted-koodisana on siis 0110011.

Kuinka dekoodata viesti Hammingissa Code

Vastaanottaja ottaa vastaan ​​saapuvan viestin ja suorittaa uudelleenlaskentoja virheiden löytämiseksi ja korjaamiseksi. Uudelleenlaskentaprosessissa käytetään seuraavia vaiheita:

• Laske redundanttien bittien lukumäärä.
• Sijoita kaikki tarpeettomat osat oikein.
• Suorita pariteettitarkistus.

Vaihe 1) Laske redundanttien bittien lukumäärä. Käytä samaa kaavaa kuin koodauksessa: 2^p ≥ n + p + 1, jossa n on databittien lukumäärä ja p on redundanttien bittien lukumäärä.

Vaihe 2) Aseta kaikki tarpeettomat osat oikein. Jokainen redundantti bitti sijaitsee bittiasemassa, joka on kahden potenssi – esimerkiksi 1, 2, 4 ja 8.

Vaihe 3) Suorita pariteettitarkistus. Pariteettibitit lasketaan uudelleen databiteistä ja vastaanotetuista redundanteista biteistä:

• p₁ = pariteetti(1, 3, 5, 7, 9, 11, …)
• p₂ = pariteetti(2, 3, 6, 7, 10, 11, …)
• p₃ = pariteetti(4–7, 12–15, 20–23, …)

Uudelleenlasketut pariteettibitit muodostavat yhdessä binääriluvun. Jos luku on nolla, virhettä ei ole; muussa tapauksessa sen arvo antaa yksittäisen vioittuneen bitin tarkan sijainnin, joka sitten käännetään ympäri viestin korjaamiseksi.

UKK