Kódolás, hibajavítás. Tervezte és készítette Géczy LászlL. szló 2002

Kódolás, hibajavítás

Tervezte és készítette Géczy László © 2002

Jelkapcsolat A jelkapcsolatban van a jelforrás, amely az üzenő, és a jelérzékelő (vevő, fogadó), amely az értesített.

Jelforrás Jelforrás

üzenet üzenet

Jelérzékelő Jelérzékelő

Általánosságban az üzenet tartalma tetszőleges lehet, ellenben a tartalmat az adott környezet korlátozhatja, és kereteit megszabhatja a jelkapcsolatban lévők között.

Jelkapcsolat Az eredeti közlemény az emberi agyban, mint gondolat áll elő és az ember átalakító képességén keresztül vagy hangokként, vagy leírt szövegként jelentkezik (kódolt közlemény) a jelkapcsolatban. A jelkapcsolat végállomásán a hallott, vagy az olvasott jelekből (vett közlemény) kikerekedik a csaknem eredeti gondolat (dekódolt közlemény).

eredeti eredeti közlemény közlemény

kódolt kódolt közlemény közlemény


vett vett közlemény közlemény

dekódolt dekódolt közlemény közlemény

Jelérzékelő Jelérzékelő

A beszédben az információ hordozó a hang, tehát a jelkapcsolat hangokkal jön létre. Az írásban az információ hordozó a betű és a jelkapcsolat betűk által valósul meg.

Az információ (a jel) Általában vizsgálva: a jelforrás jelei lehetnek diszkrétek, vagy folytonosak. A gyakorlatban előforduló információ források mindig véges sebességű jeleket bocsátanak ki. Diszkrét jelforrások esetében (emberi kapcsolat) ez azt jelenti, hogy a szolgáltatott jelek száma véges és időbeni egymásutánja (gyakorisága) egy meghatározott értéket nem halad meg. A szempontunkból lényeges diszkrét jelforrások által kibocsájtott véges számú különböző jel közül a különböző jeleket különböző, az azonos jeleket pedig azonos szimbólumokkal jelöljük (hangok, betűk, számok, írásjelek) és ezt a jelteret egy szimbólum készlettel (abc betűi) helyettesítjük.

A kódolás alapfogalmai A kód, az információk kifejezésére, közlésére, megjelenítésére szolgáló rendszer. A kód az információt hordozó szimbólumokat, a szimbólumokból felépített szavakat, valamint a szimbólumok és szavak összekapcsolásának szabályait tartalmazza.

Az információ-forrás, vagy jelforrás általános esetben az egyes szimbólumokat nem azonos valószínűséggel szolgáltatja. A szimbólum készlethez hozzá rendelhető egy diszkrét (nem folytonos) valószínűségi kép, amely a szimbólum készlettel együtt jellemzője az információ forrásának.

A magyar ABC kis betűinek használati valószínűsége a beszélt nyelvben Az alfaset betűkészlet a valószínűségi-kép alapja összes betű 1175

átlag 34,56

szórás 23,42

90

80

70

60

50

40

30

20

10

0

e

t

a

s

l

r

n

i

á

z

é

k

o

m

g

d

y

v

ó

betűk

b

ö

c

j

ő

p

f

h

u

ú

ü

ű

x

w

q

Az információ (a jel) Például az információ forrás n db szimbóluma legyen a következő: x1, x2, x3, ................., xi,...................... xn Az n darab szimbólum előfordulásának valószínűsége pedig rendre P(x1) = p1; P(x2) = p2; .................. ; P(xi) = pi; ...................... ; P(xn) = pn ez a valószínűségi kép akkor teljes, ha •egyik szimbólum valószínűsége sem 0, tehát pi ≠ 0 (i = 1, 2, ............... , n) •egyik szimbólum valószínűsége sem 100 %-os, tehát pi ≠ 1 (i = 1, 2, ............... , n) •biztos eseménynek tekintjük azt az információ szerzést, amely alatt csak az adott szimbólumkészlet kerül közvetítésre, tehát n

∑p i =1

i

=1

Az információ (a jel) A diszkrét információ forrásból szerzett információ mennyiségét információ tartalomnak vagy hírtartalomnak nevezzük. Az információ forrást jól jellemzi a szimbólumok átlagos információ tartalma.

Egy szimbólum egyedi információ tartalma: 1 I ( xi ) = log a pi

Az egyedi információ tartalom kiterjesztése a jeltér átlagos információ tartalma, entrópiája: n

H ( X ) = −∑ pi ⋅ log a pi i =1

Az információ (a jel) Bizonyítható, hogy a jelforrás átlagos hírtartalma akkor a maximális, ha szimbólumkészlete azonos valószínűségű. Az információ tömörsége:

µ=

H (X ) ≤1 H ( X ) max

Az információ redundanciája:

R=

H ( X ) max − H ( X ) = 1− µ H ( X ) max

Hogy lehet értelmezni a redundanciát?

A beszélt nyelv is redundáns.

Tapasztaljuk minden nap, hogy egy gondolatot számtalan módon lehet megfogalmazni, és még több képen lehet érteni. Ez természetesen távolabb van attól a kiinduló ponttól ahonnan szemléltük a jelforrást, de minden esetre jellemzi a redundanciát általában.

Az információ jellemzésének alapvető fogalmai Szimbólumkészlet: Azoknak a szimbólumoknak az összessége, amelyek az információ szerkesztéséhez szükségesek. A kódszó: A szimbólumkészletből alkotott sorozat, amelynek szerkesztéséhez meg kell adni a szimbólumok összekapcsolásának szabályait, valamint az egyes szavak megkülönböztetésének szabályait. A kódszó-készlet: Az egy rendszeren belül használt kódszavak készlete. Ez feltételezi azt, hogy előfordulhat olyan kódszó-készlet, amely esetében vannak megengedett és tiltott kódszavak. A szóhosszúság: A kódszóban lévő szimbólumok száma. Vannak rendszerek, amelyek rögzített (fix) szóhosszúsággal, vannak olyanok, melyek változó szóhosszúsággal dolgoznak.

A kódszó A kódok jellemzőik szerint lehetnek: –szimbólum készletük szerint –szóhosszúság szerint

