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ó + zi 2 z (5) A kódpontok a cella felezõpontjai: y i = i −1 (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  dx =∑ f i ∆12i ≈ ∑ pi ∆12i 2 N

i =1 3 N 2 i =1 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 ∞ 1 1 + = 1 , és adott az u(x) és v(x) függvény, p q ∞ és U = ∫ u( x ) dx integrál létezik és korlátos, ugyanígy V = ∫ v( x ) dx integrál is létezik p −∞ q −∞ é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 1 N ∆ ( x) N 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* R* Így ∫ λ ( 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 ∑ 2 12 N 2 i =1 λ 1 ( yi ) ( ) ⋅ 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 ⇒∫ 1 f 3 1 2  f ( x)  3  f ( x)  3 ( x ) dx = ∫ u( x ) ⋅ v( x ) dx ≤  ∫ 2 dx ⋅ ∫ λ ( x ) dx 3 =  ∫ 2 dx

 λ ( x)   λ ( x)  ( ) A keresett alsó korlát tehát: a+B ( ) 12 N 2 ∫ DQ ≈ 1 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: 1 f 3 ( x) λ* ( x ) = 1 ∫ f 3 ( 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 , mert = G ′( x ) N ⋅ G ′( x ) ∆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 1 2  f ( x) 3  f ( x) 3  f ( x)  3 2 2 3 3 3   ≤ ⋅ = ⋅ = f x dx g x dx dx g x dx dx B     ( ) ( ) ( ) ∫ 2 ∫ ∫ ∫ ∫ 2 2   g ( x )   g ( x )   g ( x)  [ 1 3 ] vagyis átrendezés után 3 1  13  ≤ f ( x ) dx f x dx ( ) ∫ ∫ 2  B 2  g ( x) azaz D Q* = ( ) 121N ∫ f ( x)dx  ≤ D(Q) = 12BN ∫ g (( x)) dx 1 3 2 3 3 2 f x 2 2 f 3 ( x) 1 Az alsó korlátot viszont

el lehet érni a g ( x ) = B * ∫ f 3 ( x ) dx 1 függvénnyel (könnyen ellenõrizhetõ). Ekkor a megfelelõ G(x) kompander karakterisztika integrálással kapható meg egy additív konstans erejéig (amely - B , mert a kompander kimeneti 2 tartománya ( − B2 , B2 ) ), tehát az aszimptotikusan optimális kompander karakterisztika: x G( x) = − ∫ f 3 ( z ) dz 1 B + B −∞ ∞ 1 2 ∫ f 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 = G ′( x ) N N , egy ∆y hosszú szakaszon pedig ∆y = ∆x ⋅ N , B B B ∆y . ∆x λ ( 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ó: x (G * ( x)) ′ = B ⋅ λ ( x) ⇒ G( x) = C + B ∫ λ ( x)dx −∞ ahol C az integrálás miatti konstans. 4