Kódolás és szimbolikus dinamika

Eötvös Lóránd Tudományegyetem Természettudományi Kar

Kódolás és szimbolikus dinamika szakdolgozat

írta: Rusz Mihály Balázs Matematika BSc, matematikai elemző szakirány Témavezető: Buczolich Zoltán egyetemi docens ELTE TTK Analízis tanszék

Budapest, 2010

Tartalomjegyzék 1. Bevezetés

3

1.1. Motiváció . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2. A merevlemez vázlatos működése . . . . . . . . . . . . .

4

1.3. Problémák egy az egyben tárolás esetén . . . . . . . . . .

5

1.4. Az MFM kódolás . . . . . . . . . . . . . . . . . . . . . .

6

2. Alapismeretek

7

2.1. A szimbolikus dinamika alapjai . . . . . . . . . . . . . .

7

2.1.1. A teljes shift . . . . . . . . . . . . . . . . . . . . .

7

2.1.2. Shift terek . . . . . . . . . . . . . . . . . . . . . .

9

2.1.3. Csúszó blokk kódok . . . . . . . . . . . . . . . . . 10 2.2. A véges állapotú gép . . . . . . . . . . . . . . . . . . . . 11 3. Véges állapotú kód építése

17

3.1. State-splitting . . . . . . . . . . . . . . . . . . . . . . . . 17 3.1.1. Elemi splitting . . . . . . . . . . . . . . . . . . . 18 3.1.2. Generált splitting . . . . . . . . . . . . . . . . . . 19 3.1.3. Teljes splitting . . . . . . . . . . . . . . . . . . . 19 3.2. Közelítő sajátvektorok . . . . . . . . . . . . . . . . . . . 20 3.2.1. A közelítő sajátvektor algoritmus . . . . . . . . . 21 3.3. Elemi v-konzisztens splitting . . . . . . . . . . . . . . . . 22 3.4. A kódoló építése . . . . . . . . . . . . . . . . . . . . . . . 23 3.4.1. A kódoló eljárás . . . . . . . . . . . . . . . . . . . 29 3.5. A state-splitting algoritmus . . . . . . . . . . . . . . . . 29 4. Állapotfüggő dekóder

30

4.1. A dekódoló eljárás . . . . . . . . . . . . . . . . . . . . . 31

2

1.

Bevezetés

1.1.

Motiváció

Napjainkban, mikor a technika igen nagy ütemben fejlődik és minden valószínűség szerint ez az iram csak nőni fog, rendkívül fontos a hatékonyság, a takarékosság és a gyorsaság. A számítógépek segítségével olyan korlátokat léptünk át, melyek a korábbi századokban megközelíthetetlennek látszottak. Egyre szélesebb körökben váltja fel a ceruzát és a tollat a billentyűzet, a papírt a merevlemez, a CD, a DVD, a pendrive, vagy éppen a mobiltelefonunkba is helyezhető Micro SD kártya. Formanyomtatványok helyett intenetes űrlapokat tölthetünk ki, például személyi jövedelemadónkat is bevallhatjuk ilyen módon. Az interneten keresztül levelezhetünk, vásárolhatunk, közzétehetjük szakdolgozatunkat, híreket olvashatunk. Szinte végtelen hosszú az újítások sora. Lehetőségünk nyílt nagyon nagy információmennyiség feldolgozására (gondoljunk például a meteorológiára), viszont ezt a rengeteg adatot tárolnunk is kell. A merevlemezen, CD-n, DVD-n, stb. az információt 0-1 sorozatok formájában tároljuk. A gyakorlat azt mutatta, hogy az ilyen sorozatokat nem célszerű egy az egyben tárolni – részben a hibalehetőségek miatt, részben pedig a tárhelyigény nagysága miatt – ezért kódolni kell őket. Ennek a dolgozatnak a célkitűzése, hogy bemutassa egy véges állapotú kódoló építésének menetét, illetve az állapotfüggő dekóder rel történő dekódolási eljárást. Először a merevlemez vázlatos működési elvét írom le, majd néhány gyakorlati problémát ismertetek, melyek a merevlemezen történő adattárolásnál jelentkeznek, azután rátérek a fő témára, hogy hogyan is 3

lehet egy véges állapotú géppel kódolni az inputként kapott 0-1 sorozatokat, majd pedig hogyan lehet a kódolt sorozatokat dekódolni.

1.2.

A merevlemez vázlatos működése

A merevlemez belsejében több, egymás fölött elhelyezkedő, mágnesezhető réteggel bevont körlemez található.

Ezek folyamatosan

forognak, manapság egy asztali 7200

számítógépben

általában

f ordulat/perc,

egy notebook-

ban pedig 5400 f ordulat/perc sebességgel. Minden lemez adatsávokra van osztva (lásd 2. ábra). Az adatokok olvasására, illetve írására egy fej szolgál, amely sugárirányban tud mozogni a lemezeken. Íráskor ebben a fejben

1. ábra. Illusztráció

áram folyik, aminek az iránya változtatható. Ennek az áramnak a hatására a lemez mágneseződik. Az 3. ábrán látható, hogyan alakul a mágnesezettség, ha a 0101000111010 sorozatot kell felírnunk a lemezre. Ha inputként egy 1-es érkezik, akkor megváltozik az áram iránya, ezzel ellentétes polaritású mágnest hoz létre, ha pedig 0, akkor nem változik. A 4. ábrán az adat visszaolvasásának folyamata látható. Az L érték az úgynevezett mérési ablak hossza. Azt figyeljük, hogy egy-egy mérési ablakon belül jelentkezik-e impulzus (feszültség csúcs), amit az ellentétes polaritású mágnesek idéznek elő. Ha van impulzus, azt 1esnek olvassuk le, a hiánya pedig a 0-t jelenti.

4

2. ábra. Az adatok elhelyezkedése a merevlemezen

3. ábra. Adat írásakor

1.3.

Problémák egy az egyben tárolás esetén

Interferencia. Ez a probléma akkor jön elő, ha túl sűrűn történik a polaritásváltás, mert ilyenkor előfordulhat, hogy a mágneses erőtérben kioltódás lép fel. A merevlemez tulajdonságai miatt létezik egy minimális ∆ távolság, aminek két polaritásváltás között lennie kell. Ha tudjuk, hogy olyan sorozatokkal dolgozunk, amelyekben két 1-es között d darab 0 van, akkor a mérési ablakunk csökkenthető lenne re, mert még így is elég messze lenne egymástól a két 1-es. Órajel-elcsúszás.

5

∆ d+1

