Informatika | Információelmélet » Információelmélet tételek

Gyakoriságfüggő kódolás A gyakoriságfüggő kódolás célja, hogy úgy érjünk el adattömörítést, hogy a szimbólumok előfordulásának gyakoriságát kihasználva egy szimbólumsorozatot minél rövidebbre kódoljunk le. A gyakoriságfüggő kódolás fontosabb jellemzői: • az adat hibamentesen visszaállítható • változó blokkméret: bemenet kimenet fix blokkméret változó blokkméret fix blokkméret Lempel-Ziv algoritmusok futamhossz kódolás változó blokkméret Huffman kódolás hibrid aritmetikai kódolás Az általunk vizsgált módszerek közös jellemzője, hogy a kódolás megadható egy leképezéssel. A kódoló függvény a következö: f : S Cn ahol S: forrás ABC szimbólumaiból álló sorozatok halmaza C: kód ABC szimbólumaiból álló sorozatok halmaza A leképező függvényt gyakran táblázatban adjuk meg, illetve olyan adatszerkezettel, amely gyors kódolást/dekódolást tesz lehetővé. Kódolási stratégiák: Statikus: A

forráseloszlás a priori módon ismert. A forráseloszlás alapján kiszámolható a kódoló és dekódoló függvények, vagy eleve rögzítettek (pl. egy szabvány által) Dinamikus: A pontos forráseloszlás nem ismert. Véges adat esetén végigolvassuk az adatot, és ez alapján elkészítjük a kódoló és dekódoló függvényeket (végtelen adat esetén véges részekre osztjuk az adatot). E módszer esetén nemcsak a kódolt adatot, hanem a dekódoló függvényt is el kell küldeni (illetve azt az információt, amely alapján ez számolható). Adaptív: A pontos forráseloszlás itt sem ismert. Veszünk egy kezdeti forráseloszlás becslést (mint a statikus módszernél), ehhez kiszámoljuk a kódoló és dekódoló függvényt. A bejövő adatokat blokkról blokkra kódoljuk, és közben felújítjuk a forráseloszlás becslését, és ehhez újra és újra módosítjuk a kódoló és dekódoló függvényt. Fontos hangsúlyozni, hogy adaptív algoritmus esetén

nincs szükséga kódoló fügvény elküldésére, mert a dekódoló a dekódolt üzenetekből szintén felújítja a forráseloszlás becslését. Prefix kódok, egyértelmű dekódolhatóság Kódoláson most szimbólumonkénti kódolást értünk, vagyis hogy a bemeneti szimbólumokhoz kódszavakat rendelünk, ahol a bemeneti szimbólumokat (forrásszimbólumokat) a forrás-ABC-ből vesszük, a kódszavak pedig egy másik betűkészletből (amely megegyezhet a forrás-ABC-vel) összeállított szavak. A kódolás a bemeneti szimbólumok sorozatát kódszavak sorozatába képezi, a dekódolás pedig a kódszavak sorozatából állítja vissza a bemeneti szimbólumok sorozatát. Mivel veszteségmentes adattömörítés a célunk, ezért olyan kódot szeretnénk készíteni, amely: • egyértelműen dekódolható • a kódolt szöveg lehetőleg minél kisebb bitszámú legyen Ebben a fejezetben a Huffman kódolást vizsgáljuk meg (Jegyzet: Optimális kódok, bináris Huffman kód).

A bináris Huffman-fa felépítése A prefix kódok ábrázolhatóak bináris fával. Az optimális prefix kód bináris fájának konstrukciójához az alábbi 3 tulajdonságot használjuk fel: az optimális kód olyanná tehető, hogy • a nagyobb valószínúségű forrásszimbólumhoz nem tartozhat hosszabb kódszó, • a két legkisebb valószínűségű kódszó egyenlő hosszú, • a két legkisebb valószínűségű kódszó nemcsak egyenlő hosszú, hanem ráadásul csak az utolós bitben különböznek. Ezen tulajdonságok alapján az N forrásszimbólum optimális prefix kódjának számítása visszavezethető N-1 forrásszimbólum optimális prefix kódjának számítására (lásd még: a jegyzet 1.17 tétele) A tételből adódó rekurzív algoritmus a következő: OptimálisPrefixKód( p1.N ) IF N = 2 kód := ( "0","1" ) ELSE // i := a legkisebb valószínűség // j := a legkisebb valószínűség, ha i-t nem nézzük i := argmin(p1.N) j :=

argmin(p1.N - {pi}) // A feladatot visszavezetjük N-1 szimbólumra // A két legkisebb szimbólum ugyanolyan hosszú, // és csak az utolsó bit más // A két utolsó helyett egy új szimbólum, // amely azt jelenti, hogy vagy si, vagy sj pj = pi + pj // Az optimális prefix kód N-1 szimbólumra kód := OptimálisPrefixKód( p1.N - {pi}) // Az si és sj megkülönböztetése utolsó kód := kód j kód j := utolsó kód * "0" Beszúr( kód, i, utolsó kód * "1") ENDIF RETURN kód Az optimális prefix kódot Huffman-kódnak nevezik, és a fenti rekurzív algoritmus az alábbi, rekurzió nélküli algoritmusra vezethető vissza: (1) Adott egy forrás a következő tulajdonságokkal: A forrásABC a következő: X =(x0, x1, ., xN) A forrásszimbólumok valószínűségét is nyilvántartjuk: P=(p0, p1, ., pN) A bináris Huffman-fát alulról felfelé építjük fel. (2) Hozzunk létre N csomópontot úgy, hogy mindegyik szombólumnak megfelel egy csomópont. Ezek a

csomópontok lesznek a bináris fa levelei: x1 x2 x3 : xN (3) Válasszuk ki a két legkisebb valószínűségű szimbólumot A-ból: x, y (4) Hozzunk létre az új z csomópontot a következő tulajdonságokkal: • P(z) = P(x) + P(y) • A z csomópont lesz x és y csomópont szülője. A szülő felé vezető két összeköttetést jelöljük meg 0-val és 1-gyel. 0 1 : 0 1 x : y : 0 z 1 : • Ez azt is jelenti, hogy x és y ugyanolyan hosszú lesz a kódja, és csak az utolsó jegyben fognak különbözni: az azonos rész éppen z kódja lesz. Ugyanez másképpen megfogalmazva: binárisKód(x) = binárisKód(z) * 0 binárisKód(y) = binárisKód(z) * 1 ahol a * a konkatenációt jelöli. (5) Töröljük A-ból x-et és y-t, és vegyük fel z-t P(z) valószínűséggel. Így A elemszáma 1-gyel csökkent. (Természetesen x-et és y-t a bináris fából nem töröljük ki!) (6) Amíg A elemszáma > 1, folytassuk (3)-ról. Dinamikus Huffman kódolás Dinamikus

Huffman-kódolást akkor alkalmazunk, amikor nem ismerjük a forráseloszlást. Mivel a Huffman-kód kiszámítása csak a forrásszimbólumok valószínűségén alapul, így elég azt kiszámolni, ebből már meghatározható a kódoló és a dekódoló függvény. A dinamikus Huffman-kódolás algoritmusa 1. A forrásszimbólumok kezdeti gyakorisága legyen K bemeneti szimbólumot kiolvasva F := (f0, f1, ., fN), ahol fi = az xi szimbólum gyakorisága N = a forrásszimbólumok száma és K = ∑ Nj =1 f j A szimbólumok becsült valószínűsége így: ( ) P x i = p i = fi ∑ j =1 f j N = fi K , i=1.N 2. Építsük fel a Huffman-fát a p1N valószínűségek használatával 3. Kódoljuk le a bemeneti szimbólumokat a kapott kóddal Problémák: • a becsült valószínűségek ( p i , i = 1.N) számábrázolása A számábrázolás problémáján a lebegőpontos aritmetika használatát értjük. A probléma a gyakorlatban ott fordul elő, ahol a fix pontos

(egész számos) aritmetika gyorsabb, és/vagy ahol nem célszerű osztást alkalmazni. Látható, hogy a Huffman-fa építésekor a pi valószínűségek összeadását és összehasonlítását kell elvégezni, így a p i valószínűségek helyén az fi gyakoriságot használva ugyanazt az eredményt kapjuk. Az fi értékekkel számolva azonban már elegendő az egész aritmetika is. Ez a megoldás főleg adaptív kódolásnál és a dekódoló függvény számítáaánál hatásos. • a dekódoló függvény elküldése 1. Tudjuk, hogy a becsült valószínűségek ( p i ) alapján számítható a Huffman-fa, de ugyanígy számítható a gyakoriságok alapján is. Ez alapján tehát az f1.N gyakoriságokat elküldve már számítható a Huffmanfa 2. Szintén használt módszer az, amikor a bináris prefix kód gyors dekódolását segítő gyorsítótáblát küldik el ügyes kódolással, vagy pedig magát a prefix kódot. A prefix kód elküldése lehetséges pl úgy, hogy

