I. Az információtovábbítás folyamatának alapjai

MKK KM I. 8. Előadás

Készítette Dr. Zachár András

I. Az információtovábbítás folyamatának alapjai Általános elméleti alapok Az információátviteli csatornán végrehajtott adatátvitel során az adó megváltoztatja a csatorna fizikai közegének valamilyen tulajdonságát, ami az adott közegen tovább terjed, és a vevő ezt a fizikai közegváltozást érzékeli. Például vezetékek esetén az átfolyó áram változhat, vagy a feszültség, vagy ha az átviteli közegnek nem egy vezetéket, hanem magát az elektromágneses hullámot használjuk, akkor például a hullám amplitúdójának (AM), frekvenciájának (FM), vagy fázisának változása hordozhat információt. adóberendezés

Elsődleges közlés

vevőberendezés

q-adikus alak

kódoló berendezés

dekódoló berendezés

Fizikai jelek Modulátor

információs csatorna

Demodulátor

Zaj Az információtovábbítás folyamatának sémája A digitális hálózati terminológiában sokszor használják a sávszélesség fogalmát, amin a maximális információ átviteli sebességet értik, az adott kommunikációs csatornára. Valójában a sávszélesség az analóg rendszerek esetén használt fogalom, amin egy analóg jel maximális és minimális frekvenciájának különbségét értik. Például az emberi beszéd frekvenciájának alsó sávja 300 Hz a felső frekvenciája 3300 Hz, így a sávszélessége 3 kHz. Digitális hálózatok esetén az adatátviteli sebességet célszerű az időegység alatt átvitt bitek számával jellemezni (bit/sec). Analóg információ átvitel A távközlés területén napjainkig az analóg átvitel volt túlnyomórészt az uralkodó. A jeleket valamelyik fizikai jellemzőjük (pl. feszültségük) időben folytonos változtatásával vitték át. Digitális információ átvitel A digitális elektronika és a számítógépek gyors fejlődése miatt, az analóg átvitelről lassan az adatátvitel minden területén kezdenek a digitális információátvitelre áttérni. A digitális információ átvitel alapvetően abban különbözik az analógtól, hogy a folyamatos jelek helyett 0-kból és 1-ekből álló sorozatok haladnak az információátviteli vonalakon. A digitális átvitel több szempontból jobb, mint az analóg átvitel. Először is nagyon kicsi az átvitel során keletkező hibák aránya az analóg átvitelhez viszonyítva. Analóg átvitel esetén erősítőket használnak az átviteli vonalakon fellépő csillapítások kompenzálására, azaz a jel regenerálására. Ez számos szempont miatt nem lehet tökéletes (az egyes eszközök öregedési folyamata, hőmérséklet 1



okozta elérések). Mivel a hibák halmozódnak, ezért a sok erősítőn átmenő jelek nagymértékben torzulhatnak. Ezzel szemben a digitális jelek tökéletesen helyreállíthatóak, mivel csak két különböző értéket, a 0-t és az 1-et vehetik fel. A digitális jelek helyreállításakor nem lép fel halmozódó hiba. A digitális átvitel egy másik nagy előnye, hogy egyetlen eszköz hatékonyabb kihasználásával, különböző típusú adatok (hang, zene, normáladat, kép) kevert átvitelét teszi lehetővé. Ezt természetesen a különböző típusú adatok bináris alakra kódolásával oldható meg. Digitális jelek fizikai kódolása A fizikai vonalon való átvitelnél a bitek ábrázolására többféle lehetőség is van. Ezek közül a legegyszerűbb az, amikor minden bitet értékétől függően két feszültségszinttel ábrázolunk. Az alábbiakban röviden a gyakorlatban használt megoldásokat tekintjük át. ¾

NRZ – Non Return to Zero – Nullára vissza nem térő. Ebben az esetben mindig az a feszültség van a vonalon, amit az ábrázolt bit határoz meg. Ez a leginkább gyakori, természetes jelforma. Ha egy bit 1-es, akkor a feszültség a teljes bit idő alatt felső (H) szintű, ha 0-s, akkor végig alacsony (L) szintű. Két vagy több egymás utáni 1-es bit esetén a feszültség megszakítás nélkül H-ban marad, a megfelelő ideig, az egyesek között nem tér vissza nullára. Nem túl jó megoldás mert magas az egyenfeszültség összetevője (V/2), és nagy sávszélességet igényel, valamint az sem előnyös, hogy polarizált a jel.

0

1

1

1

0

1

0

1

0

+V

0

1

1

0

NRZ kódolás ¾

RZ – Return to Zero – Nullára visszatérő. Nulla a “nyugalmi” állapot, 1 bitnél a bitidő első felében a felső (H) állapotban, a második felében a jel visszatér 0-ra. 0

1

1

1

0

1

0

+V

1

0

0

1

1

0

RZ kódolás Az NRZ kódoláshoz képest vannak előnyei: egyenfeszültség összetevője csak (V/4), ha az adat csupa egyest tartalmaz, akkor is vannak jelváltások, így nem jelentkeznek az ilyenkor fellépő szinkronizációs problémák, viszont a legrosszabb a sávszélesség igénye. Viszont ha sok a nulla egymásután, akkor már jelentkeznek szinkronizálási problémák, mivel nincsenek jelváltások. Ebben az esetben például azt a megoldást választják, hogy minden egymás után következő öt nulla után az adó beszúr egy 1-t is, amit aztán a vevő eltávolít a bitfolyamból.

2


¾


NRZI – Non Return to Zero Invertive– Nullára nem visszatérő, invertált. A nulla bitnek a nulla szint felel meg, az egy értékű bithez vagy nulla, vagy +V szint tartozik az alábbi szabály szerint. Ha az előző egyeshez nulla szint tartozott, akkor +V lesz, ha az előző egyeshez +V tartozott, akkor a 0 szint lesz a bithez rendelt feszültség. A nulla bitet követő 1 értékű bit mindig +V feszültségű. 0

1

1

0

0

1

1

1

1

1

0

+V

1

0

NRZI kódolás ¾

PE – Phase Encode – Manchester kódolás. Ennél a kódolási módszernél a jelátmenet hordozza az információt, és a jelátmenet irányának fontos jelentősége van, mivel a 0–1 átmenet jelentheti az 1-es bitet, az 1–0 átmenet, pedig a 0-s bitet. Akkor, amikor több azonos bit követi egymást, akkor a jelnek a két bit között félidőben vissza kell térnie az eredeti szintre azért, hogy a következő bit idején ugyanolyan irányú átmenet következhessen. A jel detektálásakor és visszaállításakor az alapfrekvenciás bit értékeket el kell különíteni a kétszeres frekvenciájú hamis átmenetektől. Mivel ennél a kódolási technikánál az információt a jelátmenetek hordozzák, kiválóan alkalmas mágneses adatrögzítésre. Mivel minden bitnél van jelváltás, így a szinkronizálás nem okoz problémát. Az egyenfeszültségű összetevője nulla. 0

1

1

1

0

1

0

1

+V

0

0

1

1

0

Manchester kódolás A fenti módszerek közül a gyakorlatban az RS-232-es protokoll az NRZ kódolási módszert használja, a Manchester kódolást, pedig az Ethernet hálózatok használják.

3