4. ábra. Adat olvasásakor Akkor jelentkezik ez a probléma, ha túl sok a 0 két 1-es között. Tartalmazzon az adatunk egy 10 . . . 01 részt. Ahol a 0-k száma n. Ezt úgy olvassuk ki, mint (n + 1) · L idővel elválasztott polaritásváltást. Ha n nagy, akkor az órajelben levő legkisebb elcsúszás is hibás n-et eredményez, amelyből következik, hogy hibás adatot fogunk kiolvasni. Ezt a hibát például úgy is ki lehet küszöbölni, hogy nem engedünk meg kettő darab 0-t egymás mellett.

1.4.

Az MFM kódolás

A fent említett problémákat orvosolhatjuk a módosított frekvencia modulációs (MFM) módszerrel is, mely a következőképpen működik. 0-t szúrunk be az 10, a 01 és az 11 közé, 1-est a 00 közé. Például 10001101 −→ 0100101001010001 Az így kapott kódok olyanok, hogy kellően sokszor fordul elő bennük 1es, amit használhatunk órajelszinkronizációra, és nincs egymás mellett 6

kettő 1-es, így a mérési ablak a felére csökkenthető (L = ∆2 ). n bitet
ugyan 2n bittel tudunk kódolni, de a helyigény 2n ∆2 = n∆ marad.

2.

Alapismeretek

Ez a fejezet azt a célt szolgálja, hogy ismertesse azokat a definíciókat és állításokat, melyek elengedhetetlenek lesznek a későbbiekben. Két terület ismeretanyagára lesz szükségünk. Először meg kell ismerkednünk a szimbolikus dinamika alapjaival, majd pedig a véges állapotú gépekkel.

2.1.

A szimbolikus dinamika alapjai

Az információt gyakran olyan sorozatokkal írjuk le, melyek elemei egy véges halmazból kerülnek ki. Pédául ez a dolgozat is betűk, írásjelek és matematikai szimbólumok hosszú sorozata. 2.1.1.

A teljes shift

2.1. Definíció. Az A véges halmazt, melyből a sorozat elemei származnak ábécének, A = {a, b, c, . . .} esetén a-t, b-t, stb. betűknek nevezzük. Például a 10-es számrendszerben felírt számok esetében A = {0, 1, 2, . . . , 9}, bináris sorozatok esetében pedig A = {0, 1}. Bár a valóságban a sorozatok végesek, gyakran praktikus végtelennek tekinteni őket. A mindkét irányban végtelen sorozatokat x = . . . x−2 x−1 x0 x1 x2 . . . alakban fogjuk felírni, ahol xi ∈ A minden i-re. Az xi szimbólumot x i-edik koordinátájának nevezzük. A 0. koordinátát külön ki is emel7

hetjük, mi pontot fogunk tenni elé. Például . . . 4021.31324 . . . esetén x0 = 3, x1 = 1 stb. 2.2. Definíció. Ha A egy ábécé, akkor teljes A-shiftnek hívjuk az összes mindkét irányban végtelen sorozat halmazát, ahol a sorozat tagjai csak A elemei közül kerülhetnek ki. Teljes r-shiftnek, vagy egyszerűen r-shiftnek nevezzük azt a teljes shiftet, amelynek ábécéje az A = {0, 1, . . . , r − 1} halmaz. A teljes A-shiftre bevezetjük azt a jelölést, hogy AZ = {x = (xi )i∈Z : xi ∈ A minden i ∈ Z-re} . Az x ∈ AZ -t AZ egy pontjának nevezzük. A későbbiekben nem csak külön-külön kell szimbólumokat kezelnünk, hanem úgynevezett blokkokat, vagy más néven szavakat is, melyeket úgy definiálunk, mint az ábécébeli szimbólumok véges hosszú sorozatai. A blokk hossza a benne szereplő szimbólumok száma. Megengedett az -nal jelölt üres blokk is, ennek hossza 0. Például A = {1, 2, 3} esetén 1312133 egy hét hosszú blokk. A k hosszú blokkokat k-blokkoknak is szoktuk hívni. Bevezetjük a blokkok számára az x[i,j] = xi xi+1 . . . xj jelölést. i > j esetén x[i,j] legyen . 2.3. Definíció. Legyen X ⊂ AZ és x = (. . . x−2 x−1 .x0 x1 x2 . . .) ∈ X. Shiftnek1 nevezzük a következő σ-val jelölt függvényt. σ : X → X,

σ(xi ) = xi+1 minden i-re, azaz

σ(. . . x−2 x−1 .x0 x1 x2 . . .) = (. . . x−1 x0 .x1 x2 x3 . . .) Látszik, hogy a shift függvény invertálható, az inverzét jelöljük σ −1 -nel. σ −1 (xi ) = xi−1 . Jelölje σ n a shift n-edik iteráltját, azaz σ(σ(. . . σ(x) . . .))t, vagyis σ n (xi ) = xi+n . Hasonló módon definiáljuk σ −n -t is. 1

Magyarra fordítva eltolást jelent, de inkább az angol verzió használatos.

8

2.1.2.

Shift terek

Sokszor szükség van arra, hogy a szimbólum sorozatainkban ne fordulhassanak elő bizonyos blokkok. A merevlemeznél, ahogy az előzőekben láttuk, problémát okoz, ha két 1-es van egymás mellett, vagy ha túl sok a 0 két 1-es között. 2.4. Definíció. Legyen F blokkoknak egy halmaza, ezeket fogjuk tiltott szavaknak hívni. Jelölje ΩA,F azon x ∈ AZ elemek halmazát, melyek F egyetlen elemét sem tartalmazzák. Shift térnek nevezzük az AZ egy Ω részhalmazát, ha Ω = ΩA,F valamilyen F blokkhalmazzal. Példák shift terekre. 1. Nyilván, minden teljes A-shiftre igaz az, hogy AZ = ΩA,{} , vagyis ha nem tiltunk le semmit, akkor meghagytuk az összes sorozatot. Szintén nyilvánvaló, hogy ΩA,A = ∅, hiszen ekkor mindent letiltunk. 2. Azt a shift teret szeretnénk definiálni, melynek ábécéje A = {0, 1}, és nem fordulhat elő benne két darab 1-es egymás mellett. Ebben az esetben a tiltóblokk-halmaz egyelemű, F = {11}. Tehát a keresett Ω shift tér az Ω2,{11} . Például az x = . . . 01000101.0010010 . . . ∈ Ω2,{11} , de y = . . . 01100111.0010010 . . . ∈ / Ω2,{11} . 3. RLL(d, k)-val2 jelöljük azokat a speciális típusú A = {0, 1} ábécé felett értelmezett shift tereket, amelyekben két 1-es között legalább d, legfeljebb k darab 0 lehet. Az RLL(0, 2) esetében a tiltóblokkokhalmaz F = {000}. 2

