Informatika | Információelmélet » Tömörítési eljárások

1 Tömörı́tési eljárások jpeg, gif, GSM, compress, pkzip, (arc, rar .) redundáns adatok: tömörı́tés sikeres! Veszteség nélküli és veszteséges eljárások Futási hossz: Pl. a 127 alatti karakter: darabszám a következő ismétlődő karakterre 128 feletti karakter: x-128 darab különböző karakter Nem mindig hatásos: pl. egy ABABAB Delta kódolás: csak a különbség: kevesebb bit! 2 Lineáris Prediktı́v Kódolás (LPC) 3 Lempel-Ziv-Welch eljárás alapötlet: szótár létrehozása • miden bejövő adat: új szó a maximális egyezésű szótárelemmel • tömörı́tett kódot a maximális egyezésű szótárelem • szótár mérete tipikusan 212-216 • ha szótár megtelik letörlik (csak az induló szótár marad meg ASCII!) 4 • visszaállı́tás/dekódolás: szótár újra épı́tése • adatfolyamban!! • minden kód rekurzı́van

helyettesı́tődik a prefix kódjával+ a követő karakterrel • HW megvalósı́tás 5 6 7 Huffman-kódolás: Bejövő jelek eloszlása előzetesen pontosan ismert sorbarendezés előfordulásuk valószı́nűségében gyakoriak - kevés bit ritkák - sok bit rekurzı́van a két legkisebb valószı́nűségű jel helyett új jelet vezet be, a két jel 8 valószı́nűségének együttes valószı́nűségével Kódolás: pl. nagyobb valószı́nűségű jel 0, a kisebb 1 Visszalépünk egyet a rendezésben, s.ı́t Prefix kódolás 9 Dekódolás: táblázattal Egyértelmű kódhatárok! Kérdés: Mekkora a példában szereplő karaktersorozat és annak Huffman kódolásának Shannon-entrópiája? 10 A statikus kódtábla felépı́téséhez ismerni kell a jelet! Aritmetikai kódolás 11 JPEG kódolás Veszteséges kódolás (l. pl wavelet) - hosszú kutatómunka,

több ajánlás JPEG Baseline coding Kép felosztása 8 × 8-as területekre (lokálisan adaptı́v) 12 Kódolás blokkonként: Karhunen-Loeve (főkomponens) transzformáció lenne a legjobb, de FFT is jó, és egyszerűbb: Ne legyen komplex kimenet: diszkrét cosinus transzformációt (DCT) alkalmazunk DCT: mintasorrend 1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2, 1+FFT szimmetria miatt valós lesz! Azaz 8 × 8 valós értékből 8 × 8 valós értéket készı́t! 13 A DCT értékeket kvantáljuk (max. 11 bit!): 14 15 kvantálási tábla: 16 Lineáris sorozattá alakı́tás: 17 egymás mellé kerülnek, a homogén, egyszı́nű felületek: AC komponensek futási hossz kóddal tömörı́tve DC komponensek: delta kóddal tömörı́tve (lassan váltooznak) 18 MPEG: mozgó JPEG 19 Zajok jellemzői Zaj és zavar: • zaj: nem lehet megszüntetni • zavar: elvben kiszűrhető Zajok

jellemzése valószı́nűségi adatokkal: Folytonos vagy mintavett jelek: Átlag és szórás: 20 Átlag és szórás: µ σ 2 = = = numerikus problémák. N −1 1 X xi N i=0 N −1 X 1 2 (xi − µ) N − 1 i=0 "N −1 # N −1 X X 1 1 2 2 xi − ( xi) N − 1 i=0 N i=0 21 N darab mérés esetén: σ σ⇒√ N Sok mérés kicsi szórás , ha stacioner a folyamat: 22 Sok mérés folytonos eloszlás: Sok mérés folytonos eloszlás: Valószı́nűségi sűrűségfüggvény: Néhány példa: 23 24 25 Normál/Gauss eloszlás P (x) = √ 1 2ıσ −(x−µ)2 /2σ 2 e Átlag és szórás tökéletesen leı́rja: Akármilyen eloszlásból sok összege ide vezet!!! 26 Zaj: effektı́v érték értelmes: λ egyenáramú jel + σ szórású Gauss eloszlású zaj a jel teljesı́tménye: Z ∞ 2 2 2 teljesı́tmény = (λ + x) G(x)dx = λ + σ = P= + P∼ −∞ A jel

teljesı́tménye az egyen- és váltakozóteljesı́tmények összege! Ha λ = 0, a teljesı́tmény a szórásnégyzettel egyezik meg Fehérzaj: teljesı́tménysűrűség adott B sávszélességű fehér zaj teljesı́tménye: Pzaj = n0B .