II. Kódelméleti alapok II.1. Alapfogalmak Az információ átvitelben, illetve az információrögzítésben (háttértárakon) alapvetően kétféle problémakör merülhet fel az átvinni vagy letárolni kívánt adatokkal. ¾ Egyrészről szeretnénk, ha az adatátvitel minél gyorsabb lenne egy adott fizikai sebességű vonalon. Ezt úgy kell érteni, hogy ha fizikailag az átviteli teljesítmény nem fokozható valamilyen ok miatt, akkor milyen egyéb ”trükkök” segítségével lehet mégis nagyobb mennyiségű adatot ”áterőszakolni” egy korlátos átviteli képességű vonalon. Erre a problémára kézenfekvő módon kínálkozik az adatok tömörítésének technikája. Ez a problémakör elsősorban arról szól, hogy milyen módon lehet egy elsődleges közlést (átvinni kívánt adatot) minél rövidebb formában az adatátviteli vonalra rávinni, hogy annak egyértelműsége és érthetősége ne csorbuljon. ¾ A másik probléma kör az, amikor az átviteli vonal valamilyen zavaró zajjal vagy hibákkal terhelt. Ekkor a feladat arról szól, hogy egy elsődleges közlést, amit az adó ad le a vevő irányába, még a vevő oldalon is egyértelműen dekódolni lehessen, azaz a közlés információtartalma az átvitel során nem sérüljön. A fenti két technika az adatok méretének szemszögéből nézve teljesen egymásnak ellentmondó eredményre vezet, mivel tömörítéskor az átvitt adatcsomag mérete csökkenni fog, az átviteli sebesség fokozása érdekében. Viszont ha az adatok hibamentes átvitelének biztonságát akarjuk fokozni, akkor óhatatlanul redundáns adatokat kell hozzáfűznünk a már meglévő adatokhoz, hogy az adatok esetleges sérülése esetén is a vevő fél, aki semmit sem tud az eredeti közlésről, vissza tudja állítani az adó által leadott teljes információ csomagot. Első témakör az adatok tömörítésének problémaköre, a másik a hibajavító kódok területe. Az alábbiakban csak az előbbivel fogunk részletesen foglalkozni. Az adókészülék általában valamilyen A= {a1, a2, …, an} kimeneti ábécé jeleit küldi ki, és a vevőkészülék ezeket a jeleket fogja fel. Az A ábécé jeleiből alkotott ai1 ai2…aik sorozatokat elsődleges közlésnek nevezzük. Vegyük például egy távirat továbbításának esetét. Itt az adó- és a vevőberendezés is egy-egy telexgép, az információs csatorna, pedig a távíróvonal. A kimeneti ábécé a latin betűs ábécé jelei, az elsődleges közlések, pedig maguk a táviratszövegek. Az információs csatorna fizikai jellemzői általában csak bizonyos rögzített számú különböző jeltípus továbbítására és azok biztos felismerésére alkalmasak. Ezt a számot célszerű a továbbiakban q-val jelölni. Általában a q szám sokkal kisebb, mint ahány betű az adott ábécében van. Az alábbiakban tételesen felsoroljuk az információ átvitel alapvető fázisait. ¾ Az elsődleges közlés átalakítása q-adikus alakra. ¾ A q-adikus alak átalakítása fizikai jelekké ¾ A jelek kiküldése az információs csatornába ¾ A jelek felfogása a vevőberendezésben ¾ A fizikai jelek visszatranszformálása q-adikus jelekké ¾ Az elsődleges közlés előállítása a q-adikus alakból

4



Az első és a hatodik fázist nevezik kódolásnak, illetve dekódolásnak, a másodikat és az ötödiket, pedig modulálásnak és demodulálásnak. Napjainkban, az információátvitel gyakorlatában a fent felsorolt hat fázist már egyetlen eszköz végzi el, például az otthoni telefonos Internet kapcsolatokat megvalósító modemek (modulátor, demodulátor) mind a hat funkciót ellátja. A gyakorlatban az információs csatorna rendszerint csak kétféle jel továbbítására alkalmas (azaz q=2), ezekhez a számokhoz a 0 és az 1 jeleket rendeljük. Legyen A= {a1, a2, …, an} egy tetszőleges kimeneti ábécé és legyen K= {α1, α2, …, αn} véges hosszúságú bináris sorozatoknak valamilyen n elemű halmaza. A sorozatokról nem tesszük fel, hogy mind azonos hosszúságú, azaz például lehet egy kód a következő alakú {110, 101, 1100, 1010} Rendeljük most hozzá az ai ∈ A betűk mindegyikéhez a K halmaz egy-egy αi elemét, úgy hogy a különböző betűkhöz különböző bináris sorozatok tartozzanak. Ekkor tetszőleges ai1 ai2…aik elsődleges közléshez egy αi1 αi2…αik bináris sorozatot tudunk rendelni. 1. Definíció: A kódolásnak azt a formáját, melynél a kimenteti ábécé minden ai betűjéhez egy-egy α i ∈ K bináris sorozatot rendelünk, betűszerinti kódolásnak nevezzük. 2. Definíció: A K halmazt kódnak, az α1, α2, …, αn elemeket kódszavaknak, a kódszavak tetszőleges sorozatát pedig kódolt közlésnek nevezzük. 1. Példa: Legyen A= {a, b, c, d} egy kimeneti ábécé a {00, 01, 100, 101} halmaz, pedig a kód, felsorolás szerinti sorrendben egymáshoz rendelve. Ekkor a dac sorozatnak, mint elsődleges közlésnek az 10100100 bitsorozat felel meg. Felmerül a kérdés, hogy vajon a bináris sorozatból egyértelműen visszaállítható-e az eredeti (elsődleges) közlés. Ennek pontosabb elemzésére felhasználhatjuk a matematikából megismert függvény fogalmat, mivel a kódolásnak nevezett eljárást úgy is tekinthetjük, hogy minden egyes elsődleges közléshez hozzárendelünk egy-egy kódolt közlést f : A* a {0,1}* , ahol az A* jelöli, az Abeli elemek összes véges sorozatából álló halmazt, {0,1}* pedig az összes lehetséges 0 és 1-ből álló sorozatok véges halmazát. Hogy az eredeti elsődleges közlést a kódolt formából visszakaphassuk, azaz a dekódolás elvégezhető legyen, léteznie kell egy f −1 :{0,1}* a A* inverz függvénynek. Ilyen függvény nyilván akkor létezik, ha f kölcsönösen egyértelmű, azaz különböző A*-beli szavakhoz különböző {0,1}*-beli elemeket rendel. 2. Példa: Legyen A= {a, b, c, d} a kimeneti ábécé, a {00, 01, 11, 0001} halmaz, pedig a kód, felsorolás szerinti sorrendben egymáshoz rendelve. Ez a kód nem egy-egyértelmű, mivel az ab illetve a d sorozatoknak egyaránt a 0001 bitsorozat felel meg. 3. Definíció: A K={α1, α2, …,αn} kódot felbonthatónak nevezzük, ha tetszőleges bináris sorozat legfeljebb egyféleképpen bontható kódszavak szorzatára. II.2. Felbonthatósági feltételek Ha a K–beli kódszavak hossza mind egyenlő, akkor a K kód nyilvánvalóan felbontható lesz, azonban adható egy ennél általánosabb feltétel is a felbonthatóságra, mivel minket éppen olyan esetben érdekel a tömörítések miatt a felbonthatóság, amikor nem egyenlők az egyes kódszavak. 4. Definíció: A K kódot prefix kódnak nevezzük, ha egyetlen kódszó sem valódi kezdőszelete (prefixuma) egy másik kódszónak

5



Ezen definíció alapján azok a kódok, amelyek egyenlő hosszúságú kódszavakból állnak, természetesen valamennyien prefix kódok lesznek, mivel a kód minden szava különböző bináris jelsorozat, így egyik sem lehet a másik valódi kezdőszelete. 3. Példa: A K1={00, 01, 11, 0001} kód nem prefix kód, mivel a negyedik eleme például valódi kezdő részeként (kezdőszelete) tartalmazza a kód első elemét. A K2={00, 01, 100, 101} viszont prefix kód, mivel egyik elemének sem kezdőrészlete valamelyik másik eleme. 1. Tétel: Minden prefix kód felbontható Bizonyítás: Tegyük fel, hogy a K={α1, α2, …,αn} prefix kód nem felbontható. Ez azt jelenti, hogy létezik olyan β bináris sorozat, amelyet legalább két különböző módon tudunk kódszavak szorzatára bontani. Legyen β bináris sorozatnak ez a két felbontása β =αi1 αi2…αis és β =αj1 αj2…αjt . Jelöljük Lel azt a legkisebb számot, melyre α iL ≠ α jL , ilyen L az indirekt feltevés miatt kell, hogy létezzen.

β =αi1 αi2…αis = αj1 αj2…αjt , A kiinduló feltevés miatt, αi1 αi2…αL-1 = αj1 αj2…αjL-1 , valamint az egyenlőségekből, azt kapjuk, hogy αiL αiL+1…αs = αjL αjL+1…αjt . De viszont az indirekt feltétel miatt tudjuk, hogy α iL ≠ α jL , ekkor viszont az αiL és αjL szavak közül a nem hosszabbik kezdőszelete lesz a másiknak, ami viszont ellentmond az indirekt feltevésünknek, hogy a K kód prefix kód.

σ

αi1

αi2

αi3

…

αiL-1

αiL

αj1

αj2

αj3

…

αjL-1

αjL

A bizonyításban felhasznált bináris szavak struktúráját mutatja a fenti ábra II.3. Optimális kódok Tegyük fel, hogy valamilyen nyelven, például magyarul kell egy szöveget kódolva továbbítani. Ebben a szövegben az egyes betűk különböző gyakorisággal fordulnak elő. Például a magyar nyelvű szövegekben az e, a betűk jóval nagyobb gyakorisággal fordulnak elő, mint az ö, c, f betűk. Ahhoz, hogy a kódolt szöveget, minél gyorsabban tudjuk továbbítani, ahhoz a leggyakrabban előforduló betűkhöz a legrövidebb kódszavakat kell hozzárendelni, a ritkábban előforduló betűk, pedig a hosszabb kódszavakkal is kódolhatóak. Legyen adva egy F jelforrás, amely egy A= {a1, a2, …, an} kimeneti ábécé betűit véletlenszerűen bocsátja ki, méghozzá az egymás utáni jeleket egymástól függetlenül. Jelölje a pi annak a valószínűségét, hogy az F által kibocsátott jel ai. A továbbiakban tegyük fel, hogy ezekre a n