elküldjük először a szimbólumokhoz tartozó kódszóhosszakat, majd a kódszavakat. 3. Vegyük észre, hogy az 1-es módszer a kód elküldésének egy pazarló módja, hiszen könnyen belátható, hogy pl. az {fi, i = 1N} és a {2*fi, i = 1.N } gyakoriságok alapján ugyanaz a Huffman-fa építhető fel. Emiatt a gyakoriságok helyett a kódszavak hosszát küldik át, és ebből ugyanúgy számítható a Huffman-fa. Ugyanezen ok miatt pazarló az is, amikor leküldjük a kódszóhossz mellé a kódot is (1. módszer) Ötlet: konstruálunk egy {h1, h2,,hN} kódszóhosszú optimális prefix kódot. A forrásszimbólumokat sorbarendezzük, és az azonos kódszóhosszak esetén a kisebb sorszámú forrásszimbólum kapja a kisebb értékű kódszavat (a kódszó értéke az őt reprezentáló bináris szám, és mert azonos hosszúak ezért nincs gond). • kétszer végig kell olvasni a bemenetet (vagy K szimbólumnyi késleltetés) Sajnos ez az, amit a dinamikus kódolásnál

nem lehet elkerülni. Valós idejű kódolásnál a K szimbólum bevárása bizonyos késleltetést okoz, ahol K kegnagyobb értéke alkalmazástól függ. Amennyiben Kmax olyan kicsi, hogy az nagyban rontja a forrás becslésének a minőségét, a dinamikus kódolás helyett adaptív algoritmust lehet használni. Adaptív Huffman kódolás Az adaptív kódolás lényege, hogy a forráseloszlást az eddig előfordult szimbólumokat felhasználva becsüljük. A kódoló függvény a mi esetünkben a becsült valószínűségek pillanatnyi állapotának megfelelő optimális prefix kód, vagy az ezzel egyenértékű Huffman-fa. A fentiek után az adaptív Huffman kódolás könnyen megfogalmazható: (1) A forrásszimbólumok kezdeti gyakorisága legyen F := (f1, ., fN), ahol fi = az ai szimbólum gyakorisága N = a forrásszimbólumok száma (2) Építsük fel a Huffman-fát a kezdeti f1.N gyakoriságok használatával (3) Olvassuk be a következő forrásszimbólumot (jelöljük

s-sel), és írjuk ki a megfelelő kódot. (4) Módosítjuk a vett szimbólum gyakoriságszámlálóját: fs = fs + 1 Értelemszerűen a többi szimbólumok gyakoriságszámlálója nem változik. (5) Felépítjük a Huffman-fát az új gyakoriságok használatával (bár a a kóder és a dekóder ugyanazt a gyakoriságszámlálókat kapta eredményül, ügyeljünk arra, hogy a kóder és a dekóder ugyanazt a fát építse fel). (6) Bizonyos periódus elteltével felezzük a gyakoriság-számlálókat. Ezzel elkerüljük a túlcsordulást, és lokális adaptivitást is biztosítunk. (7) Amíg van új forrásszimbólum, addig (3) Maga az algoritmus már működőképes, de a jelenlegi állapotában még két lényeges egyszerűsítést lehet tenni, amely a Huffman-fa tervezésével kapcsolatos. A bináris Huffman-fa globális karbantartása A Huffman-fában a 0 jelölje a bal, az 1 a jobb oldali gyermeket. A fát a gyakoriságok alapján építjük fel. Ahogy a

valószínűségekkel igaz volt, ugyanúgy a gyakoriságokra is igaz, hogy abban az esetben, ha a k sorszámú csomópont két gyermeke az i és j sorszámú, akkor: fi + fj = fk ahol fi jelöli az i-dik csomópont gyakoriságát - a csomópontok esetében fi-t gyakran az i-dik csomópont súlyának hívjuk. Legyenen a Huffman-fa csomópontjai megszámozva úgy, hogy a nagyobb súlyú csomópont nagyobb sorszámot kapjon. Ne engedjük meg a 0 gyakoriságot, azaz legyen minden csomópont legalább 1 súlyú. Vegyük észre, hogy ekkor az előbbi példában max(i,j) < k. Nevezzük blokknak azon csomópontok halmazát, amelyek súlya ugyanaz ez a súly lesz a blokk súlya is. A Huffman-fa karbantartása a blokkot, sorszámok és súlyok alapján történik a következőképpen: (1) Kódoltunk/dekódoltunk egy forrásszimbólumot. csomópont := a fában a neki megfelelő levél (2) vizsgált blokk := a vizsgált csomópont blokkja (3) Kicseréljük a blokkban levő legnagyobb sorszámú

csomóponttal a vizsgált csomópontot. Így az ő sprszáma lesz a blokkban a legnagyobb (mivel a csomópont a következő lépésben kilép ebből a blokkból az 1-gyel nagyobb súlyú blokkba). (4) Növeljuk a csomópont súlyát eggyel. (5) csomópont := a csomópont szülője (6) Ha nem vagyunk a gyökérnél, akkor (2) Vegyük észre, hogy a fenti algoritmus feltételezi, hogy minden súly nagyobb 0-nál, különben előfordulhatna az az eset, hogy a csomópontot a saját szülöjével cserélem ki. Ez az algoritmus minden lépésben előállítja az optimális Huffman-fát a becsült valószínűségekhez képest. A következő algoritmus csak lokálisan vizsgálja meg a súlyokat, emiatt nem feltétlenül kapja ugyanazt az eredményt, mint a globális algoritmus. A bináris Huffman-fa lokális karbantartása A lokális algoritmus nem tekint globálisan a fára, hanem csak a kódolás és dekódolás során bejárt csomópontokat és azok lokális környezetét v izsgálja

meg. Még pontosabban, ez a lokális környezet a testvér (a szülő másik gyermeke) és a szülő testvére. Vegyünk egy bináris Huffman-fát. Egy szülő csomópontnak itt két gyermeke van, a rekurzív tervezési algoritmus alapján pedig a szülő csomópont gyakorisága a két gyermek gyakorsiágának az összege. Például az alábbi Huffman fa estén: (1.a) (1.b) (1.c) fa = f1 + f2 fb = fa + f3 fc = f0 + fb A csomópontokra pedig relációk teljesülnek: (2.a) (2.b) (2.c) f1 ≤ f3 ≤ f0 f2 ≤ f3 ≤ f0 fa ≤ f0 fc 0 1 f0 a következő fb 0 "0" 1 fa 0 f1 "100" f3 1 "11" f2 "101" Dekódoljunk egy szimbólumot. Ezzel a bináris fában kapunk egy gyökérlevél útvonalat is, ez az útvonal adja ki a bináris kódszót is. Legyen a t+1 időpillanatban a küldött/vett szimbólumnak megfelelő levél y1. Ezzel ennek a szimbólumnak a gyakorisága 1-gyel nőtt, vagyis: f1(t+1) = f1(t) + 1 Azáltal, hogy növeltem y1

gyakoriságát, két dolgot kell tennem e csomópont környezetében: 1. A szülő testvérének vizsgálata: meg kell vizsgálni, hogy (2a) teljesül-e Ha nem, csomópontokat kel cserélni. A (2.a) feltételből itt most csak f1(t+1) ≤ f3(t+1) teljesülését kell biztosítani (a feljebb levő csomóponttal való összehasonlítást majd csak felfelé lépéskor, valamint az is tudjuk, hogy f1(t) ≤ f3(t) még igaz volt). Ha ez a feltétel teljesül, akkor nincs csere. Ha viszont nem teljesül, akkor ez csak egyféleképpen lehetséges: f1(t) = f3(t) és f1(t+1) = f3(t) + 1 Ekkor kicseréljük y1-et és y3-at, és az új Huffman-fára a (2.a) feltétel ismét teljesül (a cserével a gyökéry1 és a gyökéry3 útvonal cserélődik fel) 2. A szülő súlyának módosítása: növelni a szülő súlyát 1-gyel Ha az előző pontban volt csomópontcsere, akkor értelemszerűen az új szülő súlyát kell növelni. Vegyük észre, hogy abban az esetben, amikor csere van, a régi

"nagybácsi/nagynéni" csomópont súlya megegyezett a csomópont régi súlyával, tehát így a régi szülő súlyát nem kell a csere miatt növelni. Az előbbi operáció csak egy lépése a Huffman-fa karbantartó algoritmusnak. A teljes lokális adaptív Huffman-fa karbantartó algoritmus a következő: (1) Kódoltunk/dekódoltunk egy forrásszimbólumot. csomópont := a fában a neki megfelelő levél (2) Növeljuk a csomópont súlyát eggyel. (3) Ha a súly növelésével meghaladtuk a vizsgált csomópont szülője testvérének súlyát, akkor a Huffman-fa ezen két csomópontját cseéljül fel. (4) csomópont := a csomópont szülője (5) Ha nem vagyunk a gyökérnél, akkor (2) Aritmetikai kódolás Az aritmetikai kódolás ötlete az, hogy N forrásszimbólumra a [0,1) intervallumot N rész-intervallumokra bontjuk úgy, hogy minden szimbólum kap egy rész-intervallumot, amely rész-intervallum hossza a szimbólum valószínűsége. Egy forrásszimbólum

