next up previous
Következő: Nyolcadik fejezet, bevezetés | Tartalomjegyzék | Előző: Párhuzamos interface (IEC-busz)

A digitális információ ellenőrzése

A digitális információ, illetve annak elemei természetesen meghibásodhatnak. Az információ az egyes készülékrészek között bonyolult áramköri rendszereken keresztül halad át, melyek spontán, rövididejű zavarokat produkálhatnak. Ha az egyes készülékrészek között nagyobb távolság van és valamely kábelt, telefonvonalat, vagy rádióösszeköttetést is igénybe kell venni, e hírközlő csatornák zajjelenségei szintén az információ eltorzulásához vezetnek. Természetesen az információban bekövetkező meghibásodást csak az eredeti információ kibővítésével - redundanciával - lehet detektálhatóvá tenni. (Az ismételgetés is lehetne egyfajta eljárás, de kimutatható, hogy igen kevéssé hatékony.) A redundancia legegyszerűbb használatos formája az ún. paritás ellenőrző bit használata. Egy n bitbol álló "információcsomaghoz" egy n+1-ik bitet is hozzáadnak. Ezt a bitet az n bitben található bitek modulo kettes összegeként állítják elő. (Néha ennek komplemensét használják.) A paritásbit tehát az információ érdemi részében található logikai 1-ek páros, vagy páratlan számáról tudósít. Ez az egyszerűen képezhető és ellenőrízhető paritásbit rendszer a gyakorlatban igen hasznos. Triviálisan átláthatóan alkalmas arra, hogy minden - az információtartalomban következő - páratlan számú meghibásodást detektálhatóvá tegyen. Maga az eljárás igen egyszerű: az információ elküldésénél, elrakásánál képezzük a paritásbitet, amit természetesen szintén elküldünk/elrakunk. A felhasználásnál az információs bitek alapján újraképezzük a paritásbitet és egybevetjük azzal, ami eredetileg volt. Ha ezek megegyeznek, akkor tudjuk, hogy vagy nem következett be hiba, vagy pedig páros számú bithiba fordult elő. Paritáshiba esetén a digitális rendszerek általában azonnal megállnak és csak külső beavatkozásra folytatják üzemüket. A paritáshiba bekövetkezése mindig valamely egység hibás müködésének eredménye, mely tüzetesebb kivizsgálást igényel. Az információ meghibásodásoktól való védelme nagyon sok matematikai kutatást indított és sok hasznos eredménnyel járt. A 7.5.1. ábra szerint a négyzetalakú keretben lévő információs bitekhez függőleges és vízszintes paritásbiteket állíthatunk elő. Ha most egyetlen bit meghibásodik, akkor ezt nemcsak észrevesszük, hanem a paritásbitek viszgálatából következtethetünk a hiba valószínű helyére is. Ha a hiba helyét tudjuk, akkor azt ki is javíthatjuk.


7.5.1. ábra


Általában az információhoz adott redundáns bitek révén az egyetlen paritásbittel védett egyszerű detektáláson jócskán túlléphetünk. Az esetleg ravasz algoritmusokkal képzett paritásbitekkel kiakuló kódrendszerek két lényeges csoportba oszthatók: vannak hibajelző és hibajavító kódok. Mindkét csoportot kiterjedten alkalmazzák pl. a telefonos adatátvitelben, űrkommunikációban, speciális feladatokban. A hibajavító képességű kódrendszerek illusztrálására az ún. Hamming-féle kód egy egyszerű változatát említjük, mely 4 információs bithez 3 speciálisan képzett paritásbitet ad, és ennek következtében 1 hiba helye megállapítható. A kódolás a következőképpen történik: az x1, x2, x3, x4 információs bitekből x5, x6, x7 paritásbitet képezünk a következő szabály szerint:

\begin{displaymath}x_1 +x_2 +x_3 +x_5 = {\rm p\acute{a}ros} \end{displaymath}


\begin{displaymath}x_1 +x_2 +x_4 +x_6 = {\rm p\acute{a}ros} \end{displaymath}


\begin{displaymath}x_1 +x_3 +x_4 +x_7 = {\rm p\acute{a}ros} \end{displaymath}

legyen. (Az összeadás természesen mod 2 értendő.) Ennek megfelelően a 1010 információ paritásbitekkel kibővítve: 1010010 lesz. Az információ vételekor tehát az x1 x2 x3 x4 információs bitekből a fenti szabály szerint p5, p6, p7 értékekkel összehasonlítjuk. A hiba helyének megállapítása:


hibás hiba helye
p5 x5
p6 x6
p7 x7
p5p6 x2
p5p7 x3
p6p7 x4
p5p6p7 x1


Természetesen, ha a hibás bitek száma egynél több, a rendszer helytelenül fog javítani. (Ha n információs bithez k paritásbitet adunk, és a kódrendszer egy hibát tud javítani, akkor az alábbi egyenlőtlenségnek kell fennálnia:

\begin{displaymath}2^k \ge (n+k)+1\quad .\end{displaymath}

A paritásbitekkel rá kell tudni mutatni a hibás bitre, amelyik vagy az információs bitek, vagy a paritásbitek között foglal helyet. Ezen túlmenően a hibamentes állapotot is jeleznie kell. )
next up previous
Következő: Nyolcadik fejezet, bevezetés | Tartalomjegyzék | Előző: Párhuzamos interface (IEC-busz)


1999-09-23