Elaborazione multirate - decimazione e interpolazione

Molte applicazioni (audio, immagini, video, telecomunicazioni) trattano segnali con frequenze di campionamento diverse: un CD ha $44{,}1$ kHz, un file professionale $48$ kHz, un video può essere a $30$ o $60$ fotogrammi al secondo. L'elaborazione numerica che cambia la frequenza di campionamento (sample rate conversion) si chiama multirate. I casi sono tre:

• interpolazione (interpolation): la frequenza di uscita è $L$ volte quella di ingresso, $F_s'=LF_s$ con $L$ intero positivo;
• decimazione (decimation): la frequenza di uscita è $M$ volte più piccola, $F_s'=F_s/M$, con $M$ intero positivo;
• conversione generica: $F_s'=\frac LM F_s$ con $L,M$ interi positivi coprimi (rapporto razionale).

Gli obiettivi sono due: conservare nell'uscita il più possibile l'informazione del segnale di ingresso (cioè ridurre le distorsioni) e farlo con un costo di calcolo basso. Le basi sono il campionamento e la ripetizione degli spettri (Campionamento e ricostruzioneIl campionamento $s_c(nT)=s(nT)$ trasforma un segnale continuo in uno discreto e, in frequenza, ripete lo spettro con periodo $F_c=1/T$: $S_c(f)=\sum_kS(f-kF_c)$. Se le repliche si sovrappongono si ha aliasing e il segnale non è recuperabile. Un interpolatore $\mathbb Z(T)\to\mathbb R$ con risposta impulsiva $g$ produce $\tilde s(t)=\sum_nT g(t-nT)s(nT)$ e $\tilde S=G,S_c$. Teorema del campionamento: se $s$ ha banda $B$ e $F_c\ge2B$, l'interpolatore ideale $G=\operatorname{rect}(f/F_c)$ ricostruisce esattamente $s(t)=\sum s(nT)\operatorname{sinc}(F_c(t-nT))$. Se le ipotesi non valgono c'è un errore, in banda e fuori banda, riducibile con un prefiltro anti-aliasing.Campionamento e ricostruzione →, Interpolazione LTI e teorema del campionamentoIl campionatore R→Z(T) ripete lo spettro con periodo Fc = 1/T (Sc(f) = Σ S(f - kFc), senza fattore 1/T). Il filtro interpolatore Z(T)→R ha y(t) = Σ x(nT) g0(t-nT) con g0 = T g e in frequenza Y = G·X. Se S è nulla fuori da (-B,B) e Fc ≥ 2B, con g0(t) = sinc(Fc t) si ricostruisce esattamente s(t) dai campioni. Altrimenti c'è un errore (in banda per l'aliasing, fuori banda per la parte tagliata), ridotto da un prefiltro anti-aliasing.Interpolazione LTI e teorema del campionamento →) e la DTFT (Trasformata di Fourier a tempo discretoLa trasformata di Fourier di un segnale discreto è $S(f)=\sum_nT,s(nT),e^{-i2\pi fnT}$: una funzione continua e periodica in $f$ di periodo $F_p=1/T$. L'antitrasformata è l'integrale su un periodo, $s(nT)=\int_0^{F_p}S(f)e^{i2\pi fnT}df$. Le regole sono quelle del caso continuo (traslazione, convoluzione $\leftrightarrow$ prodotto, Parseval $\sum T|s|^2=\int_0^{F_p}|S|^2$), con incremento e somma corrente al posto di derivata e integrale. Per segnali reali $S(f)=S^*(-f)$, quindi basta $[0,F_p/2]$. Esempi: $\delta\to1$, $1\to\delta_{F_p}$, rect $\to$ sinc periodico, $a^n\mathbf 1_0\to\frac T{1-ae^{-i2\pi fT}}$.Trasformata di Fourier a tempo discreto →).

Segnali su griglie diverse

