InfElmTetel20

Ez az oldal a korábbi SCH wikiről lett áthozva.

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 $X$ valószínűségi változóhoz keressük az $N$ szintű optimális $Q$ kvantálót.
A kvantálási szintek $x_{1}<x_{2}<\ldots <x_{N}$. 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 $x$ értéket a hozzá legközelebb eső kvantálási szintre kvantálunk. Ha két kvantálási szint felezőpontjában van $x$, akkor a két szint közül tetszőlegesen választhatunk.

Formálisan:
$\forall x\in \mathbb {R} :|x-Q(x)|=\min _{1\leq i\leq N}{|x-x_{i}|}$

Súlypont feltétel

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

Formálisan:

$x_{i}=[\int _{y_{i-1}}^{y_{i}}\limits xf(x)dx]/[\int _{y_{i-1}}^{y_{i}}\limits f(x)dx]$

$y_{i}$-k jelölik a kvantálási intervallumok határait, $y_{i}={\frac {x_{i}+x_{i+1}}{2}}$.

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.