Codifica della voce e dell'audio/Tecniche PCM

Template:Codifica della voce e dell'audio Le tecniche di quantizzazione Template:Tooltip si basano su:

• codifica campione-per-campione: lavorano su un campione alla volta, e per ogni campione $x[n]$ in ingresso producono un campione quantizzato $\hat{x}[n]$ in uscita;
• codifica di forma d'onda: l'obiettivo è produrre una forma d'onda geometricamente simile all'originale → la forma d'onda risultante sarà anche percettivamente simile.

Le tecniche PCM per la codifica della voce in banda telefonica possono essere suddivise in:

• statiche: una volta che l'algoritmo è stato progettato, esso non cambia nel tempo:
  • senza memoria (o stateless): ogni campione è quantizzato indipendentemente dagli altri campioni;
  • differenziali o predittive: la quantizzazione di ogni campione sfrutta anche informazioni dagli altri campioni nel passato e/o nel futuro;
• adattative: l'algoritmo si adatta al segnale corrente stimato.

Caratteristiche delle tecniche PCM

• + robustezza ai segnali di ingresso: poiché l'algoritmo non fa assunzioni sul tipo di segnale, esso continua a funzionare dando buone prestazioni se il tipo di segnale fornito in input non è voce;
• + complessità: è quasi nulla, al massimo pari a 1 MIPS;
• + ritardo: è basso;
• − bit rate: le tecniche PCM non riescono a garantire la toll quality con un bit rate al di sotto di 32 kb/s (4 bit/campione) → è un bit rate medio-alto, e può essere troppo alto per specifiche applicazioni (ad es. telefonia satellitare).

Tecniche PCM senza memoria

Quantizzatore uniforme: PCM lineare

Esempio di quantizzazione uniforme.

Caratteristica ingresso/uscita di un quantizzatore uniforme.

Il quantizzatore uniforme è caratterizzato da una distribuzione dei livelli uniforme: la zona operativa $X_m$ è suddivisa in $2^N-1$ gradini di quantizzazione di ampiezza costante $\mathrm{\Delta }=\frac{X_m}{2^N}$.

La potenza ${\sigma }_e^2$ dell'errore di quantizzazione $e\left[n\right]$, avente una funzione densità di probabilità ${\text{PDF}}_e\left(t\right)$ uniforme, è:

${\sigma }_e^2=\underset{-\frac{\mathrm{\Delta }}{2}}{\overset{+\frac{\mathrm{\Delta }}{2}}{\int }}{e}^2\left(t\right)\cdot {\text{ PDF}}_e\left(t\right)dt=\frac{{\mathrm{\Delta }}^2}{12}$

Il rapporto segnale/rumore SNR è lineare nel numero di bit $6N$:

$\text{SNR}=10{\log }_{10}\frac{{\sigma }_x^2}{{\sigma }_e^2}\text{dB}=K+\alpha \frac{X_m}{{\sigma }_x}+6N$

→ il rapporto segnale/rumore SNR migliora di 6 dB per ogni bit in più utilizzato.

La codifica PCM lineare è basata su un quantizzatore uniforme a 4096 livelli:

• frequenza di campionamento: (imposta dal teorema di Shannon)

  $F_c=8000\text{Hz}=125\mu \text{s}>2\times 3400\text{Hz}$

• numero di bit:

  $N=12\text{bit/campione}\Rightarrow N_Q=2^N=4096\text{livelli}$

• bit rate:

  $R=12\text{bit/campione}\times 8000\text{Hz}=96\text{kb/s}$

Quantizzatore ottimo: PCM logaritmico (log PCM)

Caratteristica ingresso/uscita di un quantizzatore ottimo per la voce.

Il quantizzatore uniforme è un quantizzatore ottimo per segnali distribuiti uniformemente sulla zona operativa, ma i segnali audio naturali hanno una distribuzione di probabilità non uniforme. In particolare, la voce ha una funzione distribuzione di probabilità PDF gaussiana fortemente concentrata intorno al valor medio → a parità di qualità, è possibile risparmiare bit utilizzando un quantizzatore avente una distribuzione dei livelli non uniforme:

