Sistemi a tempo discreto e filtri FIR

Il corso lavora in inglese e le note sono in italiano: il termine inglese compare accanto a quello italiano la prima volta, perché l'esame è scritto in inglese. In tutto il corso il passo di campionamento si prende $T=1$: il segnale è una successione $x[n]$, $n\in\mathbb Z$, e le frequenze sono normalizzate ($\hat\omega$, vedi Risposta in frequenza dei sistemi FIRSe all'ingresso di un FIR c'è un esponenziale complesso A e^{jφ} e^{jω̂n} (per ogni n), l'uscita è lo stesso esponenziale moltiplicato per H(ω̂) = Σ b_k e^{-jω̂k}: la frequenza non cambia, ampiezza e fase sono modificate da |H| (guadagno) e ∠H (sfasamento). Per sovrapposizione si trattano somme di sinusoidi. H è periodica di periodo 2π e, per coefficienti reali, hermitiana (|H| pari, fase dispari). La cascata ha H = H1·H2. Esempi: ritardo (fase lineare), differenza prima (passa-alto), {1,2,1} (passa-basso), media mobile di L punti (Dirichlet: |H| = |sin(Lω̂/2)/(L sin(ω̂/2))|, fase lineare -(L-1)ω̂/2).Risposta in frequenza dei sistemi FIR →). I segnali a tempo discreto sono già trattati in Segnali a tempo discretoUn segnale a tempo discreto è una funzione complessa $s(nT)$ definita sui multipli interi del quanto temporale $T$ (insieme $\mathbb Z(T)$, velocità $F_p=1/T$). Le definizioni sono quelle dei segnali continui con la somma al posto dell'integrale e il quanto $T$ al posto di $dt$: area $\sum T,s(nT)$, energia $\sum T|s(nT)|^2$, convoluzione $\sum T,x(kT)y(nT-kT)$. L'impulso ideale discreto vale $1/T$ nell'origine. Esponenziali e sinusoidi discreti sono periodici solo se $f_0/F_p$ è razionale e hanno frequenza ambigua a meno di multipli di $F_p$. I segnali periodici con periodo $NT$ sono descritti da $N$ valori e si trattano al calcolatore.Segnali a tempo discreto → (lì con $T$ esplicito): qui si richiama solo quello che serve e si passa subito ai filtri.

Dal segnale analogico a quello digitale

Un segnale (signal) è l'evoluzione di una grandezza fisica rispetto a una variabile indipendente (il tempo per un suono, lo spazio per una fotografia) che trasporta informazione. Lo si elabora (signal processing) per due scopi: analisi (capire o estrarre l'informazione: filtrare, togliere rumore, riconoscere strutture) e sintesi (costruire un segnale che contenga una certa informazione: musica sintetica, segnali di telefonia e radio).

Ogni segnale è una funzione, e si classifica guardando dominio (il tempo) e codominio (l'ampiezza), ciascuno continuo oppure discreto:

Un calcolatore rappresenta ed elabora esattamente solo i segnali digitali: tempo scandito dai multipli di $T$ e ampiezze prese da un insieme finito di livelli.

Lo schema di elaborazione

Lo schema base per elaborare un segnale analogico $x(t)$ è la catena: filtro passa-basso (low-pass filter, LPF) di ingresso $\to$ convertitore A/D $\to$ elaborazione numerica (DSP, digital signal processing) $\to$ convertitore D/A $\to$ LPF di uscita. Le ipotesi sono due: l'ingresso è a banda limitata (è il compito del primo LPF, che evita l'aliasing) e la frequenza di campionamento $F_s$ è almeno il doppio della banda del segnale (Teorema del campionamento, interpolazione e aliasingTeorema di Shannon: un segnale a banda limitata $\omega_M$ si ricostruisce esattamente dai campioni se $T_c<\pi/\omega_M$ (frequenza di campionamento maggiore di quella di Nyquist $2f_{\max}$), con la formula di interpolazione ideale $x(t)=\sum_nx(nT_c)\operatorname{sinc}\left(\frac{t-nT_c}{T_c}\right)$. Sotto Nyquist c'è aliasing: le frequenze alte si confondono con quelle basse e l'informazione è persa.Teorema del campionamento, interpolazione e aliasing →). Sotto queste ipotesi la catena fa quello che farebbe un circuito analogico, ma con i vantaggi sotto.

