Hamming-kód: Hibaészlelés és -javítás példákkal

Mi az a hiba?

A továbbított adatok megsérülhetnek a kommunikáció során. Valószínűleg külső zaj vagy más fizikai meghibásodás befolyásolhatja. Ilyen helyzetben a bemeneti adatok nem egyezhetnek meg a kimeneti adatokkal. Ezt az eltérést „Hibának” nevezik.

Az adathibák fontos vagy biztonságos adatok elvesztéséhez vezethetnek. A digitális rendszerekben a legtöbb adatátvitel bitátvitel formájában történik. Még egy kis változtatás is befolyásolhatja az egész rendszer teljesítményét. Ha egy adatsorozatban az 1-et 0-ra, vagy a 0-t 1-re változtatjuk, azt „Bithiba”-nak nevezik.

A hibák típusai

A feladótól a vevő felé történő adatátvitel során főként háromféle bithiba fordul elő.

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

Egybites hibák

A teljes adatsorozatban egy biten végrehajtott változtatást „Egybites hibának” nevezik. Az egybites hiba előfordulása azonban nem olyan gyakori. Ezenkívül ez a hiba csak párhuzamos kommunikációs rendszerben fordul elő, mivel az adatok bitenkénti átvitele egyetlen sorban történik. Ezért nagyobb az esélye annak, hogy egyetlen vonal is zajos lehet.

Több bites hiba

Az adatszekvenciában, ha az adó és a vevő adatszekvenciájának két vagy több bitje megváltozik, azt „többbites hibának” nevezik.

Ez a fajta hiba többnyire soros és párhuzamos típusú adatkommunikációs hálózatokban is előfordul.

Burst hibák

Az adatsorozat bitkészletének változását „Burst error” néven ismerjük. Az ilyen típusú adathibák kiszámítása az első bit változásától az utolsó bitváltásig terjed.

Mi az a hibaészlelés és hibajavítás?

A digitális kommunikációs rendszerben a hiba átkerül egyik kommunikációs rendszerből a másikba. Ha ezeket a hibákat nem észleli és nem javítja ki, akkor az adatok elvesznek. A hatékony kommunikáció érdekében a rendszeradatokat nagy pontossággal kell továbbítani. Ez úgy történik, hogy először azonosítja a hibákat, és kijavítja azokat.

A hibadetektálás az adatkommunikációs rendszerben az adótól a vevő felé továbbított adatokban előforduló hibák észlelésének módszere.

Itt redundanciakódokkal keresheti meg ezeket a hibákat, hozzáadva az adatokhoz, amikor azokat a forrásból továbbítják. Ezeket a kódokat „Hiba észlelő kódoknak” nevezik.

A hibafelismerő kódok három típusa:

• 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 hibaészlelési mechanizmussal rendelkezik.
• Ebben a technikában a redundáns bitet paritásbitnek nevezik. Minden adategységhez hozzá van fűzve. Az egységben lévő 1-ek teljes számának párosnak kell lennie, amit paritásbitnek nevezünk.

Longitudinális redundancia ellenőrzése

Ebben a hibaészlelési technikában egy bitblokk táblázatos formátumban van rendezve. Az LRC módszer segít minden oszlop paritásbitjének kiszámításában. Ennek a paritásnak a halmazát is elküldi az eredeti adatokkal együtt. A paritásblokk segít a redundancia ellenőrzésében.

Ciklikus redundancia ellenőrzés

A ciklikus redundancia-ellenőrzés egy olyan redundáns sorozat, amelyet az egység végéhez kell csatolni. Ezért a kapott adategységnek oszthatóvá kell válnia egy második, előre meghatározott bináris számmal.

A célállomáson a bejövő adatokat ugyanennyivel kell elosztani. Ha nincs maradék, akkor az adategységet helyesnek tekintjük és elfogadjuk. Ellenkező esetben azt jelzi, hogy az adategység az átvitel során sérült, ezért el kell utasítani.

A Hamming-kódban a forrás úgy kódolja az üzenetet, hogy redundáns biteket ad hozzá az üzenethez. Ezeket a redundáns biteket többnyire beszúrják és előállítják az üzenet bizonyos helyein a hibaészlelési és -javítási folyamat végrehajtása érdekében.

A Hamming-kód története

• A Hamming kód az RWHamming által felépített technika a hibák észlelésére.
• A Hamming-kódot bármilyen hosszúságú adategységre alkalmazni kell, és az adat és a redundanciabitek közötti kapcsolatot használja.
• A hibajavító módszer problémáján dolgozott, és kifejlesztett egy Hamming-kódnak nevezett, egyre erősebb algoritmustömböt.
• 1950-ben kiadta a Hamming-kódot, amelyet ma széles körben használnak olyan alkalmazásokban, mint az ECC memória.

Hamming kód alkalmazása

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

• Műholdak
• Számítógépes memória
• modemek
• PlasmaCAM
• Nyissa ki a csatlakozókat
• Árnyékoló huzal
• Beágyazott processzor

A Hamming-kód előnyei

• A Hamming-kód módszer olyan hálózatokon hatékony, ahol az adatfolyamokat az egybites hibákra adják meg.
• A Hamming kód nem csak a bithiba észlelését biztosítja, hanem segít a hibát tartalmazó bit behúzásában is, hogy az javítható legyen.
• A hamming kódok egyszerű használatának köszönhetően a legjobban alkalmasak a számítógép memóriájában való használatra és az egyszeri hibajavításra.

A Hamming kód hátrányai