valószínűségekre teljesülnek a pi>0 feltételek és a

∑p i =1

i

= 1 egyenlőség is fenn áll. Más szavakkal a pi

valószínűség azt jelenti, hogy elég hosszú pl M számú jelből álló jelsorozat esetén a benne előforduló ai–k száma közelítőleg pi M. Tegyük fel, hogy az F jelforrás által kibocsátott jeleket egy K={α1, α2, …,αn} felbontható kóddal kódoltuk és legyen h1, h2, …, hn rendre az α1, α2, …,αn K-beli kódszavak hossza. 6



Egy M hosszúságú jelsorozat ai1ai2…aiM átlagos hossza kódolt formában, a következő módon adható meg. h1 p1 M + h2 p 2 M + K + hn p n M = M

n

∑p i =1

i

hi

n

Ha a L( K ) = ∑ pi hi összeg értékét tudjuk csökkenteni, akkor csökken a kódolt közlés αi1αi2…αiM i =1

átlagos hossza is. Az L(K) mennyiséget az F jelforrás K kód melletti költségének nevezzük. 2. Tétel: Tetszőleges F jelforráshoz létezik optimális prefix kód. A McMillan egyenlőtlenség

∑( 2 )≤ 1 n

−li

i =1

n ⎛1⎞ Definíció: A H ( F ) = ∑ pi log 2 ⎜⎜ ⎟⎟ mennyiséget az F jelforrás entrópiájának nevezzük. i =1 ⎝ pi ⎠

Példa: Legyen megadva egy F jelforrás A= {a, b, c, d, e, f} a kimeneti ábécéje, az ábécé egyes betűihez tartozó valószínűségek pedig rendre {0.3, 0.2, 0.2, 0.15, 0.1, 0.05}. számítsuk ki az F jelforrás entrópiáját. n ⎛1⎞ H ( F ) = ∑ pi log 2 ⎜⎜ ⎟⎟ = 0.3 log2 (1/0.3) + 0.2 log2 (1/0.2) + 0.2 log2 (1/0.2) + 0.15 log2 (1/0.15) + 0.1 i =1 ⎝ pi ⎠ log2 (1/0.1) + 0.05 log2 (1/0.05) = H(F) = 2.408695.

A számítást célszerű Excelben elvégezni, de ha nem áll rendelkezésre kisebb munkával egy egyszerű számológép is megteszi. 3. Tétel Shannon tétele az úgynevezett zajmentes csatornákra Egy F jelforráshoz tartozó tetszőleges K felbontható kódra teljesül, hogy L( K ) ≥ H ( F ) . 3. Tétel bizonyítása n n ⎛ ⎛1⎞ n H ( F ) − L( K ) = ∑ pi log 2 ⎜⎜ ⎟⎟ − ∑ pi li = ∑ ⎜ pi ⎜ i =1 i =1 ⎝ ⎝ pi ⎠ i =1 n ⎛ H ( F ) − L( K ) = ∑ ⎜ pi ⎜ i =1 ⎝

⎛ ⎞⎞ ⎛ ⎞ ⎜ log 2 ⎜ 1 ⎟ − li ⎟ ⎟ ⎟ ⎜ ⎜ ⎟⎟ ⎝ pi ⎠ ⎝ ⎠⎠

⎛ ⎞⎞ n ⎛ ⎛ ⎞ ⎜ log 2 ⎜ 1 ⎟ − log 2 2li ⎟ ⎟ = ∑ ⎜ pi ⎜p ⎟ ⎜ ⎟ ⎟ i =1 ⎜ ⎝ i⎠ ⎝ ⎠⎠ ⎝

( )

7

⎛ ⎛ − li ⎜ log 2 ⎜ 2 ⎜ p ⎜ ⎝ i ⎝

⎞ ⎞ ⎞⎟ ⎟⎟ ⎟ ⎟ ⎠ ⎠ ⎟⎠



Felhasználva azt a jól ismert összefüggést, hogy ln ( x ) ≤ x − 1 , és ebből következik, hogy 1 log 2 ( x ) ≤ ( x − 1) . Ezt felhasználva, pedig már egyszerűen adódik, az alábbi állítás ln (2) ⎛ H ( F ) − L( K ) = ∑ ⎜ pi ⎜ i =1 ⎝ n

H ( F ) − L( K ) ≤

⎛ ⎛ −li ⎜ log 2 ⎜ 2 ⎜ p ⎜ ⎝ i ⎝

(

n ⎞ ⎞ ⎞⎟ n ⎛ pi ⎛ 2− li ⎞⎞ 1 ⎛ n − li ⎟⎟ ⎟ ≤ ∑ ⎜ ⎟⎟ ⎟ = ⎜⎜ ( pi )⎞⎟ 1 − − 2 ⎜ ∑ ∑ ⎟ ⎟ i =1 ⎜ ln(2) p ⎟ ln(2) ⎝ i =1 i =1 ⎠ ⎠⎠⎠ ⎠⎠ ⎝ i ⎝

(

)

)

⎞ 1 ⎛ n ⎜ ∑ 2− li − 1⎟ . ln(2) ⎝ i =1 ⎠

Itt felhasználva a McMillan egyenlőtlenséget, már adódik Shannon tételének állítása.

II.4. Optimális kódok Huffmann-féle konstrukciója Az eddigiekben röviden ismertetve lett, hogy tetszőleges jelforrás esetén létezik optimális kód egy tetszőleges jelforrás kimeneti ábécéjéhez. Most egy olyan algoritmust ismertetünk, amellyel az optimális kódot létre is lehet hozni. Tegyük fel, hogy egy F jelforrás kimenő ábécéje A= {a1, a2, …, an}, az egyes betűkhöz tartozó valószínűségek, pedig rendre p1, p2, …, pn, ahol p1 ≥ p 2 ≥ K ≥ p n . 4. Tétel: Az F jelforráshoz létezik legalább egy K={α1, α2, …,αn} optimális prefix kód, amelyre h1 ≤ h2 ≤ K ≤ hn −1 = hn és az utolsó két kódszó α 0 és α1 alakú. Az α 0 és α1 alak úgy értendő, hogy alfa helyén egy tetszőleges hosszúságú bináris jelsorozat áll, és az α 0 valamint α1 ennek a tetszőleges bináris sorozatnak plusz egy nullával és egy, egyessel végződő alakjai. α 0 = 10011010 és α1 = 10011011 ahol α =1001101. A 4. tétel tehát azt mondja ki, hogy az optimális prefix kód, amit megszeretnénk konstruálni biztosan úgy fog kinézni, egyrészről a két utolsó kódszavának hossza megegyezik, valamint ez a két utolsó kódszava teljesen megegyezik az utolsó bitjeiket kivéve, ahol azok különbözőek, azaz az egyiknél egyes, a másiknál nulla az utolsó bit. 5. Tétel: Legyen adva F jelforrás A= {a1, a2, …, an} kimenő ábécével, és a betűkhöz tartozó p1 ≥ p 2 ≥ K ≥ p n valószínűségekkel. Legyen továbbá K={α1, α2, …,αn} az F jelforráshoz tartozó optimális prefix kód. Tegyük fel, hogy pi = q1 + q 2 , és p1 ≥ p 2 ≥ K ≥ pi −1 ≥ pi +1 K ≥ p n ≥ q1 ≥ q 2 . Ekkor a K’={α1, α2, …,αi-1, αi+1,…,αn, αi0, αi1} optimális prefix kód lesz arra az F’ jelforrásra nézve, melynek kimenő ábécéje A’= {a1, a2, …, an+1}, a betűkhöz tartozó valószínűségek, pedig rendre p1 , p 2 ,K, pi −1 , pi +1 ,K, p n , q1 , q 2 . Az optimális kód Huffmann-féle előállítása 5. és a 4. tételek módot adnak arra, hogy az n+1 betűt kibocsátó jelforráshoz tartozó optimális kód keresését visszavezessük az n betűs jelforrás esetére. Legyen ugyanis az F’ jelforráshoz tartozó ábécé A’= {a1, a2, …, an, an+1}, és a betűknek megfelelő valószínűségek p1 ≥ p 2 ≥ K ≥ p n ≥ p n +1 .

8



