Image Processing Reference
In-Depth Information
+
2
N+2
1
-N+1
0
0
-1
N-1
+
-2
_
N-2
Fig. 6.5. The circular topology of DFT indices illustrated for
N
points. An index
j
represents
the same point as
j
+
nN
, where
n
is an arbitrary integer
has an inverse transform
F
(
n
)exp
imn
2
π
N
N−
1
f
(
m
)=
(6.50)
n
=0
The DFT or its two variants in this section are special cases of the FT. In 1961
Cooley and Tukey, [48], published an algorithm that could quickly compute the dis-
crete Fourier transform. Since then this and other algorithms for quickly computing
DFTs are collectively called FFT (Fast Fourier Transform) algorithms although there
are several variants to choose from. The FFT has found many applications because
of its efficiency. In many cases, it is faster to do two FFTs, a multiplication of the
resulting functions, and then to do the inverse FFT, than doing shift-invariant com-
putations, e.g., convolutions with arbitrary filters.
6.4 Circular Topology of DFT
We note that
m
and
n
on the right-hand side of the equations in theorem 6.4, do not
necessarily have to be one of the integers in 0
···
N
−
1. We will investigate this issue
along with a practical way of dealing with it next.
In arrays with
N
elements that are DFT pairs, there can be at most
N
different
f
(
m
) or
F
(
n
) values, although
m, n
can be any integer according to the DFT lemma.
It can be easily shown that if for any integer
m, n
, and
k
the equation
n
=
m
+
kN
(6.51)
holds, then
