Formulario · Multimedia Signal Processing

1. Filtri FIR e sistemi LTI

Sistemi a tempo discreto e filtri FIR

Definizione (sistema a tempo discreto, discrete-time system). È un processo che trasforma una sequenza di ingresso $x[n]$ in una sequenza di uscita $y[n]$ , e si scrive $y[n]=T\{x[n]\}$ . In generale $y[n]$ dipende da tutto l'ingresso: passato, presente e futuro.

Definizione (campione unitario o impulso unitario, unit sample). $\delta[n]=\begin{cases}1&n=0\\0&n\neq0\end{cases}$ (il delta di Kronecker, non il delta di Dirac: qui vale $1$ , non è una distribuzione, vedi Impulso ideale (delta di Dirac)).

Definizione (gradino unitario, unit step). $u[n]=1$ per $n\ge0$ e $0$ per $n<0$ .

Esempio. La sequenza $x=\{2,4,6,4,2\}$ per $n=0,\dots,4$ (e zero altrove) è $x[n]=2\delta[n]+4\delta[n-1]+6\delta[n-2]+4\delta[n-3]+2\delta[n-4]$ .

Grafico interattivo: Il segnale x[n] = 2δ[n] + 4δ[n-1] + 6δ[n-2] + 4δ[n-3] + 2δ[n-4], usato negli esempi seguenti

Definizione (filtro FIR, finite impulse response). Un filtro FIR causale di ordine $M$ è il sistema $y[n]=\sum_{k=0}^{M}b_k\,x[n-k]=b_0x[n]+b_1x[n-1]+\dots+b_Mx[n-M].$ È una media mobile pesata di $L=M+1$ campioni, e $L$ è la lunghezza del filtro. I numeri $b_k$ sono i coefficienti (filter coefficients).

Sistemi LTI e convoluzione discreta

Definizione (invarianza temporale, time invariance). Un sistema è tempo-invariante se traslare l'ingresso traslando la stessa quantità l'uscita: $x[n]\to y[n]$ implica $x[n-n_0]\to y[n-n_0]$ per ogni intero $n_0$ .

Definizione (linearità, linearity). Se $x_1\to y_1$ e $x_2\to y_2$ allora $\alpha x_1+\beta x_2\to\alpha y_1+\beta y_2$ per ogni $\alpha,\beta$ . Sono due proprietà insieme: scalamento (raddoppiare $x$ raddoppia $y$ ) e sovrapposizione (la risposta a una somma è la somma delle risposte).

Definizione (sistema LTI). Un sistema lineare e tempo-invariante (linear time-invariant).

Esempio svolto ( $y[n]=n\,x[n]$ ). Percorso A: $y[n-n_0]=(n-n_0)\,x[n-n_0]$ . Percorso B: $w[n]=x[n-n_0]$ e poi $n\,w[n]=n\,x[n-n_0]$ . I due risultati sono diversi (il coefficiente $n$ nel secondo non è stato traslato), quindi non è tempo-invariante. Controllo numerico: con $x=\delta[n]$ e $n_0=1$ il percorso A dà $(n-1)\delta[n-1]=0$ , il percorso B dà $n\,\delta[n-1]=\delta[n-1]$ .

Formula (somma di convoluzione, convolution sum). $y[n]=x[n]*h[n]=\sum_{k=-\infty}^{\infty}x[k]\,h[n-k]=\sum_{k=-\infty}^{\infty}x[n-k]\,h[k].$ Un sistema LTI è completamente determinato da $h[n]$ . Nel corso la convoluzione si indica con $*$ (sulle slide anche $\circledast$ ).

Esempio. $x*\delta[n-n_0]=x[n-n_0]$ : convolvere con un impulso traslato traslare il segnale. Per questo un ritardo di $n_0$ campioni è l'LTI con $h=\delta[n-n_0]$ .

Teorema (proprietà algebriche). Commutativa $x*h=h*x$ ; associativa $(x_1*x_2)*x_3=x_1*(x_2*x_3)$ ; distributiva $x*(h_1+h_2)=x*h_1+x*h_2$ .

Esempio. $a=\{1,2\}$ , $b=\{3,0,1\}$ , $c=\{1,-1\}$ : $(a*b)*c=a*(b*c)=\{3,3,-5,1,-2\}$ (verificato).

2. Risposta in frequenza dei filtri FIR

Risposta in frequenza dei sistemi FIR

Definizione (risposta in frequenza, frequency response). $\mathcal H(\hat\omega)=H(e^{j\hat\omega})=\sum_{k=0}^{M}b_k\,e^{-j\hat\omega k}=\sum_{k=0}^{M}h[k]\,e^{-j\hat\omega k}.$ Con questa definizione, per ingresso $x[n]=Ae^{j\phi}e^{j\hat\omega n}$ l'uscita è $y[n]=\mathcal H(\hat\omega)\,A\,e^{j\phi}\,e^{j\hat\omega n}$ .

