NANOSCALE IMAGE PROCESSING - Bio-Inspired and Nanoscale Integrated Computing - page 525

where X(k) represents the Fourier coefficients of x(n). In general, the data
sequence x(n) is also assumed to be complex valued. Similarly, the inverse discrete
Fourier transform (IDFT) becomes

N X

N 1

1

X ð k Þ W nk
N

x ð n Þ¼ ; 0 n N 1 : ð 19 : 2 Þ

k ¼ 0

Since DFT and IDFT involve the same type of computations, our discussion
of efficient computational algorithms for the DFT applies to the efficient
computation of the IDFT as well.
We observe that for each value of k, direct computation of X(k) involves N
complex multiplications (4N real multiplications) and N 1 complex additions
(4N 2 real additions). Consequently, to compute all N values of the DFT requires
4N 2 complex multiplications and 4N 2 2N complex additions.

Direct computation of the DFT is inefficient primarily because it does not
exploit the symmetry and periodicity properties of the phase factor W N . In
particular, these two properties are

W k þ N = 2
N

¼ W N Symmetry property :

ð 19 :

3 Þ

W k þ N
N

¼ W N

Periodicity property :

The computationally efficient algorithms described in this section, known
collectively as fast Fourier transform (FFT) algorithms, exploit these two basic
properties of the phase factor.
FFT algorithms are based on the fundamental principle of decomposing the
computation of the discrete Fourier transform of a sequence of length N into
successively smaller discrete Fourier transforms. The manner in which this principle
is implemented leads to a variety of different algorithms. The algorithm we describe
here, called decimation-in-time, derives its name from the fact that in the process of
arranging the computation into smaller transformations, the sequence x(n)(time
sequence) is decomposed into successively smaller subsequences. This decomposi-
tion can be performed in several ways such as radix-2, radix-4, and Split-radix. In
the following passage, we explain the radix-2 FFT algorithm.
We split the N-point data sequence into two N/2-point data sequences f 1 (n)
and f 2 (n), corresponding to the even-numbered and odd-numbered samples of
x(n), respectively; that is

f 1 ð n Þ¼ x ð 2n Þ
f 2 ð n Þ¼ x ð 2n þ 1 Þ; 2 1 :

ð 19 : 4 Þ

n ¼ 0 ; 1 ; ...; N =

Thus f 1 (n) and f 2 (n) are obtained by decimating x(n) by a factor of 2, and
hence the resulting FFT algorithm is called a decimation-in-time algorithm. Now