Date post: | 03-May-2015 |
Category: |
Documents |
Upload: | gennaro-angelini |
View: | 214 times |
Download: | 0 times |
Calcolo veloce della DFT:
la Fast Fourier Transform (FFT)
Calcolo veloce della DFT:
la Fast Fourier Transform (FFT)
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
2Algoritmi di FFT basati sulla Algoritmi di FFT basati sulla decimazione nel tempodecimazione nel tempo ((DecimationDecimation in the in the TimeTime domain: FFT-DT) domain: FFT-DT)
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
3Algoritmi di FFT-DTAlgoritmi di FFT-DT
periodo N/2 in kperiodo N/2 in k periodo N/2 in kperiodo N/2 in k
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
4Algoritmi di FFT-DTAlgoritmi di FFT-DT
IlIl 1°passo 1°passo di decimazione ha portato alla seguente complessita’:di decimazione ha portato alla seguente complessita’:
calcolo X(k) = cal. G(k) & cal. H(k) & calcolo X(k) = cal. G(k) & cal. H(k) & cal. cal. combinazionecombinazione G(k) con H(k) G(k) con H(k)calcolo calcolo combinazionecombinazione = 1 * complessa & 1 + complessa = 1 * complessa & 1 + complessa per ogni kper ogni k
((N * N * ee N + N + in totale) in totale)
N=8N=8
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
5Algoritmi di FFT-DTAlgoritmi di FFT-DT
2°passo2°passo
4 DFT da N/4 punti e varie operazioni di combinazione4 DFT da N/4 punti e varie operazioni di combinazione
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
6
IlIl 2°passo 2°passo di decimazione ha portato alla seguente complessita’:di decimazione ha portato alla seguente complessita’:
cal. X(k) = [cal. Gcal. X(k) = [cal. G11(k) & cal. G(k) & cal. G22(k) & (k) & cal. cal. combinazionecombinazione G G11(k) & cal. G(k) & cal. G22(k)(k)]&]&[cal. H[cal. H11(k) & cal. H(k) & cal. H22(k) &(k) &cal. cal. combinazionecombinazione H H11(k) & cal. H(k) & cal. H22(k)(k)]&]&[[cal. cal. combinazionecombinazione G(k) con H(k) G(k) con H(k)]]
cal. cal. combinazionecombinazione G Gii(k) o H(k) o Hii(k) = N/2*compl. & N/2 + compl. totali(k) = N/2*compl. & N/2 + compl. totali
N=8N=8
Algoritmi di FFT-DTAlgoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
7
Nel Nel generico passogenerico passo i-mo di decimazione, la struttura del calcolo di X(k) e’ la seguente: 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. X(k) = [cal. di varie DFT su “meno punti”]& [cal. [cal. combinazionecombinazione delle DFT generate nel passo i-mo] delle DFT generate nel passo i-mo]&& [cal. [cal. combinazionecombinazione delle DFT generate nel passo (i-1)-mo] delle DFT generate nel passo (i-1)-mo]&& … …&&[cal. [cal. combinazionecombinazione G(k) con H(k) G(k) con H(k)]]
Quando si ferma l’algoritmo? Quando si ferma l’algoritmo? Se Se “meno punti” = 2“meno punti” = 2 (infatti la DFT su 2 punti e’ “pura combinazione”)(infatti la DFT su 2 punti e’ “pura combinazione”)
N=8N=8
Algoritmi di FFT-DTAlgoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
8Algoritmi di FFT-DTAlgoritmi di FFT-DT
EsempioEsempio
Marina Ruggieri & Tommaso Rossi, Modulo di Elaborazione Numerica dei Segnali, a.a. 2008/2009
9Algoritmi di FFT-DTAlgoritmi di FFT-DTschema del 1°+2° passo dell’algoritmoschema del 1°+2° passo dell’algoritmo
10
Algoritmi di FFT-DTAlgoritmi di FFT-DT
Inserendo lo schema nell’architettura della slide precedente si ottiene:Inserendo lo schema nell’architettura della slide precedente si ottiene:
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
Nota bene: WNota bene: WNN^(N/2=4)=-1, dove N=8^(N/2=4)=-1, dove N=8
11Algoritmi di FFT-DTAlgoritmi di FFT-DT
stadio 1stadio 1 stadio 2stadio 2 stadio 3=stadio 3=loglog228=log8=log22NN
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
12Algoritmi di FFT-DTAlgoritmi di FFT-DT
In generaleIn generale
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
13Algoritmi di FFT-DTAlgoritmi di FFT-DT
-
BUTTERFLY BUTTERFLY MODIFICATAMODIFICATA(richiede solo 1 * (richiede solo 1 * complessa)complessa)
(cioe’ N/2 butterly per stadio (cioe’ N/2 butterly per stadio
e e =log=log22N stadiN stadi))
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
14Algoritmi di FFT-DTAlgoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
15Algoritmi di FFT-DTAlgoritmi di FFT-DT
Per effettuare il calcolo sul posto:Per effettuare il calcolo sul posto:
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
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.
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
16Algoritmi di FFT-DTAlgoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010
17Algoritmi di FFT-DTAlgoritmi di FFT-DT
Cosimo Stallo & Paolo Emiliozzi Modulo di Elaborazione Numerica dei Segnali, a.a. 2009/2010