Un sistema che cambia la frequenza di campionamento ha l'ingresso $x[nT]$ con $F_s=\frac1T$ e l'uscita $y[nT']$ con $F_s'=\frac1{T'}$. Il sistema non è omogeneo: i domini temporali dell'ingresso e dell'uscita sono diversi, quindi bisogna dire sempre con quale griglia di tempo si lavora. Per esempio il fotogramma $40$ di un video a $30$ fps cade a $\frac{40}{30}$ s, quello di un video a $60$ fps a $\frac{40}{60}$ s.

In questa nota, per semplicità, si lavora con indici interi $n$ e frequenza normalizzata $\hat\omega$ del segnale a cui ci si riferisce; per passare alle frequenze in Hz basta ricordare che $\hat\omega=2\pi f/F$, con $F$ la frequenza di campionamento di quel segnale. I tre numeri che compaiono in un sistema generale sono: la frequenza di ingresso $F_s$, la frequenza di uscita $F_s'=\frac LMF_s$ e la frequenza intermedia $F_s''=LF_s=MF_s'$, la più alta del sistema: $F_s''=\operatorname{mcm}(F_s,F_s')$ in senso stretto (il minimo comune multiplo delle frequenze, cioè $T''=\operatorname{MCD}(T,T')$ per i periodi).

Esempio. $F_s=2$ e $F_s'=3$ (unità arbitrarie): $F_s''=6$, $T''=\frac16$. Esempio (audio). Da $44{,}1$ kHz a $48$ kHz: $\frac{F_s'}{F_s}=\frac{48000}{44100}=\frac{160}{147}$ ($\operatorname{MCD}=300$), quindi $L=160$, $M=147$ e $F_s''=44100\cdot160=7056$ kHz.

Struttura della conversione generica

Un sistema di conversione $\frac LM$ è la cascata di tre blocchi (l'ordine conta: prima si interpola, poi si decima; l'inverso perderebbe informazione):

1. un interpolatore per $L$ (espansore $\uparrow L$), da $F_s$ a $F_s''=LF_s$;
2. un sistema LTI con risposta impulsiva $h$ (filtro passabasso) che lavora a $F_s''$;
3. un decimatore per $M$ ($\downarrow M$), da $F_s''$ a $F_s'=F_s''/M$.

Il filtro lavora alla frequenza più alta $F_s''$, quindi sembra costoso: più sotto si vede come si evita.

Equazione ingresso-uscita

Si indica con $g[m]$ la risposta impulsiva del filtro sulla griglia di $F_s''$. Il segnale dopo l'espansore è $v[m]=x[m/L]$ se $L$ divide $m$, $0$ altrimenti; dopo il filtro $w[m]=\sum_kv[k]g[m-k]=\sum_{i}x[i]\,g[m-iL]$ e dopo il decimatore $y[n]=w[nM]$. Quindi

$$y[n]=\sum_{i=-\infty}^{+\infty}x[i]\;g[nM-iL].$$

