Digital Signal Processing Reference
In-Depth Information
Step 4: Computation of the product
W
4
1
k
X
2
(
k
)
This is the final step of the FFT computation. Again, there are some surprising
relations:
W
4
10
X
2
(0) = -
W
4
12
X
2
(2) =
X
2
(0)
W
4
11
X
2
(1) = -
W
4
13
X
2
(3) =
j X
2
(1)
Hence, we have to calculate, only the following terms:
W
4
10
X
2
(0)
(3.16a)
and
W
4
11
X
2
(1)
(3.16b)
Now we can make a multiplication count from Steps 2, 3, and 4. Step 2
requires four complex multiplications, by using Equation 3.13(a) and Equa-
tion 3.13(b). Step 3 requires two complex multiplications from Equation
3.15(a) and Equation 3.15(b), and finally Step 4 requires two complex mul-
tiplications, as seen from Equation 3.16(a) and Equation 3.16(b). Hence, we
get a total multiplication count of eight using the FFT procedure, as com-
pared with the direct computation of the DFT from Equation 3.9, which
requires 16 multiplications. The latter reduction in multiplication count will
be generalized into a formula in the next section.
Properties of the FFT
Some key properties of the FFT are given below:
•
An
N
-point DFT or
N
-point IDFT requires
N
2
complex multiplica-
tions if computed directly from Equation 3.4 and Equation 3.5. How-
ever, the same computation can be done with only
N Log
2
N
complex
multiplications, when a
radix-
2(
N
is a power of 2) FFT is used. This
is especially significant for large values of
N
: when
N =
128, the
number of complex multiplications is 16384 for direct computation
of DFT and only 896 for a
radix-
2 FFT computation.
•
FFT algorithms also exist when
N
is not a power of 2. These algo-
rithms are called
non-radix
-2 FFT.
Practical Usage of the FFT: Computation of Fast Fourier Transform
with MATLAB
The FFT was a major breakthrough in the efficient and fast computation of
the Fourier transform of speech, music, and other fundamental signals.
However, while the FFT is a very general formulation, there are some impor-
tant points to keep in mind, when utilizing the FFT on
periodic
and
nonperiodic
signals.
