Elaborazione e trasmissione di informazioni multimediali/A4

Da WikiAppunti.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è A4. Tecniche PCM.
Gtk-go-back-ltr.svg  A3. Codifica di sorgenteGtk-home.svg  Elaborazione e trasmissione di informazioni multimediali (A. Codifica della voce e dell'audio)A5. Tecniche parametriche  Gtk-go-forward-ltr.svg

Le tecniche di quantizzazione PCM 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[modifica]

Quantizzatore uniforme: PCM lineare[modifica]

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 \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 = \int_{- \frac{\Delta}{2}}^{+ \frac{\Delta}{2}} e^2 \left( t \right) \cdot \text{ PDF}_e \left( t \right) dt = \frac{\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)[modifica]

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[modifica]

Lo standard G.711, sviluppato da ITU, 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[modifica]

  • 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[modifica]

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)[modifica]

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[modifica]

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 \left[ n - 1 \right]

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

\rho = \frac{E \left[ x \left[ n \right] x \left[ n - 1 \right] \right]}{E \left[ x^2 \left[ n-1 \right] \right] } , \quad 0 \leq \rho \leq 1
  • se il campione x \left[ n \right] è uguale al campione precedente x \left[ n - 1 \right], la correlazione \rho è pari a 1:
    x \left[ n \right] = x \left[ n-1 \right] \Rightarrow \rho = \frac{E \left[ x^2 \left[ n-1 \right] \right]}{E \left[ x^2 \left[ n-1 \right] \right]} = 1
  • se il campione x \left[ n \right] è completamente differente rispetto al campione precedente x \left[ n-1 \right], 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 \Leftrightarrow d \left[ n \right] = x \left[ n \right] - \rho x \left[ n - 1 \right]
Dimostrazione

Dato il segnale differenziale:

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

si vuole trovare il valore ottimo \alpha che ne minimizza l'energia:

\sigma_d^2 = E \left[ d^2 \left[ n \right] \right] = E \left[ {\left( x \left[ n \right] - \alpha x \left[ n - 1 \right] \right)}^2 \right] = E \left[ x^2 \left[ n \right] \right] + \alpha^2 E \left[ x^2 \left[ n-1 \right] \right] - 2 \alpha E \left[ x \left[ n \right] \cdot x \left[ n-1 \right] \right] \Rightarrow
\Rightarrow \frac{\partial \sigma_d^2}{\partial \alpha} = 0 ; \; 2 \alpha E \left[ x^2 \left[ n-1 \right] \right] - 2 E \left[ x \left[ n \right]  x \left[ n-1 \right] \right] = 0; \; \alpha = \frac{2 E \left[ x \left[ n \right] x \left[ n - 1 \right] \right]}{2 E \left[ x^2 \left[ n-1 \right] \right] } = \rho

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,9 x[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 \left[ n - 1 \right]
  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[modifica]

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

d[n] = x[n] - f \left( x [n-1] , x[n-2], \ldots , x[n-N] \right) = 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{cases}
\frac{\partial \sigma_d^2}{\partial \alpha_1} = 0 \\
\vdots \\
\frac{\partial \sigma_d^2}{\partial \alpha_N} = 0
\end{cases}

Codifica predittiva: Linear Predictive Coding (LPC)[modifica]

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 \left( x[n-1] \right) = \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 \left( x [n-1], x[n-2], \ldots , x[n-N] \right) = \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 \left( x [n-1], x[n-2], \ldots , x[n-N] \right) =
    • 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 \left( \hat x [n-1], \hat x[n-2], \ldots , \hat x[n-N] \right) =
    • 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)[modifica]

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[modifica]

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 \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 \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:
    \textrm{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[modifica]

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] , \quad - \infty < n < + \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 \textrm{E} \left[ n_0 \right] del segnale differenziale:
    d[n] = x [n] - \sum_{i=1}^N \alpha_i  x [n-i] , \quad 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:
    \textrm{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[modifica]

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[modifica]

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

Note[modifica]

  1. E \left[ X \right] è la funzione di valore atteso della variabile casuale X.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è A4. Tecniche PCM.
Gtk-go-back-ltr.svg  A3. Codifica di sorgenteGtk-home.svg  Elaborazione e trasmissione di informazioni multimediali (A. Codifica della voce e dell'audio)A5. Tecniche parametriche  Gtk-go-forward-ltr.svg