Il convertitore A/D (analog-to-digital) è un campionatore ideale seguito da un quantizzatore uniforme. Se il segnale sta in $[-V_x,V_x]$ e il convertitore ha $B$ bit, ogni campione viene sostituito dal livello $\hat x=k\,q$ più vicino, con $k$ intero e passo di quantizzazione $$q=\frac{V_x}{2^{B-1}},\qquad \lvert x-\hat x\rvert\le\frac q2 .$$ Il dato che arriva al processore è l'intero $k$; $q$ è un fattore di scala implicito.

Esempio. Con $B=16$ e $V_x=1\ \mathrm V$: $q=1/2^{15}\ \mathrm V\approx 30{,}5\ \mu\mathrm V$ e l'errore massimo è $q/2\approx 15{,}3\ \mu\mathrm V$. Un convertitore a 8 bit con la stessa dinamica darebbe $q=1/128=7{,}8\ \mathrm{mV}$.

Il convertitore D/A (digital-to-analog) fa l'operazione inversa: da $k$ produce la tensione $k\,q$ e la mantiene costante fino al campione successivo (interpolatore di ordine zero, zero-order hold), la cui risposta in frequenza è $$H_0(f)=\frac{1-e^{-j2\pi fT}}{j2\pi f}=T\,\mathrm{sinc}(fT)\,e^{-j\pi fT}.$$ L'uscita è quindi un segnale a "scalini", a tempo continuo e ampiezza discreta, che il LPF finale liscia (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 →).

Perché il digitale

1. Precisione: dipende solo dal numero di bit con cui si rappresentano i numeri, e con registri lunghi diventa praticamente illimitata a basso costo.
2. Affidabilità (reliability): un sistema digitale che funziona esegue sempre le stesse operazioni e dà sempre lo stesso risultato; non risente di deriva termica né di rumore.
3. Adattività (adaptivity): per cambiare il comportamento di un filtro si cambiano numeri in memoria, non componenti.

L'esempio classico è la trasmissione. Un canale attenua di un fattore $G<1$ e aggiunge rumore $\sigma(t)$: il ricevitore vede $Gx(t)+\sigma(t)$. Con un segnale analogico il ricevitore può solo riamplificare di $1/G$ e ottiene $x(t)+\sigma(t)/G$: il segnale è a posto ma il rumore è stato amplificato insieme a lui. In una linea lunga con $N$ ripetitori ogni tratta aggiunge il suo rumore, che si accumula: per esempio con $G=0{,}5$ e rumore indipendente di deviazione standard $1$ per tratta, dopo $N=10$ tratte la deviazione standard del rumore è $\sqrt{10}\cdot 1/0{,}5\approx 6{,}3$ (è $\sqrt N\,\sigma/G$ perché le potenze di rumori indipendenti si sommano). Con un segnale digitale (per esempio $\pm A$) il ripetitore applica una soglia, $\hat x=\mathrm{sgn}[Gx+\sigma]$, e rigenera il segnale pulito: finché il rumore non è abbastanza forte da cambiare il segno, l'errore viene cancellato a ogni tratta invece di accumularsi.

Sistemi a tempo discreto

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.

Tutti i sistemi del corso hanno un solo ingresso e una sola uscita.

Due segnali fondamentali

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)L'impulso ideale $\delta(t)$ è il segnale "nullo fuori dall'origine e di area $1$" definito dalla proprietà rivelatrice $\int s(t)\delta(t-t_0),dt=s(t_0)$: è il limite (in senso operativo) di impulsi rettangolari sempre più stretti e alti di area $1$. Serve per scrivere derivate dei segnali con salti (la derivata del gradino è $\delta$, il salto diventa un impulso di area pari al salto), come elemento neutro della convoluzione e come risposta impulsiva dei filtri. Non ha senso parlare di energia o potenza di $\delta$.Impulso ideale (delta di Dirac) →).

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