• intorno all'intensità media il segnale è più probabile → servono livelli più fitti;
• alle basse e alle alte intensità il segnale è meno probabile → i livelli possono essere più radi.

Poiché l'orecchio umano è sensibile in modo para-logaritmico, il quantizzatore ottimo per la voce ha una distribuzione dei livelli simil-logaritmica:

I livelli del quantizzatore uniforme sono mappati ai livelli del quantizzatore ottimo secondo una distribuzione simil-logaritmica.

• intorno all'intensità media, i livelli del quantizzatore uniforme sono mappati a tanti livelli vicini tra loro del quantizzatore ottimo;
• alle basse e alle alte intensità, i livelli del quantizzatore uniforme sono mappati a pochi livelli lontani tra loro del quantizzatore ottimo.

Standard ITU G.711

Lo standard G.711, sviluppato da Template:Tooltip, usa una codifica PCM logaritmica (log PCM) basata su un quantizzatore ottimo a 256 livelli:

• numero di bit: i livelli di quantizzazione sono in minor numero ma sono meglio distribuiti secondo le caratteristiche del segnale vocale:

  $N=8\text{bit/campione}\Rightarrow N_Q=2^N=256\text{livelli}$

• bit rate: lo standard G.711 raggiunge un bit rate più basso rispetto al PCM lineare pur mantenendone le stesse prestazioni:

  $R=8\text{bit/campione}\times 8000\text{Hz}=64\text{kb/s}$

Applicazioni

• il primo standard per la telefonia digitale, chiamato ISDN

Ulteriori evoluzioni

• telefonia cellulare (GSM, 3G...): il bit rate arriva a 13 kb/s, anche se con la tecnologia di oggi si potrebbe arrivare a circa 6 kb/s;
• applicazioni militari (es. telefoni criptati) e civili (es. telefoni satellitari): il bit rate scende addirittura a 1 kb/s, ma la voce, seppur intelligibile, non è tanto naturale.

Tecniche PCM differenziali o predittive

Le tecniche PCM senza memoria sono adatte per la codifica del rumore bianco: ogni bit vale 0 o 1 con probabilità 50% → dato un qualunque campione, nessun campione nel passato o nel futuro può fornire informazioni sul campione corrente, perché i campioni sono tutti completamente scorrelati tra loro. Nei segnali audio naturali invece esistono molte correlazioni tra un campione e l'altro, che possono essere sfruttate per comprimere di più.

Quantizzatore differenziale: PCM differenziale (DPCM)

L'idea delle tecniche differenziali è quella di codificare e trasmettere non il campione del segnale originario, con tutta la sua ampia dinamica possibile di valori, ma solo la differenza, detta segnale differenziale, tra ogni campione e uno o più dei suoi campioni precedenti.

Se i campioni sono sufficientemente in media correlati tra loro, il segnale differenziale ha una dinamica $X_m$ molto inferiore e una distribuzione gaussiana più stretta (${\sigma }_x\gg {\sigma }_d$) rispetto al segnale originario → servono meno livelli di quantizzazione per raggiungere le stesse prestazioni.

Quantizzatore differenziale del 1º ordine

La differenza $d[n]$ codificata e trasmessa è calcolata tra il campione corrente $x[n]$ e il campione precedente $x[n-1]$:

$d\left[n\right]=x\left[n\right]-x[n-1]$

Il coefficiente di correlazione $\rho$ dice quanto due campioni consecutivi sono correlati tra loro:

$\rho =\frac{E\left[x\left[n\right]x[n-1]\right]}{E\left[x^2[n-1]\right]},0\le \rho \le 1$

• se il campione $x\left[n\right]$ è uguale al campione precedente $x[n-1]$, la correlazione $\rho$ è pari a 1:

  $x\left[n\right]=x[n-1]\Rightarrow \rho =\frac{E\left[x^2[n-1]\right]}{E\left[x^2[n-1]\right]}=1$

