Esercizio - Decimazione in più stadi

Testo (esercizio costruito sulla realizzazione multistadio delle lezioni 20 e 21 del corso Multimedia Signal Processing, UniPD). Un segnale audio a $F_s=48$ kHz ha banda utile fino a $f_p=800$ Hz e deve essere decimato di $M=24$ (uscita a $2$ kHz), conservando la banda utile con attenuazione di almeno $60$ dB di tutto ciò che ripiegherebbe (per aliasing) dentro la banda utile. I filtri anti-aliasing sono FIR progettati con la finestra di Kaiser.

1. Progettare il filtro nel caso a uno stadio, $M=24$, e calcolarne la lunghezza.
2. Ripetere per la decimazione in due stadi $8\times3$ e $3\times8$.
3. Confrontare il costo (moltiplicazioni al secondo) di tutte le fattorizzazioni e commentare l'ordine dei fattori.

Teoria usata: Elaborazione multirate - decimazione e interpolazioneL'elaborazione multirate cambia la frequenza di campionamento di un segnale. Interpolazione per $L$ (da $F_s$ a $LF_s$): l'espansore inserisce $L-1$ zeri fra i campioni, $W(\hat\omega)=X(L\hat\omega)$, lo spettro si ripete $L$ volte nell'asse più ampio; un passabasso con taglio $\pi/L$ e guadagno $L$ elimina le immagini, e con il sinc ideale $h[n]=\operatorname{sinc}(n/L)$ i campioni originali sono conservati ($y[nL]=x[n]$); in pratica FIR a finestre o interpolatore lineare (triangolo). Decimazione per $M$ (da $F_s$ a $F_s/M$): $y[n]=x[nM]$, $Y(\hat\omega)=\frac1M\sum_{k=0}^{M-1}X\big(\frac{\hat\omega-2\pi k}M\big)$, repliche sovrapposte (aliasing) se la banda supera $\pi/M$: si fa precedere da un passabasso con taglio $\pi/M$. Conversione razionale $F_s'=\frac LMF_s$ ($L,M$ coprimi): espansore $L$, un solo passabasso di taglio $\min(\frac\pi L,\frac\pi M)$ e guadagno $L$, decimatore $M$; $y[n]=\sum_kx[k],g[nM-kL]$ non è una convoluzione e il sistema è periodicamente tempo-invariante. Realizzare il tutto in più stadi (fattori piccoli prima per l'interpolazione, grandi prima per la decimazione) e con strutture polifase riduce molto il costo.Elaborazione multirate - decimazione e interpolazione →, Progetto di filtri FIR con il metodo delle finestreUn filtro FIR a fase lineare di tipo I (ordine $N$ pari, $h[n]=h[N-n]$) ha risposta $H(e^{j\hat\omega})=e^{-j\hat\omega N/2}\bar H(\hat\omega)$ con ampiezza $\bar H(\hat\omega)=\sum_{n=0}^{N/2}p_n\cos(n\hat\omega)$. Per approssimare un'ampiezza desiderata $D(\hat\omega)$ (passa-basso: $1$ in banda passante, $0$ in banda oscura, con tolleranze $\delta_p,\delta_s$ e frequenze $\hat\omega_p,\hat\omega_s$) ci sono tre metodi. Finestre: si tronca la serie di Fourier di $D$, cioè $h[n]=h_d[n-N/2],w[n]$ con $h_d[n]=\frac{\hat\omega_0}{\pi}\operatorname{sinc}\frac{\hat\omega_0 n}{\pi}$; la rettangolare è ottima in errore quadratico ma dà il fenomeno di Gibbs (9%, $21$ dB), le finestre rastremate (Hann, Hamming, Blackman, Kaiser) abbassano i lobi laterali allargando la transizione ($\hat\omega_s-\hat\omega_p\simeq\alpha,2\pi/L$). Campionamento in frequenza: $h=\mathrm{IDFT}$ dei campioni di $D$, esatto solo sui campioni. Minimax (Parks-McClellan): errore pesato minimo nel caso peggiore, soluzione equiripple con almeno $r+2$ alternanze, ordine più basso a parità di specifiche.Progetto di filtri FIR con il metodo delle finestre →.

Regola di progetto del filtro di uno stadio

Dopo il decimatore di uno stadio la frequenza scende da $F_{\rm in}$ a $F_{\rm out}=F_{\rm in}/M_k$ e lo spettro si ripete con periodo $F_{\rm out}$. Le frequenze utili stanno in $[0,f_p]$ e le repliche vicine in $[F_{\rm out}-f_p,\,F_{\rm out}+f_p]$ (e le analoghe attorno ai multipli di $F_{\rm out}$): per non portare niente dentro la banda utile, il filtro deve lasciar passare $[0,f_p]$ e attenuare tutto da $F_{\rm out}-f_p$ in avanti. Quindi: banda passante fino a $f_p$, banda oscura da $F_{\rm out}-f_p$, transizione $\Delta f=F_{\rm out}-2f_p$, normalizzata alla frequenza di lavoro del filtro: $\frac{\Delta\hat\omega}{2\pi}=\frac{F_{\rm out}-2f_p}{F_{\rm in}}$. La lunghezza di Kaiser per $A_s=60$ dB è $N\simeq\frac{A_s-8}{14{,}36\,\Delta\hat\omega/2\pi}$ (kaiserord usa $2{,}285$ al posto di $14{,}36/2\pi$, e arrotonda). Il costo di uno stadio con struttura polifase è $(N+1)$ moltiplicazioni per ogni campione in uscita dallo stadio: $(N+1)F_{\rm out}$ al secondo.

1. Un solo stadio

$F_{\rm out}=2$ kHz, banda oscura da $2000-800=1200$ Hz, $\Delta f=400$ Hz a $F_{\rm in}=48$ kHz: $\frac{\Delta\hat\omega}{2\pi}=\frac{400}{48000}=0{,}00833$ e $$N\simeq\frac{52}{14{,}36\cdot0{,}00833}=435\quad(\texttt{kaiserord}:\ 437).$$ Costo: $438\cdot2000=876\,000$ moltiplicazioni/s.

2. Due stadi

$8\times3$. Primo stadio: $F_{\rm out}=6$ kHz, banda oscura da $5200$ Hz, $\Delta f=4400$ Hz a $48$ kHz ($0{,}0917$): $N\simeq\frac{52}{14{,}36\cdot0{,}0917}=39{,}5$ ($\texttt{kaiserord}$: $41$), costo $42\cdot6000=252\,000$. Secondo stadio: $F_{\rm in}=6$ kHz, $F_{\rm out}=2$ kHz, banda oscura da $1200$ Hz, $\Delta f=400$ Hz a $6$ kHz ($0{,}0667$): $N\simeq54{,}3$ ($56$), costo $57\cdot2000=114\,000$. Totale $366\,000$ moltiplicazioni/s, con $41+56=97$ coefficienti contro $437$.

$3\times8$. Primo stadio: $F_{\rm out}=16$ kHz, banda oscura da $15\,200$ Hz, $\Delta f=14\,400$ Hz a $48$ kHz ($0{,}3$): $N=14$, costo $15\cdot16\,000=240\,000$. Secondo stadio: da $16$ kHz a $2$ kHz, $\Delta f=400$ Hz a $16$ kHz ($0{,}025$): $N=147$, costo $148\cdot2000=296\,000$. Totale $536\,000$.

3. Tutte le fattorizzazioni

Con la stessa procedura (calcolata con kaiserord e il costo polifase $\sum_k(N_k+1)F_{{\rm out},k}$):

Commenti:

• Ogni fattorizzazione in più stadi costa meno dello stadio unico: il risparmio va dal $22\%$ ($2\times12$) al $58\%$ ($8\times3$).
• Il fattore più grande per primo conviene: $12\times2$ ($378\,000$) batte $2\times12$ ($680\,000$), $8\times3$ ($366\,000$) batte $3\times8$ ($536\,000$), $6\times4$ ($390\,000$) batte $4\times6$ ($450\,000$). Il motivo: il primo stadio lavora a frequenza alta ma con transizione larga (pochi coefficienti) e riduce subito la frequenza; lo stadio con la transizione stretta lavora quando la frequenza è già bassa.
• Più stadi non sono automaticamente meglio: il minimo ($8\times3$) è a due stadi, e le terne costano di più ($390\,000$ e oltre).

Per l'interpolazione vale il risultato speculare (fattore piccolo per primo, stessi costi con l'ordine invertito: $3\times8$ costa $366\,000$ come $8\times3$ in decimazione, vedi la tabella in Elaborazione multirate - decimazione e interpolazioneL'elaborazione multirate cambia la frequenza di campionamento di un segnale. Interpolazione per $L$ (da $F_s$ a $LF_s$): l'espansore inserisce $L-1$ zeri fra i campioni, $W(\hat\omega)=X(L\hat\omega)$, lo spettro si ripete $L$ volte nell'asse più ampio; un passabasso con taglio $\pi/L$ e guadagno $L$ elimina le immagini, e con il sinc ideale $h[n]=\operatorname{sinc}(n/L)$ i campioni originali sono conservati ($y[nL]=x[n]$); in pratica FIR a finestre o interpolatore lineare (triangolo). Decimazione per $M$ (da $F_s$ a $F_s/M$): $y[n]=x[nM]$, $Y(\hat\omega)=\frac1M\sum_{k=0}^{M-1}X\big(\frac{\hat\omega-2\pi k}M\big)$, repliche sovrapposte (aliasing) se la banda supera $\pi/M$: si fa precedere da un passabasso con taglio $\pi/M$. Conversione razionale $F_s'=\frac LMF_s$ ($L,M$ coprimi): espansore $L$, un solo passabasso di taglio $\min(\frac\pi L,\frac\pi M)$ e guadagno $L$, decimatore $M$; $y[n]=\sum_kx[k],g[nM-kL]$ non è una convoluzione e il sistema è periodicamente tempo-invariante. Realizzare il tutto in più stadi (fattori piccoli prima per l'interpolazione, grandi prima per la decimazione) e con strutture polifase riduce molto il costo.Elaborazione multirate - decimazione e interpolazione →).