Legami utili: $\delta[n]=u[n]-u[n-1]$ (il gradino "sale" solo in $n=0$) e $u[n]=\sum_{k=-\infty}^{n}\delta[k]$. Soprattutto, ogni segnale è una somma di impulsi traslati e pesati: $$x[n]=\sum_{k=-\infty}^{\infty}x[k]\,\delta[n-k].$$ Perché: $\delta[n-k]$ vale $1$ solo per $n=k$, quindi nella somma sopravvive un solo termine, $x[n]\cdot1$. Questa scrittura è il punto di partenza di tutto il discorso sui sistemi LTI (Sistemi LTI e convoluzione discretaUn sistema lineare e tempo-invariante (LTI) è completamente descritto dalla sua risposta impulsiva h[n]: y[n] = Σ x[k] h[n-k] = x[n] * h[n] (somma di convoluzione). Si ricava scomponendo x in impulsi traslati e usando linearità e invarianza. La convoluzione è commutativa, associativa e distributiva; una cascata di LTI equivale a un solo filtro con h = h1 * h2 e l'ordine non conta. Se x ha lunghezza N e h lunghezza L, y ha lunghezza N+L-1. Si calcola col metodo della finestra scorrevole o a tabella. I FIR sono LTI; altri sistemi (n·x[n], x[-n], x²) non lo sono.Sistemi LTI e convoluzione discreta →).

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

La media mobile

Il primo filtro è la media mobile (moving average, o running average): ogni campione di uscita è la media di una finestra di campioni di ingresso che scorre. Con tre punti "in avanti": $$y[n]=\tfrac13\big(x[n]+x[n+1]+x[n+2]\big)=\tfrac13\sum_{\ell=n}^{n+2}x[\ell].$$ Questa è un'equazione alle differenze (difference equation): è una descrizione completa del filtro perché permette di calcolare $y[n]$ per ogni $n$.

Esempio svolto (calcolo di $y[n]$). Con $x=\{2,4,6,4,2\}$ in $n=0,\dots,4$:

• $y[0]=\frac13(x[0]+x[1]+x[2])=\frac13(2+4+6)=4$;
• $y[1]=\frac13(4+6+4)=\frac{14}3$;
• $y[-1]=\frac13(x[-1]+x[0]+x[1])=\frac13(0+2+4)=2$ e $y[-2]=\frac13(0+0+2)=\frac23$;
• $y[3]=\frac13(4+2+0)=2$, $y[4]=\frac13(2+0+0)=\frac23$, e $y[n]=0$ fuori da $-2\le n\le4$.

Quindi $y=\{\frac23,2,4,\frac{14}3,4,2,\frac23\}$ per $n=-2,\dots,4$ (verificato con Python). Sia l'ingresso sia l'uscita hanno supporto finito: l'uscita è più lunga di due campioni, perché la finestra comincia a "vedere" il segnale prima che l'ingresso inizi e finisce dopo.

Causalità. In questa forma l'uscita comincia (a $n=-2$) prima dell'ingresso: il filtro usa il futuro dell'ingresso. Un sistema che usa solo valori presenti e passati è causale (causal: la causa precede l'effetto, $y[n]$ è zero finché $x[n]$ non diventa diverso da zero); uno che usa valori futuri è non causale (non-causal) e non è realizzabile in tempo reale, perché i campioni futuri non sono ancora disponibili. Ma non è un difetto del segnale registrato: sulle registrazioni (immagini, audio salvato) il futuro c'è, ed è spesso conveniente usarlo.

La media a tre punti causale (backward average) è $$y[n]=\tfrac13\big(x[n]+x[n-1]+x[n-2]\big)=\tfrac13\sum_{\ell=n-2}^{n}x[\ell].$$ Dà gli stessi numeri $\{\frac23,2,4,\frac{14}3,4,2,\frac23\}$ ma partendo da $n=0$ invece che da $n=-2$: il supporto è traslato di due campioni, i valori sono gli stessi. Il filtro centrato $y[n]=\frac13(x[n+1]+x[n]+x[n-1])$ dà gli stessi valori partendo da $n=-1$: è simmetrico, quindi non ritarda il segnale.

Media mobile di $L$ punti

La media mobile causale di $L$ punti è $y[n]=\frac1L\sum_{k=0}^{L-1}x[n-k]$. Più è lunga la finestra, più l'uscita è "liscia", e più è lungo il transitorio ai bordi del segnale.

Esempio (3 e 7 punti). Ingresso $x[n]=1{,}02^n+0{,}5\cos(\frac{2\pi n}{8}+\frac\pi4)$, $0\le n\le40$: una crescita esponenziale lenta più un'oscillazione di periodo $8$ campioni. Il filtro lascia passare quasi intatta la parte lenta e attenua l'oscillazione: con $L=3$ l'ampiezza della sinusoide scende da $0{,}5$ a $0{,}5\cdot0{,}805=0{,}402$, con $L=7$ a $0{,}5\cdot\frac17=0{,}0714$ (i fattori $0{,}805$ e $\frac17$ sono il guadagno del filtro alla frequenza $\hat\omega=\frac\pi4$, calcolato in Risposta in frequenza dei sistemi FIRSe all'ingresso di un FIR c'è un esponenziale complesso A e^{jφ} e^{jω̂n} (per ogni n), l'uscita è lo stesso esponenziale moltiplicato per H(ω̂) = Σ b_k e^{-jω̂k}: la frequenza non cambia, ampiezza e fase sono modificate da |H| (guadagno) e ∠H (sfasamento). Per sovrapposizione si trattano somme di sinusoidi. H è periodica di periodo 2π e, per coefficienti reali, hermitiana (|H| pari, fase dispari). La cascata ha H = H1·H2. Esempi: ritardo (fase lineare), differenza prima (passa-alto), {1,2,1} (passa-basso), media mobile di L punti (Dirichlet: |H| = |sin(Lω̂/2)/(L sin(ω̂/2))|, fase lineare -(L-1)ω̂/2).Risposta in frequenza dei sistemi FIR →; verificati con Python). In più l'uscita arriva in ritardo di $\frac{M}2=\frac{L-1}2$ campioni ($1$ per $L=3$, $3$ per $L=7$).