(Nelle slide, con i tempi: $y[nT']=T\sum_kx[kT]\,h[nT'-kT]$, dove $h$ è definita sui multipli di $T''$ e il fattore $T$ viene dalla normalizzazione dell'integrale; nella versione discreta il guadagno $L$ del filtro assorbe quel fattore.)

Questa non è una convoluzione: i dominii dell'ingresso, dell'uscita e della risposta impulsiva sono diversi, e la somma non è commutativa. Il sistema è lineare ma non tempo-invariante in generale: se si trasla l'ingresso di un campione l'uscita non è semplicemente la traslata. È periodicamente tempo-invariante: traslando l'ingresso di $M$ campioni (cioè di $MT=\operatorname{mcm}(T,T')=LT'$ secondi) l'uscita trasla di $L$ campioni; il periodo di invarianza è $\operatorname{mcm}(T,T')$.

Esempio. Con $L=2$, $M=3$: $y[n]=\sum_ix[i]\,g[3n-2i]$. Per $n=0$ intervengono $g[0]$ con $x[0]$, $g[-2]$ con $x[1]$, $g[2]$ con $x[-1]$; per $n=1$ è $g[3]$ con $x[0]$, $g[1]$ con $x[1]$, $g[5]$ con $x[-1]$...: ogni campione d'uscita usa una fase diversa di $g$: la fase $nM \bmod L$ cambia con $n$ e si ripete ogni $L$ uscite.

Interpolazione

L'espansore (upsampler)

Definizione (espansore per $L$). Inserisce $L-1$ zeri fra due campioni consecutivi dell'ingresso: $$v[n]=\begin{cases}x[n/L],&n=0,\pm L,\pm2L,\dots\\0,&\text{altrimenti.}\end{cases}$$ (Nelle slide e nelle dispense i campioni vengono anche moltiplicati per $L$; qui il guadagno $L$ è assegnato al filtro che segue, il risultato non cambia.)

È un sistema lineare e tempo-invariante con ingresso e uscita su griglie diverse, e non perde informazione: i campioni di $x$ sono tutti dentro $v$. Esempio. $x=\{1,2,3\}$ e $L=3$: $v=\{1,0,0,2,0,0,3,0,0\}$.

Teorema (spettro dell'espansore). $V(e^{j\hat\omega})=X(e^{jL\hat\omega})$.

Dimostrazione. $V(\hat\omega)=\sum_nv[n]e^{-j\hat\omega n}=\sum_kx[k]\,e^{-j\hat\omega kL}$, perché sono diversi da zero solo i termini $n=kL$. Questa è $X$ calcolata in $L\hat\omega$. $\square$

$X(e^{j\hat\omega})$ ha periodo $2\pi$ in $\hat\omega$, quindi $X(e^{jL\hat\omega})$ ha periodo $\frac{2\pi}L$: lo spettro del segnale d'ingresso si comprime di un fattore $L$ e si ripete $L$ volte nell'intervallo $(-\pi,\pi)$. Con l'asse in Hz questo è il fatto che l'uscita ha il periodo $F_s''=LF_s$ e un intervallo fondamentale $(-\frac L2F_s,\frac L2F_s)$ che contiene lo spettro originale in $(-\frac12F_s,\frac12F_s)$ più $L-1$ immagini (images).

Esempio. $x[n]=\cos(0{,}4\pi n)$ e $L=3$: $V(\hat\omega)=X(3\hat\omega)$ ha righe in $\hat\omega=\pm0{,}1333\pi+\frac{2\pi}3m$, cioè in $0{,}1333\pi$ (il segnale originale, compresso), $0{,}5333\pi$ e $0{,}8\pi$ (le due immagini).

Il filtro di interpolazione

Per tenere solo l'informazione dell'ingresso si fa seguire l'espansore da un passabasso ideale con taglio $\frac\pi L$ (in Hz $\frac12F_s$) e guadagno $L$: elimina le $L-1$ immagini e ricostruisce lo spettro originale, ormai su una scala di frequenze $L$ volte più ampia.

Il filtro ideale ha $h[n]=\operatorname{sinc}\!\big(\frac nL\big)$ (guadagno $L$, taglio $\frac\pi L$), che vale $1$ in $n=0$ e si annulla in tutti gli altri multipli di $L$. Di conseguenza l'uscita

$$y[n]=\sum_{k=-\infty}^{\infty}x[k]\,\operatorname{sinc}\!\Big(\frac{n-kL}{L}\Big)$$

coincide con l'ingresso nei punti $n=kL$ ($y[kL]=x[k]$): è la proprietà di interpolazione corretta (correct interpolation property): i campioni originali non vengono modificati, quelli nuovi vengono dedotti. Il sinc ideale non è realizzabile (non causale e infinito), si approssima con un FIR (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 →), per esempio con la finestra di Hamming: la finestra rettangolare darebbe Gibbs e un guadagno in continua sbagliato (vedi Esercizio - Laboratorio 4 - interpolazione e zoom di immagini). Il metodo delle finestre conserva gli zeri di $h_d$ nei multipli di $L$, quindi mantiene la proprietà di interpolazione corretta.

Esempio. $L=3$, $x[n]=\cos(0{,}4\pi n)$: il passabasso (taglio $\pi/3=0{,}333\pi$) elimina le righe in $0{,}5333\pi$ e $0{,}8\pi$ e lascia $\cos(0{,}1333\pi n)$, che nei multipli di $3$ vale $\cos(0{,}4\pi k)=x[k]$.

Interpolazione lineare

Quando le risorse di calcolo sono poche si collegano i campioni con segmenti: interpolazione lineare. Il sistema è LTI. Per $L=2$ si trova la risposta impulsiva applicando un impulso: i campioni intermedi sono la media dei vicini, e si ottiene un triangolo. In generale con picco $1$ e lunghezza $2L-1$: $$h[n]=\begin{cases}1-\frac{|n|}{L},&|n|<L\\0,&\text{altrove}\end{cases}\qquad L=2:\ h=\big\{\tfrac12,\,1,\,\tfrac12\big\},\quad L=3:\ \big\{\tfrac13,\tfrac23,1,\tfrac23,\tfrac13\big\}.$$ Vale $h[kL]=\delta[k]$ (zero nei multipli di $L$ diversi da zero), quindi anche qui i campioni originali restano. La risposta in frequenza è la somma di una progressione geometrica: $$H(e^{j\hat\omega})=\frac1L\Big(\frac{\sin(L\hat\omega/2)}{\sin(\hat\omega/2)}\Big)^2,\qquad L=2:\ H=1+\cos\hat\omega,\quad H(0)=L .$$ (Il triangolo è la convoluzione di due rettangoli di lunghezza $L$, divisa per $L$, e il quadrato del nucleo di Dirichlet è la sua trasformata.) Il guadagno in continua è $L$, proprio quello richiesto; nelle slide il guadagno è diviso fra espansore e filtro, che quindi vale $1$ in continua: $\frac1{L^2}\big(\frac{\sin(L\hat\omega/2)}{\sin(\hat\omega/2)}\big)^2$.

Il filtro lineare è lontano dall'ideale (rettangolo fino a $\frac\pi L$): la transizione è lenta (per $L=5$ il guadagno normalizzato è $0{,}42$ in $\frac\pi5$ e $0{,}10$ in $0{,}3\pi$) e oltre $0{,}4\pi$ il guadagno massimo è ancora $0{,}0625$, cioè solo $-24$ dB (con il sinc finestrato con Hamming si arriva a $-51$ dB, Esercizio - Laboratorio 4 - interpolazione e zoom di immagini). Per questo l'interpolazione lineare dà buoni risultati solo se il segnale occupa frequenze molto più basse della massima; altrimenti restano immagini e distorsione.

Interpolazione in più stadi

Se $L=L_1L_2\cdots L_K$ conviene interpolare in $K$ stadi ($F_s\to L_1F_s\to L_1L_2F_s\to\dots$) invece che in uno solo: ogni filtro ha una banda di transizione più larga rispetto alla sua frequenza di lavoro e quindi meno coefficienti. Il costo minimo si ha con i fattori in ordine crescente, $L_1\le L_2\le\dots$ (il fattore più piccolo per primo), perché i primi filtri lavorano a frequenze basse.

Esempio numerico. Segnale a $2$ kHz con banda utile fino a $800$ Hz, interpolato di $L=24$ fino a $48$ kHz con $60$ dB di attenuazione (filtri di Kaiser, kaiserord; costo in moltiplicazioni al secondo con la struttura polifase):

In tutti i casi della tabella lo schema a più stadi costa meno del singolo stadio (dal $22\%$ al $58\%$ in meno), e per ogni coppia l'ordine con il fattore piccolo prima costa meno ($378\,000$ contro $680\,000$ e $366\,000$ contro $536\,000$). Non è invece detto che più stadi siano meglio di due (qui il minimo è $3\times8$). Vedere anche Esercizio - Decimazione in più stadi, che è il caso speculare.

Decimazione

Il decimatore (downsampler)

Definizione (decimatore per $M$). Conserva un campione ogni $M$: $y[n]=x[nM]$ (la frequenza scende a $F_s/M$).

Esempio. $x=\{1,2,3,4,5,6,7\}$ e $M=3$: $y=\{1,4,7\}$.

È lineare ma, a differenza dell'espansore, non tempo-invariante e perde informazione in generale.

Teorema (spettro del decimatore). $Y(e^{j\hat\omega})=\dfrac1M\displaystyle\sum_{k=0}^{M-1}X\!\Big(e^{j\frac{\hat\omega-2\pi k}M}\Big)$.

Dimostrazione. Si definisce $u[n]=x[n]\,p[n]$ con $p[n]=\sum_{k}\delta[n-kM]$ (pettine di impulsi: vale $1$ nei multipli di $M$, $0$ altrove). Allora $u[n]=x[n]$ se $M$ divide $n$ e $0$ altrimenti, e $y[m]=u[mM]$. La DTFT del pettine è $P(\hat\omega)=\frac{2\pi}{M}\sum_{k=0}^{M-1}\delta(\hat\omega-\frac{2\pi k}{M})$ (periodica), e il prodotto in tempo è convoluzione in frequenza (Proprietà della trasformata di FourierCon le proprietà (linearità, simmetrie, ritardo $\leftrightarrow e^{-j\omega t_0}$, modulazione $\leftrightarrow$ traslazione in frequenza, scala, dualità, convoluzione $\leftrightarrow$ prodotto, Parseval $E=\frac1{2\pi}\int|X|^2$, derivata $\leftrightarrow j\omega$, moltiplicazione per $t\leftrightarrow j,d/d\omega$, integrazione) quasi tutte le trasformate si ottengono da poche coppie base senza integrare.Proprietà della trasformata di Fourier →): $U(\hat\omega)=\frac1M\sum_{k=0}^{M-1}X(\hat\omega-\frac{2\pi k}M)$. Poi $Y(\hat\omega)=\sum_mu[mM]e^{-j\hat\omega m}=\sum_nu[n]e^{-j\hat\omega n/M}=U(\hat\omega/M)$, perché i soli $n$ non nulli di $u$ sono multipli di $M$. Quindi $Y(\hat\omega)=\frac1M\sum_kX\big(\frac{\hat\omega}M-\frac{2\pi k}M\big)$. $\square$ (Verificato numericamente con una sequenza casuale.)

Quindi $Y$ è la somma di $M$ versioni dello spettro di $X$, dilatate di $M$ e traslate di $2\pi k$, divise per $M$. Nelle slide, con la normalizzazione in Hz: $\tilde Y(f)=\sum_{k=0}^{M-1}\tilde X(f-kF_s')$, cioè $M$ repliche dello spettro spaziate di $F_s'=F_s/M$.

Aliasing

Le repliche si sovrappongono se $X$ occupa più di $|\hat\omega|<\frac\pi M$: in quella zona non si può più ricostruire $X$ da $Y$ (la somma di più termini non si "separa"): è l'aliasing della decimazione. Se $x$ è a banda limitata in $|\hat\omega|<\frac\pi M$ (in Hz, $|f|<\frac{F_s}{2M}=\frac{F_s'}2$) non c'è sovrapposizione e tutta l'informazione si conserva.

Esempio. $x[n]=\cos(0{,}6\pi n)$ e $M=2$: $y[n]=\cos(1{,}2\pi n)=\cos(0{,}8\pi n)$, perché $1{,}2\pi\equiv-0{,}8\pi\pmod{2\pi}$. La frequenza $0{,}6\pi>\frac\pi2$ riappare (falsamente) a $0{,}8\pi$.

Il filtro anti-aliasing

Per limitare l'aliasing si fa precedere il decimatore da un passabasso con taglio $\frac\pi M$ (in Hz $\frac{F_s}{2M}=\frac{F_s'}2$) e guadagno $1$. Il filtro ideale minimizza la distorsione: all'uscita $Y$ coincide con $X$ nella banda $|f|<\frac{F_s'}2$ e la parte di $x$ oltre quel limite è persa, ma non viene riportata dentro la banda. In pratica un FIR progettato con le finestre o il minimax (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 →).

