Fast Fourier Transform (FFT) Corso di Metodi per il Trattamento Numerico di Dati Multimediali Laura...
20
Fast Fourier Transform (FFT) Corso di Metodi per il Trattamento Numerico di Dati Multimediali Laura Patricolo (50/174) Valeria Mele (50/18)
-
Upload
michelina-serafini -
Category
Documents
-
view
217 -
download
1
Transcript of Fast Fourier Transform (FFT) Corso di Metodi per il Trattamento Numerico di Dati Multimediali Laura...
Fast Fourier Transform(FFT)
Corso di Metodi per il Trattamento Numerico di Dati Multimediali
Laura Patricolo (50/174)
Valeria Mele (50/18)
DFT
• f = [ f0, ...., fN-1]T
• per h = 0,…, N-1
• F = [F0, ...., FN-1]T
1
0
2
)(N
k
hkN
i
kh efFh
F
C
C
DFT
Forma matriciale:
Con
fWF N
1,...0,)( NkhhkN wW
khhk ww )(
)2
()2
cos(2
Nseni
New N
i
)( NF
)2/(1
NF
)2/(2
NF
...)4/(1,1NF
...)4/(2,1NF
...)4/(1,2NF
...)4/(2,2NF
L’operazione di scomposizione intesa con le due frecce indica che nella prima parte andranno gli elementi di posto pari, e nella seconda quelli di
posto dispari.
Esempio:
è il vettore di dimensione N/4, ottenuto come prima parte del vettore
a sua volta vettore di dimensione N/2, seconda parte del vettore
)4/(1,2NF
)2/(2
NF
)( NF
hkN
k
NhkNk
N
k
NhhkkN
hkk
N
k
NhhkkN
hkk
N
k
NkhNk
hkk
N
k
N
Nk
hkk
hkk
N
k
hkkh
wwffwwfwf
wfwfwfwf
wfwfwfF
12
0
)2(2
12
0
)2(2
12
0
)2(2
12
0
))2(()2(
1)2(
0
1
2
1
0
Scomposizione formale
per h = 0,…, N-1
hkN
k
NhkNk
N
k
NhhkkN
hkk
N
k
NhhkkN
hkk
N
k
NkhNk
hkk
N
k
N
Nk
hkk
hkk
N
k
hkkh
wwffwwfwf
wfwfwfwf
wfwfwfF
12
0
)2(2
12
0
)2(2
12
0
)2(2
12
0
))2(()2(
1)2(
0
1
2
1
0
Osserviamo:
hhihN
hN
iNh ieew )1()sin()cos(2
2)2(
Componenti pari:
Componenti dispari:
12
0
21)2(
)(2
1
1 2
1 N
k
km
NkkNh wffF
12
0
21)2(
)(12
1
1 2
1 N
k
kmkNkk
Nh wwffF
h1 = 0,…, (N/2)-1 ))2/(2(21
Nieww
N.B.: l’apice accanto a f indica il passo di scomposizione corrente !!
f (1)k
f(1)k+(n/2)
due trasformate di ordine N/2
)1(kf
)1()2/( Nkf
Vettore delle componenti di posto
pari di F
Vettore delle componenti di posto dispari di
F
Trasformando Trasformando
Esempio N=23=8
7
0k
hkkh wfF
fWF 8
4942352821147
4236302418126
3530252015105
282420161284
21181512963
1412108642
765432
8
1
1
1
1
1
1
1
11111111
wwwwwww
wwwwwww
wwwwwww
wwwwwww
wwwwwww
wwwwwww
wwwwwww
W Tfff 70 ,...,
TFFF )8(7
)8(0 ,...,
h1= 0, 1, 2, 3
373
262
51
40
73
62
51
40
)1(7
)1(6
)1(5
)1(4
)1(3
)1(2
)1(1
)1(0
)(
)(
)(
wff
wff
wff
ff
ff
ff
ff
ff
f
f
f
f
f
f
f
f
)8(F )4(,2
)8(12
)4(,1
)8(2
11
11
hh
hh
FF
FF
Passo I)RICORDA: nella notazione di F l’apice esprime la dimensione del problema, il pedice porta traccia della scomposizione del vettore, indicando la relazione del vettore al passo corrente con quello al passo precedente.Nella notazione di f invece l’apice esprime il passo corrente.NOTA: In questo momento il pedice di F contiene anche l’indice dell’elemento generico (h1).
1)1(
7)1(
5
)1(6
)1(4
)1(7
)1(5
)1(6
)1(4
1)1(
3)1(
1
)1(2
)1(0
)1(3
)1(1
)1(2
)1(0
)2(7
)2(6
)2(5
)2(4
)2(3
)2(2
)2(1
)2(0
)(
)(
wff
ff
ff
ff
wff
ff
ff
ff
f
f
f
f
f
f
f
f
)4(,2
)4(,1
1
1
h
h
F
F
)2(,2,2
)8(1)12(2
)2(,1,2
)8()12(2
)2(,2,1
)8(1)2(2
)2(,1,1
)8()2(2
22
22
22
22
hh
hh
hh
hh
FF
FF
FF
FF
Passo II)
h2= 0, 1
)2(7
)2(6
)2(7
)2(6
)2(5
)2(4
)2(5
)2(4
)2(3
)2(2
)2(3
)2(2
)2(1
)2(0
)2(1
)2(0
)3(7
)3(6
)3(5
)3(4
)3(3
)3(2
)3(1
)3(0
ff
ff
ff
ff
ff
ff
ff
ff
f
f
f
f
f
f
f
f
)2(,2,2
)2(,1,2
)2(,2,1
)2(,1,1
2
2
2
2
h
h
h
h
F
F
F
F
)3(7
)1(,2,2,27
)8(1)1)12(2(2
)3(3
)1(,1,2,26
)8()1)12(2(2
)3(5
)1(,2,1,25
)8(1))12(2(2
)3(1
)1(,1,1,24
)8())12(2(2
)3(6
)1(,2,2,13
)8(1)14(2
)3(2
)1(,1,2,12
)8()14(2
)3(4
)1(,2,1,11
)8(1)2(4
)3(0
)1(,1,1,10
)8()2(4
33
33
33
33
33
33
33
33
fFFF
fFFF
fFFF
fFFF
fFFF
fFFF
fFFF
fFFF
hh
hh
hh
hh
hh
hh
hh
hh
Passo III)h3= 0
schema butterfly
butterfly
a
b
z
y
x
7
6
5
4
3
2
1
0
f
f
f
f
f
f
f
f
)1(7
)1(6
)1(5
)1(4
)1(3
)1(2
)1(1
)1(0
f
f
f
f
f
f
f
f
)2(7
)2(6
)2(5
)2(4
)2(3
)2(2
)2(1
)2(0
f
f
f
f
f
f
f
f
)3(7
)3(6
)3(5
)3(4
)3(3
)3(2
)3(1
)3(0
f
f
f
f
f
f
f
f
w
w2
w3
w3
w2
w
w1
w1
w1
w1
Passo k : N = 8 addizioni/sottrazioni tra elementi del vettore f distanti N/2k
log2N=3 passi
Abbiamo ridotto il numero delle addizioni/sottrazioni
necessarie al calcolo della nostra DFT
a
N log2N = 8*3 = 24invece che
N2=64
come richieste dall’algoritmo classico
Notiamo però che il risultato dell’algoritmo è stato:
7
3
5
1
6
2
4
0
F
F
F
F
F
F
F
F
)3(7
)3(6
)3(5
)3(4
)3(3
)3(2
)3(1
)3(0
f
f
f
f
f
f
f
f
i coefficienti Fh che abbiamo ottenuto trasformando i
successivi vettori fi non sono posti nell’ordine naturale
Integer Bit Reversal (IBR)
- considera le rappresentazioni binarie degli interi 0, 1, … , N-1;
- inverte le successioni di bit delle singole rappresentazioni;
- determina i corrispondenti numeri decimali.
h inversione
7
6
5
4
3
2
1
0
111
110
101
100
011
010
001
000
111
011
101
001
110
010
100
000
7
3
5
1
6
2
4
0
for m=1, z
m2=2m-1
nm=N/2m
for i=0, m2 step 2for k=0, nm-1
g= fi*nm+k+ fnm+k
fnm+k=( fi*nm+k - f(i+1)*nm+k)wk
fi*nm+k=g
endforendfor
endfor
ALGORITMO FFT
La trasformata di Fourier è una tecnica che proprio nelle applicazioni, dalla fisica dei plasmi alla sismografia, dalla Tac alla oceanografia, alla
ricostruzione di immagini, ha trovato la sua legittimazione come strumento principale per la risoluzione effettiva di problemi concreti.
Per dare un'idea del guadagno effettivo ricordiamo che la Nasa, nell'ambito del Progetto Ciclope per la ricerca delle intelligenze
extraterrestri, ha operato la trasformazione di Fourier su un insieme di un miliardo di dati; ciò ha richiesto circa 9 ore di tempo con la Fft, contro gli
oltre 36.000 anni necessari con l'algoritmo normale. Ovvero con 1024 punti il rapporto tra i tempi è pari a circa 150.
CONCLUSIONI
Bibliografia [1] – Cooley J. W. e Tukey J. W. , An algorithm for machine calculation of complex Fourier series, Maths comput., 19, 297 – 301 (1965).[2] - D. Bini, M. Capovani, G. Lotti, F. Romani "Complessità numerica", ed. Boringhieri (1981).[3] - G. Monegato "Fondamenti di Calcolo Numerico", ed. Levrotto&Bella (1990).[4] - “www.nr.com”, by Numerical Recipes Software, pubblicato da Cambridge University Press.[5] - “www.disi.unige.it/person/BoccacciP”, dott. P. Boccacci, Università di Genova.[6] - “http://digilander.libero.it/nfragale/metodi/capitolo6.html”, Libreria di Software Matematico, Manuale per l'utente.[7] - T. Scapolla dell’Università di Pavia, La trasformata di Fourier, Una formula dell'800 usata anche dalla Nasa, Tuttoscienze, inserto del quotidiano La Stampa, (1999) (reperibile all’indirizzo http://digilander.libero.it/arti2000/ts99/960904.htm) [8] – “www.wikipedia.org”, Wikipedia, the free encyclopedia.
