Pagina:Codifica numerica del segnale audio.djvu/114

96

Codifica numerica del segnale audio

Primo criterio di ottimalità

Si supponga di avere a disposizione un vocabolario di partenza Co ma non la partizione S dello spazio sorgente. Tale partizione può essere costruita associando ogni vettore di ingresso X ad uno specifico vettore Y (i) e Co scelto all'interno del vocabolario in modo da soddisfare il criterio di minima distorsione e cioè minimizzando d{X, Y(i)). Tale operazione consiste quindi nella quantizzazione di tutti i vettori dello spazio sorgente e nella loro suddivisione in opportuni sottoinsiemi (o cluster) relativi alla stessa parola del vocabolario. Se si indica tale partizione con P 0 tt, ne consegue per come è stata costruita che

$D(S,C_{0})\geq D(P_{ott},C_{0})$

(3.49)

e cioè la distorsione media associata alla partizione ottima è minore o al più uguale della distorsione media ottenibile con qualsiasi altra partizione.

Secondo criterio di ottimalità

In questo caso si supponga di avere a disposizione la partizione dello spazio sorgente Sq ma non il vocabolario C. Per ogni sottoinsieme s, della partizione esiste un vettore a minima distorsione Y(sj) tale da minimizzare la distorsione media nel singolo cluster s it e cioè tale che:

$E\{d(X,{\bar {Y}}(s_{j}))|X\in s_{i}\}\leq E\{d(X,Z)|X\in s_{i}\}\supset Z$

(3.50)

Il vettore Y(sj) che soddisfa questa condizione prende il nome di centroide o centro di gravità generalizzato del cluster s_i. Supponendo ora di costruire un vocabolario C_ott come unione dei vari centroidi, otterremo il vocabolario ottimo C_ott = |Y(Sj); i = 1,2,..., N} per il quale vale la relazione

$D(S_{0},C)\geq D(S_{0},C_{ott})$

(3.51)

dove C rappresenta ogni possibile vocabolario.

Le due condizioni di ottimalità appena presentate sono gli elementi base utilizzati dall'algoritmo LBG che è un algoritmo iterativo strutturato sui seguenti quattro passi.