import numpy as np
n = np.arange(0, 41)
x = 1.02**n + 0.5*np.cos(2*np.pi*n/8 + np.pi/4)
for L in (3, 7):
    h = np.ones(L)/L                  # coefficienti b_k = 1/L
    y = np.convolve(h, x)             # lunghezza 41 + L - 1
    print(L, len(y))                  # 43 e 47

Il filtro FIR causale

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

La media mobile a 3 punti è il caso $M=2$, $b_0=b_1=b_2=\frac13$. Attenzione alla differenza tra ordine $M$ (numero di ritardi) e lunghezza $L=M+1$ (numero di coefficienti): confonderli è l'errore più frequente.

Supporto dell'uscita. Se l'ingresso ha supporto $0\le n\le N-1$ (lunghezza $N$), la finestra di $M+1$ campioni comincia a toccare il segnale in $n=0$ e smette in $n=N-1+M$: l'uscita ha supporto $0\le n\le N+M-1$, cioè lunghezza $N+M$. Con $N=5$, $M=2$ si ottengono i $7$ campioni di prima.

Risposta impulsiva. Con $x=\delta[n]$ nell'equazione si ha $y[n]=\sum_kb_k\delta[n-k]$, che vale $b_n$ per $n=0,\dots,M$ e $0$ altrove. Quindi $$h[n]=\sum_{k=0}^{M}b_k\,\delta[n-k]=\begin{cases}b_n&0\le n\le M\\0&\text{altrimenti}\end{cases}$$ La risposta impulsiva (impulse response) di un FIR è la sequenza dei suoi coefficienti: dura $M+1$ campioni e poi si annulla, da cui "a risposta impulsiva finita". Il filtro è completamente descritto da $h[n]$. I filtri a risposta impulsiva infinita (IIR) hanno invece una retroazione interna e possono rispondere per sempre (di solito con un decadimento): sono trattati in Filtri IIR - definizione e confronto con i FIRUn filtro IIR (infinite impulse response) è un sistema LTI descritto da $y[n]=\sum_{\ell=1}^{N}a_\ell y[n-\ell]+\sum_{k=0}^{M}b_kx[n-k]$: l'uscita usa anche le uscite passate (retroazione), per questo si chiama ricorsivo. Con le condizioni di riposo iniziale è LTI, $H(z)=\frac{\sum b_kz^{-k}}{1-\sum a_\ell z^{-\ell}}$ è un rapporto di polinomi, l'ordine è $N$ (numero di poli) e la risposta impulsiva ha durata infinita. Nel primo ordine $y[n]=a_1y[n-1]+b_0x[n]$ si ha $h[n]=b_0a_1^nu[n]$, ROC $|z|>|a_1|$, stabile se $|a_1|<1$; il gradino dà $b_0\frac{1-a_1^{n+1}}{1-a_1}\to\frac{b_0}{1-a_1}$. Si implementa iterando l'equazione alle differenze, non con la convoluzione. Rispetto ai FIR gli IIR rispettano le stesse specifiche di modulo con ordine molto più basso, ma possono essere instabili e non hanno fase lineare. Progetto: per tentativi (notch), con la trasformazione $s\to z$ dai filtri analogici, o con ottimizzazione numerica.Filtri IIR - definizione e confronto con i FIR →.

Due casi semplici