Esempio. Per $\{b_k\}=\{1,2,1\}$ : $\mathcal H(\hat\omega)=1+2e^{-j\hat\omega}+e^{-j2\hat\omega}$ . A $\hat\omega=\frac\pi3$ : $1+2e^{-j\pi/3}+e^{-j2\pi/3}=1+(1-j\sqrt3)+(-\tfrac12-j\tfrac{\sqrt3}2)=\tfrac32-j\tfrac{3\sqrt3}2$ , di modulo $3$ e fase $-\frac\pi3$ (verificato). Quindi con $x[n]=2e^{j\pi/4}e^{j\pi n/3}$ si ha $y[n]=3e^{-j\pi/3}\cdot2e^{j\pi/4}e^{j\pi n/3}=6\,e^{j\pi/4}e^{j\frac\pi3(n-1)}$ : ampiezza triplicata e ritardo di un campione.

Formula (media mobile e nucleo di Dirichlet). $\mathcal H(\hat\omega)=D_L(\hat\omega)\,e^{-j\hat\omega(L-1)/2}$ con $D_L(\hat\omega)=\dfrac{\sin(L\hat\omega/2)}{L\sin(\hat\omega/2)}$ (forma di Dirichlet), $D_L(0)=1$ .

Esempio ( $L=5$ ). $\mathcal H=D_5(\hat\omega)e^{-j2\hat\omega}$ . In $\hat\omega=0{,}3\pi$ la fase è $-0{,}6\pi$ ( $D_5>0$ ). In $\hat\omega=0{,}5\pi$ : $D_5=\frac{\sin(5\pi/4)}{5\sin(\pi/4)}=-0{,}2<0$ e la fase è $-\pi+\pi=0$ (verificato).

Grafico interattivo: Media mobile a 11 punti: |D_11(ω)| = |sin(11ω/2) / (11 sin(ω/2))|; zeri in ω = 2πk/11 (0,571; 1,142; ...), lobo principale largo 4π/11, lobi laterali di altezza ≈ 0,22

Risposta a regime e transitorio

Teorema (regime e transitorio di un FIR). Sia $x[n]=Xe^{j\hat\omega n}u[n]$ (con $X=Ae^{j\phi}$ ) l'ingresso di un FIR di ordine $M$ con risposta impulsiva $h[k]$ , $k=0,\dots,M$ . L'uscita è $y[n]=\begin{cases}0&n<0\\[2pt]\Big(\sum_{k=0}^{n}h[k]e^{-j\hat\omega k}\Big)Xe^{j\hat\omega n}&0\le n<M\\[2pt]\mathcal H(\hat\omega)\,Xe^{j\hat\omega n}&n\ge M\end{cases}$

Esempio svolto ( $M=4$ ). $\{b_k\}=\{1,-2,4,-2,1\}$ e $x[n]=\cos(0{,}2\pi n-\pi)u[n]$ . A $\hat\omega=0{,}2\pi$ il filtro ha $\mathcal H(0{,}2\pi)=e^{-j4\pi\cdot0{,}2}\,(4-4\cos0{,}2\pi+2\cos0{,}4\pi)=1{,}382\,e^{-j0{,}4\pi}$ (modulo $4-3{,}236+0{,}618=1{,}382$ ). Il regime è $y[n]=1{,}382\cos(0{,}2\pi n-\pi-0{,}4\pi)$ per $n\ge4$ . Per $n=0,1,2,3$ l'uscita è la somma incompleta: confrontandola con la formula del regime la differenza è $-0{,}573;\ 2{,}309;\ -1{,}309;\ 0{,}809$ , e da $n=4$ in poi vale esattamente $0$ (verificato con Python).

3. Trasformata zeta e funzione di sistema

Trasformata zeta - definizione e regione di convergenza

Definizione (trasformata zeta bilatera, two-sided z-transform). Per una sequenza $x[n]$ , $n\in\mathbb Z$ (con $T=1$ ), $X(z)=\sum_{n=-\infty}^{\infty}x[n]\,z^{-n},\qquad z\in R_X\subset\mathbb C,$ dove $R_X$ è la regione di convergenza: l'insieme dei $z$ in cui la serie converge.

Definizione (trasformata unilatera, one-sided). $X^+(z)=\sum_{n=0}^{\infty}x[n]z^{-n}$ .