- bináris - nem bináris - rögzített - változó.

A számítástechnika számára a bináris jelkapcsolat alapvetően meghatározó. A berendezések egyszerűsége, megbízhatósága, a jel csatorna fizikai jellemzői miatt a jelkapcsolatok többségénél bináris szimbólumokból álló jel sorozatokkal történik az információ átvitel.

A kódszó A numerikus és alfanumerikus kódolás szóhosszát, információ tartalmát, redundanciáját megismerve vizsgáljuk meg a kódszó szerkesztésének lehetőségeit. Numerikus kódolás A numerikus kódolásnak kevesebb a szimbóluma és egyszerűbb a szerkezete: − súlyozott − a decimális alapú (Pl.:BCD binárisan kódolt decimális, vagy hexadecimális) kódból, ahol a helyiértékek súlya rendre 8 - 4 - 2 - 1

d = 8 ⋅ a4 + 4 ⋅ a3 + 2 ⋅ a2 + 1 ⋅ a1 − az Aiken kódból (decimális önkomplementáló kód), ahol a súly 4 - 2 - 2 - 1

d = 4 ⋅ a4 + 2 ⋅ a3 + 2 ⋅ a2 + 1 ⋅ a1 − a három többletes kód előfeszített súlyozott kód

d = 8 ⋅ a4 + 4 ⋅ a3 + 2 ⋅ a2 + 1 ⋅ a1 − 3

A kódszó Numerikus kódolás −nem súlyozott −a Gray kód nem súlyozott kód a bináris számból a következő algoritmus szerint állítható elő, ahol a b4, b3, b2, b1 a bináris kombinációnak megfelelő tetrádok jelölése:

Bináris → Gray

a4 = b4 a3 = b4 ⊕ b3 a2 = b3 ⊕ b2 a1 = b2 ⊕ b1

Gray → Bináris

b4 = a4 b3 = a4 ⊕ a3 b2 = a4 ⊕ a3 ⊕ a2 b1 = a4 ⊕ a3 ⊕ a2 ⊕ a1

A kódszó numerikus kódok összehasonlítása index

Kód

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

BCD

HEXA

Súlyozás 8-4-2-1 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

AIKEN

3 többletes GRAY

4-2-2-1 0 1 2 3 4 5 6 7 8 9

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0 1 2 3 4 5 6 7 8 9 A B C D E F

0000 0001 0010 0011

0110

1001

1100 1101 1110 1111

nincs 0 1 2 3 0000 0001 0010 4 0011 0100 0101 5 0110 0111 1000 6 1001 7 8 9

0 1 2 3 4 5 6 7 8 9

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

0 1 2 3 4 5 6 7 8 9 A B C D E F

A kódszó Alfanumerikus kódolás A kódszavak - alfanumerikus kódok esetén használatos a kódszó helyett a karakter megjelölés, különböző jellemző csoportokba rendezettek. X2\X1 0 1 2 3 4 5 6 7 8 9 A B C D 0 Í 1 V R K 2 E Á I 3 Z S S 4 É J 5 R E B 6 L L E 7 Ő T 8 É Ű 9 J S K A E B L S C E Z D K Á E M F

EF N A G Y B E T Ű K

X2\X1 0 1 0 1 V 2 E 3 Z 4 É 5 R 6 L 7 Ő 8 9 J A E B L C E D K E F

2 3 4 5 Í R K Á I S S J E B L E T É Ű S K

6 7 N A G Y B E T Ű K

S Z Á M

A 8 bites ASCII a 7 bites kód kiegészített változata. A kiegészítés a következőképpen történik - a 7 bites kód legnagyobb helyértékét meg kell ismételni a 2. helyérték után. Például: 100 0001 → 1010 0001, 010 0001 → 0100 0001.

Hibajelzés és hibajavítás Működőképes rendszerekben csak olyan hiba fordulhat elő, amely a jelforrásból érkező kódszó egy vagy több bitjének a továbbításakor ill. megérkezésekor az adott jelkapcsolatban tévesztést okoz. Ez azt jelenti, hogy bitcsere következik be a tévesztés helyén. Kis sebességű rendszerekben egy-egy kódszóban legfeljebb egy bitcsere fordulhat elő, és a hibák egymástól függetlenek. Nagy sebességű információ-továbbítás esetén a zavaró hatás időtartama általában hosszabb egy bit továbbításának idejénél, így előfordulhat több egymás melletti biten hibacsomó. A hibák előfordulását már a kezdeti időkben is észlelték és jelzésére vagy kiküszöbölésére különböző eljárásokat vezettek be, amelyek a redundanciával függenek össze. Ezek alap módszerek és máig használatosak, amelyek két csoportba sorolhatók: •A jelkapcsolat többszörözésével többségi logika alkalmazása. (csak hibajavítás) •A jelkapcsolatban a szimbólumok redundáns kódolása. (hibajelzés és hibajavítás)

A szimbólumok redundáns kódolása A hibajavítás korlátlanul nem használható, mert mint az előző gondolatokból is kiderült jelentős költség növekedést okozhat a túlzott mértékű alkalmazás. Megoldások, amelyek a jelkapcsolatot észszerűen felhasználhatóvá teszik: –rendszertechnikai megfontolások - a kialakítási alapokat minél jobban körül kell határolni, a fizikai működést a lehető legbiztonságosabbá kell fejleszteni a technológiák megfelelő megválasztásával. –a hibaarányt jelentősen kell csökkenteni viszonylag kevés áramköri eszközzel, illetve egyéb összetett berendezéssel. A redundáns kódolás haszna: –hibajelzés, amely lényegesen alacsonyabb értékű módszer, de el kell fogadnunk, hogy ezzel arányosak a ráfordítási igények. (Error Dtecting Code = EDC) –hibajavítás, olyan kódok szerkesztésének lehetősége, amely a bitcsere helyét megadja, és a szükséges visszaállítást elvégzi. (Error Correcting Code= ECC)

