Codifica numerica del segnale audio/Capitolo 3

by Daniele Sereno/Pietro Valocchi

3 Codifica di sorgente

../Capitolo 2 ../Capitolo 4 IncludiIntestazione 17 marzo 2021 75% Da definire

Questo testo è completo.

Daniele Sereno, Pietro Valocchi - Codifica numerica del segnale audio (1996)

3 Codifica di sorgente

◄

Capitolo 2

Capitolo 4

►

3

CODIFICA DI SORGENTE

---

3.1 RATE-DISTORTION FUNCTION

La conversione A/D trasforma una sorgente continua in un’equivalente sorgente discreta, a prezzo di una distorsione del segnale. Un’interpretazione di tale processo in termini di entropia associata alla sorgente continua H(x) ed resuscitate del quantizzatore H(y), vede il rumore di quantizzazione come equivocazione H(e) del mappaggio di intervalli del segnale continuo in ingresso al quantizzatore nei valori discreti dell’uscita

$H(y)=H(x)-H(e)$

(3.1)

Trasformata la sorgente da continua in discreta, è poi possibile applicare tecniche di codifica che riducano il numero di bit per campione R ad un valore prossimo a H(y). Si nota come il numero minimo di bit da utilizzare in una codifica di forma d’onda dipenda quindi dal livello di distorsione D: la R(D) è quindi detta rate-distortion function.

Per ottenere dei risultati quantitativi, è necessario esplicitare l’espressione dell’entropia. Nel caso di sorgente continua, ipotizzata senza memoria, essa è pari a

$H(x)=-\int _{-\infty }^{\infty }p(x)log_{2}p(x)dx$

(3.2)

Considerando, per semplicità, un segnale d’ingresso con distribuzione di probabilità gaussiana, l’entropia della sorgente è calcolabile come segue:

$p(x)={\frac {1}{\sqrt {2\pi \sigma _{x}^{2}}}}e^{-{\frac {x^{2}}{2\sigma _{x}^{2}}}}$

$-log_{2}p(x)=-{\frac {ln\ p(x)}{ln\ 2}}={\frac {1}{ln\ 2}}\left(ln{\sqrt {2\pi \sigma _{x}^{2}}}+{\frac {x^{2}}{2\sigma _{x}^{2}}}\right)$

$H(x)={\frac {1}{ln\ 2}}\left(ln{\sqrt {2\pi \sigma _{x}^{2}}}\int _{-\infty }^{\infty }p(x)\ dx+{\frac {1}{2\sigma _{x}^{2}}}\int _{-\infty }^{\infty }p(x)\ x^{2}\ dx\right)$

$={\frac {1}{ln\ 2}}\left(ln{\sqrt {2\pi \sigma _{x}^{2}}}+{\frac {1}{2}}\right)={\frac {1}{ln\ 2}}\left(ln{\sqrt {2\pi \sigma _{x}^{2}}}+ln\ e^{1/2}\right)={\frac {ln{\sqrt {2\pi e\sigma _{x}^{2}}}}{ln\ 2}}$

$H(x)=log_{2}{\sqrt {2\pi e\sigma _{x}^{2}}}$

(3.3)

Tornando alla rate-distortion function, essa può essere descritta come

$R(D)=min[H(y)]=min[H(x)-H(e)]=H(x)-max[H(e)]$

(3.4)

Analizzando il segnale di errore, dato che massimizzarne l’entropia equivale ad associare ad esso una distribuzione gaussiana ed indicando con D = e_q² la sua potenza, si ottiene

$R(D)=log_{2}{\sqrt {2\pi e\sigma _{x}^{2}}}-log_{2}{\sqrt {2\pi eD}}$

$R(D)={\frac {1}{2}}log_{2}{\frac {\sigma _{x}^{2}}{D}}$

(3.5)

Invertendo tale relazione si riottiene il legame già ricavato tra distorsione e numero di bit per campione

$D(R)=2^{2R}\sigma _{x}^{2}$

$10\ log_{10}D=-6R+10\ log_{1}0\sigma _{x}^{2}$

(3.6)

Per segnali a distribuzione non gaussiana, la H(x) è inferiore a quella di segnali gaussiani, per cui l’espressione della R(D) ricavata ne rappresenta un limite superiore. D’altra parte, anche la distribuzione dei segnale d’errore non necessariamente sarà gaussiana, per cui, il calcolo della rate-distortion function come

$R(D)=H(x)-log_{2}{\sqrt {2\pi eD}}$

(3.7)

fornisce, in realtà, il suo limite inferiore.

Passando al caso di sorgenti con memoria, l’entropia della sorgente è inferiore a quella di sorgenti senza memoria, con le relative ripercussioni sulla R(D). Tale aspetto, però, non viene ulteriormente approfondito in quanto, come mostrato nel seguito, nelle codifiche effettivamente implementate la correlazione tra i campioni del segnale viene solitamente eliminata tramite tecniche predittive, per cui l’ipotesi di sorgente discreta senza memoria torna ad essere valida.

3.2 CODIFICA ENTROPICA

Nella quantizzazione uniforme, la codifica dei campioni è a lunghezza fissa e avviene assegnando a ciascuno di essi la rappresentazione binaria dell’indice che li rappresenta tra L possibili valori generabili. Il numero di bit per campione R impiegato in tal modo è fisso e tale che

$|log_{2}L|\leq R<|log_{2}L|+1$

(3.8)

dove il segno di maggioranza è valido nel caso in cui L non sia una potenza di 2. In tal caso le dimensioni di R sono tali da permettere la codifica di un numero di simboli maggiori di quelli effettivamente utilizzati. Tale inefficienza della codifica a lunghezza fissa può essere ridotta considerando la codifica, sempre a lunghezza fissa, di blocchi di N simboli. Il numero di bit per blocco diventa pari a

$N\cdot |log_{2}L|\leq R_{N}<N\cdot |log_{2}L|+1$

(3.9)

e l’inefficienza di codifica, sempre inferiore ad un solo bit, viene in questo caso condivisa tra i simboli che appartengono al blocco, con un numero di bit per simbolo pari a

${\begin{cases}R={\frac {R_{N}}{N}}\\|log_{2}L|\leq R_{N}<|log_{2}L|+{\frac {1}{N}}\end{cases}}$

(3.10)

Ad esempio, considerando una sorgente che emetta cinque simboli, la loro codifica è almeno di 3 bit. Se si considerano gruppi di due simboli, si ha un totale di 25 possibili gruppi, codificabili su 5 bit, con una media di 2.5 bit per simbolo.