Esempio. Nel caso $x[n]=\cos(0{,}6\pi n)$, $M=2$, il prefiltro con taglio $\frac\pi2$ elimina la componente: l'uscita è praticamente zero, invece di una sinusoide falsa.

Decimazione in più stadi

Come per l'interpolazione, se $M=M_1\cdots M_K$ conviene decimare in $K$ stadi. Il costo minimo si ha con i fattori in ordine decrescente (il fattore più grande per primo): i filtri più impegnativi lavorano a frequenza già ridotta. Esempio con $F_s=48$ kHz, $M=24$ (uscita $2$ kHz), banda utile $800$ Hz, $60$ dB: un solo filtro ha ordine $437$ e costa $876\,000$ moltiplicazioni/s calcolando solo i campioni d'uscita; $12\times2$ costa $378\,000$ contro $680\,000$ di $2\times12$; $8\times3$ costa $366\,000$ contro $536\,000$ di $3\times8$ (tabella e calcoli in Esercizio - Decimazione in più stadi).

Conversione generica $F_s'=\frac LMF_s$

Si interpola per $L$ e poi si decima per $M$. I due filtri fra i blocchi, l'anti-immagine (taglio $\frac\pi L$, serve a eliminare le immagini create dall'espansore) e l'anti-aliasing (taglio $\frac\pi M$, serve a evitare l'aliasing del decimatore), lavorano alla stessa frequenza $F_s''$ e sono in cascata, quindi si sostituiscono con un solo passabasso di guadagno $L$ e taglio

