Matematika | Analízis » Rusz Mihály Balázs - Kódolás és szimbolikus dinamika

http://www.doksihu 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 http://www.doksihu 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.11 A teljes shift 7 2.12 Shift terek 9 2.13 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.11 Elemi splitting 18 3.12 Generált splitting

19 3.13 Teljes splitting 19 3.2 Közelítő sajátvektorok 20 3.21 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.41 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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.11 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 http://www.doksihu hetjük, mi pontot fogunk tenni elé. Például 402131324 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 http://www.doksihu 2.12 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 = . 010001010010010 ∈ Ω2,{11} , de y = . 011001110010010 ∈ / Ω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 http://www.doksihu 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.13 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu 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 http://www.doksihu dki ≥ 2p . (3.11) 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.11 feltétel: R(i) ≥ 2p (3.12) A(Gq )u ≥ 2p u (3.13) 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.11 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 http://www.doksihu V (H 0 ) = {j ∈ H|j 6= i} ∪ {i1 , i2 } (3.14) 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.12 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.15) 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.13 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 http://www.doksihu é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.21) 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 http://www.doksihu 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.21 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 http://www.doksihu 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 Ei1 = X w(e) ≥ y1 n e∈Ei1 és Ei2 = X 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 http://www.doksihu 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.31) 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

http://www.doksihu 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 38 á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 a Ĥ FSTD-t, melynek szomszédsági mátrixát T̂ jelöli. T̂ -nek van egy csupa 1-es (T̂ , n) közelítő sajátvektora, vagyis 24 http://www.doksihu T̂ v ≥ nv, (3.41) n helyébe behelyettesítve 2p -t pedig kapjuk, hogy T̂ v ≥ 2p v. (3.42) Mivel v a csupa 1-es vektor, ez pontosan azt jelenti, hogy Ĥ-ban minden csúcs kifoka legalább 2p . Így Ĥ teljesíti a 311-es

kritériumot 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 http://www.doksihu T v ≥ nv, (3.43) és elosztjuk mindkét oldalt vmax -szal, kapjuk, hogy T (1, 1, . , 1) ≥ n(1, 1, , 1) (3.44) 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.45) 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.46) 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 http://www.doksihu Wm = m X w(ek ), m = 1, . , M (3.47) 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.48) 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.49) Ei2 = Ei − Ei1 , (3.410) Ei1 = {ek |k = m1 + 1, . , m2 } (3.411) Ei2 = Ei − Ei1 . (3.412) é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 http://www.doksihu w(e1 ) + w(e2 ) + . + w(em1 ) + + w(em2 ) ≡ 0 (mod n) (3.413) w(e1 ) + w(e2 ) + . + w(em1 ) ≡ 0 (mod n) (3.414) 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.415) (3.416) 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.417) 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 http://www.doksihu felbontását haszáljuk.  Tehát ezzel az iteratív eljárással a Gq FSTD-ből elkészítünk egy Ĥ 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 Ĥ-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.41 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 http://www.doksihu 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 10. Iteráljuk a 8-as és 9-es lépést, amíg egy olyan Ĥ gráfot nem kapunk, ahol a kifok legalább 2p 11. Ĥ minden csúcsánál hagyjunk meg 2p élet, és rendeljünk mindegyikhez 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 http://www.doksihu 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 tulajdonságot A 35 eljárás során elkészített Ĥ kódoló FSTD anticipációja 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 341-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 41 á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 http://www.doksihu 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 http://www.doksihu 9. ábra Csúszó blokk dekóder működése 33 http://www.doksihu 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