A Shanon tétel Shanon kimutatta, hogy a zajos jelkapcsolatnál tetszőleges kis hibavalószínűséggel megvalósítható a jelkapcsolat, de ekkor a kód entrópiáját - H(X)-t legalább annyival meg kell növelni, mint amekkora a jelkapcsolat zaj entrópiája. Ennek a magyarázataként, egy gyakran előforduló jelenséget vizsgáljunk meg. A kis iskolásokat kirándulni, orvosi vizsgálatra viszik. Tömegközlekedési eszközzel utaznak. Mielőtt felszálltak volna a kis iskolások, a járművön volt valamilyen alapzaj, és ehhez mérten, megfelelő hangerővel beszélgettek az utasok. A kis iskolások a felszállás után elkezdték, vagy folytatták csevegéseiket. A figyelmes utas, de a figyelmetlen is hamarosan érzékelhette, hogy néhány megálló után a csevegés ricsajjá fokozódott, és kibírhatatlanná vált. Mi a jelenség magyarázata? Nagyon egyszerű, és a Shanon tételének ez az alapja. A beszélgető kis iskolások az általuk, a környezetükben beszélgetésük által zajt keltettek egymás számára. A zaj hatásának csökkentésére növelték a beszélgetésük hang erősségét. Ez ismét zaj növekedést okozott. A zaj hatásának csökkentésére ismét hang erősség növekedés következett be. A pozitív visszacsatolás a végsőkig növeli a zajt.

A hibajelzés és a hibajavítás jellemzői A számítástechnika számára a bináris jelkapcsolat alapvetően meghatározó. Erre alapozva továbbiakban a hibajelző és -javító kódolás elmélet leginkább kidolgozott területével a bináris blokk kódokkal foglakozunk. A bináris szimbólum készletű kódok esetén a véletlen 0 → 1, vagy 1 → 0 bitcsere valószínűségének azonosságát feltételezzük, azaz a bináris csatornák a továbbiakban szimmetrikusak. A redundáns kódok hibajelző és hibajavító tulajdonságainak vizsgálatához szükséges −a kódszó súlya W(xi), −a Hamming távolság D −a kódszó Hamming súlya W(xi)

A hibajelzés és a hibajavítás jellemzői A kódszó súlya W(xi) Rögzített hosszúságú bináris kód xi kódszavának W(xi) súlyát a kódszóban lévő 1-es szimbólumok száma adja.

Hamming távolság Két kódszó Hamming távolságát úgy lehet kiszámítani, hogy a két kódszó azonos helyen álló elemeit összehasonlítjuk és megszámláljuk, hogy hány helyen áll különböző bit. xi ⊕ yi A bitek összehasonlítására alkalmas a moduló összeadás: Az X(x1, x2, ........, xn) és az Y(y1, y2, ........, yn) kódszavak Hamming távolsága n

D ( X , Y ) = ∑ ( xi , yi )

Kódszó Hamming súlya

i =1

A kódszó Hamming súlyának nevezzük azt a távolságot, amelyet a zérus kódszótól (0000 0000) mérve, a nem zérus bitjeinek száma. Ezt a mennyiséget is W(xi)-vel szokás jelölni. A definícióból következik, hogy két kódszó x1 és x2 Hamming távolsága a két kódszó moduló összegének súlyával egyezik:

D ( x1 , x2 ) = W ( x1 ⊕ x2 )

A hibajavítás korlátai A kódok hibajelző és hiba javító képességét aszerint kell megállapítani, hogy a jelkapcsolatot megvalósító rendszernek milyen az elemi hiba valószínűsége. A hibajelző és hibajavító kódok alkalmazásakor a jelkapcsolatban az információ maximális valószínűségű (maximum likelihood) dekódolását a gyakorlatban ritkán alkalmazzák. Jelentősége abban van, hogy hozzá hasonlítjuk a gyakorlatban megvalósított összes dekódolást. A hibajavító kódot optimálisan akkor választjuk meg, ha részletesen ismerjük a jelkapcsolat statisztikáját, ami a gyakorlatban többnyire nem áll rendelkezésre. A jelkapcsolat részleges ismerete alapján figyelmünket célszerűbb a tipikus hibák javítása felé fordítani. A tipikus hibák javítása, és ezentúl a véletlen hibák jelzése fontos feladat. Ennek megfelelően a javítandó ill. jelzendő hibák számának megállapítása után meg kell határozni a kódszó hosszát. A kódszó készlet javítási és jelzési feltételeit a hibák számának ismeretében a minimális Hamming távolság segítségével lehet megállapítani. A hibajavítás feltételei a redundancia biztosítására ez az első lépés.

A hibajelzés, hibajavítás korlátai Hibajelzéskor bármilyen kombinációjú d, vagy ennél kevesebb számú hiba jelzésének szükséges és elégséges feltétele:

Dmin ≥ d + 1 Hibajavításkor bármilyen kombinációjú maximálisan t számú hiba javíthatóságának feltétele:

Dmin ≥ 2 ⋅ t + 1

Hibajelzéskor és hibajavításkor maximálisan d számú hibajelzés és maximálisan t számú hibajavítás esetén a feltétel:

Dmin ≥ t + d + 1

A kódszó hosszát a hibajavítási korlátból lehet származtatni. A korlátot eddig exakt módon nem tudták előállítani, ezért a korlát számítására vonatkozóan több közelítő módszert dolgoztak ki.

A hibajavítás korlátai A kódszó készletet eredeti kódszavai k bitből állnak, a hibajavításra alkalmas kódszavak redundánsak és n-k bittel megnövelt a hosszuk. Tehát az eredeti közlemény kódszavainak hossza k, a kódolás utáni kódszavak hossza n.

eredeti eredeti közlemény közlemény kk

kódolt kódolt közlemény közlemény nn

vett vett közlemény közlemény nn


dekódolt dekódolt közlemény közlemény kk

Jelérzékelő Jelérzékelő Jelkapcsolat Zajos környezet

A hibajavítás korlátai A hiba korlátok képletei elvileg a redundanciát létrehozó bitek (n-k) számának meghatározását szolgálja. A következőkben bemutatott képletekkel explicit módon, közvetlenül nem lehet kifejezni az n-k -t.

2

Hamming korlát:

Plotkin korlát:

n−k

⎛n⎞ ≥ ∑ ⎜⎜ ⎟⎟ i =0 ⎝ i ⎠ t

