FFT

x(0)

N/4 punktowa

N/4 punktowa

x(0)

DTF

DTF

W

W

N0

N0

x(4)

x(1)

W

WN1

N2

x(2)

N/4 punktowa

N/4 punktowa

x(2)

DTF

DTF

W

WN2

N4

x(3)

x(6)

W

W

N6

N3

x(1)

N/4 punktowa

N/4 punktowa

x(4)

DTF

DTF

W

W

N0

N4

x(5)

x(5)

W

W

N2

N5

x(3)

N/4 punktowa

N/4 punktowa

x(6)

DTF

DTF

W

W

N4

N6

x(7)

x(7)

W

W

N6

N7

Równanie x(k) odpowiada zastąpieniu N- punktowych obliczeń dwoma obliczeniami (N/2)-

punktowymi. Jeśli N/2 parzyste, co ma miejsce, gdy N jest potęgą liczby 2, to wyznaczenie każdej (N/2)- punktowej transformaty może być przeprowadzone metodą wyrażenia każdej z sum w tym równaniu za pomocą dwóch (N/4)- punktowych dyskretnych transformat Fouriera, które połączone później pozwolą określić transformaty (N/2)- punktowe. Zatem G(k) i H(k) w równaniu:

k

G( k ) +

H ( k)

W

N

mogą być wyznaczone:

N

N

1

−

1

−

4

4

lk

k

lk

G( k) =

g( l

2 )

N +

N

h( l

2 + )

1

N

Σ

W

W Σ

W

l = o

4

2 l =0

4

N

N

1

−

1

−

4

4

lk

k

lk

H ( k) =

h( l

2

Σ

W

)

N + W N

h( l

2 +

Σ

W

)

1

N

l =0

4

2 l =0

4

A zatem jeśli 4- punktowe dyskretne transformaty Fouriera są wyznaczone zgodnie z powyższymi równaniami otrzymujemy kompletny graf przepływowy pokazany na powyższym rysunku. Warto zauważyć, że wykorzystano tu zależność: 2

W N = W

N

2

Przeprowadzając obliczenia według rysunku:

Graf przepływowy wyznaczania 2-punktowej dyskretnej transformaty Fouriera.

x(0)

W =1

N0

x(4)

W =W

=-1

2

NN/2

i stosując je do poprzedniego rysunku uzyskujemy kompletny graf przepływowy wyznaczania 8- punktowej dyskretnej transformaty Fouriera.

x(0)

x(0)

W

WN0

W

N0

N0

x(4)

x(1)

W

W

N4

N2

WN1x(2)

x(2)

W

W

N0

N4

WN2x(3)

x(6)

W

W

N4

W

N3

N6

x(1)

x(4)

W

W

W

N0

N0

N4

x(5)

x(5)

W

W

N4

W

N5

N2

x(3)

x(6)

W

W

N0

N4

WN6

x(7)

x(7)

W

W

W

N4

N6

N7

W ogólnym przypadku, gdy N jest potęgą liczby 2stopnia wyższego niż 3, to (N/4)- punktowe transformaty z powyższych równań zastępuje się transformatami (N/8)- punktowymi i kontynuuje ten proces aż do momentu otrzymania tylko transformat 2- punktowych.

Algorytm ten wymaga m etapów obliczeń, przy czym m=log2N. Licząc gałęzie grafu z transmitancjami typu

r

W zauważymy, że w każdym etapie obliczeń należy wykonać N

N

mnożeń i N sumowań liczb zespolonych. Ponieważ liczba etapów jest równa log2N, to obliczenia muszą się składać z Nlog2N mnożeń i Nlog2N sumowań liczb zespolonych. Jest to poważna oszczędność obliczeń. Wykorzystanie symetrii i okresowości wyrażenia r

W może

N

prowadzić do dalszego zmniejszania rozmiaru obliczeń.