W 4.1
1024
512
256
128
64
64 128 256
512
1024
Obliczanie
za pomoc
ą
FFT
Obliczanie
za pomoc
ą
DFT
Operacje[tys]
N
Rys. Porównanie szybkości algorytmu DFT oraz FFT
Przykład
Niech N=8. Wówczas X
n
współczynników DFT ma postać
4
n
0
W
Z
Y
X
W
Z
Y
X
W
Z
Y
X
W
Z
Y
X
3
3
3
3
2
2
2
2
1
1
1
1
0
0
0
0
<
≤
+
=
+
=
+
=
+
=
4
n
0
W
Z
Y
W
Z
Y
X
W
Z
Y
W
Z
Y
X
W
Z
Y
W
Z
Y
X
W
Z
Y
W
Z
Y
X
3
3
3
7
3
3
7
2
2
2
6
2
2
6
1
1
1
5
1
1
5
0
0
0
4
0
0
4
<
≤
−
=
+
=
−
=
+
=
−
=
+
=
−
=
+
=
W 4.2
Schematycznie proces obliczeniowy współczynników X
n
dla 8-punktowej
DFT z podziałem na dwie 4-punktowe DFT przedstawiono na rysunku.
DFT
(N=4)
DFT
(N=4)
0
x
2
x
4
x
6
x
1
x
3
x
5
x
7
x
0
y
1
y
2
y
3
y
0
z
1
z
2
z
0
z
0
Z
1
Z
2
Z
3
Z
4
X
5
X
6
X
7
X
4
W
5
W
6
W
7
W
0
W
1
W
2
W
3
W
0
X
1
X
2
X
3
X
3
Y
2
Y
1
Y
0
Y
Rys. Dwupunktowy algorytm FFT
Uwagi
1. Węzły oznaczają zmienne przekształcenia (współczynniki Fouriera
dla ciągów y
k
oraz z
k
).
2. Strzałki oznaczają wkład zmiennych do sumarycznych wartości
poszczególnych współczynników DFT.
3. W
n
oznacza wagi z jakimi współczynnikami sumują się w węzłach.
W 4.3
Proces obliczeniowy współczynników X dla 8-punktowej DFT z podziałem
na cztery 2-punktowe DFT przedstawiono schematycznie na rysunku.
DFT
(N=2)
DFT
(N=2)
4
X
5
X
6
X
7
X
4
W
5
W
6
W
7
W
0
W
1
W
2
W
3
W
0
X
1
X
2
X
3
X
6
W
4
W
2
W
0
W
6
W
4
W
2
W
0
W
DFT
(N=2)
DFT
(N=2)
1
x
3
x
5
x
7
x
0
x
2
x
4
x
6
x
Rys. Czteropunktowy algorytm FFT