Tekintsük ekkor azt az F jelforrást, amelynek kimenő ábécéje B= {b1, b2, …, bn}, a valószínűségek, pedig p1 ≥ p 2 ≥ K ≥ pi −1 ≥ p n + p n +1 ≥ pi +1 K ≥ p n −1 . Ha K={α1, α2, …,αn} optimális F-re nézve, akkor a K’={α1, α2, …,αi-1, αi+1,…,αn, αi0, αi1} kód F’ jelforrásra nézve lesz optimális. Az ábécé betűszámának fokozatos csökkentésével tehát végül ahhoz a feladathoz jutunk el, melynél egy redukált kétbetűs ábécéhez kell optimális kódot megadni. Ebben az esetben viszont a {0,1} kód nyilván optimális lesz. A fent ismertetett, az optimális kód előállítására vonatkozó eljárást felfedezőjéről, az amerikai Huffmannról nevezték el Huffmann-féle módszernek. A fent ismertetett eljárás jól algoritmizálható, így közvetlenül programot is lehet rá írni. 1. Példa Legyen A= {a, b, c, d, e, f, g} a kimeneti ábécé, az ábécé egyes betűihez tartozó valószínűségek pedig rendre 0.2, 0.2, 0.19, 0.12, 0.11, 0.09, 0.09. Az alábbi két táblázat az algoritmus egyes lépéseit világosan mutatja. A B C D E F G

0.2 0.2 0.19 0.12 0.11 0.09 0.09

0.2 0.2 0.19 0.18 0.12 0.11

0.23 0.2 0.2 0.19 0.18

0.37 0.23 0.2 0.2

0.4 0.37 0.23

0.6 0.4

A B C D E F G

10 11 000 010 011 0010 0011

10 11 000 001 010 011

01 10 11 000 001

00 01 10 11

1 00 01

0 1

2. példa A második példában egy adott szövegben az egyes karakterek előfordulásának gyakoriságát adtuk meg, majd a gyakoriság alapján kiszámoltuk az egyes karakterek szövegben való megjelenésének valószínűségét. Eredeti szöveg: A GYEREKEK VESZEKSZENEK A statisztika alapján 23 db karakter található a fenti szövegben, az alábbi megoszlásban. Gyakoriság 7 db E 4 db K 2 db S 2 db Z 2 db szóköz

Valószínűségek 7/23 4/23 2/23 2/23 2/23

Gyakoriság 1 db A 1 db R 1 db N 1 db G 1 db Y 1 db V 9

Valószínűségek 1/23 1/23 1/23 1/23 1/23 1/23


E K S Z

7/23 4/23 2/23 2/23 Szóköz 2/23 A 1/23 R 1/23 N 1/23 G 1/23 Y 1/23 V 1/23 E K S Z

01 10 0010 0011 Szóköz 0000 A 1110 R 1111 N 1100 G 1101 Y 00010 V 00011


7/23 4/23 2/23 2/23 2/23 2/23 1/23 1/23 1/23 1/23

01 10 0010 0011 0000 0001 1110 1111 1100 1101

7/23 4/23 2/23 2/23 2/23 2/23 2/23 1/23 1/23

7/23 4/23 2/23 2/23 2/23 2/23 2/23 2/23

01 10 0010 0011 0000 0001 110 1110 1111

7/23 4/23 4/23 2/23 2/23 2/23 2/23

01 10 0010 0011 0000 0001 110 111

10

7/23 4/23 4/23 4/23 2/23 2/23

7/23 4/23 4/23 4/23 4/23

8/23 7/23 4/23 4/23

01 10 11 0010 0011 0000 0001

01 10 11 000 0010 0011

01 10 11 000 001

8/23 8/23 7/23

00 01 10 11

15/23 8/23

1 00 01

0 1



III. Hibadetektáló és hibajavító kódolás Az információátvitel gyakorlatilag is fontos eseteiben az információátviteli csatorna általában nem működik kellő biztonsággal. Az információátviteli csatornát egy úgynevezett csatorna alapzaj is terheli, ami azt jelenti a gyakorlatban, hogy a feladó által küldött üzenet lényegesen módosulhat, mire a vevő félhez megérkezik. Az alábbiakban következő részben különböző hibadetektáló és hibajavító eljárásokat, módszereket vizsgálunk meg. III.1. Egyedi hibák detektálása, javítása

Ebben az alfejezetben olyan hibadetektáló és hibajavító módszerek kerülnek bemutatásra, melyek azonos hosszúságú kódszavakból állnak, és védekezni tudnak, a zaj okozta hibáktól. Az azonos hosszúságú kódszavakból felépített kódolás esetén a kódszavakat blokkoknak a blokkok hosszát, pedig blokk méretnek szokás nevezni. Definíció: Azt mondhatjuk, hogy az információs csatorna t darab egyedi hibát okoz, ha a csatorna alapzajának hatására tetszőleges blokkban legfeljebb t jel értéke változik meg. A megváltozott jelek a blokkon belül bármilyen elrendeződésben előfordulhatnak. Könnyen megadható olyan kód, amivel egy darab hibát feltudunk ismerni egy blokkon (kódszón) belül. Legyen ez a kód olyan, hogy minden egyes kódszavának első és második fele megegyezik. Ebben az esetben az 1 hibát okozó zaj csak a kódszó egyik felét tudja elrontani. Ezúton pedig észrevehető dekódoláskor, hogy a kódszó első és második fele eltér egymástól, azaz az információ átvitel folyamata során valamelyik biten módosulás (hiba) történt. Ehhez hasonlóan arra is lehetőség kínálkozik, hogy az 1 hibát ne csak felismerni, hanem korrigálni is tudjuk, még pedig olyan módon, hogy a kódszavak első, második és harmadik harmada is megegyezik egy-egy kódszón belül, az 1 hibát, pedig olyan módon tudjuk javítani, hogy azt a sorozatot fogadjuk el jónak (hibamentesnek), amelyik legalább kétszer szerepel a kódszón belül. Fontos megjegyezni, hogy információt csak a kódszavak fele, illetve harmada hordoz a fentebb ismertetett, az egy hibát felismerő, valamint az 1 hibát javító kódok esetén. Példa 1 hibadetektálásra. Elküldött kódszó (16 bit): A beérkezett kódszó (16 bit):

10011010 10011010 10011010 10111010

Ebből azt a következtetést tudjuk levonni, hogy az elküldött 16 bites jelsorozat hibásan érkezett meg, hogy melyik fele a hibátlan azt a vevő fél nem tudja eldönteni, hiszen nem ismeri pontosan, hogy milyen jelsorozat lett az információátviteli csatornára kiküldve. Példa 1 hibajavítására. Elküldött kódszó (24 bit): A beérkezett kódszó (24 bit):

10011010 10011010 10011010 10011010 10111010 10011010

11



Ebből nem csak azt a következtetést tudjuk levonni, hogy az elküldött 24 bites jelsorozat hibásan érkezett meg, hanem azt is, hogy melyik harmadát érte a hiba és ebből az eredeti információ előállítható, a bemutatott példában a kódszó első és harmadik harmada egyezik meg, tehát ezt tekinthetjük az eredeti információt hordozó kód szórésznek. Definíció: Legyen megadva K={α1, α2, …,αm} kód, amelyben a kódszavak száma m, a blokkméret, pedig n log 2 (m ) ekkor a kód sűrűsége alatt a számot értjük. n

12



III.2. Sorozat hibák detektálása

A CRC (Cyclic Redundancy Check) egy hibadetektálási technika, ahol a paritásbites hibadetektáláshoz hasonlóan további redundáns adatot fűznek az információt hordozó adatblokkhoz. Alapvetően a hibadetektálás hatékonyságában különbözik a CRC technika a paritás bites hibadetektálástól, mivel a paritásellenőrzés mindössze egy hibát (egy biten létrejövő eltérést) tud felderíteni, addig a CRC technikának vannak 16, 32 és 64 bites sorozathibákat is detektálni képes megvalósításai. A CRC hibadetektálás lényege, hogy minden egyes adatblokkhoz hozzáfűznek, egy úgynevezett CRC mezőt, aminek tartalma valamilyen matematikai művelet alapján képződik a kérdéses adatblokk tartalmából és egy generátor értékből. Ez utóbbi generátorokról még a későbbiekben lesz részletesen szó, jelenleg elég tudni annyit a generátorokról, hogy ez valamilyen bináris általában 17, 33 vagy 65 bit hosszúságú jelsorozat a gyakorlatban. Matematikai műveletnek a modulo 2 osztást szokták választani, ahol az osztás műveletét többféle módon is végre lehet hajtani. III. 2.1. A CRC matematikai alapja A CRC matematikai szempontból a bináris együtthatós polinomok halmazán értelmezett osztási műveleten alapul. Bináris együttható alatt azt kell érteni, hogy az együttható értéke egy vagy nulla. Az egyes polinomok között végrehajtott alapvető algebrai műveletek eredményein egy további modulo osztást kell végrehajtani (mod 2) a kettes osztóval. Az alábbiakban a négy alapműveletre láthatunk példát különféle polinomok között, a modulo osztás (mod 2) végrehajtásának figyelembevételével. Például ha összeadunk két polinomot azt a következő módon kell végrehajtani.

