Hammingov kod: otkrivanje i ispravljanje pogrešaka s primjerima

Što je pogreška?

Preneseni podaci mogu biti oštećeni tijekom komunikacije. Vjerojatno će na njega utjecati vanjska buka ili drugi fizički kvarovi. U takvoj situaciji ulazni podaci ne mogu biti isti kao i izlazni podaci. Ovo nepodudaranje poznato je kao "Pogreška".

Pogreške u podacima mogu dovesti do gubitka važnih ili sigurnih podataka. Većina prijenosa podataka u digitalnim sustavima bit će u obliku 'prijenosa bitova'. Čak i mala promjena može utjecati na performanse cijelog sustava. U nizu podataka, ako se 1 promijeni u 0 ili se 0 promijeni u 1, to se naziva "Bit error."

Vrste grešaka

Uglavnom postoje tri vrste grešaka u bitovima koje se javljaju u prijenosu podataka od pošiljatelja do primatelja.

• Pogreške jednog bita
• Pogreške s više bitova
• Rafalne pogreške

Pogreške jednog bita

Promjena napravljena u jednom bitu u cijelom nizu podataka poznata je kao "pogreška jednog bita". Međutim, pojava greške jednog bita nije tako česta. Štoviše, ova se pogreška javlja samo u paralelnom komunikacijskom sustavu jer se podaci prenose bit-wise u jednoj liniji. Stoga postoji veća vjerojatnost da jedna linija može biti bučna.

Višestruke bitne pogreške

U nizu podataka, ako postoji promjena u dva ili više bitova niza podataka od odašiljača do prijamnika, to je poznato kao "višestruke bitne pogreške".

Ova vrsta pogreške uglavnom se pojavljuje u serijskim i paralelnim podatkovnim komunikacijskim mrežama.

Burst pogreške

Promjena skupa bitova u nizu podataka poznata je kao "Burst error". Ova vrsta pogreške podataka izračunava se od promjene prvog bita do promjene posljednjeg bita.

Što je otkrivanje i ispravljanje pogrešaka?

U digitalnom komunikacijskom sustavu pogreška će se prenositi iz jednog komunikacijskog sustava u drugi. Ako se ove pogreške ne otkriju i ne isprave, podaci će biti izgubljeni. Za učinkovitu komunikaciju, podaci sustava trebaju se prenositi s visokom točnošću. To će se učiniti tako da se najprije identificiraju pogreške i ispravi ih.

Detekcija pogrešaka je metoda otkrivanja grešaka koje su prisutne u podacima koji se prenose od odašiljača do prijamnika u sustavu podatkovne komunikacije.

Ovdje možete koristiti redundancijske kodove za pronalaženje ovih pogrešaka dodavanjem podataka kada se prenose iz izvora. Ovi se kodovi nazivaju "kodovi za otkrivanje pogrešaka".

Tri vrste kodova za otkrivanje grešaka su:

• Provjera pariteta
• Ciklička redundantna provjera (CRC)
• Uzdužna provjera redundantnosti (LRC)

Provjera pariteta

• Također je poznat kao provjera pariteta.
• Ima isplativ mehanizam za otkrivanje grešaka.
• U ovoj tehnici, redundantni bit je poznat kao bit parnosti. Pridodaje se za svaku podatkovnu jedinicu. Ukupan broj jedinica u jedinici trebao bi postati paran, što je poznato kao bit parnosti.

Longitudinalna provjera redundantnosti

U ovoj tehnici otkrivanja pogrešaka, blok bitova organiziran je u tabličnom formatu. LRC metoda vam pomaže izračunati bit parnosti za svaki stupac. Skup ovog pariteta također se šalje zajedno s izvornim podacima. Blok pariteta pomaže vam provjeriti redundanciju.

Ciklična provjera redundantnosti

Ciklička provjera redundantnosti je niz redundantnosti koji se mora dodati na kraj jedinice. Zato bi nastala podatkovna jedinica trebala postati djeljiva s drugim, unaprijed određenim binarnim brojem.

Na odredištu je potrebno dolazne podatke podijeliti istim brojem. U slučaju da nema ostatka, tada se pretpostavlja da je podatkovna jedinica ispravna i prihvaća se. U suprotnom, to znači da je podatkovna jedinica oštećena u prijenosu i stoga se mora odbaciti.

U Hammingovom kodu, izvor kodira poruku dodavanjem suvišnih bitova u poruku. Ti se suvišni bitovi uglavnom umeću i generiraju na određenim mjestima u poruci kako bi se izvršilo otkrivanje pogrešaka i proces ispravljanja.

Povijest Hammingovog koda

• Hammingov kod je tehnika koju je izgradio RWHamming za otkrivanje pogrešaka.
• Hammingov kod treba primijeniti na podatkovne jedinice bilo koje duljine i koristi odnos između podataka i redundantnih bitova.
• Radio je na problemu metode ispravljanja pogrešaka i razvio sve snažniji niz algoritama koji se naziva Hammingov kod.
• Godine 1950. objavio je Hammingov kod, koji se danas široko koristi u aplikacijama poput ECC memorije.

Primjena Hammingovog koda

Evo nekih uobičajenih primjena korištenja Hammingovog koda:

• sateliti
• Memorija računala
• Modemi
• PlasmaCAM
• Otvoreni konektori
• Zaštitna žica
• Ugrađeni procesor

Prednosti Hammingovog koda

• Metoda Hammingovog koda učinkovita je na mrežama gdje se tokovi podataka daju za jednobitne pogreške.
• Hammingov kod ne samo da omogućuje otkrivanje pogreške bita, već vam također pomaže da uvučete pogrešku koja sadrži bit tako da se može ispraviti.
• Jednostavnost korištenja Hammingovih kodova čini ih najprikladnijima za korištenje u računalnoj memoriji i ispravljanje pojedinačnih pogrešaka.