$$\hat\omega_c=\min\Big(\frac\pi L,\frac\pi M\Big)\qquad\Big(\text{in Hz: }f_c=\min\Big(\frac{F_s}2,\frac{F_s'}2\Big)\Big).$$

Il caso $F_s'>F_s$ ($L>M$) è dominato dal taglio $\frac\pi L$ (si conserva tutta la banda dell'ingresso), il caso $F_s'<F_s$ ($M>L$) da $\frac\pi M$ (la banda di uscita è più stretta e si perde parte dell'ingresso). L'equazione ingresso-uscita è la già vista $y[n]=\sum_ix[i]\,g[nM-iL]$.

Esempio. $44{,}1\to48$ kHz: $L=160$, $M=147$. Il filtro lavora a $7056$ kHz ed ha taglio $\min(\frac\pi{160},\frac\pi{147})=\frac\pi{160}$, cioè $22{,}05$ kHz in Hz. Calcolarlo a $7$ MHz sarebbe proibitivo: si usa la struttura polifase (sotto) e si calcolano solo i campioni d'uscita, con una frazione di $\frac1L$ dei coefficienti per campione.

Realizzazioni efficienti

Il filtro $g$ di lunghezza $K$ fa moltiplicazioni inutili: dopo l'espansore $L-1$ campioni su $L$ sono zero, e il decimatore butta via $M-1$ uscite su $M$. Nella struttura polifase si scompone $g$ in $L$ sottofiltri $g_r[k]=g[kL+r]$, $r=0,\dots,L-1$ (nell'interpolatore ognuno produce una delle $L$ uscite fra due campioni di ingresso, a frequenza $F_s$); per la decimazione la scomposizione è analoga. Con l'interpolazione per $L$ si fanno $\frac KL$ moltiplicazioni per campione d'uscita invece di $K$; con la decimazione per $M$ si calcolano solo le uscite necessarie, $K$ moltiplicazioni ogni $M$ campioni d'ingresso, non $K$ per campione. Entrambe le identità sono state verificate numericamente (errore $\approx10^{-15}$). I conteggi nelle tabelle sopra usano queste strutture.