(x

5

(

)

+ x4 + x2 +1

(x

+

4

)

+ x3 + x 2 + x = x5 + 2x 4 + x3 + 2x 2 + x + 1 ≡

)

≡ x + 2 x + x + 2 x + x + 1 mod 2 = x 5 + x 3 + x + 1 5

4

3

2

Vegyük észre, hogy a 2x4 és a 2x2 tagok nullává váltak a modulóképzés műveletének végrehajtása során. Ez azért van így, mivel a két tag együtthatója kettő és 2 mod 2 nullával egyenlő. A kivonást is hasonló megfontolások mentén kell végrehajtani. A következőekben a szorzásra is látható egy példa

(x

3

+ x )(x 2 + 1) = x 5 + 2 x 3 + x ≡ (x 5 + 2 x 3 + x ) mod 2 = x 5 + x

Végül vegyünk egy példát az osztási műveletre. Osszuk el a x 5 + x 4 + x 2 + 1 polinomot a x 2 + 1 polinommal.

13



x5 + x4 + x2 + 1 x +1 = x3 + x2 − x + 2 ami ekvivalens módon felírható szorzat alakban is 2 x +1 x +1 x 5 + x 4 + x 2 + 1 = x 2 + 1 x 3 + x 2 − x + x + 1 . Az osztás végrehajtása során kapunk egy hányadost, ami az x 3 + x 2 − x valamint a maradékot, ami pedig az x + 1 . Ebben a példában az x 5 + x 4 + x 2 + 1 reprezentálhatja az eredeti bináris alakban kódolt információt, ami az 110101-nek felel meg, az x 2 + 1 a generátor polinomot, ami az 101 bitsorozatnak felel meg, és a maradék pedig lehet a CRC, ami ebben a példában az x + 1 , ez pedig bináris alakban a következő képpen néz ki 11. A gyakorlatban bizonyos technikai okok miatt ettől valamelyest eltérő módon határozzák meg a CRC értékét. Ezekre az eltérésekre az alábbiakban még ki fogunk térni. Az osztást az Euklideszi algoritmus alapján hajtjuk végre. Mivel az algoritmus egyes lépései nem triviálisan egyszerűek ezért a fenti osztás eredményét az alábbiakban részletesebben is ismertetjük. Az i-edik osztási lépésben képződő maradékot jelöljük mivel.

(

)(

)

m x5 + x4 + x2 + 1 = x3 + 2 1 → m1 = x 5 + x 4 + x 2 + 1 − x 3 x 2 + 1 = x 4 − x 3 + x 2 + 1 2 x +1 x +1 4 3 2 m m x − x + x +1 2 lépés. 2 1 = = x2 + 2 2 → m2 = x 4 − x 3 + x 2 + 1 − x 2 x 2 + 1 = − x 3 + 1 2 x +1 x +1 x +1 3 m m − x +1 3 lépés. 2 2 = 2 = −x + 2 3 → m3 = − x 3 + 1 − (− x ) x 2 + 1 = x + 1 x +1 x +1 x +1

(

1 lépés.

)

(

(

)

)

Az egyes lépésekben képződött tagokat összeadva kapjuk a hányadost x 3 + x 2 − x , a legutolsó lépésben megkapott maradék x + 1 , amely már alacsonyabb fokszámú polinom, mint az osztó (generátor) polinom x 2 + 1 , pedig a maradéka a teljes polinomosztási műveletnek. III. 2.2. A CRC alkalmazása Bármely információt/adatot kódoló bitsorozat egy úgynevezett üzenet polinom együtthatóiként is felfogható, jelöljük ezt a polinomot M (x) -el. Ezt az üzenetpolinomot szorozzuk x n -el. Az n a Gn (x) generátor polinom fokszáma, például az előző alfejezetben vizsgált példa esetében az n kettő lenne. Az x n -el való szorzás eredményeként az eredeti üzenetpolinom fokszáma a szorzás során értelemszerűen n-el nő, ami a bináris jelsorozat formájában azzal ekvivalens, hogy az eredeti bitsorozatot n darab nulla bittel egészítjük ki jobbról. Ez az előző alfejezetben említett egyik bizonyos technikai ok, amiben a valódi CRC generálás eltér a szokványos polinomosztással generált maradék polinom képzésre alapuló CRC eljárástól. A CRC generálás általános matematikai alakja a gyakorlatban tehát a következő.

M ( x) x n = Q( x) Gn ( x) + Rn −1 ( x) ahol Az előző alfejezetben bemutatott példára alkalmazva a fentiekben ismertetett módosított eljárást a következő eredményeket kapjuk.

14



x7 + x6 + x4 + x2 x +1 = x5 + x4 − x3 + x + 1 − 2 2 x +1 x +1 A fenti eredményt a következő lépésekben kapjuk meg. m x7 + x6 + x4 + x2 1 lépés. = x5 + 2 1 → m1 = x 7 + x 6 + x 4 + x 2 − x 5 (x 2 + 1) = x 6 − x 5 + x 4 + x 2 2 x +1 x +1 m m x6 − x5 + x4 + x2 = x4 + 2 2 → m2 = x 6 − x 5 + x 4 + x 2 − x 4 (x 2 + 1) = − x 5 + x 2 2 lépés. 2 1 = 2 x +1 x +1 x +1 5 2 m m −x +x = −x3 + 2 3 → m3 = − x 5 + x 2 − (− x 3 )(x 2 + 1) = x 3 + x 2 3 lépés. 2 2 = 2 x +1 x +1 x +1 m3 = x2 +1 m 5 lépés. 2 4 = x +1

4 lépés.

m x3 + x2 = x+ 2 4 → m4 = x 3 + x 2 − ( x )(x 2 + 1) = x 2 − x 2 x +1 x +1 2 m x −x = 1+ 2 5 → m5 = x 2 − x − (1)(x 2 + 1) = − x − 1 2 x +1 x +1

(

)

(

)(

)

M ( x) x n = x 5 + x 4 + x 2 + 1 x 2 , Rn −1 ( x) = − x − 1, Q( x) Gn ( x) = x 5 + x 4 − x 3 + x + 1 x 2 + 1

M ( x) x n − Rn −1 ( x) = Q( x) Gn ( x) Példa. Legyen a védendő adat a következő 16 bit hosszúságú bitsorozat. 10001011 00100101 A CRC generálása lépései. 10001011 00100101 0000 11001 -------------------------------01000011 00100101 0000

A hiba ellen védett adat jobb oldaról kiegészítve 4 zéró bittel Az osztó 5 bites, aminek a következő polinom felel meg osztó polinom: x 4 + x 3 + 1 Az osztási eredmény. Az osztás közönséges XOR művelet

10001011 00100101 0000 11001 01000011 00100101 0000 11001 00100111 00100101 0000 11001 00010101 00100101 0000 11001 00001100 00100101 0000 1100 1 00000000 10100101 0000 11001 00000000 01101101 0000 15


11001 00000000 00001001 0000 1100 1 00000000 00000101 1000 110 01 00000000 00000011 1100 11 001 ------------------------------00000000 00000000 1110


A maradék az XOR műveletek végrehajtása után

A CRC ellenőrző érték az 1110 bitek, amelyekkel kiegészítjük a hiba ellen védett adatot. A beérkező adat hibaellenőrzésének folyamata 10001011 00100101 1110 11001 01000011 00100101 1110 11001 00100111 00100101 1110 11001 00010101 00100101 1110 11001 00001100 00100101 1110 1100 1 00000000 10100101 1110 11001 00000000 01101101 1110 11001 00000000 00001001 1110 1100 1 00000000 00000101 0110 110 01 00000000 00000011 0010 11 001 00000000 00000000 0000

A maradék az XOR műveletek végrehajtása után nulla

Az eredmény azt mutatja, hogy az adat hibátlanul érkezett meg. Vegyünk most egy olyan esetet a fenti 16 bites példa felhasználásával, amikor három egymást követő biten hiba jelentkezik az információátvitel során. Hajtsuk végre újra a CRC ellenőrzést, a hibásan megérkezett adatbit sorozaton. 10001011 00011101 1110 11001 01000011 00011101 1110 11001 00100111 00011101 1110 11001 16


00010101 00011101 1110 11001 00001100 00011101 1110 1100 1 00000000 10011101 1110 11001 00000000 01010101 1110 11001 00000000 00110001 1110 11001 00000000 00000011 1110 11 001 00000000 00000000 1100