Nedostaci Hammingovog koda

• Jednobitni kod za otkrivanje i ispravljanje pogrešaka. Međutim, ako je pogreška utemeljena na više bitova, tada ishod može rezultirati drugim bitom koji bi trebao biti ispravan da bi se promijenio. To može uzrokovati dodatne pogreške u podacima.
• Algoritam Hammingovog koda može riješiti probleme samo s pojedinačnim bitovima.

Kako kodirati poruku u Hammingovom kodu

Proces koji koristi pošiljatelj za kodiranje poruke uključuje sljedeća tri koraka:

• Izračun ukupnog broja redundantnih bitova.
• Provjera položaja suvišnih bitova.
• Na kraju, izračunavanje vrijednosti ovih suvišnih bitova.

Kada su gornji suvišni bitovi ugrađeni u poruku, ona se šalje korisniku.

Korak 1) Izračun ukupnog broja suvišnih bitova.

Pretpostavimo da poruka sadrži:

• n– broj podatkovnih bitova
• p – broj suvišnih bitova koji mu se dodaju tako da np može naznačiti najmanje (n + p + 1) različitih stanja.

Ovdje (n + p) prikazuje mjesto pogreške u svakom od (n + p) položaja bita, a jedno dodatno stanje označava da nema pogreške. Kako p bitova može označavati 2^p države, 2^p mora biti najmanje jednak (n + p + 1).

Korak 2) Postavljanje suvišnih bitova na njihov ispravan položaj.

P redundantnih bitova treba postaviti na pozicije bitova potencije broja 2. Na primjer, 1, 2, 4, 8, 16 itd. Označavaju se kao p₁ (na poziciji 1), str₂ (na poziciji 2), str₃ (na poziciji 4) itd.

Korak 3) Izračun vrijednosti redundantnog bita.

Suvišni bitovi trebaju biti paritetni bitovi koji čine broj jedinica parnim ili neparnim.

Dvije vrste pariteta su ?

• Ukupan broj bitova u poruci koji je paran naziva se parni paritet.
• Ukupan broj bitova u poruci koji je neparan naziva se neparni paritet.

Ovdje se sav redundantni bit, p1, mora izračunati kao paritet. Trebao bi pokriti sve pozicije bita čija bi binarna reprezentacija trebala uključivati ​​1 na prvoj poziciji isključujući poziciju p1.

P1 je paritetni bit za sve bitove podataka na pozicijama čija binarna reprezentacija uključuje 1 na manje važnoj poziciji ne uključujući 1 Like (3, 5, 7, 9, ….)

P2 je bit parnosti za sve bitove podataka na pozicijama čija binarna reprezentacija uključuje 1 na poziciji 2 s desna, ne uključujući 2 Like (3, 6, 7, 10, 11,…)

P3 je paritetni bit za svaki bit na pozicijama čija binarna reprezentacija uključuje 1 na poziciji 3 s desna ne uključuje 4 Like (5-7, 12-15,… )

Dešifriranje poruke u Hammingovom kodu

Primatelj prima dolazne poruke koje zahtijevaju ponovno izračune kako bi se pronašle i ispravile pogreške.

Proces ponovnog izračuna se provodi u sljedećim koracima:

• Brojanje broja suvišnih bitova.
• Ispravno pozicioniranje svih suvišnih bitova.
• Provjera pariteta

Korak 1) Brojanje broja suvišnih bitova

Možete koristiti istu formulu za kodiranje, broj suvišnih bitova

2^p ? n + p + 1

Ovdje je broj podatkovnih bitova, a p je broj suvišnih bitova.

Korak 2) Ispravno postavljanje svih suvišnih bitova

Ovdje je p redundantni bit koji se nalazi na pozicijama bita potencije broja 2, na primjer, 1, 2, 4, 8, itd.

Korak 3) Provjera pariteta

Bitove parnosti potrebno je izračunati na temelju podatkovnih bitova i suvišnih bitova.

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

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

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

Rezime

• Preneseni podaci mogu biti oštećeni tijekom komunikacije
• Tri vrste grešaka bita su 1) pogreške jednog bita 2) pogreške višestrukog bita 3) pogreške burst bita
• Promjena napravljena u jednom bitu u cijelom nizu podataka poznata je kao "pogreška jednog bita".
• U nizu podataka, ako postoji promjena u dva ili više bitova niza podataka od odašiljača do prijamnika, to je poznato kao "višestruke bitne pogreške".
• Promjena skupa bitova u nizu podataka poznata je kao "Burst error".
• Detekcija grešaka je metoda otkrivanja grešaka koje su prisutne u podacima koji se prenose od odašiljača do prijamnika u sustavu podatkovne komunikacije
• Tri vrste kodova za otkrivanje pogrešaka su 1) provjera pariteta 2) ciklička redundantna provjera (CRC) 3) longitudinalna redundantna provjera (LRC)
• Hammingov kod je linijski kod koji je koristan za detekciju pogreške do dvije trenutne pogreške bita. Sposoban je za pogreške jednog bita.
• Hammingov kod je tehnika koju je izgradio RWHamming za otkrivanje pogrešaka.
• Uobičajene primjene korištenja Hammingovog koda su satelitska računalna memorija, modemi, ugrađeni procesor itd.
• Najveća prednost metode Hammingovog koda učinkovita je na mrežama gdje se tokovi podataka daju za jednobitne pogreške.
• Najveći nedostatak metode Hammingovog koda je to što može riješiti probleme samo s pojedinačnim bitovima.
• Uz pomoć hamming koda možemo izvršiti proces šifriranja i dekodiranja poruke.