Domande d'esame

1. Descrivi un sistema di interpolazione e il ruolo del filtro dopo l'espansore. Traccia: espansore, $V(\hat\omega)=X(L\hat\omega)$ (dimostrazione), compressione dello spettro e $L-1$ immagini; passabasso ideale con taglio $\frac\pi L$ e guadagno $L$, risposta $\operatorname{sinc}(n/L)$, interpolazione corretta; FIR con finestre; interpolazione lineare (triangolo, $\frac1L(\frac{\sin(L\hat\omega/2)}{\sin(\hat\omega/2)})^2$) e suoi limiti.
2. Descrivi la decimazione e spiega perché serve un filtro anti-aliasing. Traccia: $y[n]=x[nM]$, pettine di impulsi, $Y(\hat\omega)=\frac1M\sum_kX(\frac{\hat\omega-2\pi k}M)$, sovrapposizione delle repliche se la banda supera $\frac\pi M$; passabasso con taglio $\frac\pi M$; perdita di informazione fuori banda; più stadi con il fattore grande per primo.
3. Descrivi la conversione di frequenza con rapporto razionale e commenta le proprietà del sistema. Traccia: cascata $\uparrow L$, filtro, $\downarrow M$ ($L$, $M$ coprimi), $F_s''=LF_s=MF_s'$, filtro unico con taglio $\min(\frac\pi L,\frac\pi M)$ e guadagno $L$; equazione $y[n]=\sum x[i]g[nM-iL]$ non è una convoluzione, sistema lineare periodicamente tempo-invariante, periodo $\operatorname{mcm}(T,T')$; esempio $44{,}1\to48$ kHz con $L=160$, $M=147$; ordine dei blocchi; realizzazione polifase.