115907

związku z tym powinno być wykonane N² obliczeń.

Dyskretna i odwrotna transformata Fouriera:

^ck = X w^knx_n,k= 0,N- 1, x„ = w~^k”c_k,n = 0,N- l

n- 0    £₌ o

Sekwencja {xj reprezentuje sobą próbki sygnału, zaś sekwencja fc_k}- współczynniki widmowe.

W dyskretnej transformacie Fouriera wykorzystuje się system funkcji wykładniczych (angl. discrete exponential functions - DEF) zdefiniowanych za pomocą następującego wzoru:

n,k = 0,N- 1

def(k,n)~ exp(- j—kn)= cos-kn- jsin — kn_y N    N    N

w> = ^exP(~ —)    def(k,ń) - w* "

N

Wielkość w ^k,“ zwykle nazywa się współczynnikiem skrętu i reprezentuje sobą wektor w płaszczyźnie zespolonej. Cały system DEFmożna zapisać w postaci macierzy E_N, której wiersze są numerowane za pomocą indeksu k, kolumny - za pomocą indeksu n, a na skrzyżowaniu k-tego wiersza i n-tej kolumny zapisana jest wartość w ^k*".

0 1—    n ••• N- 1

Cl    0

1    i

E,=    i    i

k ......... w*"    ......

N - 1

W DFT ta sama wartość w_N występuje w obliczeniach wielokrotnie, gdyż jest ona funkcją okresową o limitowanej liczbie odrębnych wartości. Zadaniem więc szybkiego przekształcenia Fouriera (FFT), i jego odwrotności (IFFT), jest wykorzystanie tej nadmiarowości w celu redukcji liczby niezbędnych obliczeń cząstkowych. Z tego powodu istotne znaczenie mają procedury obliczeniowe redukujące liczbę mnożeń i sumowań. Jedną z takich procedur jest algorytm szybkiej transformaty Fouriera (FFT).

FFT to algorytm liczenia dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej. Czasem używana jest też forma szybka transformata Fouriera w odniesieniu do tej metody. Ściśle jednak transformacja jest przekształceniem, a transformata wynikiem tego przekształcenia.

Niech x0...... xN-l będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera

jest

określona wzorem:

** = X; x_ne-²*^ink k = 0,...,N-l.

u—U

Najpopularniejszą wersją FFT jest FFT o podstawie 2. Jest to bardzo efektywna