kódolásának eredménye a szimbólum rész-intervalluma, illetve egy tetszőleges szám ezen rész-intervallumon belül.A szimbólumok sorozatának kódolási eredménye az utolsó rész-intervallumból egy tetszőleges szám. A [0,1) intervallum felosztása forámlisan a következő: ForrásIntervallum Intervallum szimbólum hossza x1 P(x1) [0, P(x1)) x2 P(x2) [P(x1), P(x1)+P(x2)) x3 P(x3) [P(x1)+P(x2), P(x1)+P(x2)+P(x3)) : : xi P(xi) [P(x1)+.+P(xi-1), P(x1)++P(xi)) : : xN P(xN) [P(x1)+.+P(xN-1), 1) A kummulált valószínűségeket bevezetve a lehetséges rész-intervallumok megadása egyszerűbb lesz. Jelölje az xk-hoz tartozó kummulált valószínűséget ck, vagyis c k = ∑ik=1 p( x k ) , ha k=1.N és legyen c0=0. Ekkor az xk-hoz kezdetben a [0,1) intervallum [ck-1, ck) rész-intervalluma tartozik. Fontos, hogy 0 valószínűséget nem engedünk meg, vagyis ci<cj, ha i<j. A következő forrásszimbólumokat úgy kódoljuk, hogy a [0,1) intervallum szerepét az

előzőleg kapott rész-intervallum veszi át. Így a forrásszimbólumok sorozatának kódolásával egymásba skatulyázott rész-intervallum-sorozatot kapunk, a kódolás végeredménye pedig az utolsó, legkisebb rész-intervallumon belül egy tetszőleges szám lesz - ezt a számot tehát minden rész-intervallum tartalmazza, így lépésről lépésre az összes szimbólum dekódolható. Intervallumok egymásba skatulyázása Jelölje a t+1-dik forrásszimbólum, x(t+1) kódolásakor a kiindulási intervallumot [l(t),h(t)), és legyen az intervallum hossza kezdetben r(t)=h(t)-l(t). Az algoritmus alapján, ha x(t+1) = xk, akkor az intervallumok egymásba skatulyázásának algoritmusa • az intervallum hosszára: r(t+1) = r(t) ⋅ p(xk) • az intervallum alsó határára: l(t+1) = l(t) + r(t) ⋅ ck-1 • az intervallum felső határára: h(t+1) = l(t) + r(t) ⋅ ck Ebből látható, hogy ha a 0 valószínűséget nem engedjük meg, akkor a skatulyázás helyes, vagyis l(t+1)

≥ l(t) h(t+1) ≤ h(t) l(t) < h(t) A fenti összefüggés alapján már látható, hogy mitől végez gyakoriságfüggő kódolást az aritmetikai kódoló: t darab szimbólum kódolása után a kapott részintervallum hossza t +1 r (t + 1) = ∏i =1 p( x(i )) , az intervallum két végpontjának távolsága pedig bitekben kifejezve B= − log 2 ( r (t + 1))  = − log 2 ∏it =+11 p( x(i ))  = − ∑it +=11 log 2 ( p( x(i )) ) , ( ) tehát legfeljebb ennyi bit kell az intervallum egy pontjának kódolására. Fix pontos megvalósítás A fix pontos megvalósítás fő problémája a következő: a fentiek alapját tehát meg kell határozni (a forrásszimbólumok sorozatát végigolvasva), hogy B mennyi, és egy B pontosságú aritmetikával ezután végigszámolni az összes szimbólumra a fenti műveleteket. Ez például járható út akkor, amikor pl 10 szimbólumból álló vektorokat kell egyszerre kódolni, ahol a szimbólumok száma minden

koordinátában max. 8 bittel leírható De egy több száz kByte-os szöveg esetén ez lehetetlen. A fix pontos implementáció lényege az, hogy három részre osztjuk az aktuális rész-intervallum határát megadó két számot, vagyis l(t)-t és h(t)-t. 1. rész: l(t) és h(t) bitjei azonosak: Mivel ezek a bitek már nem változhatnak meg l(t)<h(t) miatt, ezért ezeket a biteket kiírjuk a kimenetre. A kódolás végeredménye ez a rész. 2. rész: csúszó ablak: Adott számábrázolási pontossággal (pl A bittel, ahol A állandó) ábrázoljuk l(t) és h(t) ide eső bitjeit. 3. rész: túl a számábrázolási pontosságon: Itt feltételezzük, hogy l(t) bitjei nullák, h(t) bitjei pedig egyesek. l(t) h(t) 1 rész 0.1001001111010000011101010011 0.1001001111101000011101010011 2. rész (fix biten) 3. rész 0x003E 000000. 0xC38F 111111. A fix bites rész léptetésének az a szabálya, hogy az intervallumot lehetőleg minél pontosabban ábrázoljuk, hiszen a 3. részben

már csak közelítünk Az a megoldáshoz vezető ötlet, hogy ha a csúszó ablakon belül h és l már olyan közel van egymáshoz, hogy legalább 1 biten közös a prefixumuk, akkor 1 bitet a kimenetre írva a csúszó ablakon belül a bitek balra lépnek egyet, és h és l értékeit 2-vel szorozva a köztük lévő távolság nő. Kódolás során a kimeneten lévő bináris szám az l és h prefixuma. Az utolsó szimbólum kódolása után azonban még kell biteket kiírni, ezeket mindig úgy kell megválasztani, hogy az így kapott szám az l felett, vagy azzal egyenlő legyen, de a h alatt. Mivel bináris számábrázoláson alapul az aritmetikánk, ezért az 1/4, 1/2 és 3/4 a kitüntetett pont (vagyis a felső 2 bit vizsgálata), és ezeket vizsgálva hasonlítjuk össze a csúszó ablakon belül az l alsó és a h felső korlátot. A kiegyenlítő algoritmus léptetési startégiája a következő: h l mit jelent h < 1/2 0h1.A (ekkor biztosan áll itt: 0l1.A)

(ekkor biztosan: 1h1.A) 1l1.A l ≥ 1/2 10h2.A 01l2.A h < 3/4 l ≥ 1/4 ez mit kell tenni BitKi(0,1követőkSzáma) h←1 l ←0 követőkSzáma=0 BitKi(1,0követőkSzáma) h←1 l ←0 követőkSzáma=0 ++követőkSzáma h ← 1 és h0 = 1 l ← 0 és l0 = 0 magyarázat h-ból és l-ből is 0 lép ki h-ból és l-ből is 1 lép ki Ugyanaz, mintha a beléptetés előtt h -= 1/4 l -= 1/4 A fenti algoritmusban csak a követőkSzáma szorul magyarázatra. Tekitsük ehhez a következő esetet: Kezdeti állapot 9 lépés után 9 h = 10 1 = 10000000001xx. 11xx l = 0191 = 01111111111yy. 01yy Ekkor tíz darab bitre előre meg tudjuk mondani, hogy az eredmény vagy 019, vagy pedig 109 lesz. A 11 bit alapján pedig fenti algoritmus még nem tud dönteni, a következő lépésben azonban új szimbólumot kódolunk le, ezért l nőni, h pedig csökkenni fog, tehát vagy (h esetében) az 109 fog alulcsordulni, és 019 lesz belőle, vagy pedig (l esetében) az 019 fog túlcsordulni, és

109 lesz belőle (a kettő együtt nem lehet, mert l<h). Az alulcsordulást pedig úgy vehetjük észre, hogy h esetében 0h1.A alakul ki, a túlcsordulást l esetében lehet detektálni azzal, hogy 1l1.A alakul ki Az itt bemutatott kiegyenlítő algoritmust az új rész-intervallum kiszámítása után kell lefuttatni, és amikor ez leállt (látható, hogy néhány lépésen belül ez megtörténik), akkor lehet a következő szimbólumot kódolni. Az intervallumhatárokat A biten ábrázoló aritmetikai kódoló algoritmusa tehát a következő: (1) Kezdetben legyen követőkSzáma :=0 l := 0A vagyis az intervallum alsó határa: 0.000 A h := 1 vagyis az intervallum felső határa: 0.111 (2) A következő elküldendő forrásszimbólum az xk. Végrehajtjuk az intervallum szűkítését: r := h-l+1 l := l + r ⋅ ck-1 h := l + r ⋅ ck (3) Ismételjük a kiegyenlítő eljárást addig, amíg az ír ki bitet. (4) Ha van további szimbólum, akkor (2) (5) Befejezésül jelezzük

a dekódernek, hogy az 1/4 vagy a 3/4 közelében álltunk-e le a következő módon: követőkSzáma := követőkSzáma + 1 Ha l < 1/4 Akkor BitKi(0,1követőkSzáma) Különben BitKi(1,0követőkSzáma) Az aritmetikai kódoló dekóder része Az aritmetikai kódolás kimenete egy sokbites v szám, amely az utolsó rész-intervallumon is belül van. A dekóder algoritmusa tehát a következő: be kell olvasni a sokbites v számot, és meg kel határozni, hogy az intervallumon belül melyik rész-intervallumba esik, vagyis: l + r ⋅ ck-1 ≤ v < l + r ⋅ ck Ha megtaláltuk k-t,akkor az üzenet az xk volt. Ezután követjük a dekóderrel a kódolót, ugyanazzal a forgatókönyvvel, mint a kiegyenlítő algoritmus: h l mit kell tenni magyarázat egy bit be, az ablak 0h1.A h←1 egyet lép l ←0 v ← InputBit (ekkor egy bit be, az ablak 1l1.A l ≥ 1/2 h←1 biztosan: 1h1.A) egyet lép l ←0 v ← InputBit 10h2.A 01l2A h < 3/4 v -= 1/4 és v←InputBit Ugyanaz, mintha a