Un quantizzatore, però, può essere considerato come una sorgente discreta che, in prima approssimazione, possiamo ipotizzare senza memoria. Fissata la distribuzione di probabilità del segnale in ingresso al quantizzatore e la sua caratteristica, è possibile calcolarne l'entropia come

$H(x)=-\sum _{k=1}^{L}P_{k}\ log_{2}\ P_{k}$

(3.11)

dove P_k rappresenta la probabilità del simbolo k-esimo (appartenente al quanto δk)

$P_{k}=\int _{x\in \delta _{k}}p(x)\ dx$

(3.12)

Se i simboli emessi non risultano equiprobabili, è possibile ridurre il numero medio di bit per simbolo utilizzando una codifica a lunghezza variabile di simboli o blocchi di essi. Questa codifica è tale da assegnare codici di lunghezza inferiore agli elementi emessi con maggiore frequenza dalla sorgente e viceversa. In tal modo si riduce il numero medio di bit per campione, definito come

${\bar {R}}=\sum _{k=1}^{L}P_{k}\ R_{k}$

(3.13)

dove R_k rappresenta la lunghezza della codifica del simbolo k-esimo.

Per meglio comprendere il funzionamento di un codice a lunghezza variabile, è conveniente ricorrere ad una sua rappresentazione grafica (fig. 3.1). In una codifica a lunghezza fissa, le parole di codice possono essere viste come nodi terminali di un albero binario completo di ordine R. In una codifica a lunghezza variabile, invece, le parole di codice possono essere viste come nodi terminali di un albero sbilanciato, nel quale i percorsi più brevi sono assegnati ai simboli più probabili.

Affinché i simboli siano codificabili e decodificabili istantaneamente ed univocamente, è necessario che nessuna parola di codice sia la parte iniziale di altre parole di codice (condizione del prefisso). Condizione necessaria e sufficiente affinché un codice a lunghezza variabile soddisfi la condizione del prefisso è che (disuguaglianza di Kraft)

$\sum _{k=1}^{L}2^{-R_{k}}\leq 1$

(3.14)

Fig. 3.1 - Rappresentazione grafica di codici a lunghezza fissa e variabile.

Per provare che la disuguaglianza di Kraft è una condizione sufficiente, si consideri il processo di costruzione dell’albero relativo ad una codifica a lunghezza variabile a partire da un albero binario bilanciato di ordine pari alla massima lunghezza di codice (fig. 3.2). Il numero di nodi terminali di tale albero è pari a 2 R_max. È poi possibile costruire un albero sbilanciato corrispondente ad una codifica a lunghezza variabile iniziando ad eliminare uno dei due possibili sotto-alberi relativi al livello 1 (dove il livello 0 è la radice dell’albero). In tal modo si è realizzato un nodo terminale, che corrisponde alla prima parola di codice, eliminandone contemporaneamente altri 2^R_max-R_i dall'albero completo. Continuando tale procedura, la frazione di nodi che vengono eliminati ad ogni passo (rispetto al totale dei nodi terminali) decresce progressivamente. D’altra parte, il codice generato assegnando a ciascuno dei nodi terminali che vengono via via creati una parola di codice soddisfa, per Fig. 3.2 - Costruzione di un albero relativo ad una codifica a lunghezza variabile a partire da un albero bilanciato.

costruzione, la condizione del prefisso. Notando che al livello j-esimo risulta

$\sum _{k=1}^{j}{\frac {2^{R_{MAX}-R_{k}}}{2^{R_{MAX}}}}=\sum _{k=1}^{j}2^{-R_{k}}<\sum _{k=1}^{L}2^{R_{k}}\leq 1$

(3.15)

risulta provato che la condizione è sufficiente. Per provare che la disuguaglianza di Kraft è una condizione necessaria, si osserva che i numeri di nodi eliminati al livello R_MAX è pari a

$\sum _{k=1}^{L}2^{R_{MAX}-R_{k}}\leq 2^{R_{MAX}}$

(3.16)

Dividendo tale relazione per il numero totale di nodi terminali si riottiene

$\sum _{k=1}^{L}2^{-R_{k}}\leq 1$

(3.17)

Esempio: si consideri una sorgente discreta che emetta 4 simboli e se ne consideri una codifica a lunghezza variabile ottenuta secondo il procedimento descritto per la disuguaglianza di Kraft. La codifica risultante è riportata nella seguente tabella:

	x1	x2	x3	x4
codifica	0	10	110	111
Rk	1	2	3	3

Tab. 3.1 - Codifica dei simboli emessi dalla sorgente.

Calcolando la sommatoria presente nella disuguaglianza di Kraft si ottiene

$\sum _{k_{1}}^{4}2^{-R_{k}}=2^{-1}+2^{-2}+2^{-3}+2^{3}=1$

(3.18)

Tornando al problema di determinare il valor medio minimo di bit per campione, il teorema fondamentale della codifica per canali discreti in assenza di rumore (o primo teorema di Shannon) afferma che il minimo teorico di R coincide con il valore dell’entropia H(x) della sorgente. Considerando il caso di codifica di simboli isolati, è infatti, possibile dimostrare che

$H(x)\leq {\bar {R}}<H(x)+1$

(3.19)

Nella dimostrazione di tale teorema, è utile considerare separatamente i limiti inferiori e superiori

${\begin{cases}H(x)\leq {\bar {R}}\\{\bar {R}}<H(x)+1\end{cases}}$

(3.20)

Per il limite inferiore, che può essere riscritto come H(x) — R < 0, si ha

$H(x)-{\bar {R}}=\sum _{k=1}^{L}P_{k}log_{2}{\frac {1}{P_{k}}}-\sum _{k=1}^{L}P_{k}R_{k}=\sum _{k=1}^{L}P_{k}log_{2}{\frac {2^{-R_{k}}}{P_{k}}}$

(3.21)

Sfruttando la relazione

$lnx\leq x-1$

(3.22)

si ottiene

$H(x)-{\bar {R}}\leq log_{2}(e)\sum _{k=1}^{L}P_{k}\left({\frac {2^{-R_{k}}}{P_{k}}}-1\right)=log_{2}(e)\sum _{k=1}^{L}\left(2^{-R_{k}}-{\frac {1}{P_{k}}}\right)$

(3.23)

Essendo, ovviamente, P k < 1

$log_{2}(e)\sum _{k=1}^{L}\left(2^{-R_{k}}-{\frac {1}{P_{k}}}\right)\leq log_{2}(e)\left(\sum _{k=1}^{L}2^{-R_{k}}-1\right)$

(3.24)

Riconoscendo, poi, nella sommatoria che appare nell'ultima equazione il primo membro della disuguaglianza di Kraft, rimane provato che

