294 (17)

5X8 22. Zastosowanie pr/cks7taicenia Fouriera

lub nieskończonym przedziale pulsacji, bowiem w takim przedziale ln/l(co) byłby nieskończenie wielki. Wynika stąd natychmiast, że omawiany w p. 22.7.2 filtr idealny jest fizycznie nierealizowalny.

22.8. Dyskretne przekształcenie Fouriera

Rozpatrzmy funkcję /(f) równą zeru dla t < 0 i ciągłą dla t > 0. W wyniku próbkowania (por. p. 19.1) w N chwilach t_n = nT, n = 0,1,2,..., N — 1, otrzymujemy funkcję

f*(t) = Y f(nT)S(t-nT), (22.62)

n = 0

Ciąg {J'(nT)j, n = 0, 1, 2,...,N — 1, zawiera N wyrazów, zwanych próbkami. Obliczymy gęstość widmową funkcji /*(t); mamy

= 3?{f*(t)} = Y /(nD^{<5(t-«r)},

n = 0

a stąd po uwzględnieniu wzoru (22.26) znajdujemy

jv- i

F*(a>) = ^ /(»'T)e^_j“"^r. (22.63)

n = 0

Próbkujemy teraz funkcję F*(io) w N punktach a)_m = m-Am, m = 0,1,2,..., /V — 1, przyjmując przedział próbkowania

Acj = ^. (22.64)

Otrzymujemy wówczas ciąg N próbek {F*(m Am)} gęstości widmowej, którego wyrazy są równe

N- 1

F*(m-A(o) = ^ f(nT)t-'^im*°^>nT, (22.65)

n= 0

przy czym m = 0, 1, 2,...,N— 1.

Należy podkreślić, że jeśli znamy ciąg próbek {/(nT)}, to na podstawie wzoru (22.65) możemy wyznaczyć ciąg próbek {F*(m A«)} gęstości widmowych. W ten sposób ciągowi próbek {f(nT)} funkcji f(t) jest przyporządkowany ciąg próbek {F*(m-Aa))} gęstości widmowych. Wzór (22.65) realizujący to przyporządkowanie nazywa się prostym przekształceniem dyskretnym Fouriera.

Udowodnimy, że wartości próbek, będących wyrazami ciągu {f(nT)}, można otrzymać na podstawie próbek będących wyrazami ciągu {F*(m-Aw)) gęstości widmowych, co pozwoli zrealizować odwrotne przekształcenie dyskretne Fouriera.

Mnożymy równanie (22.65) przez e^{jm Aw}'^u i sumujemy względem m:

N-1 N-1 N-t

(22.66)

X F*(mAcu)e^im'^At0'^k7' = £ /(nT) X e^jT'^A‘^om,k“ⁿ⁾.

m-0 n = 0 m-0

Uwzględniając wzór na sumę szeregu geometrycznego

mamy dla a = e^jT'^Aw'^<kn)

& 3 II	1—a* 1-a		gdy
m = 0	- N,		gdy
(k-n)
N - 1 V* gjT-Awm(k-	-"> = J	o,	gdy
m = 0	1	N,	gdy

a J= 1, a = I,

n # k, n = k,

(22.67)

bowiem T Aw/V = 2rc ze względu na zależność (22.64) wobec tego

_ ęjTSm Nik-n) _ gj(t-n)-2ii __ j

Biorąc pod uwagę wzór (22.67), stwierdzamy, że prawa strona równania (22.66) jest równa Nf(kT), wobec tego

j n-1

f(kT) = — X F*(wAco)e^jmAwkT, (22.68)

™ m = 0

przy czym k = 0, 1, 2,..., A —1.

Udowodniliśmy zatem, że wyrazom ciągu }F*(»rAa>)} są przyporządkowane wyrazy ciągu {f(nT)}. Wzór (22.68) realizujący to przyporządkowanie nosi nazwę odwrotnego przekształcenia dyskretnego Fouriera.

Zależności (22.65) i (22.68) przedstawiają parę dyskretnych przekształceń Fouriera i nadają się dobrze do obliczeń na maszynach cyfrowych. Więcej informacji na temat dyskretnego przekształcenia Fouriera zawiera praca [23],

Aby obliczyć bezpośrednio sumy w wyrażeniu (22.65), należy wykonać N mnożeń dla każdej próbki. Obliczenie całkowitego widma spróbkowanego wymaga zatem wykonania N² mnożeń. Istnieje specjalna procedura, zwana szybkim przekształceniem Fouriera i oznaczana w skrócie FFT (od angielskiego terminu „Fast Fourier Transform”), która wymaga wykonania znacznie mniejszej liczby operacji, równej w przybliżeniu N\og₂N. Tak na przykład, dla N = 256 przy stosowaniu FFT wykonuje się N\og₂N/N² = 1/32, czyli około 3% liczby operacji potrzebnych do wykonania obliczeń bezpośrednich. Informacje na temat FFT i zastosowań tej procedury są podawane w wielu publikacjach, na przykład [18, 21],