A maradék az XOR műveletek végrehajtása után nem nulla

Az eredmény azt mutatja, hogy az adat hibásan érkezett meg, hiszen a hozzáfűzött négy biten nemzéró bitek találhatóak. Példa. Az alábbi példában a rövidség kedvéért az adatblokk méret 16 bites, a generátor pedig 8 bites. A bemutatott példában az adatblokk normál kettes számrendszerbeli értéke 35621 a generátor pedig 177. Feladat, végrehajtani a következő műveletet bináris formában 35621 : 177 = 201 + 44 A 35621-ben a 177, 201-szer van meg, a maradék pedig 44. 10001011 00100101 : 10110001 Először röviden az osztási művelet végrehajtásának technikai részleteit kell átismételni, illetve azt a két lehetséges matematikai módszer, amivel a kérdéses hányados illetve a maradék képezhető. Az osztási művelet során egy nagyobb értéket az OSZTANDÓ-t kell egy kisebb számmal az OSZTÓ-val elosztani olyan módon, hogy az OSZTANDÓ legfelső bitjétől kezdődően annyi helyen ahány helyből az OSZTÓ áll egy kivonási műveletet vagy a másik lehetséges megoldás esetén egy XOR műveletet kell végrehajtani. A bináris kivonás műveletének alapszabályai. s 0 1 1 0 − 0 − 0 −1 −1 A jobboldalon felül látható nulla feletti nyíl az átvitelt jelöli, viszont az alább 1 0 1 0 következő példában az egyszerűbb szövegszerkesztés technikai okok miatt aláhúzással jelöltük az átvitelt.

17



10001011 00100101 : 10110001 = 11001001 + 101100 10001011 0 1011000 1 00110010 10 101100 01 000110 011 000 000 110 0110 000 0000 110 01100 101 10001 000 110111 000 000000 1101110 0000000 11011101 10110001 00101100 A logikai XOR művelet igazság táblája. 0 XOR 0 = 0 1 XOR 0 = 1 0 XOR 1 = 1 1 XOR 1 = 0 Felismerhető, hogy a logikai kizáró vagy művelet teljes mértékben megegyezik a bináris kivonás műveletével, illetve annak eredményével, egyetlen apró (bár technikai szempontból fontos és jelentős) eltérés kivételével. Ez az eltérés a 0 – 1 művelet esetén jelentkező átvitelben (angolul Carry) testesül meg. Ez technikailag is jelentősen megnehezíti a számolást, és ha egy elektronikát szeretnénk tervezni a CRC-ben szereplő műveletek bináris végrehajtására, akkor az XOR művelet sokkal könnyebben megépíthető elektronikus kapcsolást eredményez, mint a normál bináris kivonásra felépített elektronikus áramkör.

18



10001011 00100101 : 10110001 = 101100000 + 1000101 10110001 00111010 0 0000000 0 0111010 00 101100 01 010110 011 10110 001 00000 0100 0000 0000 0000 01000 000 00000 00 010001 00 000000 00 0100010 0 0000000 0 01000101 00000000 01000101

19



Hamming kódolás Az alábbiakban részletezett eljárás egy hiba javítására alkalmas. Tételezzük fel, hogy n darab bitből álló adatot szeretnénk egy információátviteli csatornán keresztül továbbítani, egyik pontból (Adó) egy másik pontba (Vevő). Az információátviteli csatorna zajjal terhelt és az átvitt n bites adatblokkban hiba keletkezik, az egyik bit módosul az átvitel során. Annak érdekében, hogy a hibát detektálni és javítani is tudjuk, szükség van további k darab adatbitet az adatblokkhoz fűzni. Ezzel az átvitt adatblokk mérete m=n+k bit hosszúságú lesz. n + k + 1 ≤ 2k Adatblokk méret és a hozzáfűzött bitek közötti összefüggés egy hiba javítására Adatblokk méret 8 bites 16 bites 32 bites 64 bites 128 bites 512 bites

Hozzáfűzött bitek száma 4 bit 5 bit 6 bit 7 bit 8 bit 10 bit

Kibővített adatblokk méret 12 bit 21 bit 38 bit 71 bit 136 bit 522 bit

Redundáns bitek aránya 50 % 31.25 % 18.75 % 10.94 % 6.25 % 1.95 %

Hamming (7,4) kód A Hamming (7,4) kód alkalmas 1 hiba javítására, ami tetszőleges helyen keletkezhet, illetve két tetszőleges helyen keletkező hiba detektálására. A Hamming féle (7,4) kódban egy 4 bites adatot 3 darab paritásbittel egészítenek ki. A 4-es a Hamming kódnak ebben a típusában az adatbitek számát, a 7-es pedig az összes bitek számát jelenti. Azért ez a megoldás kerül bemutatásra, mivel ez a legegyszerűbb Hamming kód, és ez könnyen szemléltethető Venn diagrammok segítségével. A Hamming kód lényege, hogy további paritásbiteket rendelünk az egyes adatbitekhez, az alábbiakban részletezett módon. Egy-egy paritásbit több adatbit tartalmáért is felelős egyszerre. 1. Minden egyes paritásbit egyrészről adatellenőrzést végez önmagán és nem végez ellenőrzést semelyik másik paritásbiten. 2. Az egyes paritásbitek azokhoz az adatbitekhez vannak hozzárendelve, ahol az adatbit helyének indexe egyenlő a megfelelő paritásbitek helyindexei összegével. Például. A d1 adatbit a harmadik indexű helyen foglal helyet, amihez a p1 és p2 paritásbitek tartoznak mivel p1 indexe 1-el p2 indexe 2-vel egyenlő, ezek összege pedig éppen 3, ami a d1-es bit helye. Vegyünk még egy példát az érthetőség miatt. A d3 adatbit a hatodik indexű helyen foglal helyet, amihez a p2 és p3 paritásbitek tartoznak mivel p2 indexe 2-vel p3 indexe 4-el egyenlő, ezek összege pedig éppen 6, ami a d3-as bit helye a generált adatszerkezetben. 20



Az alábbiakban mind két táblázat ugyanazt az információt hordozza, csak az első táblázatban a bitek normál helyérték sorrendben helyezkednek el, a második táblázatban pedig fordított (olvasási rend szerinti) sorrendben van elhelyezve. Normál bitsorrndű (helyértékes) elrendezés bit 7 6 5 4 3 d4 d3 d2 p3 d1 1 0 1 0 1 p1 1 1 0 0 1 p2 1 1 1 1 0 p3

2 p2 0 1 0

1 p1 1 0 0

Fordított bitsorrndű (alfabetikus) elrendezés bit 1 2 3 4 5 p1 p2 d1 p3 d2 1 0 1 0 1 p1 0 1 1 0 0 p2 0 0 0 1 1 p3

6 d3 0 1 1

7 d4 1 1 1

p1 p2 p3

d1 1 1 0

d2 1 0 1

d3 0 1 1

d4 1 1 1

A Hamming kódok a lineáris algebra eszközeivel is könnyen kezelhetőek, és a számítások egyes lépései (kódolás, hibadetektálás és javítás, valamint a dekódolás) mátrix algebrai úton is elvégezhetőek. A Hamming kódok használata az alábbi fontosabb lépésekből tevődnek össze. ¾ Az eredeti adat átalakítása és kibővítése paritásbitekkel (generálás) ¾ Paritásellenőrzés (a hiba helyének detektálása) ¾ Hiba javítása (egyszerű logikai negálás) ¾ Dekódolás (A javítás után ha arra szükségvolt, a Hamming kódból az eredeti adat

visszanyerése)

Vegyünk egy példát a Hamming kód alkalmazására. Legyen az elküldendő adat például a 0101. Oldjuk meg először a feladatot Venn diagrammok segítségével. Mivel az adat mérete 4 bit hosszúságú, ezért három paritásbitre van szükség a Hamming kód előállítására. Rendeljünk minden 21



egyes paritásbithez egy-egy halmazt, amiket jelöljük A, B, és C-vel, azaz p1 → A, p 2 → B, p3 → C . Ezután helyezzük el az adatbitek értékeit d1 = 0, d 2 = 1, d 3 = 0, d 4 = 1 az egyes halmazokban az adatbitek és paritásbitek kapcsolatának megfelelően. Például az előbbiekben bemutatott táblázat alapján d1 → {p1 , p 2 } , azaz A ∩ B = {0}, vagy például d 2 → {p1 , p3 } , amihez A ∩ C = {1}.