n − k ≥ 2 ⋅ Dmin − 2 − log10 Dmin

Varsharmov-Gilbert-Socks korlát:

2

n−k

≥

Dmin − 2

∑ i =0

⎛n⎞ n! ⎜⎜ ⎟⎟ = ⎝ i ⎠ i!⋅(n − i )!

⎛ n − 1⎞ ⎜⎜ ⎟⎟ ⎝ i ⎠

Hamming korlát használata t=1 azaz egy hiba javítása n-k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

2n−k ≥ n + 1

2n-k m=k/n n k 0,00000 1 0 2 0,33333 3 1 4 0,57143 7 4 8 0,73333 15 11 16 0,83871 31 26 32 0,90476 63 57 64 0,94488 127 120 128 0,96863 255 247 256 0,98239 511 502 512 0,99022 1023 1013 1024 0,99463 2047 2036 2048 0,99707 4095 4083 4096 0,99841 8191 8178 8192 0,99915 16387 16373 16384 0,99954 32767 32752 32768 0,99976 65535 65519 65536 0,99987 131071 131054 131072

Dmin = 2t + 1 = 3

Dmin/n 3,00000 1,00000 0,42857 0,20000 0,09677 0,04762 0,02362 0,01176 0,00587 0,00293 0,00147 0,00073 0,00037 0,00018 0,00009 0,00005 0,00002

m=k/n a hiba javítás hatásossága

Hamming korlát használata t=2 azaz két hiba javítása n-k 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

m=k/n 0,00000 0,00000 0,20000 0,28571 0,45455 0,53333 0,63636 0,70968 0,77778 0,82540 0,86667 0,89764 0,92265 0,94118 0,95580 0,96673 0,97514

n 2 3 5 7 11 15 22 31 45 63 90 127 181 255 362 511 724

2 n − k +1 ≥ n 2 + n + 2 k

2n-k

0 4 0 8 1 16 2 32 5 64 8 128 14 256 22 512 35 1024 52 2048 78 4096 114 8192 167 16384 240 32768 346 65536 494 131072 706 262144

Dmin/n 2,50000 1,66667 1,00000 0,71429 0,45455 0,33333 0,22727 0,16129 0,11111 0,07937 0,05556 0,03937 0,02762 0,01961 0,01381 0,00978 0,00691

Dmin = 2t + 1 = 5

m=k/n a hiba javítás hatásossága

Hamming korlát hatásossága Dmin/n 1

0,75 Dmin,t 0,5

0,25

∞ 0,25

0,5

0,75

1

k/n

A hibajavítás korlátai Dmin/n 1 Hamming korlát

0,75 Plotkin korlát

0,5

Varsharmov-Gilbert-Sacks korlát

0,25

0,25

0,5

0,75

1

k/n

Paritás elemes kód VRC (Vertical Redundacy Code) d=1 egy hiba jelzése

Dmin = d + 1 = 2

k bit eredeti közlemény, n-k=1 bit párosság ellenőrző, vagy paritás bit A kettes (2) Hamming távolságú kód csak páratlan hibák jelzésére alkalmas. A kódolt közlemény n= k+1 hosszú. A jelző rendszer a kódban lévő egyesek párosságát, vagy páratlanságát figyeli. A figyelési eljárás:

x0 ⊕ x1 ⊕ ..... ⊕ xi ⊕ ...... ⊕ xk −1 ⊕ xk = xk +1 Ahol xk+1 a paritás bit.

Ezt a vonal menti módszert sok helyen alkalmazzák. A mágnes szalagos adat rögzítésnél ezt a formát VRC-nek nevezik, mert a szalag élére merőlegesen helyezkedik el a vizsgált kódszó.

Paritás elemes kód Alkalmazása (páratlan paritással) Adat bitek

0111000 1000110 1111011 0111100 1110110 0111111 1110111 1111000

VRC (Vertical Redundacy Code)

0 0 1 1 0 1 1 1

paritás-paritása

LRC (Longitudinal Redundacy Code)

Paritás elemes kód Hibajavító képessége (páros paritással) Adat bitek

0100000 0000000 0000000 0000000 0000000 0000000 0000000 0100000 01000001 10000001 LRC

VRC

paritás elemek kódszava

VRC (Vertical Redundacy Code)

1 0 0 0 0 0 0 1

paritás-paritása LRC (Longitudinal Redundacy Code)

A paritás elemek kódszavának súlya W(xi) = 4 Hamming távolsága Dmin = 4 Hibajavító képessége t=1 Dmin = 4 ≥ 2 ⋅ t + 1 Hibajelző képessége d=3 Dmin ≥ d + 1

A hibajavítási módszerek Lineáris hibajavító kódok A kódelméletben azok kódok lineárisak, amelyek lineáris műveletek végrehajtása révén kódolhatók és dekódolhatók: Lineáris hibajavító kódok: •Mátrix kódok - esetében a kódoláshoz generátor, a dekódoláshoz paritás mátrixot használnak. •Polinom kódok - esetében kódoláshoz generátor, dekódoláshoz paritás polinomot használnak. A mátrix és polinom műveletek a bináris elem készletre értelmezettek. A mátrixok és polinomok bináris mátrixok és bináris polinomok, ezért az alkalmazott műveletek (és, vagy, kizáró vagy) a bináris térre értelmezettek (regiszter szorzás, osztás).

A hibajavítási módszerek - mátrix kód Bináris kódszó, mint vektor Bármely n = 4, 7, 8, …... többelemű kódszó felfogható vektorként is.

ksz1 ksz2 ksz3 ksz4

0100000 0011001 0100100 1010010

v1 v2 v3 v4

Az n elemű kódszó-készlet egy kódszava n dimenziós vektor, így a kódszó elemeit az n dimenziós vektortér egységvektorainak is tekinthetjük. A kódszó-készlet kódszavai a vektortér vektorai, így a kódszavak és a vektortér között egyértelmű megfeleltetés van.

A hibajavítási módszerek - mátrix kód A vektorokkal végezhető műveletek „a” skalárral való szorzás esetén a vektor (v1= 0 1 0 0 0 0 0) valamennyi komponensét szorozni kell:

