Calcolo veloce della DFT:
la Fast Fourier Transform (FFT)
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT basati sulla decimazione nel tempo
(Decimation in the Time domain: FFT-DT)
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
2
Algoritmi di FFT-DT
periodo N/2 in k
3
periodo N/2 in k
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
4
Il 1°passo di decimazione ha portato alla seguente complessita’:
calcolo X(k) = cal. G(k) & cal. H(k) & cal. combinazione G(k) con H(k)
calcolo combinazione = 1 * complessa & 1 + complessa
per ogni k
(N * e N + in totale)
N=8
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
5
2°passo
4 DFT da N/4 punti e varie operazioni di combinazione
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
6
Il 2°passo di decimazione ha portato alla seguente complessita’:
cal. X(k) = [cal. G1(k) & cal. G2(k) &
cal. combinazione G1(k) & cal. G2(k)]&
[cal. H1(k) & cal. H2(k) &
cal. combinazione H1(k) & cal. H2(k)]&
[cal. combinazione G(k) con H(k)]
cal. combinazione Gi(k) o Hi(k) = N/2*compl. & N/2 + compl. totali
N=8
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
7
Nel generico passo i-mo di decimazione, la struttura del calcolo di X(k) e’ la seguente:
cal. X(k) = [cal. di varie DFT su “meno punti”]&
[cal. combinazione delle DFT generate nel passo i-mo]&
[cal. combinazione delle DFT generate nel passo (i-1)-mo]&
…&[cal. combinazione G(k) con H(k)]
Quando si ferma l’algoritmo?
Se “meno punti” = 2 (infatti la DFT su 2 punti e’ “pura combinazione”)
N=8
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
Esempio
8
Algoritmi di FFT-DT
schema del 1°+2° passo dell’algoritmo
Marina Ruggieri & Tommaso Rossi, Modulo di Elaborazione Numerica dei Segnali, a.a. 2008/2009
9
Algoritmi di FFT-DT
10
Inserendo lo schema nell’architettura della slide precedente si ottiene:
Nota bene: WN^(N/2=4)=-1, dove N=8
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
stadio 1
stadio 2
stadio 3=n=log28=log2N
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
11
Algoritmi di FFT-DT
In generale
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
12
Algoritmi di FFT-DT
-
(cioe’ N/2 butterly per stadio
e n=log2N stadi)
BUTTERFLY
MODIFICATA
(richiede solo 1 *
complessa)
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
13
Algoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
14
Algoritmi di FFT-DT
Per effettuare il calcolo sul posto:
15
Se (n2n1n0) e’ la rappresentazione
binaria dell’indice della sequenza, il
campione x(n2n1n0) risulta
memorizzato nella posizione
X0(no,n1,n2), per determinare la
posizione di x(n2n1no) dobbiamo
invertire l’ordine dei bit dell’indice n
Il calcolo sul posto ha il
vantaggio che ogni nuova
sequenza calcolata in uscita
da un certo stadio viene
memorizzata nelle stesse
locazioni di memoria della
sequenza di ingresso.
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Algoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
16
Algoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
17