beléptetés előtt l ≥ 1/4 h ← 1 és h0 = 1 v,l,h, -= 1/4 l ← 0 és l0 = 0 Az aritmetikai tömörítés dekódoló algoritmusa a következő: (ekkor biztosan ez áll itt: 0l1.A) mit jelent h < 1/2 (1) Kezdetben legyen v := InputBit1.A l := 0A vagyis az intervallum alsó határa: 0.000 A h := 1 vagyis az intervallum felső határa: 0.111 (2) Meghatározzuk a vett szimbólum k indexét: l + r ⋅ ck-1 ≤ v < l + r ⋅ ck (3) A vett forrásszimbólum tehát az xk. Végrehajtjuk az intervallum szűkítését: r := h-l+1 l := l + r ⋅ ck-1 h := l + r ⋅ ck (4) Ismételjük a kiegyenlítő eljárást addig, amíg az beolvas bitet. (5) Ha van további szimbólum, akkor (2) Egyetlen lényeges különbség van a kódoló és a dekódoló ütemezése között: a dekóder előbbre jár, mint a kódoló, és az is látható, hogy a kódoló az utolsó szimbólum küldése után, az (5) lépésben "éri csak utol" a dekódolót. Ezen tulajdonsága miatt az

aritmetikai kódoló nem használható olyan alkalamzásban, ahol rövid késleltetéssel kell szimbólumokat küldeni, és nincs idő a kódolónak "előreszaladni" több szimbólummal a dekóder elé. Az aritmetikai kódoló felhasználása A fenti kivételtől eltekintve az aritmetikai kódoló bárhol használható, ahol a Huffman-kód. Az aritmetikai kódolóval ugyanúgy lehetséges az adaptív kódolás, ahogy a Huffman-kódolás esetében, hiszen a kiegyenlítő algoritmus lefutása után lehetséges a becsült valószínűségek módosítása. Az aritmetikai kódoló speciális felhasználási területe a nagyon kis szimbólumszámú források kódolása. Pl a {0,1} szimbólumABC-re tetszőleges forráseloszlás esetén az optimális Huffman-kód a {"0","1"} vagy az {"1","0"}, tehát tömörítést nem lehet így elérni. Gyakorlati tapasztalatok alapján futamhossz kódolással vagy több szimbólum blokkba fogásával és

Huffmankódolással elérhető tömörítési arányt az aritmetikai kódoló is eléri, de az aritmetikai kódoláshoz sokkal kevesebb paraméter szükséges, mint a futamhossz kódoláshoz és a blokkba fogáshoz, emiatt tulajdonság-térképek vagy tagsági függvények (1=benn a halmazban, 0=nincs benn a halmazban) kódolásához gyakran az aritmetikai kódolást alkalmazzák. A Lempel-Ziv algoritmusok - szótár alapú kódolás A Lempel-Ziv algoritmusok adaptív kódolási módszerek. A forrásszimbólumok sorozatát szavakra osztját, és ezeket a szavak kódjait küldik el - a szavak kódja a szótárban van tárolva, a szótárat pedig a már elküldött betűkből és szavakból építi fel. Lempel és Ziv az LZ77 algoritmust 77-ben, az LZ78 algoritmust 78-ban publikálta, az LZ78 algoritmus Welch-féle kiterjesztése 1984-ben, míg Yokoo, Kiyohara és Kawabata által javasolt LZY algoritmus 1992-ben jelent meg. Az LZ77 algoritmus Az LZ77 algoritmus szótára egy egyszerű ha

hosszú csúszó ablak, amely két részből áll: • kereső puffer: az eddig dekódolt szöveg legfrissebb hk betűje • előrenéző puffer: a most következő (kódolandó) betűk sorozata he=ha-hk hosszon A kódolás menete a következő: (1) A még nem kódolt szöveg következő darabjával feltöltjük az előrenéző puffert. Ha nincs több adat, akkor vége (2) Megkeressük a kereső pufferben azt a p pozíciót, ahol a leghosszabb egyezés van, ennek a hossza legyen h. (3) Az előrenéző pufferben a h+1-dik helyen áll az a c szimbólum, ami már nem egyezett meg a kereső pufferbeli sorozattal. (4) A kódolás eredménye: <p, h, c> A számhármas lekódolásához log2hk+log2ha+ log2N bit kell, ahol N a forrásszimbólumok száma. (5) Léptessük a csúszó ablakot h+1 pozíciót, és folytassuk (1)-től. Példa: Kereső puffer Túl régi szövegrész Előrenéző puffer A következő betűk egy szép piro s a l m a a j u t a l m a

a n n ak, aki 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 A fenti példában a leghosszabb egyezést kell megkeresni az "alma ann" füzérhez. A találat p=2, h=6, az a szimbólum pedig, ahol elakadtunk az "alma ann" füzérben, az "n", tehát az üzenet: <2, 6, "n"> A kódolás utáni 6+1=7 pozícióval való léptetés eredménye: piros alma a j u t a l m a a n n a k , a k i megtal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 12 13 14 15 16 17 18 19 A dekóder állapota az kódhármas vétele előtt: egy szép piro s a l m a a j u t 0 1 2 3 4 5 6 7 8 9 10 11 A kódhármas dekódolása után pedig: egy szép piro s a l m a a j u t a l m a a n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Egyetlen dolog van még, ami az LZ algoritmusokat érdekessé teszi, ez pedig az, hogy olyan szóra is hivatkozhatunk a szótárban,

amely még nincs befejezve. Például legyen a kóder csúszó ablaka a "rarradab" sorozat beolvasása után a következő: b l a b b a d a b r a r r a r r a d a b 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Ekkor a kódhármas: <9, 5, "d">, ezt elküldjük a dekódernek. A dekóder csúszó ablaka a kódhármas vételekor: b l a b b a d a b r a r 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 Tehát olyan betűkre is hivatkozunk (a 12-es és 13-as pozícióban), amelyek még nincsenek benn a szótárban. A másolás folyamata a következő: Szimbolikusan A12← A9 A13← A10 A14← A11 A15← A12 A16← A13 A17← "d" Konkrétan A12← "r" A13← "a" A14← "r" A15← "r" A16← "a" A17← "d" Tehát a dekóder mégiscsak dekódolni tudja a bejövő füzért. Ezek után érthető, hogy a számhármas lekódolásához miért kell

log2hk+log2ha+ log2N bit kell, és a második tag miért nem csak log2(he). Ezen a veszteségen azonban ügyes kódolással javítani lehet a következő módon: Kódoljuk a <p,h,c> számhármast a következő módon: Kódoljuk p-t log2hk biten (vagy optimális prefix kóddal), és elsőnek ezt a kódot küldjük el Mivel p értéke ismert, ezért h kódolására elegendő log2(hk-p) bit, prefix kóddal pedig elegendő hk-p kódszóból álló prefix kód. Kódoljuk c-t log2N biten. Variációk az LZ77 témára: • hibrid módszer: a kódhármast gyakoriságfüggő kódolással tömörítjük • egy jelzőbittel jelezni, hogy van-e találat, vagy nincs (a jelzőbit tömörítése aritmetikai v. futamhossz+Huffman kódolóval) Ha nincs találat, akkor a <p,h,c> kódhármas helyett elegendő c-t elküldeni, ha van, akkor pedig csak <p,h>-t küldök, c nélkül. • a kereső és az előrenéző puffer hosszának változtatása

• gyors keresési startégiák • Hibridek a gyakorlatban: Zip, PkZip, Arj, Lharc Az LZ78 algoritmus Az LZ78 algoritmus az előzőleg előfordult sorozatokat nem egy csúszó ablakban tárolja, hanem egy fát épít belőle. (1) Létrehozunk egy fát úgy, hogy kezdetben csak a gyökér adott. Legyen a gyökér sorszáma 0 n := 1 - ez lesz a következő sorszám (2) füzér := "". Definíció szerint az üres füzér benn van az üres fában (3) c := a következő szimbólum Ha nincs több szimbólum, akkor kiírjuk a füzér kódját és vége. (4) Ezen a ponton a füzér biztosan benn van a fában. Ha füzér * c nincs benn a fában a gyökértől indulva, akkor (6) / Más szóval: ha a füzér csomópontjától nem visz c útvonal, akkor (6) / (5) füzér := füzér * c /Haladunk a levelek felé a fában/ (3) (6) Kiírás fájlba: (K(füzér),c) ahol K(füzér) a füzérhez tartozó csomópont kódja c az a szimbólum, ahol elakadtunk (a befejező szimbólum) (7) A

fát tovább építem 1 új csomóponttal: a füzérhez tartozó csomóponthoz egy új levelet veszek fel: (a) A levélhez vezető úthoz rendeljük hozzá c-t, így ez a levél a gyökértől a füzér*c útvonalon érhető el (b) Az új csomópont megkapja a következő sorszámot: K(füzér*c) := n (8) Ha még van bemeneti szimbólum, akkor n:=n+1 és (2) Legyen X=(a,b,c), és vizsgáljuk meg az aabcabbccbac sorozat kódolását az LZ78 algoritmussal. Az algoritmus a következő szavakká bontja a szöveget: a | ab | c | abb | cc | b | ac | A szöveg feldolgozása során a következő fákat kapjuk az 1., 2, 3, 5, 6 és 7 lépés után, ahol 1 lépést a fenti algoritmus 1 ciklusa jelent: A szófa az 1. lépés után: 0 a 1 A szófa a 2. lépés után: 0 a A szófa a 3. lépés után: 0 a c 1 1 b 2 b 2 3 A szófa a 4. lépés után: 0 a c 1 A szófa a 6. lépés után: 0 a c b 1 3 6 3 c b 5 2 c b b 4 c c b 5 2 A szófa a 7. lépés után: 0 a c b 1 6 3 2 5