$H(x)-{\bar {R}}\leq 0$

(3.25)

Per la dimostrazione del del limite superiore, è necessario esplicitare il tipo di codifica adottata. Nel caso di codifiche a lunghezza variabile univocamente ed istantaneamente decodificabili, la scelta degli interi R_k può essere fatta in modo tale che

$2^{-R_{k}}\leq P_{k}<2^{-R_{k}+1}$

(3.26)

In tal modo si ha innanzitutto il vantaggio di legare la lunghezza della codifica alla probabilità del simbolo. Inoltre, tale codifica è valida in quanto, sommando il termine

$2^{-R_{k}}\leq P_{k}$

(3.27)

si riottiene la disuguaglianza di Kraft. D’altra parte, considerando il logaritmo del termine

P_k < 2^{-R_k+1}</math>

(3.28)

si ottiene

$log_{2}P_{k}<R_{k}+1$

$R_{k}<1-log\ P_{k}$

(3.29)

Moltiplicando entrambi i membri di quest’ultima equazione per P_k e sommando si prova il limite superiore del primo teorema di Shannon

${\bar {R}}<H(x)+1$

(3.30)

Passando al caso di codifica a lunghezza variabile di blocchi di simboli, l’inefficienza di codifica risulta ulteriormente ridotta in quanto, considerando blocchi di N simboli, risulta

$N\cdot H(x)\geq {\bar {R}}_{N}>N\cdot H(x)+1$

(3.31)

dove ${\bar {R}}_{n}$ è il numero medio di bit per blocco. Per il numero medio di bit per simbolo si ha

${\begin{cases}{\bar {R}}={\frac {{\bar {R}}_{N}}{N}}\\H(x)\geq {\bar {R}}>H(x)+\epsilon \end{cases}}$

(3.32)

dove ε è un numero positivo che può essere reso arbitrariamente piccolo. Ipotizzando di raggiungere un numero medio di bit per campione pari all'entropia della sorgente, il miglioramento che si otterrebbe rispetto all'uscita di un quantizzatore uniforme sarebbe pari a

$\Delta R=log_{2}L-H(x)$

(3.33)

Una codifica a lunghezza variabile notevolmente diffusa è la codifica di Huffman. Tale codifica viene eseguita ordinando i simboli emessi dalla sorgente discreta in una lista secondo le probabilità decrescenti. Innanzitutto si assegnano alla codifica dei due simboli con probabilità inferiore i bit “0” ed “1”. Si considera poi l’unione dei due come un nuovo simbolo con probabilità pari alla somma delle loro probabilità, procedendo al riordino della lista. Si procede quindi all'iterazione di assegnazione di un bit alla codifica dei simboli meno probabili della lista ed al suo riordino fino a che tutti i simboli non abbiano avuto almeno due bit di codice.

Esempio: si consideri una sorgente che emetta otto simboli con la seguente probabilità:

	x1	x2	x3	x4	x5	x6	x7	x8
P	0.40	0.02	0.10	0.04	0.01	0.15	0.03	0.25

Tab. 3.2 - Probabilità dei simboli emessi dalla sorgente.

Se se ne calcola l’entropia si ottiene un valore pari a

$H(x)=-\sum _{k=1}^{L}P_{k}\ log_{2}\ P_{k}$

$=-(0.40\cdot log_{2}0.40+0.02\cdot log_{2}0.02+0.10\cdot log_{2}0.10+0.04\cdot log_{2}0.04$

$+0.01\cdot log_{2}0.01+0.15\cdot log_{2}0.15+0.03\cdot log_{2}0.03+0.25\cdot log_{2}0.25)$

$H(x)=2.29$

(3.34)

La codifica di Huffman degli otto simboli si ottiene tramite le seguenti liste:

x1 P=0.40	x1 P=0.40	x1 P=0.40	x1 P=0.40	x1 P=0.40	x1 P=0.40	x2,3,4,5,6,7,8 P=0.60	x2,3,4,5,6,7,8 P=1.00
x8 P=0.25	x8 P=0.25	x8 P=0.25	x8 P=0.25	x8 P=0.25	x2,3,4,5,6,7 P=0.35	x1 P=0.40
x6 P=0.15	x6 P=0.15	x6 P=0.15	x6 P=0.15	x2,3,4,5,7 P=0.20	x8 P=0.25
x3 P=0.10	x3 P=0.10	x3 P=0.10	x3 P=0.10	x6 P=0.55
x4 P=0.04	x4 P=0.04	x2,5,7 P=0.06	x2,4,5,7 P=0.10
x7 P=0.03	x7 P=0.03	x4 P=0.04
x2 P=0.02	x2,5 P=0.03
x5 P=0.01

Tab. 3.3 - Liste utilizzate nella codifica di Huffman.

Si ottiene la seguente codifica tramite codici a lunghezza variabile:

	x1	x2	x3	x4	x5	x6	x7	x8
codifica	1	0001010	0000	00011	0001011	001	000100	01
Rk	1	7	4	5	7	3	6	2

Tab. 3.4 - Codifica di Huffman.

Se si calcola la lunghezza media della codifica per simbolo

${\bar {R}}=\sum _{k=1}^{L}P_{k}\ R_{k}$

$0.40\cdot 1+0.02\cdot 7+0.10\cdot 4+0.04\cdot 5+0.01\cdot 7+0.15\cdot 3+0.03\cdot 6+0.25\cdot 2$

${\bar {R}}=2.34$

(3.35)

La codifica illustrata, oltre che applicata a singoli simboli emessi dalla sorgente discreta, può essere utilmente applicata anche a blocchi di essi.

Esempio: si consideri una sorgente discreta binaria caratterizzata dalla seguente distribuzione di probabilità di emissione dei due simboli

	x1	x2
P	0.80	0.20

Tab. 3.5 - Probabilità dei simboli emessi dalla sorgente.

L’entropia di tale sorgente è paria a

$H(x)=-\sum _{k=1}^{2}P_{k}\ log_{2}P_{k}=-(0.80\cdot log_{2}0.80+0.20\cdot log_{2}0.20)=0.72$

(3.36)

La codifica dei simboli isolati non può che avvenire che con un bit per simbolo. Se si considera, invece la codifica di Huffman di coppie di bit, si ottengono le seguenti liste

x(1,1) P=0.64	x(1,1) P=0.64	x(1,1) P=0.64	x(1,1)(1,2)(2,1)(2,2) P=1.00
x(1,2) P=0.16	x(2,1)(2,2) P=0.20	x(1,2)(2,1)(2,2) P=0.36
x(2,1) P=0.16	x(1,2) P=0.16
x(2,2) P=0.04

