Hamming-koodi: Virheiden havaitseminen ja korjaaminen esimerkein

Mikä on virhe?

Lähetetyt tiedot voivat vioittua viestinnän aikana. Ulkoinen melu tai muut fyysiset viat voivat vaikuttaa siihen. Tällaisessa tilanteessa syöttötiedot eivät voi olla samat kuin lähtötiedot. Tämä ristiriita tunnetaan nimellä "virhe".

Tietovirheet voivat johtaa tärkeiden tai suojattujen tietojen menetykseen. Suurin osa tiedonsiirrosta digitaalisissa järjestelmissä tapahtuu "bittisiirron" muodossa. Pienikin muutos voi vaikuttaa koko järjestelmän suorituskykyyn. Jos datasekvenssissä 1 muutetaan 0:ksi tai 0 muutetaan 1:ksi, sitä kutsutaan "bittivirheeksi".

Virhetyypit

Tiedonsiirrossa lähettäjältä vastaanottajalle esiintyy pääasiassa kolmenlaisia ​​bittivirheitä.

• Yhden bitin virheitä
• Useita bittivirheitä
• Pursotusvirheet

Yhden bitin virheet

Yhden bitin muutos koko datasekvenssissä tunnetaan nimellä "Yksi bittivirhe". Yksibittisten virheiden esiintyminen ei kuitenkaan ole niin yleistä. Lisäksi tämä virhe ilmenee vain rinnakkaisviestintäjärjestelmässä, koska dataa siirretään bittikohtaisesti yhdellä rivillä. Siksi on enemmän mahdollisuuksia, että yksittäinen rivi voi olla meluisa.

Useita bittivirheitä

Datasekvenssissä, jos lähettimen ja vastaanottimen datasekvenssin kahdessa tai useammassa bitissä tapahtuu muutos, sitä kutsutaan "Multiple bit errors".

Tämän tyyppisiä virheitä esiintyy useimmiten sekä sarja- että rinnakkaistyyppisissä tietoliikenneverkoissa.

Pursotusvirheet

Bittijoukon muutosta datasekvenssissä kutsutaan "purskevirheeksi". Tämän tyyppinen datavirhe lasketaan ensimmäisen bitin muutoksesta viimeiseen bitin muutokseen.

Mitä on virheiden havaitseminen ja korjaaminen?

Digitaalisessa viestintäjärjestelmässä virhe siirtyy viestintäjärjestelmästä toiseen. Jos näitä virheitä ei havaita ja korjata, tiedot menetetään. Tehokas viestintä edellyttää järjestelmätietojen siirtoa suurella tarkkuudella. Tämä tehdään tunnistamalla ensin virheet ja korjaamalla ne.

Virheenilmaisu on menetelmä, jolla havaitaan virheet, jotka esiintyvät dataviestintäjärjestelmän lähettimeltä vastaanottimelle siirretyssä tiedossa.

Täällä voit käyttää redundanssikoodeja löytääksesi nämä virheet lisäämällä tietoihin, kun ne lähetetään lähteestä. Näitä koodeja kutsutaan "virheen havaitsemiseksi koodeiksi".

Kolmen tyyppisiä virheentunnistuskoodeja ovat:

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

Pariteetin tarkistus

• Se tunnetaan myös pariteettitarkistuksena.
• Siinä on kustannustehokas mekanismi virheiden havaitsemiseen.
• Tässä tekniikassa redundanttibitti tunnetaan pariteettibittinä. Se on liitetty jokaiselle tietoyksikölle. Yksikön ykkösten kokonaismäärän tulee olla parillinen, mikä tunnetaan pariteettibittinä.

Pituussuuntainen redundanssin tarkistus

Tässä virheentunnistustekniikassa bittilohko järjestetään taulukkomuotoon. LRC-menetelmä auttaa sinua laskemaan pariteettibitin jokaiselle sarakkeelle. Tämän pariteetin joukko lähetetään myös alkuperäisten tietojen mukana. Pariteettilohko auttaa sinua tarkistamaan redundanssin.

Syklinen redundanssitarkistus