7 b 4 b 4 Az "a | ab | c | abb | cc | b | ac" üzenet a következő módon lesz lekódolva: Szavakra bontás: A kódoló kimenete: a (-,a) ab (1,b) c (0,c) abb (2,b) cc (3,c) b (0,b) ac (1,c) A szótár pedig a következő módon néz ki minden lépés után: 1előtt Gy 0 1 után Gy 0 a 1 2 után Gy 0 a 1 ab 2 3 után Gy 0 a 1 ab 2 c 3 4 után Gy 0 a 1 ab 2 abb 4 c 3 5 után Gy 0 a 1 ab 2 abb 4 c 3 cc 5 6 után Gy 0 a 1 ab 2 abb 4 b 6 c 3 cc 5 7 után Gy 0 a 1 ab 2 abb 4 ac 7 b 6 c 3 cc 5 A fenti szótárban pl. az (a,1) bejegyzés azt jelenti, hogy az "a" füzérnek 1 a kódja, vagyis ez most azt is jelenti, hogy 1-ső lépésben vettük fel. Számoljuk meg, hogy hány bit szükséges a k-dik szó lekódolásához. Látható, hogy az első lépésben 1 csomópontja van a fának, és minden lépésben 1-gyel nő a csomópontok száma (ezt tároltuk n-ben). Amikor megvan a k-dik szó, akkor k-1 elem van a fában, ez log2(k-1) bittel írható

le, a szimbólumok száma pedig b=#(X) bit, így a (6) lépésben log2(k-1) + b bitet kell elküldeni. Az LZ78 módosulatai • LS78E (Excision - csomópont kivétele) Ez a módszer azt használja ki, hogy a fa bizonyos belső csomópontjaira egy idő után már nem fogunk hivatkozni, mert minden irányban tovább lehet menni rajta. Ha s=#(X) darab bemeneti szimbólumunk van, akkor ha egy csomópontra s alkalommal hivatkoztunk, akkor többször nem fogunk rá hivatkozni, ezért az s-dik hivatkozáskor ezt a csomópontot kizárjuk, így az ő sorszámát oda lehet adni az új csomópontnak. Például, a mi példánkban a 6-os csomópont számának a 0-t kellett volna adni, hiszen biztos, hogy a 0-ra nem fogunk többször hivatkozni. Ez csökkenti • • a sorszámok számát, azaz előfordulhat, hogy a k-dik szó lekódolásához a csomópontok sorszámának elküldésekor log2(k-1)-nél kevesebb bitre van szükség. LS78S (Suppress - a szó befejező

szimbólumának elnyomása) Ez a módszer azt használja ki, hogy amikor egy csomópontra s-dik alkalommal hivatkozunk, akkor már s-1 leszármazottja megvan a fában, az utolsó pedig kizárásos alapon adódik, tehát a befejező szimbólumot nem kell elküldeni, ekkor további b bitet takarítunk meg. LS78P (Prefix kódok használata) Ez a módszer prefix kódokkal egyrészt a   függvény bitnövelő hatását próbálja csökkenteni prefix kódokkal, célszerűen gyakoriságfüggő kódolással. A Lempel-Ziv-Welch módszer (LZW) Ez a módszer a LZ78 továbbfejlesztése. Welch módosítása a következő: ne azt csináljuk, hogy elküldjünk a befejező szimbólumot és azt hozzácsapva a megtalált és szótárban lévő szóhoz hozzunk létre egy új csomópontot, hanem tekintsünk el a befejező szimbólumtól, és a következő megtalált szó első betűjével folytassuk az előző füzért, és az legyen az új csomópont. Látható, hogy Welch módosítása

megtakarítja a befejező szimbólum elküldését, ez a következő problémákat veti fel az LZ78-hoz képest: * a szöveg 1-gyel rövidebb szavakra bomlik szét * az új csomóponthoz vezető szimbólum megjelölése (az algoritmusban a (7a) lépés) csak a következő szó megállapítása után történik csak meg, vagyis egy ütemet késik * a kezdeti fa (vagy az enekmegfelelő szótár) nem lehet üres, mert akkor nincs mit elküldeni: az LZW algoritmusban (eltérően az LZ78-tól) a kezdeti szótár az összes egybetűs szó Az LZW algoritmus működésének megértéséhez tekintsük a következő üzenetet a X=(a,b) ABC felett: ababababaa Az LZW kódoló a következő szavakra bontja az üzenetet: a|b|ab|aba|ba|a., a kódolt sorozat pedig a következő: 0,1,2,4,3,. Ez a folyamat jól nyomon követhető az alábbi táblázaton, ahol a szótár felépítése is megfigyelhető. 1előtt Új szó Új szó kódja S a z b ó t á r 0 1 1 után a 0 a 0 b 1 ab 2 2 után b 1 a 0 b 1

ab 2 ba 3 3 után ab 2 a 0 b 1 ab 2 ba 3 aba 4 4 után aba 4 a 0 b 1 ab 2 ba 3 aba 4 abab 5 5 után ba 3 a 0 b 1 ab 2 ba 3 aba 4 abab 5 baa 6 A következő táblázat a dekóder működését mutatja. A dekóder beolvassa a kódszót, és előveszi a szótárból az ehez tartozó szavat, amit a kimenetre ír. Jól megfigyelhető, hogy a dekóder az új szó dekódolása után ezt a szót felveszi a szótárba, de nem tudja még, hogy melyik betűvel kell azt folytatni, ezt a betűt egy új szimbólummal, a *-gal jelöljük. A k-dik lépésben keletkező új szó csak a k+1-dik lépésben lesz kész. Az első 3 lépésben nincs is semmi gond, azonban a 4-dik lépésbena * kimásolódik a kimenetre, mert egy olyan bejegyzésre hivatkoztunk a szótárban, ahol még nincs meg az utolsó betű. A megoldás azonban egyszerű: egy extra lépéssel kiegészítve a 4-dik lépést az új szó vége megvan (történetesen az új szó első betűje), és a kimenetről így eltűnik a *.

1előtt Új szó kódja Új szó S a z b ó t á r 0 1 1 után 0 a a 0 b 1 a* 2 2 után 1 b a 0 b 1 ab 2 b* 3 3 után 2 ab a 0 b 1 ab 2 ba 3 ab* 4 4 után 4 ab* a 0 b 1 ab 2 ba 3 aba 4 ab* 5 4 újra aba a 0 b 1 ab 2 ba 3 aba 4 aba* 5 5 után 3 ba a 0 b 1 2 3 4 5 A Lempel-Ziv-Yokoo módszer (LZY) Ez a módszer is az LZ78 továbbfejlesztése. Hasomlóan a Welch módosításhoz, itt sem küldjük el a befejező szimbólumot, hanem csak a szótár-bejegyzésekre hivatkozunk. A szótár építése azonban már az LZ77 módszerhez is hasonlatos: az eddig dekódolt szavakat használjuk fel a szótárban. A szótár felépítése a következő egyszerű szabállyal történik: a k-dik bejegyzés legyen a dekódolt szöveg k-dik pozíciójából induló, a szótárban még elő nem forduló legrövidebb sorozat. Hasonlóan az LZW módszerhez, a kezdeti szótár az összes egybetűs szó. Az LZ78 család alkalmazásai • compress (UNIX): Az LZW egyik legelterjedtebb változata

általános adattömörítésre. A szótárméret progressziven megduplázódik addig, amíg a kódszavak hossza el nem ér egy paraméterben megadott értéket, ez 9.16 bit lehet Ezután a szótár már nem változik. Ha azonban a tömörítés hatékonysága romlani kezd (az algoritmus figyeli a tömörítési arányt), akkor a szótárat kiüríti és elkezdi újra felépíteni. • gif veszteségmentes képtömörítés (Graphics Interchange Format): Ez is egy LZW alkalmazás, de képtömörítésre. A szótárméret itt is progressziven megduplázódik, a maximális méret 4096. A LLOYD ALGORITMUS 1. ALAPFOGALMAK N szintű skalár kvantáló: Q: R {y1, y2, y3,., yN} yi: kvantálási szint, reprezentációs pont, kódpont kvantálási cellák: Ri = {x | Q(x)=yi } {Ri} az R egy partíciója: Ri ∩ Rj = ∅ ∪Rj = R Kvantálási cellák: • nem korlátos cellák (overload cellák) • granuláris cellák Overload tartomány: Granuláris tartomány: a nem korlátos cellák

összessége a granuláris cellák összessége Kvantáló torzítása: adott a d(,) torzításfüggvény ∞ D( Q ) = ∫ d ( x , Q ( x )) f ( x )dx −∞ Jel-zaj viszony (SNR-Signal to Noise Ratio): SNR = 10 lg ( ) E x2 D( Q ) 2. OPTIMÁLIS KVANTÁLÓK 2.1 Kódoló-dekódoló struktúra: A kódoló: g: R {1, 2, 3,., N} A dekódoló: h: {1, 2, 3,., N} {y1, y2, y3,, yN} 2.2 Optimális kódoló az adott dekódolóra tetszőleges torzítás-kritérium mellett: (legközelebbi szomszéd feltétel) Adott a h() dekódoló függvény, vagyis az {y1, y2, y3,., yN} kódpontok halmaza (kódkönyv, codebook). A kódoló függvény feladata a partíciók meghatározása Az optimális kódoló függvény: g(x)=i ⇔ d(x, yi) =minj[d(x, yj)] Ebből a szabályból az is következik, hogy a döntés (kvantálás) nem függ az eloszlástól. Biz.: ∞ ∞ D( Q ) = ∑ ∫ d ( x , y i ) f ( x )dx = ∫ d ( x , Q ( x )) f ( x )dx ≥ ∫ min( d ( x , y i )) f ( x )dx i = 1 Ri −∞ −∞ i N