Az angol Run Length Limited rövidítése.

9

Egy adott shift térnek nem feltétlenül egyértelmű a tiltóblokk-halmaza. A 2-es példában F = {000} helyett választhattuk volna az F 0 = {1000, 010001, 00000}-t is. 2.5. Definíció. Véges típusú shift térnek hívjuk azokat a shift tereket, melyek véges sok tiltó blokkal megadhatóak. Ellenkező esetben a végtelen típusú shift tér kifejezést haszáljuk. 2.6. Definíció. Legyen X egy teljes shift részhalmaza, Bn (X) pedig az összes n-blokk, ami előfordul X-ben. X nyelvének nevezzük az B(X) =

∞ [

Bn (X)

n=0

kifejezést, vagyis az összes X-ben előforduló szavak halmazát. Az előző példák közül a 2-esben szereplő shift tér nyelve {, 0, 1, 00, 01, 10, 000, 001, 010, 100, 101 . . .} . 2.1.3.

Csúszó blokk kódok

Tegyük fel, hogy egy sorozat x = . . . x−1 x0 x1 . . . egy X shift térben az A ábécé felett. Legyenek m és n rögzített egész számok, amikre teljesül, hogy −m ≤ n. Szeretnénk x-et átalakítani egy y = . . . y−1 y0 y1 . . . egy másik C ábécé feletti sorozattá. Ehhez egy Φ függvényt használunk, amely X-beli megengedett (m+n+1)-blokkokból, azaz Bm+n+1 (X)-ből képez C-beli szimbólumokká. Az ilyen függvényeket (m + n + 1)-blokk leképezéseknek hívjuk. y koordinátáit a következő módon számítjuk ki.
yi = Φ (xi−m xi−m+1 . . . xi+n ) = Φ x[i−m,i+n] .

10

2.7. Definíció. Legyen X egy shift tér A felett és Φ : Bm+n+1 (X) → C egy blokk leképezés. Ekkor a φ : X → C Z csúszó blokk kódnak hívjuk, melynek memóriája illetve anticipációja a Φ függvényhez tartozó m és n.

2.2.

A véges állapotú gép

A véges állapotú gép szimbólumokból álló sztringekkel3 dolgozik, van egy kijelölt kezdőállapota és rendelkezik egy átmenet-függvénnyel, amely meghatározza, hogy az adott beérkező szimbólum hatására a gép melyik állapotába kerüljön (előfordulhat az is, hogy a gépnek ugyanabban az állapotában kell maradnia). Az állapotok száma pedig véges. Példa. Képzeljünk el egy embert, aki imád sportfogadásokat kötni, és egy olyan szolgáltatásra is előfizetett, amely sms-értesítést küld arról, hogy a meccs végeredménye egyezik-e az általa megtippeltel. Az sms-ben különbözés esetén a 0, egyezés esetén 1-es érkezik. Emberünk ezzel – tudta nélkül is – egy véges állapotú géppé vált, mégpedig a következő módon. Ha helyesen tippelt, akkor boldog állapotba, ha rosszul, akkor pedig szomorú állapotba kerül. Ha már eleve boldog volt, és 1-es érkezik az sms-ben, akkor boldog is marad, ha pedig szomorú volt és 0 érkezik, akkor szomorú is marad. Kis tétekkel játszik, csupán hobbiból, nem számít neki, hogy a végén profitja, vagy vesztesége származik a játékokból. Az 5. ábra mutatja, hogyan néz ki az őt leíró véges állapotú gép. Tegyük fel, hogy éppen boldog volt, amikor ezt az üzenetsorozatot kapja: 011010100111. Az ábráról jól leolvasható, miként változott a hangulata az sms-ek hatására. Az 5. ábrát a gép állapotátmeneti diagramjának (Finite State Tran3

A sztring egyszerű objektumoknak, például karaktereknek egy sorozata.

11

5. ábra. Egy véges állapotú gép sition Diagram, FSTD) hívjuk, melynek kulcsfontosságú szerepe lesz, amikor kódoló építésére használunk véges állapotú gépeket.

2.8. Definíció. FSTD-nek nevezünk egy G irányított gráfot, amelynek véges sok csúcsa (ezek felelnek meg az állapotoknak) és éle van, az élei pedig egy véges ábécé elemeivel vannak megcímkézve. A csúcsok halmazát V (G)-vel, az élek halmazát E(G)-vel jelöljük. Irányítatlan gráfokat is tudunk FSTD-ként kezelni, ha az éleket odaés visszafele irányítva is behúzzuk. Hogyan tudunk FSTD-vel sztringeket gyártani? Kiválasztunk egy kezdő csúcsot, majd innen indulunk el az élek mentén, természetesen figyelembe véve azok irányítását. Minden egyes él meg 12

6. ábra. Tipikus FSTD van címkézve, amelyeket az élen való áthaladáskor leolvasunk. A 6. ábrán látható FSTD-vel például a accca sztringet a csúcsok 421113 sorozatával tudjuk előállítani. 2.9. Definíció. Egy FSTD által generált összes véges hosszúságú sorozatok halmazát korlátozott rendszernek hívjuk és S-sel jelöljük. 2.10. Definíció. Egy G FSTD-t determinisztikusnak nevezünk, ha minden csúcsára igaz az, hogy a kimenő élek különbözően vannak megcímkézve. Vagyis ahhoz, hogy előállítsunk egy kívánt címkét, egyértelműen meg van határozva, hogy melyik élen kell elindulnunk az adott csúcsból. 2.11. Definíció. Ha a G FSTD minden i csúcsára teljesül, hogy minden a + 1 hosszú út, ami i-ben kezdődik és ugyanazt a sorozatot állítja elő ugyanazzal az éllel indul, és a a legkisebb ilyen pozitív egész, akkor a-t G lokális anticipációjának nevezzük. Más szavakkal, elég ha tudjuk a kiinduló csúcsát egy útnak és a sztring első a + 1 szimbólumát amit generál ahhoz, hogy tudjuk az első él végpontját. 13

2.12. Definíció. Egy G FSTD-nek véges a lokális anticipációja, ha a véges. Ha nincs véges a, akkor végtelen lokális anticipációjúnak nevezzük. Az FSTD determinisztikussága ekvivalens azzal, hogy a lokális anticipációja 0, hiszen ez azt jelenti, hogy ha tudjuk a kiinduló csúcsot és a sztring 0 + 1 = 1 szimbólumát amit generál, az elég ahhoz, hogy tudjuk az első és egyben egyetlen él végpontját.

7. ábra. 1 anticipációjú FSTD

2.13. Definíció. Egy G FSTD-t irreducibilisnek nevezünk, ha bármely i kezdőcsúcsából vezet út bármely kiválasztott j csúcsba. Ha pedig nem irreducibilis, akkor reducibilisnek nevezzük. 2.14. Definíció. Egy G FSTD-t szétesőnek nevezünk, ha az éleinek halmaza szétbontható két részre úgy, hogy ne létezzen olyan él, melynek végpontjai különböző részben vannak. Ha nem széteső, akkor összefüggőnek nevezzük.

14

2.15. Definíció. Egy G irreducibils FSTD-t, amely valódi része (egyenlőséget nem engedünk meg) egy irreducibilis FSTD-nek, irreducibilis komponensnek nevezünk.

8. ábra. Egy reducibilis FSTD és az irreducibilis komponensei

2.16. Definíció. Gq -t G q-adik hatványának nevezzük.

Gq csúcsai

ugyanazok, mint G csúcsai, de akkor van él két csúcs között, ha Gben létezett egy q-hosszú út köztük. A Gq által generált rendszert S q -val jelöljük. S q ábécéjét S-beli q-blokkok alkotják. Ha G-nek véges lokális anticipációja volt, akkor Gq -nak is az lesz. Ha G irreducibilis FSTD, akkor bármely hatványa vagy irreducibilis, vagy szétesik diszjunkt irreducibilis komponensekre. 2.17. Definíció. A Cap(S) = limn→∞

log2 (N (n;S)) n

mennyiséget az S

rendszer Shannon-kapacitásának nevezzük, ahol az N (n; S) az S-beli n hosszú utak számát jelöli. Cap(S) az n hosszú sztringek növekedési ütemét méri, azaz elég nagy n-re a megengedett n hosszú sztringek száma jól becsülhető a 2Cn értékkel, ahol Cn =

log2 (N (n;S)) . n

15

Shannon megmutatta, hogy ez a mennyiség felső korlátot ad az elérhető rátára bármely véges állapotú rendszerben. Sőt, adott p, q egymáshoz relatív prím egészekre, amelyekre p/q ≤ Cap(S) teljesül, létezik olyan k egész szám és 2kp blokk S-ben, amelyek kq hosszúak. Bármely S-et reprezentáló G FSTD Shannon-kapacitását kiszámíthatjuk, feltéve, hogy a lokális anticipációja véges. A legegyszerűbb abban az esetben, ha az FSTD determinisztikus. A számításhoz a gráf szomszédsági mátrixát használjuk, amit A(G)-vel jelölünk4 . 2.18. Állítás. Legyen G egy FSTD. Ha G-nek véges a lokális anticipációja, akkor Cap(S) = log2 λ(A(G)), ahol λ(A(G)) a szomszédsági mátrix legnagyobb valós sajátértéke. 2.19. Állítás. Legyen G egy FSTD, szomszédsági mátrixa pedig A(G) és legyen m ≥ 1. Ekkor az m hosszú utak száma i-ből j-be (A(Gm ))ij , ebből adódóan Gq szomszédsági mátrixa A(G)q lesz. Bizonyítás. m = 1-re igaz az állítás, hiszen így definiáltuk A(G)t. Legyen A = A(G). A2 = AA. Jelölje ai. a baloldali mátrix i-edik sorvektorát, a.j a jobboldali mátrix j-edik oszlopvektorát. Ekkor a (A2 )ij = ai1 a1j + ai2 a2j + . . ., ahol ai1 azt mutatja, hogy hányféleképpen juthatok el (hány út vezet) i-ből 1-be, a1j pedig azt, hogy hányféleképpen juthatok el 1-ből j-be. ai1 a1j az összes kettő hosszú utat jelenti, ami átmegy az 1-es csúcson. Ugyanígy ai2 a2j a 2-es csúcson átmenő kettő hosszú utakat számolja és így tovább. Összegük tehát az összes i-ből j-be vezető kettő hosszú utak száma. Ugyanezzel az érveléssel, Am = Am−1 A esetén Am−1 az összes m − 1 hosszú utat megszámolta, az A-val való szorzás pedig megnöveli az utak hosszát eggyel.  4

A(G) = {aij } szomszédsági mátrix, ahol aij az i csúcsból a j csúcsba vezető

élek számát jelenti.

16

2.20. Állítás. Az S q rendszer kapacitása q-szorosa az S rendszer kapacitásának, azaz Cap(S q ) = qCap(S). Bizonyítás. Tudjuk, hogy Cap(S) = log2 (λ(A)). Cap(S q ) = log2 (λ(Aq )) = log2 (λ(A))q = qλ(A).

3.

Véges állapotú kód építése

3.1. Tétel. Véges állapotú kódolás tétele. Legyen az S rendszer Shannon-kapacitása Cap(S). Legyenek p, q ∈ Z+ , p/q ≤ Cap(S). Ekkor létezik véges állapotú kódoló állapotfüggő dekóderrel, amely bináris adatot kódol a rendszerbe konstans p/q rátával. Ez a tétel biztosítja, hogy létezik olyan véges állapotú kód, amelynek rátája eléri a Cap(S)-t abban az esetben, ha az racionális, másrészt bármely adott p, q egészekre, amelyek teljesítik a fenti feltételeket, létezik olyan kódoló, amely p/q rátával működik. A tétel bizonyítása a következő módszeren alapszik.

3.1.

State-splitting

Adott a G FSTD és p/q rátájú kódot szeretnénk készíteni (p/q ≤ Cap(S)). Tekintsük Gq -t, G q-adik hatványát. Itt a csúcsok ugyanazok, mint G-ben, az élek viszont G-beli q hosszú utaknak felelnek meg. Ahhoz, hogy elő tudjunk állítani minden adatként érkező p-blokkból egy q-blokkot, Gq minden egyes csúcsából legalább 2p darab él kell, hogy kiinduljon. Az egy csúcsból kiinduló élek számát kifoknak nevezzük és dki -vel jelöljük. Tehát a feltételünk a következő.

17

dki ≥ 2p .

(3.1.1)

A későbbiekben látni fogjuk, hogy valójában elég, ha létezik egy rész-FSTD, amely rendelkezik ezzel a tulajdonsággal. 3.2. Definíció. Az R(i) sorösszeget a következő módon definiáljuk. R(i) = A(K)i,1 + A(K)i,2 + . . . + A(K)i,N , ahol A(K)i,j a K-beli i csúcsból a j-be vezető élek száma. Vagyis ha a szomszédsági mátrix egy sorának elemeit összeadjuk, akkor pont a sorindex által reprezentált csúcs fokát kapjuk meg. Ezzel a jelöléssel a 3.1.1 feltétel: R(i) ≥ 2p

(3.1.2)

A(Gq )u ≥ 2p u

(3.1.3)

Tekintsük az

egyenlőtlenséget, ahol u egy 0-1 oszlopvektor, vagyis olyan oszlopvektor, amelynek komponensei 0 vagy 1 értékűek lehetnek. Azok a csúcsok, amelyeknek megfelelő u-beli komponens 1-es, egy olyan rész-FSTD-t alkotnak, amely teljesíti a feltételt. 3.1.1.

Elemi splitting

Legyen H egy FSTD és legyen Ei az i csúcsból induló élek halmaza. Osszuk fel két diszjunkt részre Ei -t. A felosztás utáni egyik élhalmazt jelöljük Ei1 -vel, a másikat pedig Ei2 -vel. Ezután elkészítünk egy H 0 FSTD-t, amelynek a csúcshalmazába belevesszük i-t kivéve H minden csúcsát, az i csúcsot pedig két új csúccsal helyettesítjük, melyeket jelöljünk i1 -gyel és i2 -vel. Tehát 18

V (H 0 ) = {j ∈ H|j 6= i} ∪ {i1 , i2 }

(3.1.4)

i1 -et és i2 -t i leszármazottjainak, i-t pedig i1 és i2 szülőjének nevezzük. H 0 élei pedig a következők lesznek: 1. eset: ha H-ban az él j 6= i-ből i-be vezetett, akkor H 0 -ben i1 -be és i2 -be is behúzunk egy élt. 2. eset: ha H-ban i-ből indult és j 6= i-be vezetett, és e ∈ Eik , akkor H 0 -ben ik -ból fog j-be vezetni (k ∈ {1, 2}). 3. eset: ha H-ban i-nél hurokél található és e ∈ Eik , akkor H 0 -ben két él indul ik -ból, egy i1 -be és egy i2 -be. Minden esetben az élek címkéi H 0 -ben megegyeznek a szülő élek címkéivel. 3.1.2.

Generált splitting

Ez egy általánosabb formája a elemi splittingnek és vissza is lehet vezetni rá. 2 helyett N részhalmazra bontjuk az éleket. Ei = Ei1 ∪ Ei2 ∪ . . . ∪ EiN

(3.1.5)

3.3. Állítás. A H 0 által generált sorozatok rendszere pontosan ugyanaz, mint amit H generál. Ha a H által generált rendszer anticipációja a volt, akkor H 0 -é legfeljebb a + 1. Ha H irreducibilis volt, akkor H 0 is az. 3.1.3.

Teljes splitting

Ez az eljárás nem más, mint a generált splitting abban az esetben, amikor úgy partícionáljuk az élhalmazt, hogy minden partíció egy-egy 19

élnek feleljen meg. Azt az FSTD-t, amelyet ezzel az eljárással kapunk H (2) -vel jelöljük és H élgráfjának nevezzük. A state-splitting eljárásokkal megváltoztathatjuk a lokális képét bármely FSTD-nek, például a csúcsok kifokát is.

3.2.

Közelítő sajátvektorok

Ebben a részben azt vizsgáljuk meg, hogy mit tehetünk akkor, ha ugyan p/q ≤ Cap(S), de Gq nem teljesíti a kifok-kritériumot? 3.4. Definíció. Az Aq v ≥ 2p v egyenlőtlenséget közelítő sajátvektor egyenlőtlenségnek, a benne szereplő v-t pedig (Aq , 2p )-közelítő sajátvektornak nevezzük. Ennek jelentése a Gq gráfban: tekintsük v-t, mint a csúcsok súlyvektorát, azaz v = (v1 , v2 , . . . , vr ) esetén vi az i csúcs súlyát jelenti. Ugyanezeket a súlyokat rendeljük hozzá az élekhez is, mégpedig úgy, hogy vj legyen annak az élnek a súlya, amelyiknek a vépontja j. Az élek súlyát jelöljük w(e)-vel. Így a közelítő sajátvektor egyenlőtlenség megfelel annak a kritériumnak, hogy minden csúcsra igaznak kell lennie annak, hogy ha összeadjuk a csúcsból kimenő élek súlyait, akkor annak legalább 2p -szer nagyobbnak kell lennie, mint a csúcs súlya. Képlettel a következő képpen tudjuk felírni: X

w(e) ≥ 2p vi

(3.2.1)

e∈Ei

A gyakorlatban mindig feltehető, hogy a v közelítő sajátvektor komponensei pozitívak a következő miatt. Ha v komponensei között található 0 értékű, akkor a nekik megfelelő 0 súlyú csúcsokat, és ezen csúcsokhoz tartozó éleket töröljük Gq -ból. Ily módon létrehozunk egy K részFSTD-t. A v vektort K-ra megszorítva, azaz v komponensei közül a 20

0 értékűeket elhagyva egy w vektort kapunk, ami (A(K), 2p ) közelítő sajátvektor lesz. De hogyan találhatunk közelítő sajátvektort? 3.2.1.

A közelítő sajátvektor algoritmus

A következő algoritmus P. A. Franaszektől származik. Legyen T = (tij ) egy mátrix, melynek elemei nemnegatív, egész számok és legyen n pozitív egész szám. Amit keresünk, az egy (T, n)-közelítő sajátvektor, vagyis egy olyan nemnegatív egész komponensű vektor, amely teljesíti a T v ≥ nv egyenlőtlenséget. Az algoritmus lépései a következők: 1. Legyen k = 0. 2. Legyen v(0) = (L, L, . . . , L). 3. Minden koordinátára definiáljuk  h P i a (k+1) (k) = min vik , n1 j tij vj vi mennyiséget. 4. Ha v(k+1) 6= v(k) , akkor k := k + 1 és a 3. lépéstől folytatjuk. 5. Ha v(k+1) = v(k) , akkor legyen v = v(k) . Ez az algoritmus mindig egy nemnegatív, egész komponensekkel rendelkező v vektort fog előállítani. Ha v = 0, az azt jelenti, hogy L-et túl kicsinek választottuk, és nem létezik közelítő sajátvektor legfeljebb L értékű komponensekkel. Ebben az esetben újra kell kezdeni az algoritmust egy nagyobb L értékkel. Kézenfekvő az a módszer, hogy először L = 1-gyel indítjuk az algoritmust, majd egyesével növeljük az értékét, amíg nem találunk egy közelítő sajátvektort. A keresést lehet gyorsítani, például azzal, hogy L = 1, 2, 4, 8, . . . értékekkel próbálkozunk és ha valamilyen k-ra L = 2k esetén az algoritmus közelítő sajátvektort talál, akkor bináris keresést hajtunk végre a 2k−1 és 2k közötti számokon. 21

3.5. Állítás. A közelítő sajátvektor algoritmussal kapott vektor a legnagyobb közelítő sajátvektor abban az értelemben, hogy komponensei legfeljebb akkorák, mint a kezdeti vektoré. Ezt úgy is mondhatnánk, hogy ha az u vektor egy közelítő sajátvektor, amelyre teljesül, hogy u ≤ v(0) , akkor u ≤ v. Tehát ezzel az algoritmussal meg tudjuk találni a (T, n)-közelítő sajátvektort. Ha T -nek A(Gq )-t, n-nek pedig 2p -t választjuk, akkor megkaphatjuk azt a közelítő sajátvektort, amire szükségünk van a kód építése során.

3.3.

Elemi v-konzisztens splitting

Legyen H egy FSTD, T = A(H) és n ∈ Z+ . Adott egy v (T, n)-közelítő sajátvektor. Ei jelöli az i csúcsból kiinduló élek halmazát. 3.6. Definíció. Elemi v-konzisztens felosztásnak nevezünk egy Ei = Ei1 ∪ Ei2 felosztást, amely rendelkezik azzal a tulajdonsággal, hogy

1 X

Ei = w(e) ≥ y1 n e∈Ei1

és

2 X

Ei = w(e) ≥ y2 n e∈Ei2

ahol y1 és y2 egészek, y1 ≥ 1, y2 ≥ 1 és y1 + y2 = vi . Az i csúcsra vonatkozó, ezzel a felosztással meghatározott splittinget elemi v-konzisztens splittingnek hívjuk. Az splitting után eredményül kapott FSTD-t jelöljük H 0 -vel, a szomszédsági mátrixát pedig T 0 -vel. Legyen v0 az a vektor, amelynek kompo-

22

nensei a H 0 -beli csúcsokat reprezentálják, és értékei pedig a következőképpen vannak meghatározva vj0

=

   

vj ha j 6= i

y1 ha j = i1    y ha j = i . 2 2

(3.3.1)

3.7. Állítás. A H-ból elemi v-konzisztens splittinggel kapott H 0 FSTDP P nek eggyel több csúcsa van, mint H-nak, és k vk = k vk0 és vi v0 -ben két szigorúan kisebb pozitív egész számmal lett helyettesítve, amiknek az összege vi .

3.4.

A kódoló építése

3.8. Állítás. Legyen T a H irreducibilis FSTD szomszédsági mátrixa, és v pozitív (T, n)-közelítő sajátvektor. Tegyük fel, hogy a csupa 1 vektor nem (T, n)-közelítő sajátvektor. Ekkor H-nak van elemi v-konzisztens splittingje. Mielőtt bizonyítanánk az állítást, megmutatjuk, hogyan használhatjuk fel azt iteratív módon, kódoló FSTD készítésére. Szükségünk lesz arra a feltételre, hogy a rendszer Shannon-kapacitása legalább p/q legyen. Legyen Gq az S q rendszer FSTD-je, és tegyük fel, hogy nincs 0-1 (A(Gq ), 2p )közelítő sajátvektor, valamint legyen x (A(Gq ), 2p )-közelítő sajátvektor. Ha x-nek van 0 komponense, akkor figyelmünket arra a K FSTD-re irányítjuk, amelyet a nemnulla komponensek határoznak meg. Nevezzük w-nek azt a vektort, amelyet úgy kapunk, hogy x-et megszorítjuk K-ra, vagyis töröljük belőle a 0 értékű komponenseket. w egy (A(K), 2p )közelítő sajátvektor K-ban. Ha K irreducibilis, akkor használhatjuk a 3.8 állítást, viszont előfordulhat, hogy K nem lesz irreducibilis. Abban az esetben, ha K 23

reducibilis lenne, akkor egy irreducibilis komponensére szorítkozunk, majd erre a komponensre alkalmazzuk a 3.8 állítást. Ezt megtehetjük, mégpedig a következő érvelés miatt. Vegyük sorra K irreducibilis komponenseit és keressünk közöttük olyat, amelyre igaz az, hogy az abból a komponensból kiinduló élek abban a komponensben is végződnek (az ilyeneket nyelőnek hívjuk). Ezt mindig meg tudjuk tenni az alábbi módszerrel. Vizsgáljuk meg az egyik irreducibilis komponenst, hogy rendelkezik-e a keresett tulajdonsággal. Ha igen, akkor megállhatunk. Ha nem, akkor léteznie kell egy útnak egy másik irreducibilis komponensbe, térjünk át annak a vizsgálatára. Ismételve ezt az eljárást, biztosan találni fogunk egy megfelelő komponenst, mert különben ellentmondásra jutnánk azzal, hogy irreducibilis részekre bontottuk az eredeti FSTD-t. A keresett komponenst nevezzük el H-nak. Mivel H, K egy irreducibilis komponense, és nincs 0-1 (A(Gq ), 2p )közelítő sajátvektor, ezért a csupa 1-es vektor nem lehet (A(H), 2p )közelítő sajátvektor. És mivel a H-ból induló élek H-ban is végződnek, ezért a v-nek H-ra történő megszorítása után kapott w vektor pozitív komponensű, (A(H), 2p )-közelítő sajátvektor lesz. A 3.8 állítást használhatjuk n = 2p -nel, hogy végrehajtsuk a v-konzisztens splittinget H-n, amellyel egy irreducibilis H 0 -t állítunk elő. Láttuk, hogy a v-konzisztens splitting v komponenseit szigorúan kisebb pozitív egészekre bontja, iterálva ezt a splitting eljárást elkészítjük ˆ FSTD-t, melynek szomszédsági mátrixát Tˆ jelöli. Tˆ-nek van egy aH csupa 1-es (Tˆ, n) közelítő sajátvektora, vagyis

24

Tˆv ≥ nv,

(3.4.1)

n helyébe behelyettesítve 2p -t pedig kapjuk, hogy Tˆv ≥ 2p v.

(3.4.2)

ˆ Mivel v a csupa 1-es vektor, ez pontosan azt jelenti, hogy H-ban minden ˆ teljesíti a 3.1.1-es kritériumot. csúcs kifoka legalább 2p . Így H 3.9. Állítás. A szükséges iterációk száma legfeljebb

P

i

vi − 1.

Bizonyítás. Az i csúcsnak, amihez a vi komponens tartozik, legfeljebb vi leszármazottja lehet, amihez vi − 1 vágás kell. Hasonlóan érvelve a P többi csúcs esetén is, összesen i vi − 1 vágásra lesz szükségünk. Most már hozzáláthatunk a 3.8-as állítás bizonyításához. Bizonyítás. Legyen vmax 6= 1 v-nek a legnagyobb komponense. Először megmutatjuk, hogy létezik egy i csúcs, amely rendelkezik a 1. vi = vmax 2. tij 6= 0 valamilyen j csúcsra, amelyre vj < vmax tulajdonságokkal, majd pedig belátjuk, hogy ennek a csúcsnak van vkonzisztens vágása. Indirekt tegyük fel, hogy nem létezik ilyen csúcs. Ekkor a vmax értékű komponensekhez tartozó csúcsokból kiinduló élek végpontjai csak olyan csúcsok lehetnek, melyek szintén vmax értékű komponensekhez tartoznak. Mivel feltettük, hogy H ireducibilis, a v közelítő sajátvektor konstans kell hogy legyen, mégpedig minden komponensének vmax -szal kell egyenlőnek lennie. Vagyis v = (vmax , vmax , . . . , vmax ). Ha tekintjük a közelítő sajátvektor egyenlőtlenséget, azaz 25

T v ≥ nv,

(3.4.3)

és elosztjuk mindkét oldalt vmax -szal, kapjuk, hogy T (1, 1, . . . , 1) ≥ n(1, 1, . . . , 1)

(3.4.4)

ami azt jelenti, hogy a csupa 1-es vektor is közelítő sajátvektor. De T -ről feltettük, hogy a csupa 1-es vektor nem közelítő sajátvektora, így ellentmondásra jutottunk.  Láttuk tehát, hogy biztosan van egy i csúcs, amely rendelkezik az 1-es és 2-es tulajdonsággal. Feladatunk, hogy megkonstruáljuk ennek a csúcsnak a v-konzisztens vágását. Vegyük észre, hogy Ei legalább n elemű (|Ei | ≥ n). A közelítő sajátvektor egyenlőtlenséget koordinátánként kiírva kapjuk, hogy X

tik vk ≥ nvi ,

(3.4.5)

k

az 1-es feltétel szerint vi = vmax , így felülről becsülhetjük az egyenlőtlenséget, ha minden k-ra vk helyett vmax -ot írunk, vagyis |Ei |vmax ≥

X

tik vmax ≥ nvmax 5 ,

(3.4.6)

k

az egyenlőtlenséget vmax -szal elosztva éppen azt kapjuk, hogy |Ei | ≥ n. Jelöljük |Ei |-t M -mel, írjuk fel Ei -t Ei = {e1 , e2 , . . . , eM } alakban, és e1 végpontja legyen j. A 2. feltételt használva tudjuk, hogy vj = w(e1 ) < vmax . Jelölje Wm a súlyok m-ig vett részletösszegét, vagyis a 5

Mivel a T mátrix i. sorában szereplő elemek összege éppen az i csúcsból kiinduló P P élek száma, így k tik vmax = vmax k tik = vmax |Ei |.

26

Wm =

m X

w(ek ),

m = 1, . . . , M

(3.4.7)

k=1

kifejezést és jelölje Rm Wm n-nel vett osztási maradékát, azaz Rm ≡ Wm (mod n),

m = 1, . . . , M.

(3.4.8)

A skatulya-elvhez hasonló állítás miatt, miszerint n helyre n tárgyat úgy tudunk csak elhelyezni, hogy vagy minden helyen lesz egy, vagy lesz olyan hely, ahova több tárgy is kerül, az alábbi két eset fordulhat elő. 1. Rm ≡ 0 (mod n),

valamely 1 ≤ m ≤ n esetén, vagy

2. Rm1 ≡ Rm2 (mod n),

valamely 1 ≤ m1 < m2 ≤ n esetén.

Az első eset fennállása esetén úgy határozzuk meg a v-konzisztens vágáshoz szükséges felosztásokat, hogy Ei1 = {ek |k = 1, 2, . . . , m}

(3.4.9)

Ei2 = Ei − Ei1 ,

(3.4.10)

Ei1 = {ek |k = m1 + 1, . . . , m2 }

(3.4.11)

Ei2 = Ei − Ei1 .

(3.4.12)

és

a második esetben pedig

és

Mindkét esetben az Ei -beli élek súlyainak összege osztható lesz n-nel, hiszen az első esetben Wm ≡ Rm ≡ 0 mod n, a második esetben pedig az igaz, hogy 27

w(e1 ) + w(e2 ) + . . . + w(em1 ) + . . . + w(em2 ) ≡ 0 (mod n)

(3.4.13)

w(e1 ) + w(e2 ) + . . . + w(em1 ) ≡ 0 (mod n)

(3.4.14)

a két kongruenciát kivonva egymásból kapjuk, hogy w(em1 +1 ) + . . . + w(em2 ) ≡ 0

mod n

Tehát mindkét esetben létezik r egész szám, hogy X w(e) = rn.

(3.4.15)

(3.4.16)

e∈Ei1

3.10. Állítás. 1 ≤ r < vmax . Bizonyítás. Nyílvánvaló, hogy 1 ≤ r, mert Ei1 nem üres egyik esetben sem. Az első esetben Ei1 -nek legfeljebb n eleme van és köztük szerepel e1 is, amiről feltettük, hogy a súlya kisebb, mint vmax . Ezért a súlyösszeg biztosan kisebb lesz vmax n-nél, azaz r < vmax . A második esetben pedig Ei1 , n-nél szigorúan kisebb elemszámú, és minden elem legfeljebb vmax -szal járul hozzá az összeghez.  Ezek után már feltehetjük, hogy X X X w(e) − w(e) ≥ vi n − rn = (vi − r)n. w(e) = e∈Ei2

e∈Ei

(3.4.17)

e∈Ei1

A 3.6 definícióban meghatározott v-konzisztens vágáshoz szükséges y1 és y2 értékeit úgy választjuk meg, hogy y1 = r y2 = vi − r legyen, Ei -nek pedig az Ei = Ei1 ∪ Ei2 28

felbontását haszáljuk.  ˆ Tehát ezzel az iteratív eljárással a Gq FSTD-ből elkészítünk egy H FSTD-t, amely ugyanazt az S q rendszert írja le, de rendelkezik már azzal a tulajdonsággal, hogy minden csúcsának a kifoka legalább 2p . ˆ Ebből a H-ból könnyen tudunk p/q arányú kódolót készíteni, mégpedig úgy, hogy minden i csúcsból kiválasztunk 2p darab kimenő élet, a többit pedig kitöröljük. Ezután minden élhez (2p darab) különböző bináris p-blokkokat (ezeket input-tag-eknek hívjuk) rendelünk, hogy megkülönböztessük őket a már a gráfon lévő címkézéstől.

3.4.1.

A kódoló eljárás

1. Választunk egy kezdő kódoló csúcsot, jelöljük i0 -lal. 2. Ha jelenleg az i csúcsban vagyunk és az adatként kapott szó b (ami egy p-blokk), megkeressük azt az e ∈ Ei élet, amihez a b input-tag tartozik. A kódszó, amit generáltunk, az a q-blokk, ami az e címkéjén szerepel. 3. Ismételjük az előző lépést, amíg van adatszó.

3.5.

A state-splitting algoritmus

Ebben a részben összefoglaljuk a kódoló építésének lépéseit. 1. Találjunk egy véges anticipációjú G FSTD-t, ha lehetséges, akkor determinisztikusat, amely reprezentálja az adott S rendszert. 2. Írjuk fel A(G)-t, G szomszédsági mátrixát.

29

3. Határozzuk meg Cap(S)-t, a rendszer kapacitását, melyet megkaphatunk, mint a szomszédsági mátrix legnagyobb sajátértékének kettes alapú logaritmusa. 4. Válasszuk ki a kívánt p/q kódolási arányt, amire teljesül, hogy Cap(S) ≥ pq . Általában célszerű p-t és q-t relatíve kicsinek választani. 5. Készítsük el Gq -t. 6. Használjuk a közelítő sajátvektor algoritmust, hogy találjunk egy (A(Gq ), 2p )-közelítő v sajátvektort. 7. Ha szükséges, töröljük ki azokat az i csúcsokat, amelyekre vi = 0, és szorítkozzunk egy H irreducibilis nyelő komponensre. 8. Keressük meg H egy csúcsának egy elemi v-konzisztens felosztását. 9. Keressük meg az ennek a felosztásnak megfelelő elemi v-konzisztens splittingjét. Így létrehozzuk a H 0 FSTD-t, amihez a v0 sajátvektor tartozik. ˆ gráfot nem ka10. Iteráljuk a 8-as és 9-es lépést, amíg egy olyan H punk, ahol a kifok legalább 2p . ˆ minden csúcsánál hagyjunk meg 2p élet, és rendeljünk minde11. H gyikhez egy p-blokkot.

4.

Állapotfüggő dekóder

Az előzőekben láttuk hogyan építhetünk kódolót, most pedig áttérünk a kódolási folyamat másik részére, a dekódolásra. Itt is feltesszük, hogy a kódoló eljárás során egy determinisztikus, de legalábbis véges lokális 30

anticipációjú G FSTD-ből indultunk ki. Láttuk azt is, hogy ekkor Gq nak is véges a lokális anticipációja (az anticipációt itt q-blokkokban mérjük). Továbbá beláttuk, hogy a state-splitting megőrzi ezt a tulajˆ kódoló FSTD anticipációja donságot. A 3.5 eljárás során elkészített H legyen a.

4.1.

A dekódoló eljárás

A következő módon tudjuk dekódolni a 3.5 eljárással előállított kódot. 1. A 3.4.1-es fejezetben leírt eljárás 2-es pontjában választott i0 kezdőcsúcsot használjuk itt is. 2. Ha a jelenlegi csúcs i, akkor a soron következő és az azutáni a darab kódszó, amit dekódolni szeretnénk, egy q-blokkokban mért a+1 hosszúságú sorozatot alkot, amit egy i-ből induló út generál. Mivel a lokális anticipáció a, az első éle az útnak egyértelműen meg van határozva. A dekódolt szó pedig ennek az élnek az inputtag-je lesz. 3. Ismételjük a 2-es lépést egészen addig, amíg kódszavaink vannak. Ezzel bebizonyítottuk a 3.1-es tételt, hiszen memutattuk mind a kódoló, mind a dekóder ekészítésének menetét. Ennek az eljárásnak az a hátránya, hogy ha meghibásodik az inputként kapott kódolt üzenet, akkor könnyen instabillá válik a dekódolás abban az értelemben, hogy az inputban levő kevés hiba esetén is sok hiba lesz a dekódolt üzenetben. A 4.1. ábrán látható kódoló FSTD esetében az éleken szereplő x/y címkében x jelenti a kódoló címkéit, y a dekóder címkéit.

31

Válasszuk kezdőállapotnak az 1-es csúcsot. Ha kódolni szeretnénk a 00000 . . . sorozatot, akkor az aaaaa . . . kódszót kapjuk eredményül. Tegyük fel, hogy egy hiba folytán a sorozat első a eleme meghibásodott és b lett belőle. Dekódoláskor így az 11111 . . . adatot fogjuk kapni, ami végzetes következményekhez vezethet. Például ha Beethoven IX. szimfóniáját tároltuk digitális formában, akkor rettentő zajokat fog eredményezni pár bithiba a fájlban. Ezért a gyakorlatban inkább a csúszó blokk kódokon alapuló úgynevezett csúszó blokk dekódereket használják, mivel azok nem függnek a csúcsoktól. Működése során a csúszó blokk dekóder a beérkező sorozatokban lévő adott szót, az őt megelőző m és az őt követő n szót is figyelembe veszi. A 9. ábrán egy csúszó blokk dekóder vázlatos rajzát láthatjuk. Jól látható, hogy egy bitnyi hiba csak egy m + n + 1 hosszú "ablakban" levő szavakra hat a dekódolás során.

32

9. ábra. Csúszó blokk dekóder működése

33

Hivatkozások [1] Brian H. Marcus, Paul H. Siegel, Jack K. Wolf: Finite-State Modulation Codes for Data Storage, IEEE Journal on Selected Areas in Communication Vol. 10 No. 1 January (1995) [2] Douglas Lind, Brian Marcus: An Introduction to Symbolic Dynamics and Coding, Cambridge University Press (1992)

34