Pagina:Codifica numerica del segnale audio.djvu/125

3 - Codifica di sorgente

107

La velocità complessiva, nel caso di struttura ad albero, sarà data dalla somma delle velocità parziali ad ogni singolo livello:

$R=\sum _{n=1}^{L}R_{n}$

(3.56)

In generale quindi si può concludere che i QV strutturati ad albero consentono una riduzione di complessità di calcolo a scapito di un aumento della quantità di memoria necessaria per memorizzare esplicitamente il vocabolario. Tale riduzione di complessità è tanto maggiore quanto minore è il numero di rami che si dipartono da ogni singolo nodo. Questa riduzione diventa quindi massima nel caso di struttura binaria dove da ogni nodo si dipartono due soli rami. Il confronto in termini di complessità e di memoria tra le tre strutture descritte è riportato in tabella 3.8 dove R rappresenta la velocità complessiva del QV in bit/vettore ed L il numero di livelli.

	Numero di livelli	Velocità al livello n	Numero di calcoli di distorsione	Numero di vettori da memorizzare
Ricerca esaustiva	1	R	2 R	2 R
Ricerca ad albero	L	Rn	$\sum _{n=1}^{L}2^{R_{n}}$	$\sum _{i=1}^{L}\prod _{n=1}^{i}2^{R_{n}}$
Ricerca binaria	L=R	1	2-R	$\sum _{i=1}^{R}2^{i}$

Tab. 3.8 - Confronto in termini di complessità di calcolo e memoria necessaria tra le diverse strutture di quantizzatori vettoriali.

Il progetto di QV con struttura ad albero utilizza l’algoritmo base LBG con alcune semplici modifiche. Si comincia calcolando il QV, e quindi il vocabolario ottimo, per il primo livello. Quindi si divide la sequenza di addestramento nei vari cluster relativi ad ogni singolo nodo di tale livello (calcolo della partizione ottima). Per ogni nodo, ed utilizzando come sequenza di addestramento i vettori del cluster, si calcola il vocabolario ottimo di dimensione pari al numero di rami che si dipartono da quel livello. La procedura continua fino all’ultimo livello allo stesso modo.