A legközelebbi szonszéd feltétel érdekes tulajdonsága az, hogy nem függ az eloszlástól, de függ a torzítás kritériumtól. 2.3 Optimális dekódoló az adott kódolóra négyzetes torzítás-kritérium mellett (súlypont feltétel): Adott a g() kódoló függvény, vagyis az {Ri} partíció. A dekódoló feladata a kódpontok elhelyezése. Az optimális dekódoló függvény a partíció várható értékére teszi a partícióhoz tartozó kódpontot, vagyis: [ ∫ x ⋅ f ( x ) dx ] yi = E x x ∈ Ri = Ri ∫ f ( x ) dx Ri Biz.: ∞ D( Q) = D(Q x ∈ Ri ) P( x ∈ Ri ) ∫ d ( x, Q( x)) f ( x)dx = ∑ ∫ d ( x, yi ) f x∈R ( x) P( x ∈ Ri )dx = ∑ i =1 i =1 N N i −∞ Ri Tehát a partíciókon belül, egymástól függetlenül lehet minimalizálni a torzítást a kódpont elhelyezésével. Az Ri partícióhoz tartozó optimális kódpont az, ahol minimális a torzítás: ( ) D Q x ∈ Ri = ∫ d ( x, yi ) f x∈R ( x)dx = ∫ ( x − yi ) i Ri

2 [( f x ∈Ri ( x )dx = E x − y i Ri ) 2 x ∈ Ri ] ⇒ yi = E[ x x ∈ Ri ] 2.4 Példa az optimalitási feltételekre: Egyenletes kvantáló a [0,A) tartományon egyenletes eloszlású valószínűségi változóra A N 0 y1 2A N y2 3A N y3 (N-1)A N yN-1 A N pontú egyenletes kvantáló a [0,A) tartományon kódkönyv: partíciók: -"- hossza: A A − N 2N A A  R i = ( i − 1) , i  N N  A ∆i = N yi = i A súlypont feltétel és a legközelebbi szomszéd feltétel is igaz. A kvantáló torzítása pedig 2 2 2  1  A ∆2 A  1 N ∆ A   A dx =   dx =   = ∫  x − i ⋅ − ∫x −  N 2N   A 2N  12  N  12 A 0 i =1( i −1)⋅∆  D( Q ) = ∑ N i⋅∆ 3. A LLYOD ALGORITMUS 3.1 A Lloyd iteráció kódkönyv tervezésére A kvantálót {Ri} partíció és C={y1, y2, y3,., yN} kódkönyv jellemzi Cél a partíció és a kódkönyv javítása lépésről lépésre. A

Lloyd algoritmus alapötlete a következő: a kvantáló optimalizálása (a kódoló és dekódoló együttes optimalizálása) algoritmikusan nehéz feladat. A szub-optimumot viszont el lehet érni azáltal, hogy lépésről lépésre javítjuk a teljes rendszer torzítását azáltal, hogy felváltva optimalizáljuk a kódolót és a dekódolót. A 21 és 22 pont alapján megállapíthatjuk, hogy mindkét lépésben csökken a torzítás. (1) Vegyünk fel egy kezdeti kódkönyvet: C(0) = egy jó közelítés m=0 Számoljuk ki a torzítást. (2) Optimalizáljuk a partíciót a C(m) kódkönyvhöz a legközelebbi szomszéd feltétel kielégítése (3) Optimalizáljuk a kódkönyvet a kapott partícióhoz, így kapjuk C(m+1)-et. (4) Számoljuk ki, hogy mennyivel csökkent a torzítás. (5) Ha a torzítás már csak jelentéktelenül csökken, akkor vége, különben pedig folytassuk (2)-ről m=m+1 értékkel. 3.2 Fleischer tétele Ha létezik f(x) sűrűségfüggvény és logf(x)

szigorúan konkáv, akkor ∀N kódkönyvméretre egyértelműen ∃Q(x) kvantáló, amely kielégíti a Lloyd feltételeket, és ekkor a Lloyd algoritmus a globális optimumhoz konvergál. 3.3 Empirikus kvantálótervezés a Lloyd algoritmussal A 3.1 pontban ismertetett Lloyd algoritmusban csak utaltunk a torzítás számítására, illetve a két optimalitási feltétel alkalmazására. A 2 pontban a feltételekben azt az esetet adtuk meg, amikor ismerjük a sűrűségfüggvényt. Empirikus esetben azonban csak mintáink vannak a jelből. Jelölje a tanító mintákat x1,x2,.,xM - a tanítóminta elnevezés onnan származik, hogy ezekkel a mintákkal tanítjuk be a kvantálót. Amikor tanító mintáink vannak, akkor a következő lesz a Lloyd algoritmus: (1) Vegyünk fel egy kezdeti kódkönyvet: C(0) = {y1, y2, y3,., yN} m=0 (2) Optimalizáljuk a partíciót a C(m) kódkönyvhöz a legközelebbi szomszéd feltétel kielégítése: Ri={x | d(x, yi) = minj[d(x, yj)] } (3)

Optimalizáljuk a kódkönyvet a kapott partícióhoz, így kapjuk C(m+1)-et: [ ] y i = E x x ∈ Ri = ∑x x ∈Ri # Ri (4) Számoljuk ki, hogy mennyivel csökkent a torzítás.    D Q = ∑  xk − y g ( xk )   k =1 ( ) M 2 ahol a g()függvény a kódoló függvényt jelöli. (5) Ha a torzítás már csak jelentéktelenül csökken, akkor vége, különben pedig folytassuk (2)-ről m=m+1 értékkel. KOMPANDERES KVANTÁLÓTERVEZÉS A kompander egy függvény, amely a skalár kvantálás előtt áttranszformálja a jelet. A kompander függvény inverze a dekóder oldalon az expander. Kompander Kódoló Dekódoló Expander y=G(x) i=Q(y) y=Q-1(i) x=G-1(y)  Kvantáló y=G(x) x=G-1(y) y x 2. A kompanderes kvantáló torzítása, optimális kompander függvény Ebben a pontban az aszimptotikus kvantáláselmélet alapján levezetjük a Benettintegrált közvetlenül a kompander függvényre. Célunk

egyenletes skalár kvatnáló mellett az aszimptotikusan optimális kompander karakterisztika meghatározása a sűrűségfüggvényből, amit a Benett-integrál alsó becslésével teszünk meg. Az aszimptotikus kvantáláselmélet alapötlete az, hogy nagyon nagy kódkönyvet használunk, ekkor a cellák már olyan kicsik, hogy azon belül az eloszlás már egyenletes eloszlással közelíthető, így a bonyolult sűrűségfüggvényt is lehet egyszerű módon közelíteni. Feltevések: (1) N nagy (2) ∆i= zi - zi-1 mindenhol kicsi, ahol a cellát a [zi-1,zi) intervallum jelöli (3) Egy cellán belül f(x) sima, vagyis f(x) ≈ fi (4) Nincs nem korlátos tartomány, vagy pedig elhanyagolható (5) A kódpontok a cella felezőpontjai: y i = zi −1 + zi 2 (6) Egy cella valószínűsége: P(zi-1 ≤ x < zi) ≈ (zi - zi-1) ⋅ fi = ∆i ⋅ fi (7) A torzítás közelítése: ( ) N ( D Q ≈ ∑ ∫ f ( x) x − yi i =1 Ri N zi N ∆i i =1 zi −1 i =1 0 ) 2 dx ≈ ∑

f i ∫ ( x − yi ) 2 dx =∑ f i ∫  x − ∆2i  2 N dx = ∑ f i i =1 N ∆3i ∆2i ≈ ∑ pi 12 i =1 12 Képezze le a kompander a (-∞,∞) tartományt a ( − 21 , 21 ) intervallumra, és legyen a kompander karakterisztika y=G(x). Feleltessük meg az yi kódpontoknak (y tartomány) a kompander bemenetén a megfelelő xi=G-1(yi) pontokat, és ugyanígy a cellákat és a cella szélességeket is. Álljon a kódkönyv N kódpontból, és legyen a kvantáló egyenletes skalár kvantáló. Ekkor minden egyes cella szélessége ∆ = ∆y i = 1 N , az Ri cella megfelelőjének ∆y 1 = ( ) G′ x N ⋅ G ′( x ) szélessége az x tengelyen (a kompander bemenetén) így ∆x i = G ′( x ) = ∆G ( x ) = ∆x ∆y . A torzítás ekkor aszimptotikusan: ∆x N ∆2i 1 1 D Q ≈ ∑ pi ⋅ = ∑ pi ⋅ 2 ≈ 2 12 N2 12 12 N ⋅ [ G ′( x )] i =1 i =1 ( ) N N ∑ i =1 ( ) f x i ∆x i [ G ′( x )] ≈ 2 ∞ 1 12 N 2 , mert f ( x) ∫ 2

