Informatika | Információelmélet » Aszimptotikus kvantáláselmélet

A SZI M PTOTI K US K VANTÁL ÁSEL M ÉL ET (AZ EL ÕADÁS TEL JES ANYAGA ) 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 1. A Hölder egyenlõtlenség Az aszimptotikus kvantáláselmélet egyik fõ tételének, a Benett-integrálnak az alkalmazásához a Hölder-egyenlõtlenséget használjuk a Benett-integrál alsó becslésére, ezért itt kimondjuk ezt az egyenlõtlenséget: Adott p,q>0 konjugált exponensek, vagyis ∞ és U = ∫ 1 1 + = 1 , és adott p q u( x ) dx integrál létezik és korlátos, ugyanígy V = p −∞ az u(x) és v(x) függvény, ∞ ∫ v( x ) q dx integrál is létezik −∞ és korlátos. Ekkor ∞ ∫ u( x) ⋅ v( x) dx ≤ U 1 p ⋅V 1 q −∞ Példa: bizonyítsd be a Cauchy-Schwarz egyenlítlenséget a Hölder-egyenlõtlenséggel. 2. K vantálási pont-sûr ûség függvény λ ( x ) : = lim N ∞ 1 N ∆ ( x) ∆ N ahol N∆(x) = ennyi kódpont található az [x, x+∆) tartományon. Tegyük fel, hogy N már olyan nagy, hogy a kvantálási pont-sûrûség függvényre a fenti képlet már a határérték nélkül is jó. Vegyük

észre, hogy ilyen nagy N-re az x pont egy ∆x hosszúságú környezetében N⋅∆x⋅λ(x) kódpont van. Továbbá, ha az i -dik cella ∆ szélességû környezetében körülbelül egyforma hosszú cellák vannak (mindegyik cella hossza kb. ∆i ), akkor: ∆i ≈ ∆ 1 = N ⋅ ∆ ⋅ λ ( x) N ⋅ λ ( x) Mint láttuk, nagy N-re egy ∆x hosszúságú környezetben N⋅∆x⋅λ(x) kódpont van, így ennek integrálja a teljes tartományra az összes kódpontszámot adja ki, vagyis N-t, azaz 1 N= ∫ N ⋅ λ ( x)dx = N ∫ λ ( x)dx R* Így R* ∫ λ ( x)dx = 1 , vagyis λ(x) egy sûrûségfüggvény (ahogy a nevében is benne van). R* 3. Benett-integr ál a kvantálási pont-sûr ûség függvénnyel Tudjuk, hogy D( Q ) ≈ ∑ f i N i =1 ( ) N ∆3i ∆2 ≈ ∑ pi i 12 i =1 12 N D Q ≈ ∑ pi i =1 1 ( ) 12 N ⋅ λ y i 2 2 = . N 1 ∑ 12 N 2 i =1 1 λ ( yi ) 2 ( ) ⋅ f yi ∆ i ≈ f ( x) 1 12 N 2 ∫ λ2 ( x) dx R* A levezetésben az