a * v1= a*0 a*1 a*0 a*0 a*0 a*0 a*0 = 0 a 0 0 0 0 0 Két vektor összeadásakor a vektor elemeire moduló (átvitel nélküli) összegzést kell alkalmazni.

v1 ⊕ v2 v1 ⊕ v2 =

0011001 v1 0101101 v2 0110100

A hibajavítási módszerek - mátrix kód Lineáris kombinációk és a vektortér A vektorok vektorai

v1, v2, v3, ………. vn

A vektorok lineáris kombinációi

u = d1 ⋅ v1 ⊕ d2 ⋅ v2 ⊕ d3 ⋅ v3 ⊕ ………. ⊕ dn ⋅ vn A lineárisan független vektorok

u = d1 ⋅ v1 ⊕ d2 ⋅ v2 ⊕ d3 ⋅ v3 ⊕ ………. ⊕ dn ⋅ vn ≠ 0 kivétel

d1 = d2 = d3 = ………. = dn = 0

A hibajavítási módszerek - mátrix kód Lineáris kombinációk és a vektortér A 4 bites kódszavak teljes készlete

k = 4 elem

2k = 16 vektor

A k = 4 bázis vektorok lineárisan független

v1 = 0001 v2 = 0011 v3 = 0110 v4 = 1100

A hibajavítási módszerek - mátrix kód A 4 vektor lineáris kombinációjával 16 vektor állítható elő d1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

d2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

d3 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

d4 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

u kombináció 0v1⊕0v2 ⊕0v3⊕0v4 1v1⊕0v2 ⊕0v3⊕0v4 0v1⊕1v2 ⊕0v3⊕0v4 1v1⊕1v2 ⊕0v3⊕0v4 0v1⊕0v2 ⊕1v3⊕0v4 1v1⊕0v2 ⊕1v3⊕0v4 0v1⊕1v2 ⊕1v3⊕0v4 1v1⊕1v2 ⊕1v3⊕0v4 0v1⊕0v2 ⊕0v3⊕1v4 1v1⊕0v2 ⊕0v3⊕1v4 0v1⊕1v2 ⊕0v3⊕1v4 1v1⊕1v2 ⊕0v3⊕1v4 0v1⊕0v2 ⊕1v3⊕1v4 1v1⊕0v2 ⊕1v3⊕1v4 0v1⊕1v2 ⊕1v3⊕1v4 1v1⊕1v2 ⊕1v3⊕1v4

u műveletek 0⊕0⊕0⊕0 v1 v2 v1⊕v2 v3 v1⊕v3 v2⊕v3 v1⊕v2 ⊕v3 v4 v1⊕v4 v2⊕v4 v1⊕v2 ⊕v4 v3⊕v4 v1⊕v3 ⊕v4 v2⊕v3 ⊕v4 v1⊕v2 ⊕v3⊕v4

0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

kódszavak 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0

0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0

A mátrix kód - generátormátrix Az n elemű vektorok 2n sokaságából választható ki az az „n” lineárisan független vektor, amelyet generátormátrixként lehet használni a hibajavításnál. Lineárisan független bázis vektorok képezik a generátormátrixot (G).

v1 = 0001 v2 = 0011 v3 = 0110 v4 = 1100

0001 G1 = 0011 0110 1100

Más bázis vektor választással a generátormátrix

v1 = 1000 v2 = 0100 v3 = 0010 v4 = 0001

1000 G2 = 0100 0010 0001

A hibajavítási módszerek - a hibajavító elemek A kódszó készletet eredeti kódszavai k bitből állnak, a hibajavításra alkalmas kódszavak redundanciát biztosító kiegészítői n-k bit hosszúak. Az eredeti közlemény kódszavainak hossza k, a kódolás utáni kódszavak hossza n. Hamming korlát szerint t=1 hiba javításához k=4 bit hosszúságú eredeti kódszó esetén n-k=3, tehát n=7. Eredeti kódszavak vektorai

k= 4

v1k = 0001 v2k = 0011 v3k = 0110 v4k = 1100

Kódolt kódszavak vektorai

n= 7

v1n = 0001 001 v2n = 0011 010 v3n = 0110 011 v4n = 1100 100

Az n elemű vektorok 2k sokaságából választható ki az az „k” lineárisan független vektor, amely megfelel hibajavítás feltételének és generátormátrixként lehet használni.

v1n = 0001 001 v2n = 0011 010 v3n = 0110 011 v4n = 1100 100

G1 =

0001 001 0011 010 0110 011 1100 100

Az általános generátormátrix Hamming korlát szerint t=1 hiba javításához k=4 bit hosszúságú eredeti kódszó esetén n-k=3, tehát n=7.

G=

0001 0011 0110 1100

Eredeti kódszavak mátrixa

G=

G=

Ik

i11 i12 i13 ….. i1(k-1) i1k i21 i22 i23 ….. i2(k-1) i2k ………….. ….. …... ………….. ….. …... ik1 ik2 ik3 ….. ik(k-1) ikk

001 010 011 100 Paritás kódszavak mátrixa

Pn-k p11 p12 ….. p1(n-k) p21 p22 ….. p2(n-k) ………….. . …... ………….. . …... pk1 pk2 ….. pk(n-k)

A hiba észlelés Vektoralgebrából ismert, hogy a lineárisan független vektorok ortogonálisak azaz skaláris szorzatuk 0. Például a háromdimenziós térben az i, j, k egységvektorok merőlegesek egymásra. Az „n” dimenziós terekre is mondhatjuk, hogy a G generátormátrix-szal leírt altér ortogonális a HT paritás-vizsgáló mátrix alterére. G • HT = 0 Így a G valamennyi lineáris kombinációja ortogonális a HT valamennyi lineáris kombinációjára, azaz u • HT = 0 Amennyiben

A továbbiakban

u • HT ≠ 0 a vizsgált kódszó nem megengedett kódszó. u • HT = s ≠ 0

n-k elemű szindróma vektor.

A hibamátrix A generátormátrix ismeretében a H, ill. HT mátrixok előállíthatók. Eredeti kódszavak mátrixa

HT =

Paritás kódszavak mátrixa

G=

Ik

HT =

PTk In-k

