 |
Questa pagina è stata trascritta e formattata, ma deve essere riletta. | |
| 3 - Codifica di sorgente | 105 |
possibili vettori disponibili nel vocabolario, al fine di determinare quello a distorsione minima. Tale tipo di ricerca esaustiva (full-search), seppur molto diffusa, è solo una delle possibili tecniche di ricerca e quindi di quantizzazione vettoriale.
Un’altra possibilità introdotta in letteratura è quella della ricerca ad albero (tree-search) che ha come caso particolare la ricerca binaria (binary-search). Il motivo per cui si sono considerate tecniche alternative di ricerca, risiede nella complessità di calcolo associata con la tecnica di QV a ricerca esaustiva. Infatti un algoritmo di ricerca completa richiede per la quantizzazione di un vettore, il calcolo di N valori di distorsione dove N è il numero di parole del vocabolario. Nel caso anche semplice di misura di distorsione come il m.s.e., sono necessarie almeno k somme e k prodotti per ogni vettore e quindi per QV con lunghezze di vettori superiori a 20 e dimensioni superiori a 12 ÷ 14 bit la complessità può cominciare ad essere un problema.
La tecnica di ricerca ad albero si basa sulla costruzione di un vocabolario strutturato ad albero in cui quindi il vettore di ingresso è confrontato con un sottoinsieme di codeword e quella a distorsione minima individua la strada da percorrere all'intemo dell’albero per giungere al vettore rappresentativo che è contenuto nell'ultimo livello dell’albero. Questa procedura è schematizzata in figura 3.8 per un esempio di quantizzatore vettoriale a tre livelli con dimensioni pari a 2 per il primo livello, 4 per il secondo e 2 per il terzo.
Nell’esempio in questione il vettore di ingresso è confrontato con le due parole al primo livello. Si supponga la parola a distorsione minore sia Y1,0,0, questa individua i quattro vettori al livello 2 tra cui calcolare la codeword più rappresentativa. Una volta selezionato il vettore Y1,2,0 al secondo livello, l’ultima ricerca verrà effettuata al terzo livello tra i due vettori Y1,2,1 e Y1,2,2 e nell'ipotesi il vettore a minima distanza sia Y1,2,2, questo costituirà la versione quantizzata del vettore di ingresso. La dimensione massima del vocabolario è in questo esempio di 16 parole (tutte quelle dell’ultimo livello), ma il numero di calcoli di distorsione è ridotto a otto, in contrapposizione ai sedici necessari con una procedura full-search.
Dall'esempio appare anche evidente che, a fronte della riduzione di complessità di calcolo, la struttura ad albero comporta un aumento della quantità di memoria necessaria per memorizzare il vocabolario che in questo caso passa da 16 celle a 26. Si noti tuttavia che tale aumento di capacità di memoria esiste solo al trasmettitore, in quanto al ricevitore è sufficiente memorizzare l’ultimo livello e quindi ancora solo 16 celle.
