**. FFT- szybka transformata Fouriera


1.przedstawienie przebiegów czasowych w dziedzinie częstości ma bardzo duże
znaczenie praktyczne (np. rozpoznawanie mowy, obrazów),
2.Przekształcenie całkowe Fouriera ma podstawową wadę, wymaga nieskończonego
czasu całkowania.

T

Na rysunkach pokazano wpływ ograniczenia się do czasów skończonych obserwacji (okno
Prostokątne) na obserwowany przebieg czasowy.

( )

( ) ( )

ω

ω

ω

j

Y

j

X

j

Z

∗

=

Iloczynowi w dziedzinie czasu odpowiada splot w dziedzinie częstość.

1/T

Mamy już skończony czas obserwacji. Teraz zastąpimy całkowanie, sumowaniem
próbkowanego sygnału:

( )

( )

( )

( )

0

t

j

t

j

e

t

x

j

X

e

t

x

j

X

ω

ω

ω

ω

−

∞

∞

−

−

∞

∫

∫

=

=

zamieniamy na sumę przy założeniu że, znane jest N próbek sygnału:

( )

1

2

1

0

2

1

0

−

=

=

−

=

∑

N

,.........

,

,

k

e

x

jk

X

N

π

k n

j

N-

n

n

Jest to wzór na dyskretne przekształcenie Fouriera.
Podobnie można wyznaczyć odwrotne dyskretne przekształcenie Foruriera:

( )

1

2

1

0

1

2

1

0

−

=

=

−

=

∑

N

,.........

,

,

n

e

X

N

n

x

N

π

k n

j

k-

k

k

Aby wyliczyć dyskretną transformatę Fouriera należy obliczyć

2

N

wyrażeń typu:

2

2

e

W

e

W

N

π

k n

j

kn

N

j

−

−

=

=

π

pomnożyć je przez odpowiednie

n

x

oraz zsumować. Bardzo dużo obliczeń. ale jest na to

bardzo prosty sposób, jeżeli przyjmiemy, że ilość próbek czasowych jest liczbą typu:

całałkowi

liczba

2

−

=

l

N

l

różnych wartości wyrażeń typu

kn

W

będzie tylko N a nie aż

2

N

. I tak jeżeli ilość próbek

czasowych

n

x

jest np. 128 należy obliczyć tylko 128 różnych

kn

W

a nie 16.384 jak w

przypadku dowolnym. Liczba mnożeń ogranicza się do:

2

gdy

log

2

l

N

N

N

=

np.:

2

1024

10

=

=

N

wówczas

1%

0.0098

1024

10

log

log

FT

FFT

2

2

2

≈

=

=

=

=

N

N

N

N

N

k= 0

n= 0,1,2,3,4,5,6,7

k= 2

0,4

1,5

2,6

3,7

k= 4

0,2,4,6

1,3,5,7

k= 6

0,4

1,5

2,6

3,7

k= 1

0

1

1

1

2

3

4

5

6

7

k= 3

0

1

2

3

4

5

6

7

k= 5

0

1

2

3

4

5

6

7

k= 7

0

1

2

3

4

5

6

7

Jak naprawdę obliczać w matlabie:

clear all
T=100;
dt=.01;
t=0:dt:T;
k=length(t); % k=10001
q=log2(k); % q=13.2879
r=floor(q); % r=13
l=2^r; % l=8192
m=l/2; % m=4096
w1=5; % częstość w Hz
x=sin(2*pi*w1*t); % sinusoida
figure(1);plot(x(1:l)); % rysunek1
f=(dt^(-1)*(0:m-1))/l; % skala częstości
z=fft(x,l); % fft
figure(2);plot(z); % rysunek-motylek
p=(z.*conj(z))*l; % gęstość widmowa
figure(3);plot(f,p(1:m)); % rysunek3