• se il campione $x\left[n\right]$ è completamente differente rispetto al campione precedente $x[n-1]$, la correlazione $\rho$ è pari a 0.

Il coefficiente di correlazione $\rho$ è il valore ottimo che minimizza l'energia del segnale differenza $d[n]$:

$\text{min}{\sigma }_d^2\iff d\left[n\right]=x\left[n\right]-\rho x[n-1]$

Il quantizzatore differenziale funziona molto bene con la voce telefonica grazie al fatto che statisticamente è un segnale fortemente correlato:

$\rho \simeq 0,9\Rightarrow d[n]=x[n]-0,9x[n-1]$

Processo di codifica e decodifica

1. il codificatore calcola il segnale differenziale $d[n]$ tra il campione corrente $x[n]$ e il campione precedente $x[n-1]$:

   $d\left[n\right]=x\left[n\right]-\rho x[n-1]$

2. il codificatore invia al decodificatore la versione quantizzata $\hat{d}[n]$ del segnale differenziale;
3. il decodificatore riceve il segnale differenziale quantizzato $\hat{d}[n]$ e ricostruisce il campione corrente $\hat{x}[n]$:

   $\hat{x}[n]=\hat{d}[n]+\rho \hat{x}[n-1]$

Quantizzatore differenziale di ordine N

La differenza $d[n]$ è calcolata tra il campione corrente $x[n]$ e la combinazione lineare degli $N$ campioni precedenti:

$d[n]=x[n]-f(x[n-1],x[n-2],\dots ,x[n-N])=x[n]-\sum _{i=1}^N{\alpha }_{i}x[n-i]$

L'ordine $N$ deve essere scelto dal compromesso tra:

• prestazioni di compressione: più l'ordine è alto, più informazioni da campioni passati vengono prese per il campione corrente;
• prestazioni di calcolo: all'aumentare dell'ordine aumentano:
  • la memoria necessaria per bufferizzare gli $N$ campioni passati;
  • la complessità di calcolo.

Per la voce telefonica, la correlazione di breve termine (= relativa ai campioni adiacenti) è concentrata in media entro 8÷12 campioni → per la codifica della voce in banda telefonica è sufficiente il quantizzatore differenziale di ordine 10: il campione corrente viene codificato prendendo informazioni fino a 10 campioni (equivalenti a 1,2 ms) nel passato.

I valori ottimi dei parametri ${\alpha }_i$ possono essere calcolati risolvendo un sistema di $N$ derivate parziali in modo analogo al caso del 1º ordine:

$\{\begin{array}{c}\frac{\partial {\sigma }_d^2}{\partial {\alpha }_1}=0\\ ⋮\\ \frac{\partial {\sigma }_d^2}{\partial {\alpha }_N}=0\end{array}$

Codifica predittiva: Linear Predictive Coding (LPC)

Un approccio alternativo alla codifica differenziale è la codifica predittiva, che affronta un problema di predizione: data la serie storica dei valori passati, è possibile fare una predizione del campione $x[n]$ a partire dai campioni passati?

L'idea delle tecniche predittive è quella di codificare e trasmettere l'errore di predizione $e[n]$, cioè la differenza tra il valore effettivo del campione corrente $x[n]$ e il valore predetto $\tilde{x}[n]$:

$e[n]=x[n]-\tilde{x}[n]$

• codifica predittiva di ordine 1: la predizione $\tilde{x}[n]$ del campione corrente è basata solo sull'ultimo campione $x[n-1]$:

  $\tilde{x}[n]=f(x[n-1])=\alpha x[n-1]$

  Se $\alpha$ è il coefficiente di correlazione $\rho$ tra il campione predetto $\tilde{x}[n]$ e il campione effettivo $x[n]$, l'errore di predizione $e[n]$ è minimizzato e la codifica è ottima;
• codifica predittiva di ordine N: la predizione $\tilde{x}[n]$ del campione corrente è basata sulla combinazione lineare degli ultimi $N$ campioni:

  $\tilde{x}[n]=f(x[n-1],x[n-2],\dots ,x[n-N])=\sum _{i=1}^N{\alpha }_{i}x[n-i]$

  Se i parametri ${\alpha }_i$ sono i coefficienti di predizione lineare, l'errore di predizione $e[n]$ è minimizzato e la codifica è ottima.

Processo di codifica e decodifica

La codifica predittiva funziona grazie al fatto che, dato che il decodificatore ha a disposizione una serie storica simile a quella a disposizione del codificatore, le predizioni svolte da entrambi indipendentemente l'uno dall'altro saranno simili:

1. il codificatore calcola il valore predetto del campione corrente a partire dagli ultimi $N$ campioni:

   $\tilde{x}[n]=f(x[n-1],x[n-2],\dots ,x[n-N])=$

   • ordine 1:

     $=\rho x[n-1]$

   • ordine N:

     $=\sum _{i=1}^N{\alpha }_{i}x[n-i]$

2. il codificatore calcola l'errore di predizione $e[n]$ confrontando il valore predetto $\tilde{x}[n]$ con il valore effettivo $x[n]$:

   $e[n]=x[n]-\tilde{x}[n]=$

   • ordine 1:

     $=x[n]-\rho x[n-1]$

   • ordine N:

     $=x[n]-\sum _{i=1}^N{\alpha }_{i}x[n-i]$

3. il codificatore invia al decodificatore la versione quantizzata $\hat{e}[n]$ dell'errore di predizione;
4. anche il decodificatore calcola il valore predetto per il campione corrente a partire dagli ultimi $N$ campioni ricostruiti:

   $\tilde{x}[n]=f(\hat{x}[n-1],\hat{x}[n-2],\dots ,\hat{x}[n-N])=$

   • ordine 1:

     $=\rho \hat{x}[n-1]$

   • ordine N:

     $=\sum _{i=1}^N{\alpha }_i\hat{x}[n-i]$

5. il decodificatore riceve l'errore di predizione quantizzato $\hat{e}[n]$ e ricostruisce il campione corrente $\hat{x}[n]$:

   $\hat{x}[n]=\hat{e}[n]+\tilde{x}[n]=$

   • ordine 1:

     $=\hat{e}[n]+\rho \hat{x}[n-1]$

   • ordine N:

     $=\hat{e}[n]+\sum _{i=1}^N{\alpha }_i\hat{x}[n-i]$

Tecniche PCM adattative: adaptive PCM (APCM)

Schema a blocchi dell'algoritmo usato dalle tecniche APCM.

Le tecniche PCM statiche sono progettate in base alle caratteristiche statistiche di lungo termine del segnale (valor medio $\mu$, varianza $\sigma$, funzione PDF...) → sono adatte per segnali stazionari le cui caratteristiche non dipendono dal tempo. I segnali audio naturali tuttavia sono fortemente non stazionari.

L'idea delle tecniche adattative è quella di usare un algoritmo in grado di adattarsi al segnale corrente stimato nel tempo, con l'obiettivo di risparmiare bit quando il segnale è meno complesso da codificare.

Algoritmo

1. stima dello stato del segnale: si determina lo stato del segnale (ad es. rumore o voce) all'interno di una finestra ampia $M$ campioni centrata in $n_0$;
2. scelta dell'algoritmo ottimo: si sceglie quale algoritmo di codifica è il più adatto al segnale corrente stimato entro la finestra corrente.
   L'algoritmo di codifica scelto deve essere mandato direttamente al ricevitore, cosicché il ricevitore sappia in che modo è stato codificato il segnale. I bit necessari per comunicare queste informazioni al ricevitore sono detti bit di overhead perché sono inviati insieme ai campioni quantizzati del segnale e quindi pesano sul bit rate complessivo;
3. codifica di $M$ campioni: si applica l'algoritmo di codifica scelto sulla sequenza di $M$ campioni compresa nella finestra corrente, e i campioni quantizzati sono mandati al ricevitore;
4. si ritorna al passo 1 avanzando la finestra alla sequenza di $M$ campioni successivi.

Il numero $M$ di campioni su cui viene applicato l'algoritmo di codifica scelto è un compromesso tra:

• prestazioni di compressione dei bit che trasportano informazioni multimediali: un adattamento molto frequente permette di seguire fedelmente l'evoluzione del segnale nel tempo e stimare lo stato in modo meno grezzo;
• limitazione dei bit di overhead: occorre contenere il bit rate complessivo evitando di inviare troppi bit di overhead.

Siccome il segnale vocale varia approssimativamente da 50 a 100 volte al secondo, è sufficiente aggiornare la scelta dell'algoritmo ottimo:

• ogni 20 ms:

  $\frac{1\text{s}}{50\text{volte/s}}=20\text{ms}$

• ogni $M=160$ campioni:

  $\frac{20\text{ms}}{125\mu \text{s/campione}}=160\text{campioni}$

Vantaggi/svantaggi

• + prestazioni di compressione
• − complessità di calcolo: occorre stimare lo stato del segnale 50 volte al secondo (per la voce);
• − overhead: i bit di overhead, essendo inviati insieme ai campioni quantizzati del segnale, pesano sul bit rate complessivo;
• − robustezza: a volte è difficile stimare lo stato del segnale (ad es. voce con rumore di fondo)

Energy-tracking APCM

Schema a blocchi dell'algoritmo usato dalla codifica energy-tracking APCM.

La codifica energy-tracking APCM è basata su un quantizzatore uniforme con fondo scala variabile nel tempo al fine di adattarsi ai cambiamenti nel tempo dell'energia del segnale:

• il fondo scala si riduce quando il segnale ha meno energia;
• il fondo scala si allarga quando il segnale ha più energia.

Riducendo del fondo scala quando possibile, si possono ottenere due risultati:

• aumento del rapporto segnale/rumore SNR a parità di bit rate: viene ridotta l'ampiezza $\mathrm{\Delta }$ del gradino di quantizzazione, e quindi l'errore di quantizzazione $e[n]$, mantenendo costante il numero $N_Q$ di livelli di quantizzazione;
• riduzione del bit rate a parità di rapporto segnale/rumore SNR: viene ridotto il numero $N_Q$ di livelli di quantizzazione, mantenendo costante l'ampiezza $\mathrm{\Delta }$ del gradino di quantizzazione.

Algoritmo

1. stima dell'energia istantanea: si misura l'energia locale istantanea del segnale $x[n]$ all'interno della finestra corrente:

   $\text{E}\left[n_0\right]=\sum _{i=n_0-\frac{M}{2}}^{n_0+\frac{M}{2}}{x}^2[i]$

2. scelta del fondo scala: si calcola il fondo scala più adatto per la finestra corrente (ad es. tramite la regola euristica del $4\sigma$), e si invia come overhead al ricevitore il fondo scala scelto;
3. quantizzazione uniforme di $M$ campioni con il fondo scala scelto;
4. si ritorna al passo 1.

Tecniche ADPCM

Schema a blocchi dell'algoritmo usato dalle tecniche ADPCM.

Le tecniche ADPCM introducono nelle tecniche DPCM l'adattività ai cambiamenti nel tempo dell'energia del segnale differenziale:

• DPCM: i valori ottimi dei parametri ${\alpha }_i$ sono calcolati una volta in fase di progetto, in modo da minimizzare globalmente l'energia ${\sigma }_d^2$ del segnale differenziale:

  $d[n]=x[n]-\sum _{i=1}^N{\alpha }_{i}x[n-i],-\mathrm{\infty }<n<+\mathrm{\infty }$

• ADPCM: i valori ottimi dei parametri ${\alpha }_i$ sono calcolati di volta in volta per la finestra corrente di $M$ campioni, in modo da minimizzare localmente l'energia istantanea $\text{E}\left[n_0\right]$ del segnale differenziale:

  $d[n]=x[n]-\sum _{i=1}^N{\alpha }_{i}x[n-i],n_0-\frac{M}{2}<n<n_0+\frac{M}{2}$

Algoritmo

1. stima dell'energia istantanea: si misura l'energia istantanea del segnale differenziale $d[n]$ all'interno della finestra corrente:

   $\text{E}\left[n_0\right]=\sum _{i=n_0-\frac{M}{2}}^{n_0+\frac{M}{2}}{d}^2[i]$

2. calcolo dei valori localmente ottimi dei parametri ${\alpha }_i$: si risolve il sistema di $N$ derivate parziali ($N=10$ per la voce), e si inviano come overhead al ricevitore i valori ottimi calcolati e quantizzati ${\hat{\alpha }}_i$ (il ricevitore dovrà compiere un'operazione di inversione della matrice);
3. quantizzazione differenziale di ordine N di $M$ campioni con i parametri ${\alpha }_i$ calcolati, e il segnale differenziale quantizzato $\hat{d}[n]$ è mandato al ricevitore;
4. si ritorna al passo 1.

Quantizzazione dei parametri ${\alpha }_i$

Quantizzatore uniforme

I valori ottimi dei parametri ${\alpha }_i$ calcolati per la finestra di trasmissione corrente sono numeri reali → oltre ai campioni del segnale stesso, occorre quantizzare anche questi valori per poterli mandare al ricevitore in modo digitale → occorre progettare un quantizzatore uniforme per ognuno dei 10 parametri ${\alpha }_i$:

1. creazione di un database: si raccoglie un numero statisticamente significativo di valori del parametro ${\alpha }_i$ a partire da un campione rappresentativo di segnali vocali;
2. caratterizzazione statistica: si costruisce la funzione densità di probabilità PDF del parametro ${\alpha }_i$, ricavandone le caratteristiche statistiche (per una gaussiana: la media $\mu$ e la varianza $\sigma$);
3. scelta del fondo scala $X_m$, ad esempio tramite la regola euristica del $4\sigma$;
4. scelta del numero $N_Q$ di livelli:
   • se è noto a priori il rapporto segnale/rumore SNR desiderato, è facile ricavare il numero di livelli per mezzo della formula:

     $\text{SNR}=10{\log }_{10}\frac{{\sigma }_x^2}{{\sigma }_e^2}\text{dB}=K+\alpha \frac{X_m}{{\sigma }_x}+6N_Q$

   • nel caso di segnali multimediali, si usano tanti livelli quanti bastano per ottenere una quantizzazione percettivamente trasparente: la voce ricostruita usando il parametro quantizzato ${\alpha }_i$ è percettivamente indistinguibile dalla voce ricostruita usando il parametro non quantizzato ${\hat{\alpha }}_i$.

Quantizzatore ottimo

La distribuzione di probabilità di ognuno dei parametri ${\alpha }_i$ però è fortemente concentrata intorno al valor medio → occorre progettare un quantizzatore ottimo, con distribuzione di livelli non uniforme, per ognuno di questi parametri.

Una volta progettato il quantizzatore ottimo, esso è in grado di quantizzare ogni parametro ${\alpha }_i$ su 3÷4 bit → i 10 parametri quantizzati ${\hat{\alpha }}_i$ richiedono complessivamente circa 40 bit (sarebbe richiesto circa il doppio dei bit con il quantizzatore uniforme) → essendo inviati 50 volte al secondo (ogni 20 ms), generano un overhead di 2000 b/s: le prestazioni di compressione devono apportare un miglioramento tale da giustificare questo notevole overhead.

Standard ITU G.726

Lo standard ITU G.726, grazie a una codifica molto complessa che è derivata dalla tecnica ADPCM, riesce a dimezzare il bit rate del precedente standard, l'ITU G.711, mantenendo la stessa qualità (toll quality):

$R=4\text{bit/campione}\times 8000\text{Hz}=32\text{kb/s}$

al prezzo di una complessità molto alta pari a 1 MIPS.

Applicazioni

• cordless
• ambito spaziale