p11 p12 ….. p1k p21 p22 ….. p2k ………….. . …... ………….. . …... p(n-k)1 p(n-k)2 ….. p(n-k)k

Pn-k

i11 i12 ….. i1(n-k) i21 i22 ….. i2(n-k) ………….. ………. ………….. ………. i(n-k)1 i(n-k)2 ….. i(n-k)( n-k)

A hibajavító Hamming-kód R. W. Hamming szerkesztette az „n” elemből álló t=1 hibát javító kód algoritmusát. Jellemzője, hogy a szindróma vektor, mint bináris szám a hibás elem helyére mutat. Hamming mátrixok

11 információ bittel 4 információ bittel

1 információ bittel

01 H(3,1) = 10 11

001 010 011 H(7,4) = 100 101 110 111

H(15,11) =

0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1111

A hibajavító Hamming-kód Az ellenőrző, hibajavító elemek helye (indexe) 2 egész számú hatványa, 20, 21 , ….. , 2n-k-1, azaz a HT mátrix olyan oszlopainak felel meg, amelyben csak egy 1-es van.

u = a1 a2 a3 a4 a5 a6 a7

kódszó vektor és elemei

1 0 1 0 1 0 1 HT(7,4) = 0 1 1 0 0 1 1 0 0 0 1 1 1 1 Nem szisztematikus kód, mert a kódszó eredeti bitjei keverednek a hibajavító elemekkel.

u = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 HT(15,11) =

1 0 0 0

0 1 0 0

1 1 0 0

0 0 1 0

1 0 1 0

0 1 1 0

1 1 1 0

0 0 0 1

1 0 0 1

0 1 0 1

1 1 0 1

0 0 1 1

1 0 1 1

0 1 1 1

1 1 1 1

A hibajavító Hamming-kód Az ellenőrző, hibajavító elemek értékének meghatározása 4 eredeti bit esetére: A G generátormátrix-szal leírt altér ortogonális a HT paritás-vizsgáló mátrix alterére, ezért annak vektorai is ortogonálisak.

u • HT (7,4) = 0

a1 ⊕ a3 ⊕ a5 ⊕ a7 = 0 a2 ⊕ a3 ⊕ a6 ⊕ a7 = 0 a4 ⊕ a5 ⊕ a6 ⊕ a7 = 0

vektor és mátrix kifejtett szorzata

Így a vektor és a mátrix kifejtett szorzatából meghatározhatók az eredeti információ vektorából a hibajavító elemek.

a1 = a3 ⊕ a5 ⊕ a7 a2 = a3 ⊕ a6 ⊕ a7 a4 = a5 ⊕ a6 ⊕ a7

A hibajavító Hamming-kód Az ellenőrző, hibajavító elemek értékének meghatározása 11 eredeti bit esetére: A G generátormátrix-szal leírt altér ortogonális a HT paritás-vizsgáló mátrix alterére, ezért annak vektorai is ortogonálisak.

u • HT (15,11) = 0

a1 ⊕ a3 ⊕ a5 ⊕ a7 ⊕ a9 ⊕ a11 ⊕ a13 ⊕ a15 = a02 ⊕ a3 ⊕ a6 ⊕ a7 ⊕ a10 ⊕ a11 ⊕ a14 ⊕ a15 = a04 ⊕ a5 ⊕ a6 ⊕ a7 ⊕ a12 ⊕ a13 ⊕ a14 ⊕ a15 = a08 ⊕ a9 ⊕ a10 ⊕ a11⊕ a12 ⊕ a13 ⊕ a14 ⊕ a15 = 0

Így a vektor és a mátrix kifejtett szorzatából meghatározhatók az eredeti információ vektorából a hibajavító elemek.

a1 = a3 ⊕ a5 ⊕ a7 ⊕ a9 ⊕ a11 ⊕ a13 ⊕ a15 a2 = a3 ⊕ a6 ⊕ a7 ⊕ a10 ⊕ a11 ⊕ a14 ⊕ a15 a4 = a5 ⊕ a6 ⊕ a7 ⊕ a12 ⊕ a13 ⊕ a14 ⊕ a15 a8 = a9 ⊕ a10 ⊕ a11⊕ a12 ⊕ a13 ⊕ a14 ⊕ a15

A hibajavítás megvalósítása A kódszó készletet eredeti kódszavai k bitből állnak, a hibajavításra alkalmas kódszavak redundánsak és n-k bittel megnövelt a hosszuk. Az eredeti közlemény kódszavainak hossza k, a kódolás utáni kódszavak hossza n.

eredeti eredeti közlemény közlemény kk

kódolt kódolt közlemény közlemény ellenőrző ellenőrző elemek elemek számítása számítása

vett vett közlemény közlemény szindróma szindróma képzése képzése hibajavítás hibajavítás


dekódolt dekódolt közlemény közlemény kk

Jelérzékelő Jelérzékelő Jelkapcsolat Zajos környezet

A hibajavítás megvalósítása A hibajavító elemek értékének meghatározása kódszavanként (7,4) : 7 6 5 3

az eredeti kódszó

0 1 1 0

a1 = a3 ⊕ a5 ⊕ a7 a2 = a3 ⊕ a6 ⊕ a7 a4 = a5 ⊕ a6 ⊕ a7

a1 = 0 ⊕ 1 ⊕ 0 = 1 a2 = 0 ⊕ 1 ⊕ 0 = 1 a4 = 1 ⊕ 1 ⊕ 0 = 0

7 6 5 4 3 2 1

átviendő kódszó

0 1 1 0 0 1 1

A hibajavító elemek értékének meghatározása kódszavanként: 7 6 5 4 3 2 1

átvitt kódszó

0 1 1 1 0 1 1

a1 ⊕ a3 ⊕ a5 ⊕ a7 = s1 a2 ⊕ a3 ⊕ a6 ⊕ a7 = s2 a4 ⊕ a5 ⊕ a6 ⊕ a7 = s3

1 ⊕ 0 ⊕ 1 ⊕ 0= 0 1 ⊕ 0 ⊕ 1 ⊕ 0= 0 1 ⊕ 1 ⊕ 1 ⊕ 0= 1