Tab. 3.6 - Liste utilizzate nella codifica di Huffman.

che portano alla seguente codifica:

	x(1,1)	x(1,2)	x(2,1)	x(2,2)
codifica	0	11	100	101
Rk	1	2	3	3

Tab. 3.7 - Codifica di Huffman.

Il numero medio di bit per coppia di simboli è pari a

${\bar {R}}=\sum _{k=1}^{4}P_{k}\ R_{k}=0.64\cdot 1+0.16\cdot 2+0.16\cdot 3+0.04\cdot 3=1.56$

(3.37)

e quindi un numero medio di bit per simbolo pari a ${\bar {R}}=0.78$

3.3 CODIFICA DI SORGENTE ADATTATIVA

L’efficienza di una codifica di sorgente a lunghezza variabile è legata alla conoscenza a priori della probabilità dei simboli emessi. Nel caso in cui non si abbia tale informazione è necessario adottare algoritmi che estraggano in tempo reale le caratteristiche del flusso numerico emesso (compressione adattativa).

Per comprendere il funzionamento di una compressione adattativa è utile analizzare una ricodifica tramite Huffman di simboli codificati con parole di lunghezza fissa. In tal caso la compressione si ottiene riducendo la lunghezza dei codici più frequentemente emessi dalla sorgente ed aumentando la lunghezza di quelli meno frequenti. Non disponendo della distribuzione della probabilità dei simboli, si può mantenere fissa la lunghezza delle parole di codice, ma associando ed esse blocchi di simboli di dimensione crescente in funzione della loro frequenza di emissione. In il numero medio di bit per simbolo, quindi, si riduce tanto più quanto maggiore è la possibilità di avere ripetizioni di lunghe sequenze di simboli.

Un algoritmo di compressione adattativa particolarmente diffuso è l’algoritmo di Ziv-Lemplel (LZ). Essendosi diffuso per applicazioni essenzialmente legate alla compressione di informazioni su memoria di massa, in tale algoritmo le sequenze a lunghezza variabile di simboli vengono dette “stringhe” e la dimensione dei codici, legata alla lunghezza delle parole nei sistemi di elaborazione, sono tipicamente a 12 o 16 bit.

Tale algoritmo si basa sulla realizzazione di una tabella di conversione, inizializzata per contenere, come stringhe iniziali, tutti i simboli generabili dalla sorgente (es.: tutti i possibili caratteri ASCII per un file di testo), presi singolarmente. Tale algoritmo di compressione si basa sulla proprietà per la quale ciascuna stringa presente nella tabella ha un prefisso “w” ottenuto eliminando il simbolo terminale “K” (estensione), anch'esso nella tabella.

Durante la compressione, vengono costruite stringhe di dimensioni crescenti ordinando sequenzialmente i simboli in ingresso (fig. 3.3). Contemporaneamente si controlla che la stringa w che si viene via via formando sia compresa in tabella, nel qual caso tale procedura continua. Nel momento in cui, ricevendo il simbolo K, la stringa wK non risulta presente nella tabella, si eseguono i seguenti passi:

• viene emesso il codice relativo alla stringa w, che rappresenta la più lunga delle stringhe già tabellate contenuta nella stringa da codificare;
• la stringa wK viene inserita nella tabella, assegnando ad essa un nuovo codice;
• K diventa il simbolo iniziale di una nuova stringa.

Analizzando le prestazioni di tale algoritmo, si nota come nella fase iniziale viene eseguita, in realtà, un’espansione del flusso (dato che singoli simboli vengono codificati in codici di dimensioni maggiori). Successivamente, però, ciascun codice emesso sarà via via relativo a stringhe di dimensioni crescenti, con un’efficienza che aumenta man mano che il processo di compressione procede. Fig. 3.3 - Algoritmo di Ziv-Lempel applicato ad una sequenza di tre simboli base.

Per la decodifica ciascun codice viene progressivamente scomposto nelle due componenti prefisso ed estensione. Tale scomposizione procede ricorsivamente fino a che il prefisso non rappresenti un simbolo isolato. Il simbolo finale di tale espansione viene utilizzato per aggiornate la tabella di decompressione, assegnando un nuovo codice alla stringa ottenuta dalla giustapposizione di tale simbolo alla stringa precedentemente ricevuta. Trascurando il problema di avere in ricezione simboli ordinati inversamente rispetto alla trasmissione (risolvibile tramite una struttura LIFO), l’algoritmo di decompressione presentato fallisce qualora la stringa d’ingresso contenga la sequenza KwKwK, dove Kw appare già nella tabella di compressione. Il compressore, infatti, individuata la stringa Kw, invia il codice relativo ed aggiunge la stringa KwK alla sua tabella; successivamente, individuata la stringa KwK, utilizzerà il codice appena inserito. Tale codice risulta indefinito al decompressore, che risulta in attesa dell’estensione K alla stringa precedente. Per evitare tale inconveniente, ogni volta che in fase di decodifica ci si trova di fronte ad un codice non definito, si deve ipotizzare che tale codice sia un’estensione della stringa precedente, utilizzando come il primo simbolo da emettere l’estensione della stringa stessa.