• Egybites hibaészlelő és -javító kód. Ha azonban több bit alaphibája van, akkor az eredmény egy másik bitet eredményezhet, amelyet helyesen kell megváltoztatni. Ez további hibákat okozhat az adatokban.
• A Hamming-kód algoritmus csak egybites problémákat képes megoldani.

Üzenet kódolása a Hamming-kódban

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

• A redundáns bitek teljes számának kiszámítása.
• A redundáns bitek helyzetének ellenőrzése.
• Végül kiszámítjuk ezeknek a redundáns biteknek az értékét.

Amikor a fenti redundáns bitek be vannak ágyazva az üzenetbe, az elküldésre kerül a felhasználónak.

Step 1) A redundáns bitek teljes számának kiszámítása.

Tegyük fel, hogy az üzenet tartalmazza:

• n– adatbitek száma
• p – a redundáns bitek száma, amelyek hozzáadódnak ahhoz, hogy np legalább (n + p + 1) különböző állapotokat jelezhessen.

Itt (n + p) a hiba helyét ábrázolja az (n + p) bitpozíciók mindegyikében, és egy extra állapot azt jelzi, hogy nincs hiba. Ahogy a p bitek 2-t jelezhetnek^p kimondja, 2^p legalább egyenlőnek kell lennie (n + p + 1).

Step 2) Helyezze a redundáns biteket a megfelelő helyre.

A p redundáns biteket 2-es hatványú bithelyzetekre kell helyezni. Például 1, 2, 4, 8, 16 stb. Ezekre p-ként hivatkozunk.₁ (az 1. pozícióban), p₂ (az 2. pozícióban), p₃ (a 4-es pozícióban) stb.

Step 3) A redundáns bit értékeinek kiszámítása.

A redundáns biteknek paritásbiteknek kell lenniük, így az 1-ek száma páros vagy páratlan.

A kétféle paritás ?

• Az üzenetben lévő bitek teljes számát párosnak nevezzük páros paritásnak.
• Az üzenetben páratlan bitek teljes számát páratlan paritásnak nevezzük.

Itt az összes redundáns bitet (p1) paritásként kell kiszámítani. Le kell fednie az összes olyan bitpozíciót, amelyek bináris reprezentációjában 1-et kell tartalmaznia az 1. pozícióban, kivéve a p1 pozícióját.

P1 az összes adatbit paritásbitje olyan pozíciókban, amelyek bináris ábrázolása 1-et tartalmaz a kevésbé fontos pozícióban, amely nem tartalmazza az 1 Like-ot (3, 5, 7, 9, …. )

P2 a paritásbit minden olyan pozícióban lévő adatbithez, amelyek bináris ábrázolása 1-et tartalmaz a 2-es pozícióban jobbról, a 2 Like (3, 6, 7, 10, 11,…) nélkül.

A P3 minden olyan bit paritásbitje, ahol a bináris reprezentáció 1-et tartalmaz a 3-as pozícióban jobbról, de nem tartalmazza a 4-et Like (5-7, 12-15,… )

Üzenet visszafejtése Hamming-kódban

A vevő megkapja a bejövő üzeneteket, amelyek újraszámítást igényelnek a hibák megtalálásához és kijavításához.

Az újraszámítási folyamat a következő lépésekben történik:

• A redundáns bitek számának számolása.
• Az összes redundáns bit helyes elhelyezése.
• Paritásellenőrzés

Step 1) A redundáns bitek számának számolása

Ugyanazt a képletet használhatja a kódoláshoz, a redundáns bitek számához

2^p ? n + p + 1

Itt az adatbitek száma és p a redundáns bitek száma.

Step 2) Az összes redundáns bit helyes elhelyezése

Itt p egy redundáns bit, amely 2, például 1, 2, 4, 8 stb. hatványok bitpozícióin található.

Step 3) Paritásellenőrzés

A paritásbiteket az adatbitek és a redundáns bitek alapján kell kiszámítani.

p1 = paritás(1, 3, 5, 7, 9, 11…)

p2 = paritás(2, 3, 6, 7, 10, 11…)

p3 = paritás(4-7, 12-15, 20-23…)

Összegzésként

• A továbbított adatok megsérülhetnek a kommunikáció során
• A bithiba három típusa: 1) Egybites hibák 2) Többbites hiba 3) Burst Bit hibák
• A teljes adatszekvenciában egy biten végrehajtott változtatást „egybites hibának” nevezik.
• Az adatszekvenciában, ha az adó és a vevő adatszekvenciájának két vagy több bitje megváltozik, azt „többbites hibának” nevezik.
• Az adatsorozat bitkészletének változását „Burst error” néven ismerjük.
• A hibadetektálás az adatkommunikációs rendszerben az adótól a vevő felé továbbított adatokban előforduló hibák észlelésének módszere.
• Háromféle hibaészlelési kód: 1) Paritásellenőrzés 2) Ciklikus redundancia-ellenőrzés (CRC) 3) Longitudinális redundancia-ellenőrzés (LRC)
• A Hamming kód egy vonalkód, amely akár két azonnali bithiba észlelésére is használható. Egybites hibákra képes.
• A Hamming kód az RWHamming által felépített technika a hibák észlelésére.
• A Hamming-kód használatának gyakori alkalmazásai a műholdas számítógépmemória, a modemek, a beágyazott processzor stb.
• A hamming kód módszer legnagyobb előnye azokon a hálózatokon hatékony, ahol az adatfolyamokat az egybites hibákra adják.
• A hamming kód módszer legnagyobb hátránya, hogy csak egybites problémákat tud megoldani.
• Az üzenet titkosítását és dekódolását hamming kód segítségével tudjuk végrehajtani.