• Ritardo: $y[n]=x[n-n_0]$ è un FIR con un solo coefficiente non nullo. Per $n_0=3$: $\{b_k\}=\{0,0,0,1\}$, $M=3$, $h[n]=\delta[n-3]$.
• Somma mobile (running sum) di 3 punti con ingresso gradino: $y[n]=u[n]+u[n-1]+u[n-2]$ vale $1,2,3,3,3,\dots$ per $n=0,1,2,3,\dots$ La finestra "si riempie" in $M=2$ campioni; da lì in poi il filtro vede solo uni e l'uscita è costante. Con la media mobile a $L=5$ punti sul gradino si ottiene $0{,}2;\,0{,}4;\,0{,}6;\,0{,}8;\,1;\,1;\dots$: una rampa lineare di $L-1=4$ passi che sale fino a $1$ (di qui l'idea di regime e transitorio, vedi Risposta a regime e transitorioLa formula y[n] = H(ω̂) X e^{jω̂n} vale per un esponenziale complesso definito per ogni n. Se l'esponenziale è applicato all'istante n = 0, x[n] = X e^{jω̂n}u[n], l'uscita di un FIR di ordine M ha tre regioni: zero per n < 0, transitorio per 0 ≤ n < M (somma incompleta Σ_{k=0}^{n} h[k]e^{-jω̂k}), regime per n ≥ M (uguale al caso bilatero). Per un IIR stabile il transitorio non si annulla in tempo finito ma tende a zero; la sua analisi dice se il sistema è stabile.Risposta a regime e transitorio →).

Schemi a blocchi

Per calcolare un FIR servono tre operazioni: moltiplicare per una costante ($y=\beta x$), sommare ($y=x_1+x_2$) e ritardare di un campione ($y[n]=x[n-1]$, l'unico elemento con memoria). Con questi tre blocchi si disegna il filtro. Nella forma diretta (direct form) l'ingresso scorre in una catena di ritardi, ogni uscita della catena è moltiplicata per un $b_k$ e i prodotti vengono sommati. Nella forma trasposta (transposed form) il segnale $x[n]$ è inviato in parallelo a tutti i moltiplicatori $b_M,\dots,b_0$ e la catena dei ritardi raccoglie le somme parziali. Le due forme hanno la stessa equazione (si verifica sostituendo all'indietro le equazioni dei nodi). I FIR sono feed-forward: tutti i percorsi vanno dall'ingresso all'uscita, senza anelli.

Per scrivere l'equazione di uno schema qualsiasi: si dà un nome all'ingresso di ogni ritardo, si scrive la sua uscita in funzione di quel nome, si scrive un'equazione per ogni sommatore e si eliminano i segnali interni.

Esempio (costo della cascata). Due medie mobili $h_1=\{1,1,1,1\}$ e $h_2=\{1,1,1\}$ in cascata equivalgono a un solo filtro $h=\{1,2,3,3,2,1\}$ (calcolato in Sistemi LTI e convoluzione discretaUn sistema lineare e tempo-invariante (LTI) è completamente descritto dalla sua risposta impulsiva h[n]: y[n] = Σ x[k] h[n-k] = x[n] * h[n] (somma di convoluzione). Si ricava scomponendo x in impulsi traslati e usando linearità e invarianza. La convoluzione è commutativa, associativa e distributiva; una cascata di LTI equivale a un solo filtro con h = h1 * h2 e l'ordine non conta. Se x ha lunghezza N e h lunghezza L, y ha lunghezza N+L-1. Si calcola col metodo della finestra scorrevole o a tabella. I FIR sono LTI; altri sistemi (n·x[n], x[-n], x²) non lo sono.Sistemi LTI e convoluzione discreta →). Realizzato come singolo filtro servono $6$ moltiplicazioni e $5$ addizioni; realizzato come cascata $w[n]=\sum_{k=0}^3x[n-k]$, $y[n]=\sum_{k=0}^2w[n-k]$ servono $5$ addizioni e nessuna moltiplicazione ($3+2$ somme; il corso conta $6$ e $7$ addizioni contando i termini invece delle somme, ma la differenza che conta sono le moltiplicazioni). In hardware (FPGA) un moltiplicatore costa molta più area e potenza di un sommatore: la cascata è più economica.

Domande d'esame

1. Vantaggi dell'elaborazione numerica e schema di conversione. Traccia: schema LPF–A/D–DSP–D/A–LPF e le due ipotesi (banda limitata, $F_s\ge2B$); A/D = campionatore + quantizzatore, $q=V_x/2^{B-1}$, errore $\le q/2$; D/A con interpolatore di ordine zero; precisione, affidabilità, adattività; esempio della trasmissione (analogico: il rumore si amplifica e si accumula; digitale: soglia e rigenerazione).
2. Definire un filtro FIR causale e determinarne risposta impulsiva e supporto dell'uscita. Traccia: equazione alle differenze, ordine $M$ e lunghezza $L=M+1$; $h[n]=b_n$; uscita lunga $N+M$ per ingresso lungo $N$; causalità; esempio con la media mobile a 3 punti (causale e centrata: stessi valori, supporto traslato di $M/2$).