Hamming CodeHibaészlelés és -javítás példákkal

Mi az a hiba?

TransmitA bevitt adatok kommunikáció közben megsérülhetnek. Valószínűleg külső zaj vagy más fizikai hibák befolyásolhatják őket. Ilyen helyzetben a bemeneti adatok nem lehetnek azonosak a kimeneti adatokkal. Ezt az eltérést „hibának” nevezzük.

Az adathibák fontos vagy biztonságos adatok elvesztését okozhatják. A digitális rendszerekben az adatátvitel nagy része „bitátvitel” formájában történik, és egyetlen bit apró változása is befolyásolhatja a teljes rendszer teljesítményét. Egy adatsorozatban, ha egy 1-es 0-ra, vagy egy 0-s 1-re változik, azt „bithibának” nevezzük.

A hibák típusai

Főként háromféle bithiba fordul elő, amikor az adatok transmita küldőtől a fogadóig. Az alábbi ábra szemlélteti, hogy az egyes típusok hogyan befolyásolják az adatsorozatot:

• Egybites hibák
• Több bites hiba
• Burst hibák

Egybites hibák

Az egész adatsorozat egyetlen bitjének megváltoztatását „egybites hibának” nevezzük. Az egybites hibák előfordulása nem túl gyakori. Leginkább párhuzamos kommunikációs rendszerekben fordul elő, mivel az adatok bitenként, külön vonalakon kerülnek átvitelre, így nagyobb az esélye annak, hogy az egyik vonal zajossá válik, míg a többi tiszta marad.

Több bites hiba

Amikor egy adatsorozat két vagy több bitje megváltozik a kettő között transmita ter és a vevő között „többbites hibának” nevezzük.

Ez a fajta hiba mind soros, mind párhuzamos adatátviteli hálózatokban előfordul.

Burst hibák

Az adatsorozat egymást követő bitjeinek egy halmazában bekövetkező változást „burst hibának” nevezzük. A burst hiba hosszát az első megváltozott bittől az utolsó megváltozott bitig mérjük.

Mi a hibakeresés és hibajavítás?

Egy digitális kommunikációs rendszerben hibák keletkezhetnek, amikor az adatok egyik eszközről a másikra mozognak. Ha ezeket a hibákat nem észlelik és nem javítják ki, az adatok elvesznek. A hatékony kommunikációhoz nagy pontossággal kell az adatokat továbbítani, amit a hibák azonosításával, majd kijavításával érnek el.

Hibaészlelés egy módszer az adatokban található hibák megtalálására transmitted egy transmitegy vevőhöz egy adatkommunikáció rendszer.

A redundanciakódokat úgy használják ezen hibák megtalálására, hogy extra biteket adnak az adatokhoz, amikor azok... transmita forrásból. Ezeket az extra biteket „hibadetektáló kódoknak” nevezzük. A három leggyakoribb hibadetektáló kódtípus a következő:

• Paritásellenőrzés
• Ciklikus redundanciaellenőrzés (CRC)
• Longitudinális redundancia ellenőrzés (LRC)

Paritásellenőrzés

• Paritásellenőrzésnek is nevezik.
• Költséghatékony mechanizmust biztosít a hibák észlelésére.
• Ebben a technikában az egyes adategységekhez hozzáadott redundáns bitet paritásbitnek nevezik. Úgy van beállítva, hogy az egységben lévő egyesek teljes száma páros (páros paritás) vagy páratlan (páratlan paritás) legyen.

Longitudinális redundancia ellenőrzése

Ebben a hibaészlelési technikában egy bitblokkot táblázatba rendeznek. Az LRC módszer minden oszlophoz kiszámít egy paritásbitet, és ezt a paritásbit-készletet az eredeti adatokkal együtt elküldik. A paritásbit-blokk segít a vevőnek a redundancia ellenőrzésében és a hibák észlelésében.

Ciklikus redundancia ellenőrzés

A ciklikus redundancia-ellenőrzés redundáns bitek sorozatát fűzi az adategység végéhez úgy, hogy az eredményül kapott adategység pontosan osztható legyen egy második, előre meghatározott bináris számmal.

A célállomáson a bejövő adatokat ugyanazzal a számmal osztják el. Ha nincs maradék, az adategységet helyesnek tekintik, és elfogadják. Ellenkező esetben ez azt jelzi, hogy az adategység megsérült az átvitel során, és el kell utasítani.

Mi az a Hamming Code?

A Hamming-kód egy lineáris kód, amely akár két azonnali bithiba észlelésére és egybites hibák javítására is alkalmas. Az ilyen típusú hibajavítás jellemzően az adatkapcsolati rétegen működik, keretezi az adatokat és ellenőrzi azok integritását a szomszédos csomópontok között.

A Hamming-kódban a forráskód redundáns bitek hozzáadásával kódolja az üzenetet. Ezeket a redundáns biteket a rendszer az üzenet meghatározott pozícióiba illeszti be és generálja a hibaészlelés és -javítás végrehajtása érdekében.

Hamming története Code

• A Hamming-kód egy RW Hamming által fejlesztett technika a hibák észlelésére és javítására.
• Bármilyen hosszúságú adategységre alkalmazható, és az adatbitek és a redundanciabitek közötti kapcsolatot használja ki.
• Hamming a hibajavítás problémáján dolgozott, és egyre hatékonyabb algoritmusokat fejlesztett ki.
• 1950-ben publikálta a Hamming-kódot, amelyet ma is széles körben használnak olyan alkalmazásokban, mint az ECC memória.

Hamming alkalmazásai Code

Íme néhány gyakori Hamming-kód alkalmazás:

• Műholdak
• Számítógépes memória (ECC RAM)
• modemek
• PlasmaCAM
• Nyissa ki a csatlakozókat
• Árnyékolt vezeték
• Beágyazott processzorok

Hamming előnyei Code

• A Hamming-kód olyan hálózatokon hatékony, ahol az adatfolyamok egybites hibáknak vannak kitéve.
• Nemcsak a bithibákat észleli, hanem segít azonosítani a hibát tartalmazó bitet is, hogy az kijavítható legyen.
• A Hamming-kódok könnyű használhatósága alkalmassá teszi őket számítógépes memóriában és egyszeres hibajavításban való alkalmazásra.

Hamming hátrányai Code

• Ez egy egybites hibaészlelő és -javító kód. Ha több bit hibásnak bizonyul, az eredmény egy másik, valójában helyes bitet is megfordíthat, ami tovább torzítja az adatokat.
• A Hamming-kód algoritmusa csak egybites problémákat képes megoldani.

Hogyan kódoljunk üzenetet Hammingban Code

A küldő által az üzenet kódolására használt folyamat a következő három lépésből áll:

• Számítsd ki a redundáns bitek teljes számát.
• Határozza meg a redundáns bitek pozícióját.
• Számítsd ki az egyes redundáns bitek értékét.

Amikor a redundáns bitek beágyazódnak az üzenetbe, a teljes kódszó elküldésre kerül a vevőnek.

1. lépés) Számítsa ki a redundáns bitek teljes számát.

Tegyük fel, hogy az üzenet tartalmazza n adatbitek és p redundáns bitek, hozzáadva úgy, hogy 2^p legalább (n + p + 1) különböző állapotot jelezhet.

Itt az (n + p) az (n + p) bitpozíciók mindegyikében a hiba helyét veszi figyelembe, és egy plusz állapot a hiba hiányát jelzi. Mivel p paritásbit 2-t jelezhet^p kimondja, 2^p legalább (n + p + 1)-gyel kell egyenlőnek lennie.

2. lépés) Helyezze a redundáns biteket a megfelelő helyükre.

A p redundáns bitek a 2 hatványai – például 1, 2, 4, 8 és 16 – bitpozíciókban helyezkednek el. Ezeket p-nek nevezzük.₁ (az 1. pozícióban), p₂ (az 2. pozícióban), p₃ (a 4. pozícióban), és így tovább.

3. lépés) Számítsa ki az egyes redundáns bitek értékét.

Minden redundáns bit egy paritásbit, amely a csoportjában lévő 1-esek számát párossá vagy páratlanná teszi. A paritás két típusa a következő:

• Páros paritás: A fedett pozíciókban lévő 1-esek teljes száma páros lesz.
• Páratlan paritás: A fedett pozíciókban lévő 1-esek teljes számát páratlanná tesszük.

Minden paritásbit egy meghatározott pozíciókészletet fed le, amelyet a pozíciószámok bináris ábrázolása határoz meg:

• p₁ minden olyan pozíciót ellenőrz, amelynek bináris értékének legkisebb helyiértékű bitjében 1 szerepel – 1., 3., 5., 7., 9., 11. és így tovább.
• p₂ minden olyan pozíciót ellenőrz, amelynek bináris értékének jobbról a második bitjében 1 szerepel – 2., 3., 6., 7., 10., 11. és így tovább.
• p₃ minden olyan pozíciót ellenőrz, amelynek bináris értékének harmadik bitjében jobbról 1 szerepel – ez a 4–7., a 12–15. és így tovább pozíciók.

Kidolgozott példa (7,4): Tekintsük a négy adatbitet 1011Három paritásbit szükséges (2³ = 8 ≥ 4 + 3 + 1), ami egy hétbites kódszót eredményez, amely p-ként van leírva.₁ p₂ d₁ p₃ d₂ d₃ d₄Az adatok elhelyezése a 3., 5., 6., 7. pozíciókat a következőképpen állítja be: 1, 0, 1, 1. Páros paritás használatával: p₁ lefedi az 1., 3., 5., 7. pozíciókat (1., 0., 1. bit → p₁ = 0); p₂ lefedi a 2., 3., 6., 7. biteket (1., 1., 1. → p₂ = 1); p₃ lefedi a 4., 5., 6., 7. biteket (0., 1., 1. → p₃ = 0). A transmitA ted kódszó tehát 0110011.

Hogyan dekódoljunk egy üzenetet Hammingban Code

A fogadó fél fogadja a bejövő üzenetet, és újraszámításokat végez a hibák megtalálása és kijavítása érdekében. Az újraszámítási folyamat a következő lépésekből áll:

• Számold meg a redundáns bitek számát.
• Helyezze el helyesen az összes redundáns bitet.
• Végezze el a paritásvizsgálatot.

1. lépés) Számolja meg a redundáns bitek számát. Ugyanazt a képletet használd, mint a kódoláshoz: 2^p ≥ n + p + 1, ahol n az adatbitek száma, p pedig a redundáns bitek száma.

2. lépés) Helyezze el helyesen az összes redundáns bitet. Minden redundáns bit a 2 hatványának megfelelő bitpozícióban található – például 1, 2, 4 és 8.

3. lépés) Végezze el a paritásellenőrzést. A paritásbiteket az adatbitekből és a vett redundáns bitekből újraszámolja a rendszer:

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

Az újraszámított paritásbitek együttesen egy bináris számot alkotnak. Ha ez a szám nulla, akkor nincs hiba; egyébként az értéke az egyetlen hibás bit pontos pozícióját adja meg, amelyet aztán megfordít a rendszer az üzenet javítása érdekében.

GYIK