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