Ezek az összerendelések (kódolás) láthatóak szemléletes formában a fenti ábra baloldalán. A következő lépésben meg kell állapítani a paritásbitek értékeit, ehhez páros paritást feltételezünk. Szemléletesen ez azt fogja jelenteni, hogy minden egyes halmazban (körben) páros számú egyes szerepelhet. Ebből a következő eredményeket kapjuk p1 = 0, p 2 = 1, p3 = 0 . A Hamming kódolt adat Venn diagrammban a fenti ábra jobb oldalán látszódik. Tehát az információt (adatot) küldő fél a következő bitsorozatot küldi át az információ átviteli csatornán p1 , p 2 , d1 , p3 , d 2 , d 3 , d 4 0100101. Tegyük fel, hogy az információátviteli csatorna hibája miatt a következő jelsorozatot veszi a vevő fél 0110101. A hibát olyan módon tudja a vevő felderíteni, hogy maga is egy paritás ellenőrzést hajt végre páros paritás szerint. A hiba helye olyan módon azonosítható, hogy a az A és a B halmazokban is pártalan számú egyes található, de a C halmaz paritása viszont rendben van, ami egyértelműen azonosítja a d1 adatbitet, mivel az A és B halmaz együtt csak kizárólag a d1-es bitért felel. Ebből már a vevő fél könnyedén megkapja a hibátlan adatot, mivel a d1-es bit értékét negálja.

22



A fent bemutatott lépések formálisabb matematikai műveletekkel is végrehajthatóak. A mátrix algebra eszközeivel mint a kódolás (generálás), mind a paritásellenőrzés, illetve az eredeti adat előállítása (dekódolás) végrehajtható. Az alábbiakban emlékeztetőül a mátrixok szorzatára tanult általános összefüggést röviden részletezzük. Legyenek A ∈ ℜ N ×K , B ∈ ℜ K ×M valós elemű mátrixok ekkor létezik olyan C ∈ ℜ N×M valós elemű K

mátrix, amelyre A B = C és ci , j = ∑ ai ,k bk , j = ai ,1 b1, j + ai , 2 b2, j + K + ai , K bK , j k =1

Ezt a szorzást szokták sor-oszlop szorzásnak is nevezni, mivel az első mátrix sorain és a második mátrix oszlopain megyünk végig, a szorzási művelet végrehajtása közben. Mintapélda mátrixszorzásra Legyen ⎡ 1 2⎤ ⎡ 1 5 0⎤ ⎥ ⎢ Α = ⎢ 4 2 3⎥, B = ⎢⎢ 2 0⎥⎥ , a szorzat eredménye pedig, ⎢⎣− 2 1 ⎥⎦ ⎢⎣− 1 1 4⎥⎦

Fontos megjegyezni, hogy általában a szorzási művelet operátorát nem szokás kiírni, mint az, az alábbiakban látható, de ezt most az egyértelmű jelölés és az érthetőség miatt, pedagógiai okokból mégis kiírtuk. ⎡ 1 5 0⎤ ⎡ 1 2⎤ ⎡ 1 * 1 + 5 * 2 + 0 * (−2) 1 * 2 + 5 * 0 + 0 * 1 ⎤ ⎡ 11 2 ⎤ Α B = ⎢⎢ 4 2 3⎥⎥ ⎢⎢ 2 0⎥⎥ = ⎢⎢ 4 * 1 + 2 * 2 + 3 * (−2) 4 * 2 + 2 * 0 + 3 * 1 ⎥⎥ = ⎢⎢ 2 11⎥⎥ ⎢⎣− 1 1 4⎥⎦ ⎢⎣− 2 1 ⎥⎦ ⎢⎣− 1 * 1 + 1 * 2 + 4 * (−2) − 1 * 2 + 1 * 0 + 4 * 1⎥⎦ ⎢⎣− 7 2 ⎥⎦

A fenti táblázatok alapján a következő mátrixok definiálhatóak a (7,4)-es Hamming kóddal kapcsolatos műveletek mátrix algebrai végrehajtására. Generátor mátrix ⎡1 ⎢1 ⎢ ⎢1 ⎢ G = ⎢0 ⎢0 ⎢ ⎢0 ⎢0 ⎣

1 0 0 1 1 0 0

0 1 0 1 0 1 0

Paritásellenőrző mátrix

1⎤ p1 1⎥⎥ p 2 p1 p 2 0⎥ d1 ⎡1 0 ⎥ 1⎥ p3 , H = ⎢⎢ 0 1 0⎥ d 2 ⎥ ⎣⎢ 0 0 0⎥ d 3 1⎥⎦ d 4

Dekódoló mátrix

p1 0 1⎤ , 0 1⎥⎥ R = 0 1⎦⎥ 0

d1 p3 d 2 d 3 d 4 1 1

0 1 0 0

0 1

0

1 1

1

p 2 d1 p3 d 2 d 3 d 4 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0

0

0

0

0

1

A G generátor mátrixot úgy kapjuk meg, hogy vesszük a 17-es oldalon látható redukált tábla (3 soros 4 oszlopos tábla) sorait és elhelyezzük a három sort azokon a helyeken (sorokban) ahol a paritásbit

23



található azaz 1, 2 , 4-es sorok. A többi helyre (további 4 sor) pedig az négyszer négyes egységmátrix sorait illesztjük be. A paritásellenőrző mátrix egyszerűen csak a paritásbiteket és az adatbiteket összerendelő táblázat. A dekódoló mátrix pedig egy speciálisan felbontott négyszer négyes egységmátrix oszlopai, azokban az oszlopokban ahol adatbitek helyezkednek el. A paritásbites oszlopok teljesen nullából állnak. Vegyük az előzőekben Venn diagrammok segítségével megoldott példát. Jelölje a kiinduló adatbit sorozatot a következő d vektor. ⎡0 ⎤ ⎢1 ⎥ d= ⎢ ⎥. ⎢0 ⎥ ⎢ ⎥ ⎣1 ⎦

1a. Hamming kód előállítása Szorozzuk meg G mátrixot jobbról a d mátrixal. Mivel G ∈ ℜ 7×4 , d ∈ ℜ 4×1 a két mátrix összeszorozható az eredményük pedig egy ℜ 7×1 -es mátrix, illetve oszlopvektor lesz. Jelölje a Hamming kódolt bitsorozatot a h vektor. ⎡0 ⎤ ⎡ 2⎤ ⎡ 2⎤ ⎡1 1 0 1 ⎤ ⎢1 ⎥ ⎢1 ⎥ ⎢1 ⎥ ⎢1 0 1 1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ ⎡0 ⎤ ⎢ ⎥ ⎢ ⎢0 ⎥ ⎢0 ⎥ ⎢1 0 0 0 ⎥ ⎢ ⎥ ⎢ 0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎢ h = ⎢2⎥ mod 2 = ⎢0⎥ Mivel az eredményeket kettes = ⎢ 2⎥ . h = G d = ⎢0 1 1 1 ⎥ ⎢0 ⎥ ⎢1 ⎥ ⎢1 ⎥ ⎢0 1 0 0 ⎥ ⎢ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎥ ⎣1 ⎦ ⎢ ⎥ ⎢ ⎢0 ⎥ ⎢0 ⎥ ⎢0 ⎥ ⎢0 0 1 0 ⎥ ⎢1 ⎥ ⎢1 ⎥ ⎢1 ⎥ ⎢0 0 0 1 ⎥ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎦ ⎣ számrendszerben kell megkapnunk ezért a szorzás eredményét modulo kettő osztani kell. A kapott oszlopvektor pedig pontosan megegyezik a p1 , p 2 , d1 , p3 , d 2 , d 3 , d 4 0100101 bitsorozattal. 1b. Paritásellenőrzés A paritásellenőrző mátrixot H megszorozzuk a Hamming kódolt bitsorozatot tartalmazó h vektorral. Jelölje a hibavektor bitsorozatát az e vektor. A mátrix szorzat eredményét itt is modulo kettő kell osztani. ⎡0 ⎤ ⎢1⎥ ⎢ ⎥ 0 1 0 1⎤ ⎢0⎥ ⎡2⎤ ⎡2⎤ ⎡0⎤ ⎡1 0 1 ⎢ ⎥ ⎢ ⎥ ⎥ ⎢ ⎢ ⎥ e=Hh=⎢0 1 1 0 0 1 1⎥ ⎢0⎥ = ⎢2⎥ . e = ⎢2⎥ mod 2 = ⎢⎢0⎥⎥ . A hibavektor a csupa ⎢⎣2⎥⎦ ⎢⎣0⎥⎦ ⎢⎣ 0 0 0 1 1 1 1⎥⎦ ⎢1⎥ ⎢⎣2⎥⎦ ⎢ ⎥ ⎢0 ⎥ ⎢1⎥ ⎣ ⎦ nullát tartalmazó vektor, ami azt jelenti, hogy az adat hibátlanul érkezett meg. 24