Cyclic Redundancy Check on redundanttien sarja, joka on liitettävä yksikön päähän. Tästä syystä tuloksena olevasta datayksiköstä tulee tulla jaollinen toisella, ennalta määrätyllä binääriluvulla.

Kohteessa saapuvat tiedot on jaettava samalla luvulla. Jos jäännöstä ei ole, tietoyksikön oletetaan olevan oikea ja se hyväksytään. Muussa tapauksessa se osoittaa, että tietoyksikkö on vaurioitunut lähetyksessä, ja siksi se on hylättävä.

Hamming-koodissa lähde koodaa viestin lisäämällä viestiin redundantteja bittejä. Nämä redundantit bitit lisätään ja generoidaan enimmäkseen viestin tiettyihin kohtiin virheiden havaitsemis- ja korjausprosessin suorittamiseksi.

Hamming-koodin historia

• Hamming-koodi on RWHammingin rakentama tekniikka virheiden havaitsemiseksi.
• Hamming-koodia tulisi soveltaa minkä tahansa pituisiin tietoyksiköihin, ja se käyttää datan ja redundanssibittien välistä suhdetta.
• Hän työskenteli virheenkorjausmenetelmän ongelman parissa ja kehitti yhä tehokkaamman joukon algoritmeja nimeltä Hamming-koodi.
• Vuonna 1950 hän julkaisi Hamming-koodin, jota käytetään nykyään laajalti sovelluksissa, kuten ECC-muisti.

Hamming-koodin soveltaminen

Tässä on joitain yleisiä Hamming-koodin käytön sovelluksia:

• satelliitit
• Tietokoneen muisti
• modeemit
• PlasmaCAM
• Avaa liittimet
• Suojavaijeri
• Sulautettu prosessori

Hamming-koodin edut

• Hamming-koodimenetelmä on tehokas verkoissa, joissa datavirrat annetaan yksibittisille virheille.
• Hamming-koodi ei ainoastaan ​​tunnista bittivirhettä, vaan myös auttaa sinua sisentämään bitin sisältävän virheen, jotta se voidaan korjata.
• Hamming-koodien helppokäyttöisyys tekee niistä parhaiten soveltuvia käytettäväksi tietokoneen muistissa ja yhden virheen korjauksessa.

Hamming-koodin haitat

• Yksibittinen virheentunnistus- ja korjauskoodi. Kuitenkin, jos useat bitit ovat perusteltuja virheitä, tuloksena voi olla toinen bitti, joka pitäisi olla oikein muutettava. Tämä voi aiheuttaa lisävirheitä tiedoissa.
• Hamming-koodialgoritmi voi ratkaista vain yksittäisiä bittejä koskevat ongelmat.

Viestin koodaaminen Hamming-koodiin

Prosessi, jota lähettäjä käyttää viestin koodaamiseen, sisältää seuraavat kolme vaihetta:

• Redundanttien bittien kokonaismäärän laskeminen.
• Redundanttien bittien paikan tarkistaminen.
• Lopuksi lasketaan näiden redundanttien bittien arvot.

Kun yllä olevat redundantit bitit on upotettu viestiin, se lähetetään käyttäjälle.

Vaihe 1) Redundanttien bittien kokonaismäärän laskeminen.

Oletetaan, että viesti sisältää:

• n– databittien määrä
• p – redundanttien bittien määrä, jotka siihen lisätään niin, että np voi osoittaa vähintään (n + p + 1) eri tiloja.

Tässä (n + p) kuvaa virheen sijaintia kussakin (n + p) bittipaikassa ja yksi ylimääräinen tila ilmaisee, ettei virhettä ole. Kuten p-bitit voivat osoittaa 2^p osavaltiot, 2^p on oltava vähintään yhtä suuri kuin (n + p + 1).

Vaihe 2) Redundanttien bittien asettaminen oikeaan paikkaan.

P redundantit bitit tulisi sijoittaa bittipaikkoihin, joiden potenssit ovat 2. Esimerkiksi 1, 2, 4, 8, 16 jne. Niitä kutsutaan p:ksi₁ (paikassa 1), s₂ (paikassa 2), s₃ (asemassa 4) jne.

Vaihe 3) Redundantin bitin arvojen laskenta.

