InfElmTetel20

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style>

Lloyd-Max algoritmus

Nagyobb valószínűségű helyeken a kvantálási intervallumot kisebbnek választunk. Adott [math]X[/math] valószínűségi változóhoz keressük az [math]N[/math] szintű optimális [math]Q[/math] kvantálót.
A kvantálási szintek [math]x_1\lt x_2\lt \ldots\lt x_N[/math]. A négyzetes torzítást akarjuk minimalizálni.

Feltételek

Az optimális kvantáló kielégíti a Lloyd-Max feltételeket:

Legközelebbi szomszéd feltétel

Minden [math]x[/math] értéket a hozzá legközelebb eső kvantálási szintre kvantálunk. Ha két kvantálási szint felezőpontjában van [math]x[/math], akkor a két szint közül tetszőlegesen választhatunk.

Formálisan:
[math]\forall x \in \mathbb{R}: |x-Q(x)|=\min_{1 \leq i \leq N}{|x-x_i|} [/math]

Súlypont feltétel

Minden kvantálási szint a saját kvantálási intervallumának súlypontja.

Formálisan:

[math] x_i = [\int_{y_{i-1}}^{y_i}\limits x f(x) dx]/[\int_{y_{i-1}}^{y_i}\limits f(x) dx] [/math]

[math]y_i[/math]-k jelölik a kvantálási intervallumok határait, [math]y_i = \frac{x_i+x_{i+1}}{2}[/math].

Algoritmus

Az ilyen kvantáló a Lloyd-Max kvantáló. Az algoritmus:

• Vegyünk fel egy közelítést a kvantálási szintekre.
  
• Optimalizáljuk a kvantálót a kvantálási szintek szerint, a legközelebbi szomszéd feltétel kielégítésével.
  
• Számítsuk ki a torzítást, ha ez egy küszöbértéknél kisebb lett, akkor készen vagyunk.
  
• Optimalizáljuk a kvantálót a kapott intervallumokhoz a súlypont feltétel kielégítésével, és ugorjunk a 2. pontra.
  

author{Vigovszky Dániel, Bálint Márton}

-- Sales - 2006.06.25.