Dal punto di vista implementativo, risulta conveniente memorizzare le stringhe d’ingresso come coppie di un codice (relativo al prefisso w della stringa corrente) ed un simbolo (relativo all'estensione k). Ciò permette l’accesso in tabella tramite codici di dimensioni fisse, potendo quindi adottare tecniche di hashing.

L’LZ ha molti vantaggi rispetto ad algoritmi che permettono livelli di compressione paragonabili. Innanzitutto non è legato all'eliminazione della ridondanza di un particolare tipo di sorgente; inoltre, la semplicità dell’implementazione ne permette l’impiego run-time. Come ulteriore punto a favore di tale algoritmo, si ha che esso non introduce degradazione del segnale, e quindi è utilizzabile per la compressione di dati numerici. Tra gli svantaggi si hanno:

• l’indeterminatezza delle dimensioni del flusso compresso (e quindi delle dimensioni della memoria di massa destinato a contenerlo o della banda necessario per trasmetterlo;
• la propagazione di errori di trasmissione;
• l’inefficienza della compressione per piccoli blocchi di dati;
• la perdita di efficienza per blocchi di grandi dimensioni contenenti dati eterogenei (dovuta all'omogeneizzazione della probabilità dei simboli).

Il fattore di compressione ottenibile con I’LZ è, ovviamente, funzione del livello di strutturazione del flusso in ingresso. Tale rapporto, che per testi alfanumerici o dati formattati supera il 100%, è normalmente prossimo al 65%.

3.4 QUANTIZZAZIONE VETTORIALE

Un risultato della codifica di sorgente è che è possibile ridurre l’inefficienza di codifica codificando blocchi di simboli piuttosto che simboli isolati. Questo approccio può essere seguito anche per quanto riguarda la quantizzazione. La quantizzazione uniforme precedentemente descritta prevede la codifica di campioni isolati del segnale, per cui viene anche indicata come quantizzazione scalare. La quantizzazione vettoriale, invece, prevede la codifica di segmenti di forma d’onda o, più in generale di insiemi di campioni o parametri, organizzati in un vettore.

Il processo di quantizzazione vettoriale può essere visto pertanto come l’associazione ad un vettore di ingresso X di un vettore riproduzione Y(i) scelto da un insieme finito di elementi che prende il nome di vocabolario o codebook.

La codifica si traduce quindi nell'emissione di un indice i associato al vettore Y(i) e rappresentativo del vettore di ingresso X. L’operazione di decodifica è duale e consiste semplicemente nell'indirizzamento di una tabella e la conseguente emissione del vettore indirizzato da i, il quale rappresenta la versione quantizzata del vettore di ingresso. Tali operazioni sono schematizzate in figura 3.4.

L’idea della Quantizzazione Vettoriale (QV) trae la sua origine dalla formulazione matematica di Shannon [Dha71] in cui un sistema di compressione di dati è modellato come un codice a blocco di sorgente, e dove i vari blocchi contigui e non sovrapposti sono trasformati in corrispondenti blocchi di simboli di canale. Tali codici di sorgente possono essere pensati come il risultato di una quantizzazione. vettoriale (o multi-dimensionale), che comprende come caso particolare e sub-ottimo la quantizzazione scalare, in cui la lunghezza del vettore collassa ad uno.

Nonostante l'intrinseca superiorità della quantizzazione vettoriale rispetto a quella scalare in termini di efficienza di codifica, solo pochi lavori di ricerca sono apparsi in letteratura prima del 1979. Il motivo principale di tale apparente contraddizione risiedeva nella mancanza di uno strumento efficiente per la costruzione del vocabolario (o codebook).

Nel 1980 tre ricercatori americani: Linde, Buzo e Gray [Lin80], hanno proposto un algoritmo per la generazione del vocabolario il quale consente il progetto di quantizzatori vettoriali localmente ottimi con lunghezza del blocco, dimensione del vocabolario e misura di distorsione del tutto arbitrarie. Tale Fig. 3.4 - Schematizzazione delle procedure di quantizzazione vettoriale (codifica) e quantizzazione inversa (decodifica).

algoritmo ha preso successivamente il nome di algoritmo LBG, dalle iniziali dei tre ricercatori, ed ha determinato lo sviluppo di diversi lavori di ricerca nel settore, come pure F applicazione della tecnica della quantizzazione vettoriale a vari schemi di codifica. In particolare la QV, tramite l’impiego di una particolare misura di distorsione, ha contribuito alla formulazione della tecnica di codifica CELP che sarà trattata diffusamente in un capitolo successivo.

Un quantizzatore vettoriale è un codificatore di sorgente caratterizzato da quattro elementi principali descritti nel seguito.

• Una sorgente discreta di vettori ( X } appartenenti ad uno spazio reale a k-dimensioni R^k e cioè:

$X=[x1,x2,\ldots ,x_{k}]^{T}\in R^{k}$

(3.38)

In pratica tali vettori possono costituire segmenti successivi del segnale vocale campionato, raccolti in vettori di lunghezza k, ma possono anche essere rappresentativi di insiemi di coefficienti di predizione, o vettori di moduli di FFT ecc.

• Un insieme finito di vettori di riproduzione detto vocabolario (o codebook):

$C=\{Y(i)\supset i=l,2,\ldots ,N\}$

(3.39)

in cui ogni vettore

$Y(i)=\left[y_{1}(i),y_{2}(i),\ldots ,y_{k}(i)\right]^{T}\in R^{k}$

(3.40)

Ne consegue che il vocabolario di riproduzione sarà una matrice di N x k elementi.

• Una misura di distorsione d(X, Y(i)), anche detta misura di distanza, tra il generico vettore della sorgente X e la generica parola del vocabolario (codeword) Y(i). Una misura di distorsione tra le più utilizzate è Terrore quadratico medio (mean squared error):

$m.s.e.={\frac {1}{k}}\sum _{j=1}^{k}\left(Y_{j}(i)-X_{j}\right)^{2}$

(3.41)

• Una regola di quantizzazione q(.) che mappa lo spazio dei reali a k dimensioni nel vocabolario

$q:R^{k}\to C$

(3.42)

La regola di quantizzazione universalmente utilizzata è quella della minima distorsione, e cioè:

$q(X)=Y(i)\Leftrightarrow d(X,Y(i))\leq d(X,Y(j))\supset j\neq i$

(3.43)

Come conseguenza diretta della introduzione della regola di quantizzazione, è possibile definire una partizione S dello spazio di ingresso come suddivisione dello spazio in sottoinsiemi (cluster) ognuno dei quali contiene tutti i vettori di ingresso associati con la regola di quantizzazione q alla stessa parola del vocabolario Y (i). In formule:

$S=\cup _{i}s_{i}\ con\ s_{i}=\{X|q(X)=Y(i)\}\supset i=1,2,\ldots ,N$

(3.44)

I parametri che definiscono le prestazioni di un quantizzatore vettoriale sono la distorsione media ed il rapporto di compressione che si suole esprimere in termini di velocità di trasmissione.

La distorsione media caratteristica di un quantizzatore vettoriale è un indicatore della fedeltà con cui i vettori dello spazio sorgente sono riprodotti ed è funzione della partizione S e del vocabolario di riproduzione C. In generale, la distorsione media può essere espressa come media di insieme dalla formula D(S, C) = E[d(X, q(X))] dove E indica l’operatore di media di insieme e considerando che la partizione S è composta da N elementi disgiunti sì si ottiene:

$D(S,C)=\sum _{i=1}^{N}p(X\in s_{i})E\left[d(X,Y(i)|X\in s_{i}\right]$

(3.45)

in cui p(X e sì) rappresenta la probabilità discreta che X appartenga al cluster sì. Questa formulazione presuppone una conoscenza statistica della sorgente che spesso non è disponibile. Nei casi pratici si approssima la funzione densità di probabilità con d.d.p. note. Inoltre se il processo vettoriale costituito dalla successione dei vettori X(n) nel tempo è stazionario ed ergodico, la media di insieme può essere sostituita dalla media nel tempo a lungo termine, e quindi la relazione della distorsione media diventa:

$D(S,C)=\lim _{M\to \infty }{\frac {1}{M}}\sum _{i=1}^{N}d(X(n),q(X(n)))$

(3.46)

Quest’ultima formulazione è di gran lunga la più utilizzata ed in pratica vengono considerate per il progetto sequenze di addestramento (training) in cui M è sufficientemente grande e per le quali lo spazio sorgente è considerato rappresentativo della situazione operativa in cui il quantizzatore si troverà ad operare.

La velocità di trasmissione rappresenta il numero di bit necessari a trasferire l’informazione relativa all'indirizzo della parola di codice, quindi dipende dalle dimensioni del vocabolario, e vale:

$R=\lceil log_{2}N\rceil \ bit/vettore$

(3.47)

È evidente quindi che per sfruttare al meglio la velocità di trasmissione, i vocabolari utilizzati avranno una dimensione potenza di due. Se si vuole tenere conto anche della lunghezza del vettore si introduce la velocità espressa in bit/campione come:

$r={\frac {1}{k}}R={\frac {1}{k}}\lceil log_{2}N\rceil \ bit/campione$

(3.48)

Quest’ultima relazione mette bene in evidenza la caratteristica dei quantizzatori vettoriali di consentire la codifica di segnali a velocità anche di frazioni di campioni al secondo. Questa caratteristica è molto utile nei sistemi di codifica a bassissima velocità o in quei sistemi in cui si vuole suddividere la velocità disponibile tra diversi segnali da codificare in modo ottimale.

Questi elementi sono sufficienti per implementare in modo semplice un algoritmo di quantizzazione vettoriale che nella sua realizzazione più diretta è un algoritmo di calcolo esaustivo della distorsione tra il vettore di ingresso da codificare e tutti quelli raccolti nel codebook. Il vettore del codebook a distorsione minima rappresenta la versione quantizzata del vettore di ingresso e l’indice che lo identifica rappresenta l’informazione da trasmettere al ricevitore.

Si noti infine che il vocabolario, pur essendo una matrice di valori reali, può essere memorizzato in virgola mobile, qualora la dinamica dei singoli elementi lo renda necessario, ma molto più spesso è rappresentato in memoria in aritmetica finita utilizzando un numero sufficiente di bit (tipicamente 16 bit). Questo ulteriore passo di quantizzazione può essere comunque completamente separato dal processo di quantizzazione vettoriale, nell'ipotesi in cui la distorsione introdotta sia trascurabile nei confronti di quella introdotta dal processo di QV.

3.4.1 Algoritmo LBG di generazione del vocabolario

Il problema principale nell'impiego della quantizzazione vettoriale consiste nel progetto del vocabolario, progetto che deve essere ottimo in relazione al criterio di minima distorsione. L’algoritmo LBG fornisce uno strumento efficace per la generazione di tale vocabolario.

Al fine di illustrare l’algoritmo, è necessario introdurre due criteri di ottimalità che fanno riferimento a due condizioni specifiche. L’algoritmo LBG utilizza tali criteri in un processo iterativo costruendo un vocabolario di volta in volta migliore dal punto di vista delle prestazioni. 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.

• Passo 1 - Dato un vocabolario iniziale Co di dimensione N e con vettori di lunghezza k, una soglia di distorsione e > 0 piccola a piacere, una funzione di distribuzione statistica della sorgente (o alternativamente una sequenza di addestramento sufficientemente lunga), si inizializza l’algoritmo con m= 0 (indice delle iterazioni) e D-i = °° (distorsione media alla iterazione 1 ).
• Passo 2 - Dato il vocabolario corrente Cm = (Y(i); i = 1,2.N), si applica il primo criterio di ottimalità calcolando la partizione ottima Pm(Cm) = {pi; i= 1, 2,.... N}. Si calcola quindi la distorsione media D m = D(Pm(C m ), C m ) associata alla partizione ottima P m ed al vocabolario corrente Cm.
• Passo 3 - Qualora la distorsione media sia diminuita percentualmente di una quantità inferiore ad e nel passare dall'iterazione m -1 all'iterazione m e cioè in formule se

${\frac {D_{m-1}-D_{m}}{D_{m}}}\leq \epsilon$

(3.52)

l’algoritmo termina con C m vocabolario finale, altrimenti l’algoritmo continua con il passo 4.

• Passo 4 - Data la partizione ottima P m calcolata al passo 2, si applica il secondo criterio di ottimalità calcolando il nuovo vocabolario Cm+l = { Y(sj); i = 1, 2,N} come collezione dei centroidi di ogni cluster pi. Si incrementa m e si ritorna al passo 2.

Il valore della distorsione media può essere calcolato come media di insieme, qualora si disponga della funzione di distribuzione statistica del segnale sorgente, o come media nel tempo qualora si disponga di una sequenza di addestramento sufficientemente lunga. Dalle due condizioni di ottimalità prima descritte, si evince che D m < D m -1 e quindi l’algoritmo converge ad un valore minimo seppur con un numero di iterazioni che può essere infinito. Linde, Buzo e Gray hanno dimostrato [Lin80] che il loro algoritmo tende a produrre un quantizzatore ottimo, se questo esiste, attraverso un metodo di successive approssimazioni, pertanto se l’algoritmo termina con un valore di e = 0 in un numero finito di iterazioni, tale quantizzatore limite risulta determinato. In realtà, a causa delle inevitabili approssimazioni introdotte (ad esempio considerando una sequenza di training finita), i quantizzatori vettoriali prodotti con questo metodo sono solo localmente ottimi. Tuttavia le prestazioni sono di gran lunga superiori a quelle ottenibili con quantizzatori scalari e consentono pertanto rapporti di compressione più alti.

A titolo di esempio, la figura 3.5a visualizzala procedura di generazione di un vocabolario tramite l’impiego dell’algoritmo LBG. L’esempio si riferisce ad un vocabolario di quattro parole con vettori di dimensione K=2 campioni che consentono una semplice rappresentazione grafica. La figura mostra l’insieme dei 4000 vettori che costituiscono la sequenza di addestramento, in questo caso relativa a campioni distribuiti uniformemente. I quattro punti in basso a destra rappresentano le parole iniziali del codebook, mentre gli asterischi indicano il codebook finale. Sono inoltre rappresentate le traiettorie degli spostamenti delle quattro parole all'aumentare delle iterazioni. L’andamento della distorsione nel passare dal codebook iniziale al codebook finale è riportato in figura 3.5b.

Le prestazioni, in termini di SNR e relative a QV con dimensioni e lunghezze dei vettori diverse, sono riportate in figura 3.6. Le prestazioni sono relative ad una sequenza di test diversa da quella utilizzata per l’addestramento e pertanto i risultati sono generalizzabili. In particolare in figura 3.6a sono riportate le prestazioni al variare della dimensione del vocabolario per lunghezze del vettore da 2 a 10. La lunghezza di addestramento era in questo caso costituita da circa 400.000 vettori di voce campionata a 8 kHz e relativa a 12 parlatori di tre lingue diverse. Si nota come le prestazioni crescano circa linearmente, in dB, con la dimensione. La figura 3.6b riporta i valori del grafico precedente parametrizzati rispetto alla velocità espressa in bit/campione. In questo caso appare evidente come vettori più lunghi consentano prestazioni migliori. In particolare si può osservare che circa le stesse prestazioni (10 dB) sono ottenibili con r=2 bit/campione e K=2 oppure con r=l bit/campione e K=8 e cioè a velocità metà.

Resta infine da evidenziare che il calcolo dei centroidi dei singoli cluster è una operazione strettamente legata alla particolare misura di distorsione impiegata. Infatti esistono misure di distorsione per le quali il calcolo del centroide è particolarmente complesso o addirittura non definito. Nel caso specifico dell’errore quadratico medio, il centroide è semplicemente calcolato come media aritmetica dei vettori appartenenti al cluster:

${\bar {Y}}(s_{i})=|s_{i}|^{-1}\sum _{X\in s_{i}}X$

(3.53)

3.4.2 Sequenza di addestramento

Come è stato già evidenziato, l’algoritmo LBG è solitamente usato impiegando una lunga sequenza di addestramento che consente di prescindere dalla conoscenza delle caratteristiche statistiche della sorgente. È evidente che tale sequenza di addestramento deve essere rappresentativa dello spazio sorgente, in caso contrario il quantizzatore vettoriale risulta subottimo e con prestazioni che sono molto variabili al variare del segnale in ingresso.

Una misura della significatività della sequenza di addestramento, consiste nella valutazione delle prestazioni dì un quantizzatore vettoriale nei due casi distinti ottenuti considerando sequenze di test che fanno parte della sequenza di addestramento (inside) e sequenze che non sono state utilizzate per il progetto (outside). La sequenza sarà tanto più rappresentativa tanto minore è la differenza di prestazioni nei due casi inside e outside.

Il parametro che maggiormente influenza tale differenza di prestazioni è la lunghezza M della sequenza di addestramento, e cioè il numero di vettori considerati. Un esempio della differenza di prestazioni ottenibile, espresso in termini di SNR, è illustrato in figura 3.7, dove si vede come tale differenza diminuisca all'aumentare della lunghezza della sequenza.

In particolare nell'esempio specifico, relativo ad una VQ con k=8 campioni, si può notare che le prestazioni outside tendono a stabilizzarsi quando si sono usati più di 25000 vettori. Tenendo in conto che in questo caso la dimensione del QV è di 256 vettori, ne risulta che in media occorrono almeno 100 vettori per ogni singola codeword del vocabolario. Questa considerazione, relativa ad un esempio specifico, è tuttavia generalizzabile e solitamente si assume di avere a disposizione una sequenza di addestramento che contenga almeno 1000 vettori per codeword. Sempre facendo riferimento all'esempio di figura 3.7, considerando che la lunghezza del vettore è di 8 campioni, per un vocabolario di 4096 parole (R=12 bit/vettore o r=1.5 bit/campione) occorreranno circa 70 minuti di segnale vocale per progettare un QV con prestazioni Fig. 3.5a - Procedura di generazione di vocabolario tramite LBG.

Fig. 3.5b - Esemplificazione della procedura di generazione di un vocabolario con k=2 e R=2. adeguate. Vale la pena ancora sottolineare come le prestazioni valutate con sequenze che appartengono alla sequenza di addestramento siano decisamente fuorviami in quanto, anche per sequenze di addestramento molto lunghe, risultano superiori a quelle effettive.

Un secondo elemento di importanza al fine delle prestazioni è costituito dalla necessità di considerare nella sequenza di addestramento segnali che siano rappresentativi delle condizioni in cui il QV opererà e quindi si dovrà tenere opportunamente in conto di diversi tipi di parlatori, diverse lingue, ecc. Nel caso poi di QV che devono operare su segnali preprocessati (come vettori relativi a set di coefficienti di filtri LPC, oppure insieme di moduli di una DFT), tutte le operazioni di preprocessamento che sono utilizzate nello schema di codifica, devono essere anche considerate per generare la sequenza di addestramento. Ne consegue che nel caso di schemi di codifica molto complessi, in cui il QV è inserito all'interno di un sistema in catena chiusa con delle possibili controreazioni, la sequenza di addestramento potrà dipendere dalla procedura di quantizzazione vettoriale stessa, e di conseguenza anche la generazione della sequenza di addestramento e la conseguente generazione del QV, dovranno essere condotte con procedure iterative, per approssimazioni successive.

3.4.3 Procedura di sdoppiamento

L’algoritmo LBG assume come condizione iniziale, oltre alla sequenza di addestramento, la conoscenza di un vocabolario di partenza C 0. Tale condizione iniziale influisce in una certa misura sulla bontà del quantizzatore vettoriale prodotto dall'algoritmo stesso. Si può infatti intuire che se la funzione di costo associata alla generazione del vocabolario è una funzione complessa con molti minimi locali, il punto di partenza determina la zona nell'intorno della quale l’algoritmo troverà il minimo.

Inoltre una scelta errata del vocabolario di partenza può determinare malfunzionamenti dell’algoritmo LBG come l’occorrenza di celle vuote. Questo fenomeno si presenta in quei casi in cui nella determinazione della partizione ottima dello spazio sorgente (primo criterio di ottimalità), per certe codeword non esistono vettori dello spazio sorgente associabili tramite il criterio della minima distorsione. Questo fenomeno in realtà è considerato problematico anche in quei casi in cui il numero di vettori di ingresso associati ad una codeword sia particolarmente esiguo (meno del 5 % del valore medio Fig. 3.6 - Andamento del rapporto segnale su rumore (SNR): (a) al crescere della dimensione del vocabolario N e per diverse lunghezze del vettore k, (b) al crescere della lunghezza del vettore e per diverse velocità r in bit/campione. delle altre codeword). Si intuisce come un vocabolario in cui alcune parole siano rappresentative di una porzione molto ristretta dello spazio sorgente abbia prestazioni medie subottime. Per completezza va detto che questo fenomeno può anche essere indicativo di una sequenza di addestramento troppo corta, sicuramente non tale da consentire le stesse prestazioni inside ed outside.

La tecnica più utilizzata per ovviare a questo problema è quella dello sdoppiamento o splitting procedure che riduce la ricerca del vocabolario iniziale alla determinazione di una sola codeword di partenza. Questo corrisponde a considerare un vocabolario iniziale con una sola parola e tale parola può quindi coincidere con il centroide della intera sequenza di addestramento.

La procedura di generazione di un vocabolario di dimensione IV avviene quindi tramite i seguenti passi:

• Passo 1 - Si calcola il centroide dell’intera sequenza di addestramento Y_c e si produce un vocabolario iniziale di n=2 parole moltiplicando il centroide per due vettori di perturbazione η₁ e η₂:

$C_{0}^{\{n\}}=\left\{Y_{c}\cdot \eta _{1}\right\}\cup \left\{Y_{c}\cdot \eta _{2}\right\}$

(3.54)

• Passo 2 - Si calcola il vocabolario ottimo C_m^{n} relativo alla dimensione n utilizzando l’algoritmo LBG prima descritto
• Passo 3 - Se la dimensione n è quella voluta, il vocabolario finale è prodotto, altrimenti si raddoppia la dimensione del vocabolario utilizzando la splitting procedure:

$C_{0}^{\{n\cdot 2\}}=\left\{C_{0}^{\{n\}}(\eta _{1})\right\}\cup \left\{C_{0}^{\{n\}}(\eta _{2})\right\}$

(3.55)

in cui i due semivocabolari sono ottenuti moltiplicando ogni singola codeword del vocabolario ottimo di dimensione n per i vettori di perturbazione η₁ e η₂ rispettivamente. Quindi si raddoppia il valore di n e si ritorna al passo 2.

La procedura appena descritta si presta molto bene al progetto di quantizzatori vettoriali con dimensioni potenza di 2, che rappresentano tuttavia la quasi totalità dei casi per gli evidenti vantaggi in termini di efficienza di trasmissione.

La scelta dei valori da utilizzare per i vettori di perturbazione η₁ e η₂ dipende dalla particolare sorgente, ma in generale non è molto critica e solitamente questi hanno valori nell'intervallo 0.01 0.1. Inoltre al fine di garantire una diminuzione della distorsione media nel passare da una dimensione alla dimensione doppia, si pone uno dei due vettori di perturbazione pari al vettore unitario. Questo garantisce che il vocabolario a dimensione doppia contenga una replica del vocabolario ottimo calcolato al passo precedente, più una sua versione modificata.

Sebbene la procedura di sdoppiamento costituisca uno strumento efficace per risolvere il problema delle celle vuote (o sottopopolate), in alcuni casi particolari il problema può persistere ed in questi casi si suole inserire nell'algoritmo di progetto un ulteriore passo di controllo in cui viene valutato il numero di vettori presenti in ogni cluster. Qualora per qualche cella questo sia minore di una certa soglia percentuale, si introduce uno sdoppiamento di quelle celle che maggiormente contribuiscono alla distorsione media.

Fig. 3.7 - Andamento della distorsione media tra sequenze inside e outside alla sequenza di training, all'aumentare della lunghezza della sequenza di addestramento.

3.4.4 Struttura dei quantizzatori vettoriali

Nella presentazione della tecnica di quantizzazione vettoriale cosi pure come nella descrizione dell’algoritmo LBG, abbiamo fino ad ora ipotizzato che il processo di quantizzazione avvenga confrontando il vettore di ingresso con tutti i 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 Y_1,0,0, questa individua i quattro vettori al livello 2 tra cui calcolare la codeword più rappresentativa. Una volta selezionato il vettore Y_1,2,0 al secondo livello, l’ultima ricerca verrà effettuata al terzo livello tra i due vettori Y_1,2,1 e Y_1,2,2 e nell'ipotesi il vettore a minima distanza sia Y_1,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. Fig. 3.8 - Struttura di un quantizzatore vettoriale ad albero a tre livelli. 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. Fig. 3.9 - Confronto di prestazioni tra struttura full-search e binary-search. La velocità è di 1 bit/campione e quindi la lunghezza del vettore k coincide con la dimensione del codebook R.

Relativamente alle prestazioni, tutte le strutture di ricerca semplificate comportano una, seppur contenuta, degradazione rispetto al caso di ricerca esaustiva. A titolo esemplificativo la figura 3.9 riporta le prestazioni ottenibili, a parità di velocità di trasmissione, utilizzando una struttura full-search ed una struttura tree-search. L’esempio si riferisce ad uno spazio sorgente costituito da vettori di segnale vocale campionato ad 8 kHz

Si è visto quindi che le strutture ad albero consentono una riduzione della complessità di calcolo a scapito di un aumento della capacità di memoria. Le strutture cosiddette multistadio consentono invece un risparmio anche della capacità di memoria.

Il principio su cui si basano queste strutture è quello di operare una seconda QV sul segnale errore di quantizzazione prodotto da un primo QV. Questa struttura è rappresentata in figura 3.10.

In generale i due QV avranno dimensioni N1 ed N2. Ipotizzando siano strutturati entrambi in full-search ed abbiano vettori della stessa lunghezza k, la quantità di memoria necessaria sarà di mem = (N1 + N2) vettori reali e questo coincide anche con il numero di calcoli di distorsione necessari calc = (N1 + N 2). La velocità complessiva sarà data da R = R1 + R2 = log₂N₁ + log₂N₂.

Un QV a singolo stadio a pari velocità di trasmissione, anch'esso con struttura full-search, avrà velocità pari a R = R₁ + R₂ e quindi un numero di Fig. 3.10 - Struttura di un quantizzatore vettoriale multistrato a due stadi.

parole nel vocabolario pari a N = 2^R = 2^R₁ • 2^R₂ = N₁ • N₂. La memoria necessaria ed il numero di operazioni quindi in questo caso saranno pari a N₁ • N₂. Ne consegue che il fattore di risparmio γ, nell'utilizzare una struttura multi- stadio, vale:

$\gamma ={\frac {N_{1}\cdot \mathbb {N} _{2}}{N_{1}+\mathbb {N} _{2}}}$

(3.57)

Questo risparmio può essere consistente e per QV di grande dimensione si possono considerare anche più stadi in cascata. Anche in questo caso a fronte di significativi vantaggi computazionali si ha una degradazione delle prestazioni. Un confronto di prestazioni è fornito in figura 3.11. Nel caso multiple stage sono stati considerati due stadi con uguale dimensione.

Fig. 3.11 - Confronto di prestazioni tra struttura a singolo stadio e struttura a due stadi. La velocità è di l bit/campione e quindi la lunghezza del vettore k coincide con la dimensione del code book R.