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

mathematicians, engineers, and applied scientists have tried to efficiently imple-
ment DFT due to its broad range of applications in not only image processing but
also other digital signal processing applications. The DFT can calculate a signal's
frequency spectrum that allows a direct examination of information encoded in
the frequency, phase, and amplitude of the component sinusoids. Moreover, the
DFT can find a system's frequency response from the system's impulse response,
and vice versa [26]. A class of particularly efficient algorithms for computing DFT
is called fast Fourier transform (FFT) [27].
DFT (and FFT) can be used in spectral estimation [28], interpolation [29],
multichannel carrier modulation (MCM) such as orthogonal frequency division
multiplexing (OFDM) [30], object recognition [31], frequency analysis [32], speech
coding [33], harmonic analysis [34], digital audio compression [35], channel
separation and combination [36], watermarking [37], and bit reversal algorithms
[38]. They also have several applications in spectral analysis, convolution, and
correlation [39, 40]. DFT (and FFT) can be used in designing several tools such as
Dolby AC-2 and AC-3 audio coders [41], MPEG decoders [42, 43], and digital
filters such as low-pass (LPF), band-pass (BPF), high-pass (HPF), generalized
cepstrum, homomorphic filtering [44], nonlinear [45], and adaptive filters [46]. One
of the applications of both nanoscale DFT and FFT modules can be in image
processing used in medical imaging [54-56].
The DFT is identical to samples of the Fourier transform at equally spaced
frequencies, W k =2 p k/N. Several methods have been developed for computing
values of the DFT. A class of particularly efficient algorithms for computing DFT
is called fast Fourier transform (FFT) [27]. In this section, after a theoretical
discussion of DFT and FFT, we first show how to implement a module that
computes DFT coefficients at the nanoscale, and afterwards, we discuss how this
solution is optimized by using FFT techniques.
The DFT and FFT architectures can be implemented on a simplified version
of a spin-wave reconfigurable mesh [57]. In implementation of DFT and FFT all
the processing nodes of a reconfigurable mesh are used; however, no spin-wave
switches are required to realize the DFT/FFT computation. In Section 19.2.1 we
show how DFT and FFT are implemented on a reconfigurable mesh.

19.2.1. Discrete Fourier Transform (DFT) and Fast Fourier
Transform (FFT)
The computational problem for the DFT is to compute the sequence {X(k)} of N
complex-valued numbers given another sequence of data {x(n)} of length N,
according to Equation 19.1 [27]
X ð k Þ¼ X

N 1

x ð n Þ W k N ;

0 k N 1

ð 19 : 1 Þ

n ¼ 0

W N ¼ e j2 p= N