1c. Dekódolás A hibaellenőrzés után, ha az e vektor nullvektor, akkor már csak az eredeti adatnak a kinyerése van hátra a Hamming kódolt alakból. Szorozzuk meg az R mátrixot a megérkezett Hamming kódolt bitsorozatot tartalmazó h vektorral jobbról.

⎡0 ⎢0 Rh=⎢ ⎢0 ⎢ ⎣0

0 0 0 0

1 0 0 0

0 0 0 0

0 1 0 0

0 0 1 0

0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦

⎡0 ⎤ ⎢1⎥ ⎢ ⎥ ⎡0 ⎤ ⎢0 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢0⎥ = ⎢0⎥ , ez pedig éppen a kiinduló adatbitsorozat. ⎢1⎥ ⎢ ⎥ ⎢ ⎥ ⎣1⎦ ⎢0 ⎥ ⎢1⎥ ⎣ ⎦

Vegyünk példának okáért egy olyan esetet ahol a hiba a negyedik adatbiten keletkezik, ami a hetedik bit a Hamming kódolt adatbit sorozatban, azaz p1 , p 2 , d1 , p3 , d 2 , d 3 , d 4 0100100 bitsorozatot kapjuk az előbbiekben vizsgált helyes bitsorozathoz képest. Hajtsuk végre a paritásellenőrzést. ⎡0 ⎤ ⎢1 ⎥ ⎢ ⎥ 0 1 0 1⎤ ⎢0⎥ ⎡1⎤ ⎡1⎤ ⎡1⎤ ⎡1 0 1 ⎢ ⎥ ⎢⎥ ⎢ ⎥ ⎥ ⎢ e=Hh=⎢0 1 1 0 0 1 1⎥ ⎢0⎥ = ⎢1⎥ . e = ⎢1⎥ mod 2 = ⎢⎢1⎥⎥ . A hibavektor most nem a ⎢⎣1⎥⎦ ⎢⎣1⎥⎦ ⎢⎣ 0 0 0 1 1 1 1⎥⎦ ⎢1⎥ ⎢⎣1⎥⎦ ⎢ ⎥ ⎢0 ⎥ ⎢0 ⎥ ⎣ ⎦ csupa nullát tartalmazó vektor, hanem egyeseket is tartalmazó vektor, ami azt jelenti, hogy az adat hibásan érkezett meg. De az e vektor ennél sokkal többet is elárul a hibáról. Mégpedig azt, hogy melyik biten keletkezett a hiba, amit úgy tudunk megállapítani, hogy vesszük az e vektor tízes számrendszerben vett értékét, ami éppen a hibás bit helyét mutatja balról jobbra vett sorrendben, az indexelést pedig az 1-esről indítjuk. A következő ábra a (7,4) Hamming kódolást végrehajtó logikai áramkört mutatja. A (7,4)-es Hamming kód bemenete tulajdonképpen négy darab adatbit, a kimenete, pedig három darab paritásbit. A (7,4)-es Hamming kódban minden egyes paritásbithez három-három darab adatbit van hozzárendelve, amelyek a paritásbitek értékeit megfogják egyértelműen határozni. Mind az alábbiakban látható logikai áramkör elkészítése, mind pedig az erre írt SystemC-beli modell kidolgozásakor páros paritást tételezünk fel, azaz a három adatbit a paritásbittel együtt páros számú egyest (0, 2, 4 db) kell tartalmazzon.

25



d1

p1

xor

d2

xor p2

xor d3

xor xor p3

xor

d4

Az egyes paritásbitek értékei előállíthatóak az egyes adatbit csoportokon két egymásután végrehajtott logikai xor művelet eredményeként. A következő két alapeset vizsgálata segít megérteni, hogy ez miért működik a logikai xor műveletekkel. Páros számú egyes esetén d1 d2 1 1

d4 0

p1 0

Az alábbiakban látható logikai műveletek eredménye a fenti táblázatban megadott d1, d2, d4 értékekre minden esetben logikai nulla értéket adnak eredményül. p1 = (d1 ⊗ d 2 ) ⊗ d 4 = (d1 ⊗ d 4 ) ⊗ d 2 = (d 4 ⊗ d 2 ) ⊗ d

p1 = (1 ⊗ 1) ⊗ 0 = (0) ⊗ 0 = 0

→

p1 = 0

p1 = (1 ⊗ 0) ⊗ 1 = (1) ⊗ 1 = 0 p1 = (0 ⊗ 1) ⊗ 1 = (1) ⊗ 1 = 0

Ez pedig esetünkben éppen megfelel a szükséges paritásbit értéknek, mivel a három adatbit közül kettő egyes értékű, és páros paritást megkövetelve a paritásbitnek ekkor éppen nulla logikai értékűnek kell lennie. Páratlan számú egyes esetén d1 d2 0 1

d4 0

p1 1

p1 = (d1 ⊗ d 2 ) ⊗ d 4 = (d1 ⊗ d 4 ) ⊗ d 2 = (d 4 ⊗ d 2 ) ⊗ d

26

→

p1 = 1



Itt a számításokat nem részletezve, az előzőekhez hasonlóan belátható, hogy a paritásbit értéke egy lesz függetlenül a művelet végrehajtási sorrendtől, ami éppen a páros paritás megtartásához szükséges.

A következő ábrán a (7,4)-es Hamming kód paritás ellenőrzésének végrehajtására látható egy logikai áramkör. Az áramkör hét bemenettel és három kimenettel rendelkezik, ahol a bemenetek az adatbitekből és a paritábitekből állnak. A három kimenet annak ellenőrzésére szolgál, hogy megváltozott-e az eredeti adatcsomag, illetve egyetlen hiba esetén a hibás bit pozícióját is szolgáltatja a logikai áramkör. A paritás ellenőrzés végrehajtásához szintén xor kapukat célszerű alkalmazni. p1 d1

xor

d2

xor

p2

xor

d3

xor

ch1

xor

ch2

xor

ch3

xor xor

p3 xor

d4

A paritás ellenőrzésére, illetve ha valamelyik biten hiba jött létre, akkor a három kimeneti vonal értékeinek előállítására az egyes paritásbitek és a hozzátartozó adatbit csoportokon páronként párhuzamosan végrehajtott xor, majd a két xor művelet eredményén egy további logikai xor műveletet végrehajtva kapjuk a paritás ellenőrzés eredményét. Ha mind három kimeneti vonalon nulla logikai érték jön létre, akkor a négy bemeneti adat- és paritásbit vagy hibátlanul érkezett meg a feladótól, vagy kettőnél több hiba keletkezett az adatátvitel vagy az adattárolás során. A következő két alapeset (hibátlan, hibás) vizsgálata segít megérteni, hogy a paritás ellenőrzés miért működik a logikai xor műveletek felhasználásával. Hibátlan adatátviteli eset Tegyük fel, hogy beérkezett 7 bitből az 1-es paritásbithez tartozó adatoknak az alábbi táblázatban látható értékei adottak. d1 d2 1 0

d4 1

p1 0 27



Az alábbiakban látható logikai műveletek eredménye a fenti táblázatban megadott d1, d2, d4, p1 értékekre minden esetben logikai nulla értéket adnak eredményül. ch1 = (d1 ⊗ d 2 ) ⊗ ( p1 ⊗ d 4 ) = (d1 ⊗ d 4 ) ⊗ (d 2 ⊗ p1 ) = K → ch1 = 0 ch1 = (1 ⊗ 0 ) ⊗ (0 ⊗ 1) = 1 ⊗ 1 = 0

ch1 = (1 ⊗ 1) ⊗ (0 ⊗ 0) = 0 ⊗ 0 = 0 Hibás adatátviteli eset Tegyük fel, hogy beérkezett 7 bitből az 1-es paritásbithez tartozó adatoknak az alábbi táblázatban látható értékei adottak. Hogy a hiba a 7 bit pozíció közül melyiken keletkezett azt ebből még nem tudjuk eldönteni, ahhoz meg kell vizsgálni a másik két paritásbitet a hozzájuk tartozó adatbit csoportokkal együtt, de az látható, hogy a páros paritás sérül. d1 d2 1 0

d4 1

p1 1

Az alábbiakban látható logikai műveletek eredménye a fenti táblázatban megadott d1, d2, d4, p1 értékekre minden esetben logikai egyes értéket adnak eredményül. ch1 = (d1 ⊗ d 2 ) ⊗ ( p1 ⊗ d 4 ) = (d1 ⊗ d 4 ) ⊗ (d 2 ⊗ p1 ) = K → ch1 = 1 ch1 = (1 ⊗ 0) ⊗ (1 ⊗ 1) = 1 ⊗ 0 = 1 ch1 = (1 ⊗ 1) ⊗ (0 ⊗ 1) = 0 ⊗ 1 = 1

28

I. Az információtovábbítás folyamatának alapjai

Recommend Documents