dx −∞ [ G ′( x )] A fenti összefüggés a Benett-integrál kompanderre számított alakja. A Hölder-egyenlőtlenség alapján adható alsó becslés a Benett-integrálra. Jelölje a kompander karakterisztika deriváltját g(x), azaz g(x)=G(x), és mivel a kimeneti intervallum ( − 21 , 21 ) , emiatt ∞ G( x ) − lim G( x ) = 1 . ∫ g( x)dx = xlim ∞ x −∞ −∞ A Hölder egyenlőtlenség a következőt mondja ki: Adott p,q>0 konjugált exponensek, vagyis ∞ és U = ∫ 1 1 + =1, p q és adott az u(x) és v(x) függvény, u( x ) dx integrál létezik és korlátos, ugyanígy V = p −∞ ∞ ∫ v( x ) q dx integrál is létezik −∞ és korlátos. Ekkor 1 p ∞ ∫ u( x) ⋅ v( x) dx ≤ U ⋅V 1 q −∞ Alkalmazzuk a Hölder-egyenlőtlenséget a következő módon:  f ( x)  u( x ) =  2  ,  g ( x)  3 p = 3, q= 2 3 , 2 v( x ) = g 3 ( x ) 1 ⇒∫ f 1 3 ( x ) dx = ∫ 1  f ( x)  3 u( x ) ⋅ v( x ) dx

≤  ∫ 2 dx ⋅  g ( x)  (∫ g( x)dx) vagyis átrendezés után  f  ∫ azaz D Q* = 1 3 ( x ) dx  ( ) 3  ≤∫ 1 12 N 2 f ( x) g 2 ( x)  f  ∫  f ( x)  3 =  ∫ 2 dx  g ( x)  dx ( x ) dx  1 3 2 3  f ( x) 3 ≤ D( Q) = f ( x) 1 12 N 2 ∫ g 2 ( x) dx 1 3 Az alsó korlátot viszont el lehet érni a g * ( x ) = ∫ f 3 ( x )dx 1 függvénnyel (könnyen ellenőrizhető). Ekkor a megfelelő G*(x) kompander karakterisztika integrálással 1 2 kapható meg egy additív konstans erejéig (amely - , mert a kompander kimeneti tartománya ( − 21 , 21 ) ), tehát az aszimptotikusan optimális kompander karakterisztika: x 1 G ( x) = − + 2 * ∫f 1 3 ( z )dz ∫f 1 3 ( z )dz −∞ ∞ −∞ A fenti, aszimptotikusan optimális kompanderes kvantóló torzítása, vagyis a Benettintegrál minimuma adott eloszlás mellett: ( ) D Qopt ≈ 1 12 N 2 (∫ f 1 3 ( x

)dx ) 3 Megemlítjük, hogy nem csak ebben a speciális esetben (kompander + egyenletes lépésközű skalár kvantáló) ennyi az aszimptotikusan optimális torzítás, hanem tetszőleges skalár kvantáló esetén is ugyanennyi a torzítás minimuma. Végezetül azt vizsgáljuk meg, hogy ez az optimum hogyan függ a szórástól. Itt f(x) az x valószínűségi változó sűrűségfüggvényét jelöli. Legyen t= { x − E {x} E ( x − E ( x )) 2 } = x − mx σx a t az x valószínűségi változó normalizáltja 1 egységnyi szórásúra és 0 várható értékűre, azt is mondhatnánk, hogy a sűrűségfüggvény alakja ugyanaz, csak a szórás és a várható érték más. Legyen a t valószínűségi változó sűrűségfüggvénye ft(), ezt nevezzük az x valószínűségi változó prototípus sűrűségfüggvényének Eloszlástranszformációval belátható, hogy ekkor a minimális torzítás értéke: ( ) D Qopt ≈ σ x2   1  f ∫ t 3 (

x)dx 12 N 2  3 vagyis azonos prototípus sűrűségfüggvényű, de más szórású valószínűségi változók esetén az optimális torzítás a szórásnégyzettel egyenesen arányos. PREDIKCIÓ, PREDIKTÍV KVANTÁLÁS 1. Optimális predikció A feladat egy X valószínűségi változó becslése egy megfigyelt Y valószínűségi változó függvényével, g(Y)-nal úgy, hogy a becslés hibája négyzetes értelemben a legkisebb 2 legyen, azaz E ( X − g( Y ) )  minimális legyen.  Tétel:  g( y ) = E [ X | Y = y ] Bizonyítás: [ Tekintsük min E ( X − g(Y )) g ( ⋅) 2 ] feladat helyett a min E[( X − a) ] minimalizálási feladatot, 2 a vagyis ahol a konstans megválasztása a feladat. Tudjuk, hogy ekkor a várható érték minimalizál, vagyis a = E[ X ] Feltéve, hogy az Y valószínűségi változó y értéket vett fel, a tétel állítása adódik. Megjegyezzük, hogy normális eloszlás esetén az optimális predikció a

lineáris predikció. 2. Optimális lineáris predikció Az optimális lineáris predikció csak úgy érdekes feladat, ha több valószínűségi változót tudunk megfigyelni, és ezek lineárkombinációjával becslünk. A feladat itt egy A valószínűségi változó becslése egy megfigyelt Y1,Y2,.,Yn valószínűségi változók lineárkombinációjával úgy, hogy a becslés hibája négyzetes értelemben a legkisebb legyen, vagyis keressük azt az a=a1,a2,.,an együttható vektort, amelyre 2 n     min E  X − ∑ a i ⋅ Yi   . a    i =1 A Linder-Lugossi jegyzetből az optimális a vektor a következő módon kapható meg: és m = [ E { XYi }] i =1.n jelöléssel a K ⋅ a = m lineáris egyenletrendszer K = E {Yi Y j } [ ] i =1.n , j1n megoldása, vagyis a = K −1 ⋅ m 3. Sztochasztikus folyamat következő mintájának lineáris predikciója véges memóriával A lineáris predikciós feladatot gyakran úgy adjuk meg, hogy