utolsó lépésben a Riemann-közelítõ összeget helyettesítettük integrállal, ahol R* a granuláris tartomány (az overload tartományt elhanyagoltuk). Példa: mutasd meg, hogy a Benett-integrál felhasználásával is kijön az egyeneltes skalár kvantáló torzítása (segítség: λ(x)-t kell jól megválasztani). 4. Optimális pont-sûr ûség függvény Keressük az minimális torzítást adó pont-sûrûség függvényt. Ezt úgy érjük el, hogy csak a sûrûségfüggvénytõl függõ alsó korlátot adunk a Benett-integrálra, és az alsó korláthoz pedig megadjuk a kvantálási pont-sûrûség függvényt. Alkalmazzuk a Hölder-egyenlõtlenséget (a következõ pontban mondjuk ki) a következõ módon:  f ( x)  u( x ) =  2  ,  λ ( x)  3 p = 3, q= 2 3 , 2 v( x ) = λ 3 ( x ) 1 ⇒∫ f 1 3 ( x ) dx = ∫  f ( x)  3 u( x ) ⋅ v( x ) dx ≤  ∫ 2 dx ⋅ ∫ λ ( x ) dx  λ ( x)  ( 1 ) 2 3  f ( x)  3 =

 ∫ 2 dx  λ ( x)  A keresett alsó korlát tehát: ( ) DQ ≈ 1 12 N 2 a+B ∫ a f ( x)  a+B 1   ∫ f 3 ( x )dx dx ≥  λ2 ( x) 12 N 2  a  1 3 Az alsó korlátot a következõ λ* (x) pont-sûrûség függvény adja ki: f λ* ( x ) = 1 3 ( x) 1 3 ∫ f ( x)dx 5. K ompander es kvantálóter vezé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. 2 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 6. A Benett-integr ál közvetlen kiszámítása kompander es kvantálór a 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. Képezze le a kompander a (-∞,∞) tartományt a ( − B2 , B2 ) 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 (figyelem: az elõzõekkel ellentétben itt xi már nem cellahatárpontot jelöl!). Á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 ∆ = ∆yi = B N , az Ri cella megfelelõjének szélessége az x tengelyen (a kompander bemenetén) így ∆x i = ∆G ( x ) ∆y B = G ′( x ) N ⋅ G ′( x ) , mert ∆y . A torzítás ekkor aszimptotikusan: ∆x ∆x N N ∆2 B2 B 2 N f ( x i ) ∆x i B 2 ∞ f ( x) ≈ ≈ D( Q ) ≈ ∑ p i ⋅ i = ∑ p i ⋅ dx ∑ ∫ 2 12 i =1 i =1 12 N 2 i =1 G ′( x ) 2 12 N 2

−∞ G ′( x ) 2 12 N 2 ⋅ G ′( x ) G ′( x ) = = [ [ ] [ ] ] A fenti összefüggés a Benett-integrál kompanderre számított alakja. A Hölder-egyenlõtlenség alapján itt is 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 ( − B2 , B2 ) , emiatt ∞ ∫ g ( x ) dx = lim G ( x ) − lim G ( x ) = B . x ∞ −∞ x −∞ Ekkor a Hölder- egyenlõtlenség alapján: 1 1  f ( x) 3  f ( x)  3 2 3   ≤ = f x dx g x dx dx   ⋅ ∫ g ( x ) dx ( ) ( ) ∫ 2 ∫ 2 ∫   g ( x )   g ( x)  [ 1 3 vagyis átrendezés után 1  ∫f B 2  azaz D Q* = ( ) 1 3 ( x )dx  3 ≤∫  f ∫ 12 N 2  1 3 1 3 f ( x) g 2 ( x) 1 ] 2 3  f ( x) 3 2 = ∫ 2 dx  ⋅ B 3  g ( x )  dx ( x )dx  3 ≤ D( Q ) = B2 12 N 2 ∫ f ( x) g 2 ( x) dx Az

alsó korlátot viszont el lehet érni a g ( x ) = B 1 3 ∫f ( x ) függvénnyel (könnyen ( x )dx 1 3 f * ellenõrizhetõ). Ekkor a megfelelõ G(x) kompander karakterisztika integrálással kapható meg egy additív konstans erejéig (amely - B 2 , mert a kompander kimeneti tartománya ( − B2 , B2 ) ), tehát az aszimptotikusan optimális kompander karakterisztika: x ∫f B G ( x ) = − + B −∞ ∞ 2 ∫f −∞ 1 3 ( z)dz 1 3 ( z)dz 7. K ompander es kvantáló Benett-integr álj a a kvantálási pont-sûr ûség függvény alapj án Képezze le a kompander a [-∞,∞) tartományt egy B hosszú tartományra, és legyen a kompander karakterisztika y=G(x). Álljon a kódkönyv N kódpontból Így a kódpontok száma egységnyi szakaszon mert G ′( x ) = ∆G ( x ) ∆x = ∆y ∆x N B , egy ∆y hosszú szakaszon pedig ∆y G ′( x ) N , = ∆x ⋅ N B B . λ ( x) = Tehát a kvantálási pont-sûrûség függvény: A kvantáló torzítása a

Benett-integrál alapján: D( Q ) ≈ a+ B B2 12 N 2 ∫ a G ′( x ) B f ( x) [G ′( x ) ] 2 . dx Az optimális kompander karakterisztika deriváltja az optimális λ* (x) pont-sûrûség függvénybõl számítható: ( G * ( x )) ′ = B ⋅ λ ( x ) x ⇒ G( x ) = C + B ∫ λ* ( x )dx −∞ ahol C az integrálás miatti konstans. 4