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