Esempio. $x[n]=\delta[n]$ ha $X(z)=1$ in tutto il piano. $x[n]=\delta[n-1]$ ha $X(z)=z^{-1}$ (definita per $z\ne0$ ); $x[n]=\delta[n+1]$ ha $X(z)=z$ (definita per $\lvert z\rvert<\infty$ , cioè tutto $\mathbb C$ ma non l'infinito).

Teorema (Abel). Se $\sum_{n\ge0}x[n]z_0^{-n}$ converge in $z_0=r_0e^{j\theta_0}$ , allora converge (assolutamente) per ogni $z$ con $\lvert z\rvert>r_0$ ; se non converge in $z_0$ , non converge per nessun $z$ con $\lvert z\rvert<r_0$ .

Formula (esponenziale causale). $a^nu[n]\ \longleftrightarrow\ \dfrac1{1-az^{-1}}=\dfrac z{z-a},\qquad\lvert z\rvert>\lvert a\rvert.$

Formula (esponenziale anticausale). $-a^nu[-n-1]\ \longleftrightarrow\ \dfrac1{1-az^{-1}},\qquad\lvert z\rvert<\lvert a\rvert.$

Esempio. $x[n]=(0{,}5)^nu[n]$ ha $X(z)=\frac1{1-0{,}5z^{-1}}$ , $\lvert z\rvert>0{,}5$ : nel punto $z=1$ la serie $\sum0{,}5^n=2$ coincide con $\frac1{1-0{,}5}=2$ (verificato). La sequenza $-(0{,}5)^nu[-n-1]$ ha la stessa $X(z)$ ma ROC $\lvert z\rvert<0{,}5$ : in $z=0{,}25$ la serie $-\sum_{m\ge1}2^m\,0{,}25^m=-\sum(0{,}5)^m=-1$ coincide con $\frac1{1-0{,}5\cdot4}=-1$ (verificato).

Grafico interattivo: Piano z: ROC di (0,5)^n u[n] (esterno della circonferenza di raggio 0,5, zona colorata) con il polo in 0,5 (x), lo zero in 0 (o) e la circonferenza unitaria tratteggiata; la ROC contiene la circonferenza unitaria, quindi il sistema è stabile

Proprietà della trasformata zeta

Proprietà (linearità). Se $x\leftrightarrow X$ (ROC $R_X$ ) e $y\leftrightarrow Y$ (ROC $R_Y$ ), allora $\alpha x+\beta y\leftrightarrow\alpha X(z)+\beta Y(z)$ con ROC contenente $R_X\cap R_Y$ .

Proprietà (ritardo). $x[n-n_0]\leftrightarrow z^{-n_0}X(z)$ , con la stessa ROC (con la possibile esclusione dell'origine e inclusione dell'infinito).

Esempio. $\delta[n-1]\to z^{-1}$ (ROC $z\ne0$ ), $\delta[n+1]\to z$ (ROC senza infinito). Un FIR $y[n]=\sum b_kx[n-k]$ ha $Y=\big(\sum b_kz^{-k}\big)X$ : la funzione di sistema è il polinomio (vedi Funzione di sistema, poli, zeri e stabilità).

Proprietà (convoluzione). $x[n]*h[n]\leftrightarrow X(z)H(z)$ , con ROC $\supseteq R_X\cap R_H$ .

Proprietà (stabilità). Il sistema è BIBO stabile se e solo se la ROC di $H(z)$ contiene la circonferenza unitaria $\{\lvert z\rvert=1\}$ .

Proprietà (time reversal). $x[-n]\leftrightarrow X(z^{-1})$ , ROC $\{\frac1{R_2}<\lvert z\rvert<\frac1{R_1}\}$ (raggi invertiti).

Esempio. $a^nu[n]\to\frac1{1-az^{-1}}$ , $\lvert z\rvert>\lvert a\rvert$ . Allora $a^{-n}u[-n]\to\frac1{1-az}$ con ROC $\lvert z\rvert<\frac1{\lvert a\rvert}$ : infatti $\sum_{n\le0}a^{-n}z^{-n}=\sum_{m\ge0}(az)^m$ , geometrica di ragione $az$ (verificato numericamente con $a=0{,}6$ ).

Proprietà (derivazione). $n\,x[n]\leftrightarrow-z\dfrac{dX(z)}{dz}$ , stessa ROC. Iterando: $n^2x[n]\leftrightarrow-z\frac{d}{dz}\big(-z\frac{dX}{dz}\big)$ .

Esempio. Da $a^nu[n]\to\frac1{1-az^{-1}}$ : $-z\frac{d}{dz}\frac1{1-az^{-1}}=\frac{az^{-1}}{(1-az^{-1})^2}$ , ovvero $n\,a^nu[n]\leftrightarrow\dfrac{az^{-1}}{(1-az^{-1})^2}$ , $\lvert z\rvert>\lvert a\rvert$ (verificato numericamente con $a=0{,}6$ , $z=1{,}7e^{0{,}9j}$ ). È la coppia che serve per i poli doppi.

Proprietà (scalamento in $z$ ). $a^nx[n]\leftrightarrow X(z/a)$ con ROC $\{\lvert a\rvert R_1<\lvert z\rvert<\lvert a\rvert R_2\}$ .

Teorema (valore iniziale). $x[0]=\lim_{z\to\infty}X^+(z)$ .

Teorema (valore finale). Sia $W(z)=(1-z^{-1})X^+(z)$ . Se la ROC di $W$ contiene $z=1$ , allora $\lim_{n\to\infty}x[n]=\lim_{z\to1}(1-z^{-1})X^+(z)$ .

Esempio. $x[n]=(2-0{,}5^n)u[n]$ , $X=\frac2{1-z^{-1}}-\frac1{1-0{,}5z^{-1}}$ : $(1-z^{-1})X\to2$ per $z\to1$ , e $x[n]\to2$ (verificato). Controesempi: $(-1)^nu[n]$ ha $(1-z^{-1})\frac1{1+z^{-1}}\to0$ ma la successione non ha limite (polo in $-1$ sul cerchio); $2^nu[n]$ ha $(1-z^{-1})\frac1{1-2z^{-1}}\to0$ ma $x[n]\to\infty$ (polo fuori dal cerchio). Il teorema vale solo se la ROC di $W$ contiene $z=1$ .

Antitrasformata zeta

Formula (inversione della zeta). $x[n]=\dfrac1{2\pi j}\displaystyle\oint_CX(z)\,z^{n-1}\,dz$ , con $C$ una qualsiasi curva chiusa semplice, antioraria, che circonda l'origine e sta dentro la ROC (per il teorema di Cauchy il risultato non dipende dalla curva: Integrale di linea complesso e teorema di Cauchy).

Esempio. $X(z)=\frac1{1-0{,}5z^{-1}}$ , $\lvert z\rvert>0{,}5$ : $X(z)z^{n-1}=\frac{z^n}{z-0{,}5}$ . Per $n\ge0$ l'unico polo dentro $C$ è $0{,}5$ , residuo $0{,}5^n$ : $x[n]=0{,}5^n$ ( $n\ge0$ ). Per $n<0$ compare anche un polo in $z=0$ di ordine $-n$ e la somma dei residui dà $0$ (la ROC è esterna: segnale causale). Nella pratica il calcolo con i residui si usa poco: si usano i metodi seguenti.

Funzione di sistema, poli, zeri e stabilità

Definizione (funzione di sistema di un FIR). $H(z)=\displaystyle\sum_{k=0}^{M}b_kz^{-k}=\sum_{k=0}^{M}h[k]z^{-k}$ , la trasformata zeta della risposta impulsiva. Con ingresso $z^n$ l'uscita è $h[n]*z^n=H(z)z^n$ .

Teorema (stabilità di un LTI causale). Un sistema causale è BIBO stabile se e solo se tutti i poli di $H(z)$ stanno dentro il cerchio unitario, $\max_k\lvert p_k\rvert<1$ (a meno di cancellazioni polo-zero).

Esempio (FIR dato dagli zeri). $H(z)=(1-z^{-1})(1+z^{-2})(1-0{,}9z^{-1}+0{,}81z^{-2})$ , che espanso dà $1-1{,}9z^{-1}+2{,}71z^{-2}-2{,}71z^{-3}+1{,}71z^{-4}-0{,}81z^{-5}$ , è un FIR di ordine $5$ con cinque zeri in $1,\ \pm j,\ 0{,}9e^{\pm j\pi/3}$ e cinque poli in $0$ (verificato). Solo gli zeri sulla circonferenza unitaria ( $1$ e $\pm j$ ) annullano l'uscita per un ingresso esponenziale $e^{j\hat\omega n}$ , cioè per $\hat\omega=0,\pm\frac\pi2$ (Esercizio - Esercitazione 9 - funzione di sistema e zeri).

4. Fase lineare e filtri FIR simmetrici

Sistemi a fase lineare e assenza di distorsione

Definizione (condizione di non distorsione, no distortion condition). Un sistema LTI causale non distorce se $y[n]=K\,x[n-n_0],\qquad K\in\mathbb R\setminus\{0\},\ n_0\in\mathbb N,$ cioè se l'uscita è una copia scalata e ritardata dell'ingresso.

Esempio. Con $K=2$ , $n_0=3$ e $x=\{1,4,2\}$ (da $n=0$ ) si ha $y[3]=2,\ y[4]=8,\ y[5]=4$ : stessa forma, ampiezza doppia, tre campioni dopo.

Definizione (ritardo di gruppo, group delay). $\tau(\hat\omega)=-\frac{d\varphi(\hat\omega)}{d\hat\omega}.$ Misura di quanti campioni viene ritardato l'inviluppo di un segnale a banda stretta attorno a $\hat\omega$ .

Esempio. Per la fase $\varphi=-n_0\hat\omega$ si ha $\tau=n_0$ , costante: tutte le frequenze subiscono lo stesso ritardo, e per questo la forma si conserva. Se $\tau$ dipendesse da $\hat\omega$ , le componenti del segnale arriverebbero sfasate l'una rispetto all'altra e la forma d'onda cambierebbe (distorsione di fase).

Definizione (fase lineare generalizzata, generalized linear phase). Un sistema ha fase lineare se la sua risposta in frequenza si scrive $H(e^{j\hat\omega})=A(\hat\omega)\,e^{-j\alpha\hat\omega}\,e^{j\beta},$ con $\alpha,\beta$ costanti reali e $A(\hat\omega)$ funzione reale (detta amplitude response o zero-phase response), che può anche cambiare segno.

Esempio. Il filtro $h=\{1,2,3,2,1\}$ ha $H(e^{j\hat\omega})=e^{-j2\hat\omega}\,(3+4\cos\hat\omega+2\cos2\hat\omega)$ : qui $\alpha=2$ , $\beta=0$ e $A(\hat\omega)=3+4\cos\hat\omega+2\cos 2\hat\omega=(1+2\cos\hat\omega)^2$ . In $\hat\omega=0$ : $A=9=\sum h[n]$ .

Teorema (fase lineare e simmetria). Un sistema LTI discreto, reale e causale ha fase lineare (generalizzata) se e solo se è un filtro FIR di ordine $N$ la cui risposta impulsiva soddisfa $h[n]=h[N-n]\ \ (\text{simmetrica, } \beta=0)\qquad\text{oppure}\qquad h[n]=-h[N-n]\ \ (\text{antisimmetrica, } \beta=\tfrac\pi2),\qquad n=0,\dots,N,$ e in entrambi i casi $\alpha=N/2$ . Il filtro ha $N+1$ coefficienti.

Esempio. $h=\{3,-1,4,-1,3\}$ è simmetrica ( $N=4$ ): ha fase lineare con ritardo $2$ . $h=\{2,1,0,-1,-2\}$ è antisimmetrica ( $N=4$ , centro $h[2]=0$ ): ritardo $2$ , fase $-2\hat\omega+\pi/2$ .

Filtri FIR a fase lineare - tipi e zeri

Formula (ampiezza dei quattro tipi).

Tipo I ( $N$ pari, simmetrica): $A(\hat\omega)=h\!\left[\tfrac N2\right]+2\sum_{k=1}^{N/2}h\!\left[\tfrac N2-k\right]\cos(k\hat\omega)=\sum_{k=0}^{N/2}a_k\cos(k\hat\omega)$ , con $a_0=h[N/2]$ e $a_k=2h[N/2-k]$ .

Tipo II ( $N$ dispari, simmetrica): $A(\hat\omega)=2\sum_{k=1}^{(N+1)/2}h\!\left[\tfrac{N+1}2-k\right]\cos\!\big((k-\tfrac12)\hat\omega\big)$ .

Tipo III ( $N$ pari, antisimmetrica): $A(\hat\omega)=2\sum_{k=1}^{N/2}h\!\left[\tfrac N2-k\right]\sin(k\hat\omega)$ .

Tipo IV ( $N$ dispari, antisimmetrica): $A(\hat\omega)=2\sum_{k=1}^{(N+1)/2}h\!\left[\tfrac{N+1}2-k\right]\sin\!\big((k-\tfrac12)\hat\omega\big)$ .

Grafico interattivo: Ampiezza A(w) di un esempio per tipo: I (N=4), II {1,2,2,1}, III {1,1,0,-1,-1}, IV {1,2,-2,-1}. Il tipo II si annulla in w = π, i tipi III e IV in w = 0, il tipo III anche in π

Teorema (posizione degli zeri). Sia $h$ reale e $h[n]=\pm h[N-n]$ .

Se $z_0\neq0$ è uno zero, lo è anche $1/z_0$ (zero reciproco).

Se $z_0$ è uno zero, lo è anche $z_0^*$ (coniugato), perché $h$ è reale.

Quindi uno zero complesso fuori dalla circonferenza unitaria genera una quaterna $\{z_0,\ z_0^*,\ 1/z_0,\ 1/z_0^*\}$ .

Uno zero sulla circonferenza unitaria, $z_0=e^{j\theta}$ , ha reciproco $1/z_0=z_0^*$ (già incluso): gli zeri sulla circonferenza vengono in coppie $\{e^{j\theta},e^{-j\theta}\}$ .

Uno zero reale $z_0\ne\pm1$ viene in coppie $\{z_0,1/z_0\}$ .

Gli zeri in $z=1$ e $z=-1$ sono il proprio reciproco e il proprio coniugato: possono comparire da soli.

Esempio (quaterna). Zeri in $0.8e^{\pm j\pi/4}$ e in $1.25e^{\pm j\pi/4}$ : il polinomio è $(1-1.1314z^{-1}+0.64z^{-2})(1-1.7678z^{-1}+1.5625z^{-2})$ , cioè $h=\{1,\ -2.8991,\ 4.2025,\ -2.8991,\ 1\}$ , di tipo I (simmetrico) come previsto. Il fattore $1.1314=2\cdot0.8\cos\frac\pi4$ è la somma dei due zeri $0.8e^{\pm j\pi/4}$ e $0.64=0.8^2$ il loro prodotto.

Teorema (zeri forzati).

Tipo I: nessun vincolo.

Tipo II: zero in $z=-1$ (cioè $A(\pi)=0$ ).

Tipo III: zeri in $z=1$ e in $z=-1$ .

Tipo IV: zero in $z=1$ (e non in $z=-1$ ).

Grafico interattivo: Zeri di un FIR di tipo I (quaterna 0.8 e^(±jπ/4) e 1.25 e^(±jπ/4)): nessuno zero forzato. Parte reale in ascissa, immaginaria in ordinata

5. Filtri notch e applicazioni dei FIR

Filtri notch e applicazioni dei filtri FIR

Formula (notch FIR del secondo ordine). Per eliminare una sinusoide alla pulsazione normalizzata $\hat\omega_0$ : $H(z)=1-2\cos(\hat\omega_0)z^{-1}+z^{-2},\qquad h=\{1,\ A,\ 1\},\quad A=-2\cos\hat\omega_0,$ con equazione alle differenze $y[n]=x[n]+A\,x[n-1]+x[n-2]$ . In frequenza $H(e^{j\hat\omega})=e^{-j\hat\omega}\big(2\cos\hat\omega-2\cos\hat\omega_0\big).$

Esempio. Per $\hat\omega_0=\pi/4$ : $A=-\sqrt2\approx-1.4142$ e $h=\{1,-1.4142,1\}$ . Con $x[n]=\cos(\frac\pi4n+0.7)$ le uscite sono $y[0]=0.7648$ , $y[1]=-0.9964$ e poi $y[n]=0$ per $n\ge2$ (calcolato con Python, errore sotto $10^{-14}$ ): il tono scompare dopo due campioni.

6. DFT e convoluzione a blocchi

Trasformata di Fourier discreta (DFT) e convoluzione circolare

Definizione (DFT e IDFT, con $T=1$ ). $X[k]=\sum_{n=0}^{N-1}x[n]\,e^{-j2\pi kn/N},\qquad x[n]=\frac1N\sum_{k=0}^{N-1}X[k]\,e^{j2\pi kn/N},\qquad k,n=0,\dots,N-1.$ Con la notazione $W_N=e^{-j2\pi/N}$ (radice $N$ -esima primitiva dell'unità): $X[k]=\sum_nx[n]W_N^{kn}$ e $x[n]=\frac1N\sum_kX[k]W_N^{-kn}$ . Gli estremi delle somme possono essere qualsiasi $N$ interi consecutivi, perché i termini sono periodici.

Esempio. $x=\{1,2,3,4\}$ , $N=4$ : $X[0]=1+2+3+4=10$ ; $X[1]=1+2(-j)+3(-1)+4(j)=-2+2j$ ; $X[2]=1-2+3-4=-2$ ; $X[3]=-2-2j$ . Si ottiene $X=\{10,\ -2+2j,\ -2,\ -2-2j\}$ (verificato con Python, con l'IDFT che restituisce $x$ ).

Teorema (DFT = campionamento della zeta sulla circonferenza). Per $N\ge M$ , la DFT a $N$ punti di $x[n]$ è $X[k]=X(z)\Big|_{z=e^{j2\pi k/N}}=X\big(e^{j\hat\omega}\big)\Big|_{\hat\omega=2\pi k/N},\qquad k=0,\dots,N-1,$ cioè la zeta valutata nelle $N$ radici $N$ -esime dell'unità: $N$ punti equispaziati sulla circonferenza unitaria a partire da $z=1$ .

Esempio. $x=\{1,1,1,1\}$ e $N=8$ : $X[k]=\frac{\sin(\pi k/2)}{\sin(\pi k/8)}e^{-j3\pi k/8}$ , con moduli $\{4,\ 2.613,\ 0,\ 1.082,\ 0,\ 1.082,\ 0,\ 2.613\}$ .

Proprietà della DFT ( $x[n]\leftrightarrow X[k]$ , $N$ punti).

Linearità: $\alpha x+\beta y\leftrightarrow\alpha X+\beta Y$ .

Traslazione circolare (circular shift): $x[(n-n_0)_N]\leftrightarrow e^{-j2\pi kn_0/N}X[k]$ : il modulo non cambia, la fase sì. Traslare di $N$ campioni (o multipli) non cambia il segnale.

Simmetria coniugata: se $x$ è reale, $X[k]=X^*[N-k]$ ( $=X^*[(-k)_N]$ ): parte reale pari, parte immaginaria dispari, modulo pari, fase dispari. Allora $X[0]=\sum x[n]$ è reale e, se $N$ è pari, anche $X[N/2]=\sum x[n](-1)^n$ è reale. Bastano $\lfloor N/2\rfloor+1$ valori complessi per descrivere la DFT di un segnale reale.

Convoluzione circolare: $X[k]H[k]\leftrightarrow y[n]=\sum_{\ell=0}^{N-1}x[\ell]\,h[(n-\ell)_N]=(x\circledast h)[n]$ .

Parseval: $\sum_n\lvert x[n]\rvert^2=\frac1N\sum_k\lvert X[k]\rvert^2$ .

Esempio (traslazione). $x=\{1,2,3,4\}$ , $X=\{10,-2+2j,-2,-2-2j\}$ . Il segnale traslato di un campione, $x[(n-1)_4]=\{4,1,2,3\}$ , ha DFT $\{10,\ 2+2j,\ 2,\ 2-2j\}$ , uguale a $X[k]e^{-j2\pi k/4}$ : i moduli sono invariati ( $10,\ 2\sqrt2,\ 2,\ 2\sqrt2$ ).

Teorema (convoluzione lineare tramite DFT). Se $x$ ha lunghezza $D_x$ e $h$ lunghezza $M$ , e si sceglie $N\ \ge\ D_y=D_x+M-1,$ allora, dopo aver completato $x$ e $h$ con zeri fino a $N$ campioni, la convoluzione circolare a $N$ punti coincide con quella lineare: $y_{\rm lin}[n]=y_{\rm circ}[n]$ per $0\le n\le N-1$ . Con $N<D_y$ la coda di $y_{\rm lin}$ (gli ultimi $D_y-N$ campioni) si ripiega sull'inizio.

Esempio (lezione). $x=\{1,2,3,4\}$ e $h=\{1,1,1,1\}$ . Convoluzione lineare: $y_{\rm lin}=\{1,3,6,10,9,7,4\}$ , lunghezza $4+4-1=7$ . Convoluzione circolare con $N=4$ : $y_{\rm circ}=\{10,10,10,10\}$ (lunghezza $4$ ): infatti $y_{\rm circ}[0]=y_{\rm lin}[0]+y_{\rm lin}[4]=1+9$ , $y_{\rm circ}[1]=3+7$ , $y_{\rm circ}[2]=6+4$ e $y_{\rm circ}[3]=10$ : le somme valgono tutte $10$ . Per evitare l'aliasing si completa con zeri a $N=8\ge7$ ( $x=\{1,2,3,4,0,0,0,0\}$ , $h=\{1,1,1,1,0,0,0,0\}$ ) e si ottiene $y_{\rm circ}=\{1,3,6,10,9,7,4,0\}=y_{\rm lin}$ più uno zero.

Grafico interattivo: Convoluzione lineare di x = {1,2,3,4} con h = {1,1,1,1}: y = {1, 3, 6, 10, 9, 7, 4}, lunghezza 7

7. Analisi spettrale e spettrogramma

Trasformata di Fourier a tempo breve e spettrogramma

Definizione (STFT, "DFT dipendente dal tempo"). Sia $x[n]$ una sequenza lunga e $w[n]$ una finestra di analisi (analysis window, per esempio di Hann) diversa da zero solo per $n=0,\dots,L-1$ , con $L$ molto minore della lunghezza di $x$ . Per ogni istante di analisi $\ell$ si definisce $X[k,\ell]=\sum_{n=0}^{L-1}w[n]\,x[\ell+n]\,e^{-j2\pi kn/N},\qquad k=0,1,\dots,N-1,\quad N\ge L.$

Esempio. Un segnale di $D=10\,000$ campioni, finestra $L=301$ , passo $R=30$ ( $\approx0.1L$ ) e $N=1024$ : $\lfloor(10000-301)/30\rfloor+1=324$ frame; per un segnale reale bastano i bin $k=0,\dots,512$ ( $N/2+1=513$ valori) per la simmetria coniugata. Con $L=75$ e $R=8$ : $1241$ frame. Il numero di valori calcolati è $324\times513$ , circa $1.7\cdot10^5$ : ogni frame costa una FFT a $N=1024$ punti (Trasformata di Fourier discreta (DFT) e convoluzione circolare).

8. Progetto di filtri FIR

Progetto di filtri FIR con il metodo delle finestre

Definizione (specifiche del passa-basso).

$\hat\omega_p$ : limite della banda passante (pass-band edge); per $|\hat\omega|\le\hat\omega_p$ il segnale passa praticamente inalterato.

$\hat\omega_s$ : limite della banda oscura (stop-band edge); per $\hat\omega_s\le|\hat\omega|\le\pi$ il segnale è fortemente soppresso. Per $\hat\omega_p<|\hat\omega|<\hat\omega_s$ si è in banda di transizione e non si impone nulla.

$\delta_p$ : errore in banda passante, $1-\delta_p\le|H(e^{j\hat\omega})|\le1+\delta_p$ (l'ideale sarebbe $|H|=1$ ).

$\delta_s$ : errore in banda oscura, $|H(e^{j\hat\omega})|\le\delta_s$ (l'ideale sarebbe $|H|=0$ ).

In decibel: ondulazione in banda passante (pass-band ripple) $R_p=20\log_{10}\dfrac{1+\delta_p}{1-\delta_p}$ e attenuazione in banda oscura (stop-band attenuation) $A_s=-20\log_{10}\delta_s$ .

Esempio. Con $\delta_p=\delta_s=10^{-2.5}=0{,}00316$ si ha $A_s=50$ dB e $R_p=20\log_{10}\frac{1{,}00316}{0{,}99684}=0{,}055$ dB. Con $\delta_p=0{,}05$ e $\delta_s=0{,}01$ si ha $R_p=20\log_{10}\frac{1{,}05}{0{,}95}=0{,}87$ dB e $A_s=40$ dB.

Teorema (i tre metodi).

Finestre (windowing, o troncamento della serie di Fourier): si usa una somma parziale della serie di $D$ .

Campionamento in frequenza (frequency sampling): $h$ è l'IDFT di campioni di $D$ , quindi $H$ coincide con $D$ solo su quei campioni.

Minimax (algoritmo di Parks-McClellan): si cercano i coefficienti che minimizzano il massimo dell'errore pesato $W(\hat\omega)\,|D(\hat\omega)-\bar H(\hat\omega)|$ ; il peso $W$ permette errori diversi nelle diverse bande. I filtri risultanti sono equiripple.

Teorema (ottimalità). Fra tutti i filtri FIR a fase lineare di ordine $N=2r$ , la somma parziale $\bar H(\hat\omega)=\sum_{n=-r}^{r}h_d[n]e^{-j\hat\omega n}$ minimizza l'errore quadratico medio $E^2=\frac1{2\pi}\int_{-\pi}^{\pi}\big(D(\hat\omega)-\bar H(\hat\omega)\big)^2d\hat\omega$ .

Esempio. Con $\hat\omega_0=\pi/3$ il massimo di $\bar H$ è $1{,}0706$ per $L=21$ , $1{,}0928$ per $L=61$ , $1{,}0908$ per $L=151$ e $1{,}0900$ per $L=401$ : il sovraelongo converge a circa il 9% del salto (con minimo $-0{,}089$ nella banda oscura), come si vede nel grafico. L'errore in banda passante e in banda oscura è circa $\delta_p\simeq\delta_s\simeq0{,}09$ , cioè $A_s\simeq21$ dB, e non dipende da $L$ . Quello che dipende da $L$ è la larghezza della transizione, circa $0{,}9\cdot\frac{2\pi}{L}$ , e la rapidità delle oscillazioni.

Grafico interattivo: Passa-basso con ω0 = π/3 progettato con la finestra rettangolare: aumentando L le oscillazioni si stringono ma il sovraelongo (circa 9%) resta; con Hamming scompaiono

Teorema (alternanza). Sia $\bar H(\hat\omega)=\sum_{n=0}^{r}p_n\cos(n\hat\omega)$ una combinazione di $r+1$ coseni e $E(\hat\omega)=W(\hat\omega)(D(\hat\omega)-\bar H(\hat\omega))$ . $\bar H$ è la soluzione del problema minimax se e solo se $E$ ha almeno $r+2$ alternanze, cioè punti $\hat\omega_0<\dots<\hat\omega_{r+1}$ in $I$ con $E(\hat\omega_i)=-E(\hat\omega_{i+1})$ e $|E(\hat\omega_i)|=\max_I|E|$ .

Esempio. $N=10$ ( $r=5$ , quindi servono $7$ alternanze), banda passante $[0,0{,}3\pi]$ , banda oscura $[0{,}4\pi,\pi]$ , pesi uguali. scipy.signal.remez dà $h=\{-0{,}0338,-0{,}1353,-0{,}0002,0{,}1237,0{,}2840,0{,}3493,\dots\}$ (simmetrica) con errore massimo $0{,}1742$ in entrambe le bande. I punti di errore massimo sono $\hat\omega/\pi=0;\,0{,}191;\,0{,}3;\,0{,}4;\,0{,}514;\,0{,}734;\,1$ con segni $-,+,-,+,-,+,-$ : sono proprio $7$ , di cui $4$ ai bordi delle bande. Con peso $1:10$ (banda oscura più importante) gli errori diventano $0{,}4926$ e $0{,}0494$ , in rapporto $9{,}97\simeq10$ .

Grafico interattivo: Minimax con N = 10, banda passante [0, 0,3π], banda oscura [0,4π, π]: l'errore oscilla con ampiezza costante (equiripple); con peso 10 sulla banda oscura l'errore lì è dieci volte più piccolo

9. Elaborazione multirate

Elaborazione multirate - decimazione e interpolazione

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.)

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

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).

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\}$ .

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)$ .

10. Filtri IIR e trasformazione bilineare

Filtri IIR - definizione e confronto con i FIR

Definizione (filtro IIR). La classe più generale di sistemi LTI a tempo discreto realizzabili con un numero finito di operazioni è $y[n]=\sum_{\ell=1}^{N}a_\ell\,y[n-\ell]+\sum_{k=0}^{M}b_k\,x[n-k].$ I $N$ coefficienti $a_\ell$ sono i coefficienti di retroazione (feedback coefficients), gli $M+1$ coefficienti $b_k$ quelli in avanti (feed-forward coefficients). Servono $N+M+1$ coefficienti. Con $N=0$ si ricade nei FIR. L'ordine del filtro IIR è $N$ , il numero di termini di retroazione.

Esempio. $y[n]=0{,}8\,y[n-1]+5\,x[n]$ è un IIR del primo ordine con $N=M=1$ , $a_1=0{,}8$ , $b_0=5$ , $b_1=0$ .

Formula (blocco elementare). $h[n]=a_1^nu[n]\ \longleftrightarrow\ H(z)=\dfrac{1}{1-a_1z^{-1}}$ , con regione di convergenza $|z|>|a_1|$ .

Esempio. $y[n]=a_1y[n-1]+b_0x[n]+b_1x[n-1]$ ha $H(z)=\frac{b_0+b_1z^{-1}}{1-a_1z^{-1}}$ , con uno zero in $-b_1/b_0$ e un polo in $a_1$ .

Trasformazione bilineare

Definizione. La trasformazione bilineare (o di Möbius) è $s=\dfrac{\alpha z+\beta}{\gamma z+\delta}$ , con $\alpha,\beta,\gamma,\delta\in\mathbb C$ e $\alpha\delta-\beta\gamma\ne0$ . È una mappa conforme (conserva gli angoli) che porta circonferenze in circonferenze (eventualmente degeneri: rette). Imponendo che il cerchio unitario vada nell'asse immaginario si ottiene $s=\frac{z-1}{z+1},\qquad z=\frac{1+s}{1-s}.$

Esempio. $s=-0{,}5\Rightarrow z=\frac{1-0{,}5}{1+0{,}5}=\frac13$ : un polo analogico reale in $-0{,}5$ diventa un polo digitale in $\frac13$ (stabile).

11. Filtri di Butterworth

Filtri di Butterworth

Formula (Butterworth analogico). $|H_a(j\Omega)|^2=\frac{1}{1+\big(\frac{\Omega}{\Omega_0}\big)^{2N}}$ con $N$ ordine e $\Omega_0$ pulsazione di taglio a $-3$ dB. Vale $1$ in $0$ , $\frac12$ in $\Omega_0$ per ogni $N$ , ed è monotona decrescente fino a $0$ per $\Omega\to\infty$ ; per $N\to\infty$ tende al rettangolo ideale.

Esempio. Con $\Omega_0=1$ e $N=4$ : $|H_a(j0{,}5)|^2=\frac1{1+0{,}5^8}=0{,}9961$ , $|H_a(j2)|^2=\frac1{1+2^8}=0{,}00389$ (circa $-24$ dB). A $\Omega=2\Omega_0$ (un'ottava sopra il taglio) l'attenuazione è $10\log_{10}(1+2^{2N})\simeq6N$ dB: $24$ dB per $N=4$ , $48$ dB per $N=8$ .

Grafico interattivo: Butterworth analogico, |H_a(jΩ)| = 1/√(1+(Ω/Ω0)^(2N)) con Ω0 = 1: tutte le curve passano per 1/√2 ≈ 0,707 in Ω = Ω0; più N è grande, più la transizione è ripida

FormularioMultimedia Signal Processing: definizioni, teoremi e formule delle note, in ordine di capitolo