Redundanttien bittien tulee olla pariteettibittejä, mikä tekee ykkösten lukumäärästä parillisen tai parittoman.

Kaksi pariteettityyppiä ovat ?

• Parillisen viestin bittien kokonaismäärää kutsutaan parillisiksi pariteetiksi.
• Viestin parittoman bittien kokonaismäärää kutsutaan parittomaksi pariteetiksi.

Tässä kaikki redundanttibitti, p1, on laskettava pariteettina. Sen tulisi kattaa kaikki bittipaikat, joiden binääriesityksen tulisi sisältää 1 ensimmäisessä paikassa, lukuun ottamatta p1:n sijaintia.

P1 on pariteettibitti jokaiselle databitille paikoissa, joiden binääriesitys sisältää 1:n vähemmän tärkeässä paikassa ilman 1 Like:ta (3, 5, 7, 9, .... )

P2 on pariteettibitti jokaiselle databitille paikoissa, joiden binääriesitys sisältää 1 kohdassa 2 oikealta, ei sisällä 2 Like (3, 6, 7, 10, 11,…)

P3 on pariteettibitti jokaiselle bitille paikoissa, joiden binääriesitys sisältää 1:n kohdassa 3 oikealta, ei sisällä 4 Like (5-7, 12-15,… )

Viestin salauksen purku Hamming-koodissa

Vastaanotin saa saapuvia viestejä, jotka vaativat uudelleenlaskutoimituksia virheiden löytämiseksi ja korjaamiseksi.

Uudelleenlaskentaprosessi suoritetaan seuraavissa vaiheissa:

• Redundanttien bittien lukumäärän laskeminen.
• Kaikkien redundanttien bittien oikea sijoitus.
• Pariteettitarkistus

Vaihe 1) Redundanttien bittien lukumäärän laskeminen

Voit käyttää samaa kaavaa koodaukseen, redundanttien bittien lukumäärään

2^p ? n + p + 1

Tässä databittien lukumäärä ja p on redundanttien bittien määrä.

Vaihe 2) Sijoita kaikki redundantit bitit oikein

Tässä p on redundantti bitti, joka sijaitsee potenssien 2 bittipaikoissa, esimerkiksi 1, 2, 4, 8 jne.

Vaihe 3) Pariteettitarkistus

Pariteettibitit on laskettava databittien ja redundanttien bittien perusteella.

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

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

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

Yhteenveto

• Lähetetyt tiedot voivat vioittua viestinnän aikana
• Kolme bittivirhetyyppiä ovat 1) yhden bitin virheet 2) usean bitin virheet 3) purskebittivirheet
• Yhdessä bitissä koko datasekvenssissä tehty muutos tunnetaan nimellä "Yksi bittivirhe".
• Datasekvenssissä, jos lähettimen ja vastaanottimen datasekvenssin kahdessa tai useammassa bitissä tapahtuu muutos, sitä kutsutaan "Multiple bit errors".
• Bittijoukon muutosta datasekvenssissä kutsutaan "purskevirheeksi".
• Virheiden havaitseminen on menetelmä, jolla havaitaan virheet, jotka esiintyvät dataviestintäjärjestelmän lähettimestä vastaanottimelle siirretyssä tiedossa.
• Kolmen tyyppisiä virheiden havaitsemiskoodeja ovat 1) Pariteetin tarkistus 2) Cyclic Redundancy Check (CRC) 3) Longitudinal Redundancy Check (LRC)
• Hamming-koodi on liner-koodi, joka on hyödyllinen virheiden havaitsemiseen jopa kahteen välittömään bittivirheeseen. Se kykenee yksibittisiin virheisiin.
• Hamming-koodi on RWHammingin rakentama tekniikka virheiden havaitsemiseksi.
• Yleisiä Hamming-koodin käyttösovelluksia ovat satelliittitietokonemuisti, modeemit, sulautettu prosessori jne.
• Hamming-koodimenetelmän suurin hyöty on tehokas verkoissa, joissa datavirrat annetaan yksibittisille virheille.
• Hamming-koodimenetelmän suurin haittapuoli on, että se voi ratkaista vain yksittäisiä bittejä.
• Voimme suorittaa viestin salauksen ja dekoodauksen hamming-koodin avulla.