4.5
Filtraggio numerico↓ via
DFT
La definizione di DFT illustrata al §
4.4↑ ben si presta a calcolare il risultato
relativo ad un integrale di convoluzione, a patto di seguire alcune
accortezze.
4.5.1
Convoluzione discreta
↓
Dati due segnali
x(t)
e
h(t) limitati in banda tra
− W e
W, anche il
risultato della convoluzione
y(t) = x(t)*h(t) è limitato in banda, ed i suoi
campioni
yn = y(nTc)
(con
Tc > (1)/(2W))
possono essere calcolati a partire da quelli
di
x(t) e
h(t),
come
Nel caso in cui le sequenze
xn
e
hn abbiano
durata finita e pari rispettivamente a
N
ed
M campioni, si otterrà una
sequenza
yn di
durata pari a
N + M − 1
campioni.
Esempio: il lato sinistro di fig. (4.23↑) mostra una
sequenza triangolare ed una rettangolare con un numero di elementi non
nulli rispettivamente pari a 5 e 4, la cui convoluzione si estende su
8 valori.
4.5.2
Convoluzione circolare↓
Date due sequenze
xn
ed
hn di durata
finita
N, il prodotto
Ym
= XmHm delle
rispettive DFT
Xm = ∑N − 1n =
0xne
− j2π(m)/(N)n
ed
Hm = ∑N
− 1n = 0hne − j2π(m)/(N)n possiede
antitrasformata
ỹn = DFT − 1{Ym} periodica in
n
di periodo
N, e pari a
in cui
x̃n e
h̃n sono le sequenze
periodiche di periodo
N ottenute
replicando infinitamente le sequenze originali
xn
ed
hn (). La convoluzione (
8.41↑) è detta
circolare perché è possibile immaginare le sequenze
xn
ed
hn incollate
su due cilindri concentrici, e la somma svolta sui prodotti degli
elementi coincidenti. Ogni valore di
p
corrisponde ad una diversa rotazione relativa (con angolo multiplo di
2π ⁄ N) dei cilindri, ed il
campione di
hn
che era allineato ad
xN − 1
rientra dall’altro lato, per corrispondere ad
x0.
La parte centrale di fig.
(4.23↑) mostra il risultato della
periodicizzazione delle stesse sequenze dell’esempio precedente, assieme
al risultato della convoluzione circolare tra esse, considerando un
periodo
N = 6 per entrambe: come
evidente, il risultato è abbastanza differente da quello ottenuto nel
caso della convoluzione discreta.
4.5.3
Convoluzione tra sequenze di durata finita via DFT↓
Sappiamo che la convoluzione produce un
risultato di durata pari alla somma delle durate degli operandi; come
anticipato, nel caso di due sequenze
xn
ed
hn di durata
N ed
M,
il risultato della convoluzione discreta
yn
= ∑N − 1k =
0xkhn − k
produce valori non nulli per indici
n =
0, 1, …, N + M − 1. Pertanto, per fare in modo
che la (
8.41↑)
produca lo stesso effetto di una convoluzione discreta, occorre
costruire delle sequenze
x’n
e
h’n di
lunghezza almeno pari ad
N + M − 1,
ottenute a partire dai valori di
xn
ed
hn, a cui si
aggiungono
M − 1 ed
N
− 1 valori nulli, rispettivamente. In tal modo, il prodotto
X’mH’m
tra le DFT ad
N + M − 1
punti di queste due nuove sequenze, può essere antitrasformato, per
fornire il risultato corretto.
La parte destra di fig.
(4.23↑) mostra come estendendo con zeri le due
sequenze di esempio fino ad una stessa lunghezza
N
= 9, il risultato della loro convoluzione circolare anch’esso
di periodo
N ora fornisca con
esattezza lo stesso risultato ottenuto calcolando direttamente la
convoluzione discreta.
4.5.4
Convoluzione di segnali via DFT
Due segnali x(t)
e h(t) limitati in banda non possono, a
rigore, essere limitati nel tempo. Viceversa, una finestra di segnale
non può, a rigore, essere rappresentata dai suoi campioni: infatti,
l’effetto della convoluzione in frequenza tra la trasformata della
finestra (nominalmente illimitata in banda) e lo spettro del segnale,
produce una dispersione frequenziale di quest’ultimo.
Ciononostante, disponendo di un numero di campioni
sufficientemente elevato, si può assumere che la trasformata della
finestra si attenui più velocemente in frequenza, fino a rendersi
trascurabile oltre un certo valore. Inoltre, l’adozione di una frequenza
di campionamento più elevata provoca un allontanamento delle repliche
spettrali del segnale campionato. In queste due ipotesi, è lecito
ritenere l’elaborazione condotta sui campioni di segnale, equivalente a
quella da svolgere sul segnale originario.
Consideriamo quindi il caso di operare su campioni
prelevati alla frequenza opportuna, e di voler determinare la risposta
di un filtro caratterizzato dai campioni
hn = Tc⋅h(nTc)
di durata finita
M, ad un ingresso
descritto dai campioni
xn
= x(nTc) di durata indefinita. Per applicare
i risultati fin qui descritti, occorre suddividere la sequenza
xn
in segmenti
xqn
di lunghezza
L
xqn = ⎧⎨⎩
xn
per qL ≤ n < (q + 1)L
0
altrove
in modo da poter scrivere
xn
= ∑∞q = − ∞xqn,
operare una successione di convoluzioni discrete
yqn
= xqn*hn,
ed infine ottenere
yn =
xn*hn = ∑∞q = − ∞xqn*hq
per la linearità della convoluzione.
Osserviamo ora che ognuno dei termini yqn
risulta di estensione N = M + L
− 1 punti, e può essere calcolato mediante la DFT inversa ad N punti del prodotto Xq’mHq’m
tra le DFT ad N punti delle
versioni allungate con zero (zero
padded) di xqn
ed hqn.
Infine, notiamo che l’estensione temporale
N = M + L − 1 dei
termini
yqn è maggiore di quella
dei segmenti originali
xqn,
di lunghezza
L: pertanto la
sequenza
yn si
ottiene sommando ai primi
M − 1
valori di ognuna delle
yqn,
gli ultimi
M − 1 valori risultanti
dalle operazioni precedenti. Per questo motivo, il metodo prende il nome
di
Overlap and Add↓.