A hiba jellemzője a szindróma vektor a 4-es helyre mutat.

A hibajavítás megvalósítása Kombinációs hálózattal Jelforrás

Jelérzékelő U4 a7

a7

a7 a7

U5 a6

a6

INV a5

a5

U1

XOR2 U6

a6 a6

U7 a4 INV a3

XOR3 U2

a3

a5

XOR2 U8

U9

a5

U10 a2 U3

XOR2 INV

a4

XOR3

U11

a1 a3

XOR4 U12

XOR3

U14

a2 XOR4 U15

Ellenőrző elemek előállítása a1

D C B A

a3

U13 Y9 Y8 Y7 Y6 Y5 Y4 Y3 Y2 Y1 Y0

XOR2 INV

X74_42 XOR4

Szindróma képzése, hiba javítása

A hibajavítási módszerek - ciklikus kód Bináris kódszó, mint polinom Bármely n = 4, 7, 8, …... többelemű kódszó felfogható polinomként is. A ciklikus (n, k) kód olyan n hosszúságú k információs szimbólumot tartalmazó lineáris kód, amelyben az elemek (n-1)-ed fokú polinom együtthatói. A kódszó (a0, a1, a2, a3 …... an-2, an-1) leírható a következő polinommal:

an-1•xn-1+an-2•xn-2+ …... +a3•x3+a2•x2+a1 •x+ a0 A vektortér bármely v = (a0, a1, a2, a3 …... an-2, an-1) vektorára igaz, hogy a belőle képzett v = (an-1, a0, a1, a2, a3 …... an-2) vektor szintén benne van a vektortérben. A vektortér elemeinek képzése: A vektortér elemeket cilikusan eggyel jobbra toljuk.

A hibajavítási módszerek - ciklikus kód A ciklikus kód matematikai alapja a moduló polinom algebra. Az (xn-1) moduló algebrában a polinom szorzása x-szel megfelel egy ciklikus léptetésnek. Egy ciklikus kódot egyértelműen meghatároz egy r-ed fokú g(x) polinom, amely osztja az (xn-1)-et. Az (n, k) kód értelmezhető k = n - r összefüggéssel, ahol k az eredeti kódszó hossza, r a hibajavító elemek száma. Az r-ed fokú g(x) polinommal meghatározott kódtérnek csak akkor eleme az f(x) polinom, ha osztható g(x)-szel.

f ( x) = q ( x) g ( x)

f ( x) = q( x) ⋅ g ( x)

A különböző f(x) polinomoknak különböző q(x) az eredményük.

A generátor polinom kiválasztása Egy (n, k) ciklikus kódot egyértelműen meghatároz egy r-ed fokú g(x) polinom, amely osztja az (xn-1)-et. Minden g(x) polinomhoz különböző kódtér tartozik. Az n=7 esetében a (xn-1) moduló algebrában az (x7-1) primtényezői: x7-1 = (1-x)•(1+ x+ x3)•(1+ x2 + x3) A primtényezőkből lehet választani generátor polinomot. Példa generátor-polinomok:

g(x) = 1+ x+ x3 g(x) = 1+ x2 +x3

Primtényezők ellenőrzése: (1-x)•(1+ x + x3) = 1 ⊕ x ⊕ x3 ⊕ x ⊕ x2 ⊕ x4 = 1+ x2 + x3 + x4 moduló algebrában ez moduló összegzés

moduló algebrában azonos páros elemek összege 0

(1+ x2 + x3 + x4) •(1+ x2 +x3) = 1⊕ x2⊕ x3⊕ x4⊕ x2⊕ x4⊕ x5⊕ x6⊕ x3⊕ x5⊕ x6⊕ x7 = = x7-1

A generátor polinom felhasználása A g(x) = 1+ x2 + x3 (7, 4) r=3-ad fokú polinom egyértelműen meghatározza (x7-1) ciklikus kódot. A g(x) generátor polinom teljes alakja: g(x) = 1+ x2 + x3

g(x) = 1 + 0·x1 + x2 + x3 + 0·x4 + 0·x5 + 0·x6

Ennek figyelembevételével g(x) a lineáris vektortér bázis vektorai és generátor mátrixa a következők: 1·g(x) = 1 x·g(x) = 0 x2·g(x) = 0 x3·g(x) = 0

0 1 0 0

1 0 1 1

1 1 0 0

0 1 1 1

0 0 1 1

0 0 0 0

G=

1 0 0 0

0 1 0 0

1 0 1 0

1 1 0 1

0 1 1 0

0 0 1 1

0 0 0 1

Tekintettel arra, hogy a kód ciklikus és lineáris a bázis vektorok és lineáris kombinációja is kódpolinom. 1·g(x) = f0(x) x·g(x) = f1(x) x2 ·g(x) = f2(x) x3 ·g(x) = f3(x)

Ellenőrző elemek A g(x) polinommal előállított kódtér kódjai, mint a generátor mátrixból is látszik nem szisztematikus, nem választható információs és hibajavító elemekre.

G=

1 0 0 0

0 1 0 0

1 0 1 0

1 1 0 1

0 1 1 0

0 0 1 1

0 0 0 1

A kódolás, dekódolás szempontjából a megvalósítás egyszerűbb a szisztematikus kód használatával. A (k-1)-ed fokú p(x) információ polinomot xn-k-val megszorozva (xn-1) kódtérnek része lesz, azonban ezzel - a g(x) polinommal meghatározott ciklikus kóddá még nem vált. A p(x) ·xn-k információ polinomot g(x) polinommal elosztva nagyon valószínű, hogy a q(x) hányados polinom mellett r(x) maradék polinom is képződik.

p ( x) ⋅ x n − k = q ( x) + r ( x) g ( x)

Ellenőrző elemek számítása A p(x) ·xn-k információ polinom, akkor válik f(x) kódpolinommá, ha :

f ( x) = p ( x) ⋅ x n − k + r ( x) = q ( x) ⋅ g ( x) Az r(x) hibajavító polinom - (n-k) = r elem számú - azaz (r-1)-ed fokú. A ciklikus kódok azért is terjedtek el, mert előállításuk egyszerű, viszonylag kevés áramköri elem szükséges felépítésükhöz. A kódolás xn-k · p(x) szorzásból, kettes számrendszerben léptetésből, és az r(x) meghatározásából áll. A kódoláshoz szükséges polinom műveletek elvégezhetők visszacsatolt léptető regiszterekkel, mert a bináris szorzás és az osztás alapvetően léptetési algoritmusok. Például:

(7,4) választás esetén n-k = 3

g(x) = 1+ x + x3

x3 · p(x) = x3 · (1+ x ) = x3 + x4

Ellenőrző elemek számítása Például: (7,4) választás esetén n-k = 3 g(x) = 1+ x + x3 p(x) = 1+ x információ polinom x3 · p(x) = x3 · (1+ x ) = x3 + x4 A 3-ad fokú p(x) információ polinomot x3-nal megszorozva (x7-1) kódtérnek része lesz. p ( x) ⋅ x 3 = q( x) + r ( x) r ( x) ≠ 0 g ( x) Ezzel azonban a g(x) polinommal meghatározott ciklikus kóddá még nem vált. (x4 + x3 ) : (x3 + x + 1) = x + 1 x4 + x2 + x x3 + x2 + x +x+1 x3 x2 +1 Maradék polinom - a polinom hibjavító része

Az osztásban a moduló műveleteket kell alkalmazni.

r(x) = x2 + 1

p ( x) ⋅ x 3 + r ( x) = q( x) g ( x)

Hogyan tehető szisztematikussá a ciklikus kód? Az információ polinomok szorzása xn-k-val a ciklikus kódot szisztematikussá tette, mert az x0 helyértékű elem is xn-k helyértékű lesz és még a maradék polinom n-k-1 helyértékű eleme is hozzá illeszthető. Például:

(7,4) választás esetén n-k = 3

Információ kód p(x) 3210 0000 0 0001 1 0010 x 0011 x+1 0100 x2 0101 x2+1 0110 x2+x 0111 x2+x+1 1000 x3 1001 x3+1 1010 x3+x 1011 x3+ x+1 1100 x3+ x2 1101 x3+ x2+1 1110 x3+ x2+x 1111 x3+ x2+x+1

3

g(x) = 1+ x2 + x3 3

x p(x)

r(x)

f(x)= x p(x)+ r(x)

0 x3 x4 x4+x3 x5 x5+x3 x5+x4 x5+ x4+x3 x6 x6+x3 x6+x4 x6+ x4+x3 x6+x5 x6+ x5+x3 x6+ x5+x4 x6+ x5+x4+x3

0 x +1 2 x +x+1

0+0 x3+x2+1 x4+x2+x+1 x4+x3+x x5+x+1 x5+x3+x2+x x5+x4+x2 x5+ x4+x3+1 x6+x2+x x6+x3+x+1 x6+x4+1 x6+ x4+x3+x2 x6+x5+x2+1 x6+ x5+x3+0 x6+ x5+x4+x x6+ x5+x4+x3+x2+x+1

2

x+1 x2+x x2 1 2 x +x x+1 1 x2 x2+1 0 x 2 x +x+1

Kódolt információ 6543 210 0000 000 0001 101 0010 111 0011 010 0100 011 0101 110 0110 100 0111 001 1000 110 1001 011 1010 001 1011 100 1100 101 1101 000 1110 010 1111 111

Ellenőrző elemek áramköri előállítása g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear

Az áramkör működésének szimulációja: p(x) = 0 x3·p(x) = 0 1 0 1 0 0 0

D CE C CLR

Q

FDCE

A maradék polinom előállítását végző osztó áramkör

1 0 1

információ polinommal


R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear


D CE C CLR

Q

FDCE


1 0 1



R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear


D CE C CLR

Q

FDCE


1 0 1



R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear


D CE C CLR

Q

FDCE


1 0 1



R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear


D CE C CLR

Q

FDCE


1 0 1



R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear


D CE C CLR

Q

FDCE


1 0 1



R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

x3

D CE C CLR FDCE

U6 Q XOR2

D CE C CLR

U7 Q XOR2 U3

FDCE

CE clock clear


D CE C CLR

Q

FDCE


1 0 1


r(x)

Az áramköri hiba ellenőrzési folyamat Hiba ellenőrzésének szimulációja: f(x) = 1

0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 0 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 0 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 0 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 0 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 0 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 0 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q


Az áramköri hiba ellenőrzési folyamata Hiba ellenőrzésének szimulációja: f(x) = 1

0 0 0 1 1 0

kódolt polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR

Q

FDCE


0 0 0 1 1 0

r(x)


0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 1 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 1 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 1 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 1 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 1 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

0 0 1 1 1 0

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR FDCE

Q



0 0 1 1 1 0

hibás polinommal

g(x) = 1+ x2 + x3

R_x_0 R_x_1 R_x_2

1 log0

x2

U1

U2 U5

I_x XOR2

D CE C CLR

U6 Q XOR2

FDCE

CE clock clear

f(x) = 1

x3

D CE C CLR FDCE

U7 Q XOR2 U3

D CE C CLR

Q

FDCE


0 0 1 1 1 0

r(x)

VXA helikális rögzítési technológiájához kapcsolódó hibajavítás A rögzítés alapja a Discrete Packet Format (DPF)

Szalag éle

Szalag éle

Sávok

Discrete Packet Format (DPF) 387 Packets

Sáv

A Packet felépítése SYNC ADDR

DATA

CRC ECC

Packet

Az olvasott Packet elhelyezése a puffer területen SYNC SYNC SYNC ADDRSYNC ADDR ADDR ADDR

DATA DATA DATA DATA

Buffer Segment

CRC CRC CRC ECC ECCCRC ECC ECC

Az olvasott Packet elhelyezése a puffer területen SYNC SYNC SYNC ADDRSYNC ADDR ADDR ADDR

DATA DATA DATA DATA

Buffer Segment

CRC CRC CRC ECC ECCCRC ECC ECC

DATA

Y-Axis ECC

Error Correction Code

X-Y ECC X-Axis ECC Diagonal ECC

Buffer Segment

CRC

Kódolás, hibajavítás. Tervezte és készítette Géczy LászlL. szló 2002

Recommend Documents