Digital Signal Processing Reference
In-Depth Information
as the DCT have become increasingly popular in recent years, especially for real-
time systems. They provide a large compression ratio.
6.2 DEVELOPMENT OF THE FFT ALGORITHM WITH RADIX-2
The FFT reduces considerably the computational requirements of the DFT. The
DFT of a discrete-time signal
x
(
nT
) is
N
-
Â
0
1
()
=
()
nk
Xk
xnW
k
=
01
, ,...,
N
-
1
(6.1)
n
=
where the sampling period
T
is implied in
x
(
n
) and
N
is the frame length. The
constants
W
are referred to as
twiddle constants
or
factors
, which represent the
phase, or
We
j
-
2
p
N
=
(6.2)
and are a function of the length
N
. Equation (6.1) can be written for
k
=
0,1,...,
N
-
1, as
...
()
=
()
+
()
()
(
)
(
)
Xk
x
0
x
1
W
k
+
x
2
W
2
k
++
xN
-
1
W
Nk
-
1
(6.3)
This represents a matrix of
N
N
terms, since
X
(
k
) needs to be calculated for
N
values for
k
. Since (6.3) is an equation in terms of a complex exponential, for each
specific
k
there are (
N
¥
-
1) complex additions and
N
complex multiplications. This
results in a total of (
N
2
N
) complex additions and
N
2
complex multiplications.
Hence, the computational requirements of the DFT can be very intensive, especially
for large values of
N
. FFT reduces computational complexity from
N
2
to
N
log
N
.
The FFT algorithm takes advantage of the periodicity and symmetry of the
twiddle constants to reduce the computational requirements of the FFT. From the
periodicity of
W
,
-
WW
kN
+
=
k
(6.4)
and from the symmetry of
W
,
WW
kN
+
2
=-
k
(6.5)
Figure 6.1 illustrates the properties of the twiddle constants
W
for
N
=
8. For
example, let
k
W
2
.
For a radix-2 (base 2), the FFT decomposes an
N
-point DFT into two (
N
/2)-point
or smaller DFTs. Each (
N
/2)-point DFT is further decomposed into two (
N
/4)-point
DFTs, and so on. The last decomposition consists of (
N
/2) two-point DFTs. The
=
2, and note that from (6.4),
W
10
=
W
2
, and from (6.5),
W
6
=-
Search WWH ::
Custom Search