a A valószínűségi változó helyett egy {X} stochasztikus folyamat elemeit kell előrejelezni az előző n darab érték ismeretében. Ekkor a fenti képletbe a k-dik minta becslésekor X helyett Xk-t kell írni, az Yi helyett pedig valamelyik mintát az előző n mintából, mondjuk Xk-i-t. Ekkor a következő módon kell felírni a lineáris egyenletrendszer együtthatóit: és m = [ E { X k ⋅ X k − i }] K = E { X k −i X k − j } i =1.n [ ] i =1.n , j1n 3.1 Gyengés stacionárius folyamat tiszta előrejelzése 1 mintával előre lineáris predikcióval Ekkor a feladat ugyanaz, mint az előző esetben, de további egyszerűsítést jelent az, hogy a sztochasztikus folyamat gyengén stacionárius. Ekkor a következő módon egyszerűsödik a feladat: gyengén stacionárius, 0 várható értékű folyamat esetén ( )  E X i ⋅ X j = E X 0 ⋅ X  j −i (   = R i− j  ) Így a megoldandó lineáris egyenletrendszer a következő lesz:  R( 0)

  R(1)  R( 2 )   R( 3)     R( n − 2 ) R n −1 )  ( R(1) R( 0) R( 2 ) R(1) R( 3) R( 2 )  R( n − 2 )  R( n − 3) R( 2 )  R(1)  R( 0)   R( n − 5)   R(1) R( n − 3) R( n − 2 ) R( 0) R( n − 4 ) R( n − 3) R(1) R( n − 5) R( n − 4 )  R( n − 4 ) R( 0) R(1) R( n − 1)    R(1)  R( n − 2 )    R( n − 3)   R( 2 )   R( n − 4 )  ⋅ a =         R( n − 1)    R( n )  R(1)     R( 0)  Látható, hogy a megoldandó egyenletrendszer csak n+1 paramétert tartalamaz, vagyis ezek a paramlterek a R(0),R(1),.,R(n) Létezik olyan gyors algoritmus, amely ebből az n+1 darab paraméterből számolja ki közvetlenül az a lineáris predikciós együtthatókat, és nem direkt módon invertálja a fenti n*n-es mátrixot. A gyors algoritmus azért fontos, mert a gyakorlatban ritkán találkozunk gyengén stacionárius jelekkel,

azonban az már gyakran előfordul, hogy a jel szakaszai gyengén stacionárius (illetve annak tekinthető) részekből állnak össze. Ekkor szakaszonként kell a prediktor együtthatóit változtatni. 4. Prediktív kvantálás 4.1 Prediktív kvantálás előrecsatolt prediktorral A prediktív kvantálás ötlete az, hogy nem a jelet kvantáljuk, hanem a becslési hibát. Az alábbi ábrán egy előrecsatolt prediktor látható. Az előrecsatolt prediktornál a kódoló a bemenő jelből becsli a következő mintát, és a valóságos és a becsült minta különbségét kvantálja. A dekóder - mivel nem ismeri az eredeti bemenő jelet - a kvantált értékből visszaállítja a jelet, amely pontos rekonstrukció (y(t)=x(t)) lenne akkor, ha nem lenne kvantálás. A visszaállításhoz a dekóder a dekódolt jelből becsli a következő mintát, és ezt használja a dekódoláshoz. x(t) + e(t) + - A(z) x( t ) e~(t ) Kvantáló Kódoló: i (t ) = int + { } e( t ) 10

y(t) + + y ( t ) A(z) Dekódoló: e( t ) = 10 ⋅ i ( t ) Bemenő jel (x(t)) 8 13 18 23 28 Becslés a x(t)-ből 0 8 13 18 23 Becslési hiba (e(t)) 8 5 5 5 5 e(t) kvantálva 10 10 10 10 10 y(t) kvantálva 0 10 20 30 40 Kimenő jel y(t) 10 20 30 40 50 Az előrecsatolt prediktor halmozza a kvantálási hibát. Ez abból látható, hogy miközben a bemenő jel, vagyis x(t) mintái 5-tel növekednek, addig a kimenő jel mintái 10-zel, és az egyenletes lépésközű skalár kvantáló kvantálási hibája a végén már 22 volt, ami 10-es lépésköz esetén csak a -5.+5 tartományban lehetne A jelenség oka az, hogy a kódoló és a dekódoló nem ugyanabból a jelből végzi a becslést. Ezt a hibát az ún. visszacsatolt prediktorral lehet kijavítani 4.2 Prediktív kvantálás visszacsatolt prediktorral Az előrecsatolt prediktor vizsgálatánál láttuk, hogy az előrecsatolt predikció halmozza a kvantálási hibát. Az alábbi ábrán az ún visszacsatolt predikció

látható A visszacsatolt predikció lényege az, hogy ugyanabból a jelből becsli a kódoló is a bemenő jelet, mint a dekódoló, ezért nem halmozódik a kvantálási hiba. Ennek a rendszernek a neve a differenciális pulzus kód moduláció (DPCM), ahol a differencia a predikált és a valóságos minta közötti különbségre utal. x(t) + e(t) + e~(t ) Kvantáló - + + y ( t ) + A(z) y ( t ) + A(z) y(t) + + y(t) A fenti ábra alapján jól nyomonkövethető, hogy a kvantálási hiba nem halmozódik fel. A DPCM rendszerben a hibajelbe bevitt kvantálási hiba megegyezik az eredeti jelbe bevitt kvantálási hibával, ezt a következő módon lehet belátni: y = y + e~ e − e~ = ( x − y ) − ( y − y ) = x − y Emlékezzünk arra, hogy az optimális kvantáló torzítása a Benett-integrál alapján a szórásnégyzettel arányosan növekszik, még pontosabban: ( ) D Qopt ≈ σ x2   1 3 ( )  2  ∫ f t x dx 12 N 3

Emiatt - eltekintve a prototípus sűrűségfüggvény, vagyis ft(x) változásának hatásától a jel-zaj viszony jól jellemzi a kódolási torzítás változásának hatását. Vizsgáljuk meg tehát, hogy mennyivel változott a jel-zaj viszony azáltal, hogy bevezettük a zárhturkú predikciót (a zajt nem az x(t), hanem e(t) kvantálása okozza): SNR = { σ x2 E (e − e~ ) 2 } = σ x2 ⋅ { σ e2 σ e2 E (e − e~ ) 2 } = GCLP ⋅ SNRQ Durván azt lehet mondani, hogy a kvantáló jel-zaj viszonyát (SNRQ) egy GCLP (ún. predikciós nyereség) 1-nél nagyobb számmal szoroztuk meg, vagyis növeltük a jel-zaj viszonyt. 6. Delta moduláció A delta moduláció egy olyan speciális DPCM, ahol 1 bites kvantálót alkalmaznak. A módszer onnan kapta a nevét, hogy így a kvantáló dekóderének kimenetén vagy -∆, vagy +∆ jelenik meg. A delta modulátor algoritmusa a következő: y ( t ) = y( t − 1) e( t ) = x( t ) − y ( t ) e~( t ) = ∆ ⋅ sgn( e( t

) ) vagyis a prediktor az előzőleg dekódolt mintára becsül. Az alábbi ábrán a delta modulációra látunk példát. 8∆ 4∆ 2∆ ∆ T 2T 4T 6T 8T 10T 12T 14T 16T Vizsgáljuk meg a delta moduláció két fő problémáját az fenti ábrán, ahol a szaggatott vanallal jelölt jelet kell követni a delta modulációval működő rendszernek (vastag vonal): • majdnem egyenszint (a jel ingadozása hosszú időn át kicsi a ∆-hoz képest): ekkor a delta modulátor fel-le ugrál, vagyis kisebb ∆ lenne jó • meredek emelkedés (a meredekség nagyobb ∆/T-nél): mivel a delta modulátor csak ∆/T emelkedést tud produkálni, ezért ekkor lemarad, és a kvantálási hiba amplitudója túlnő ∆-n. A delta modilációt a fentiek miatt adaptív ∆ lépésközzel szokták megvalósítani a következő módon: • ha a jel ingadozása "hosszú időn át" kicsi a ∆-hoz képest csökkentsük ∆-t • ha a jel meredeken emelkedik a ∆/T-hez képest *

növeljük ∆-t Ezt például a következő algoritmussal lehet megtenni: b(k) : a k-dik időpillanatban az előjelbit ∆(k) : a k-dik időpillanatban a lépésköz HA AKKOR KÜLÖNBEN b(k) = b(k-1) = b(k-2) f := (1-β)(∆max - ∆min) f := 0 /* vagyis meredek emelkedés van / /* vagyis majd növeljük ∆-t/ /* vagyis majd növeljük ∆-t/ ∆(k):= ∆min + f + β(∆(k-1) - ∆min) 7. A lineáris predikciós szűrő szűrő hatékony kódolása A lineáris predikciónak azt a fajtáját, ahol a következő mintát az előző n mintából becslik, gyakran tekintik/nevezik lineáris predikciós szűrésnek is. Ha a memória P hosszú, vagyis az előző P mintát használjuk a becslésre, akkor x(t) = P ∑ a i ⋅ x(t - i) , ez i=1 * Itt megoldást jelent az is, ha növeljük T-t (akár lokálisan, akár az globálisan), azaz növeljük a mintavételi frekvenciát! P pedig egy konvolúciónak is felfogható. A prediktor függvény ekkor A(z) = ∑ a i ⋅ z −i , i=1

az a1,a2,.,aP paramétereket pedig LPC (Linear Predictive Coding - lineáris predikciós kódolás) paramétereknek nevezik. Gyakorlati alkalmazásokban a prediktor együtthatókat is el kell küldeni a dekódernek, tehát kvantálni kell azokat. Mivel a szűrő stabilitása a kvantálás miatt megváltozhat, ezért a stabilitását általában úgy valósítják meg, hogy nem direkt formában, vagyis P A(z) = ∑ a i ⋅ z −i szűrővel szűrnek, hanem az ún. lattice szűrővel i=1 Σ Σ Σ Σ Σ -kN -kN-1 -k1 -kN -kN-1 -k1 -1 z Σ z-1 Σ z-1 Σ z-1 Σ z-1 A lepkeszűrő ki paramétereire, az ún. PARCOR (parciális korrelációs) együtthatókra a stabilitási feltétel a |ki|≤1, ahol a PARCOR paraméterek száma megegyezik az LPC paraméterek számával. Mivel a PARCOR paraméterek az 1 közelében nagyobb érzékenységet mutatnak a kvantálásra, ezért azok nemlineáris függvényét használják, mint például az IS (inverz szinusz) vagy a LAR (log

area ratio) reprezentációt. A LAR definíciója:  1 − ki  LARi = log   1 + ki  A LAR és IS paraméterek jól kvantálhatóak, és az előbbit széles körben használják. A gyakorlatban a legjobb jelrekonstrukcióhoz mindig a fenti PARCOR alapú szűrést alkalmazzák, mégha a kvantálást nem is PARCOR együtthatókon végzik el. Szintén elterjedt és népszerű az ún. vonalas spektrum frekvenciás (LSF - Line Spectral Frequency) vagy a vele rokon spektrumvonal páros (LSP - Line Spectral Pairs) ábrázolás, ahol az LSP paraméterek az LPC szűrő és annak konjungáltjából képezett összegpolinom, vagyis P(z)=A(z)+z-p-1A(z-1) és különbségpolinom, vagyis Q(z)=A(z)z-p-1A(z-1) gyökei párban, és mivel P(z) és Q(z) gyökei, vagyis az LSP-k az egységkörön vannak, vagyis ejϖ alakúak, ezért az LSP-knek megfelelő frekvenciákkal is le lehet írni a szűrőt, és eze a frekvenciák az LSF paraméterek. A LSF frekvenciák kvantálásával a

gyökök továbbra is az egységkörön vannak, a stabilitáshoz csak azt kell biztosítani, hogy a szigorúan monoton növekedés tulajdonsága végig megmaradjon. Az LSF paraméterek nagyjából a beszédspektrum csúcsait és "völgyeit" veszik körbe, emiatt erősen emlékeztetnek a beszéd formánsaira. A jelenlegi legjobb kódolók az LSF paramétereket használják, de pl. a beszédfelismerésben is népszerű Végezetül meg kell említeni, hogy a legtöbb kódoló az ún. előre adaptív kódolást alkalmazza, ami azt jelenti, hogy a jelet blokkora osztják, a blokkok autokorrelációs mátrixából kiszámítják a szűrőparamétereket (az LPC paramétereket a Levinson-Durbin, a PARCOR paramétereket a Shur-algoritmussal), és azokat kvantálva elküldik