**
Hardware Architecture of DFT:**

** **

The Discrete Fourier Transform (DFT) of
discrete signal *x*(*n*) can be directly computed as:

(3.1)

Where and is called twiddle factor.

are the sequence of complex number.

An efficient method of computing the DFT
that significantly reduces the number of required arithmetic operations is
called FFT [10-11]. An FFT algorithm divides the DFT calculation into many
short-length DFTs and results in huge savings of computations. If the length of
DFT *N= R _{v}*, i.e., is the product of identical factors, the
corresponding FFT algorithms are called Radix-R algorithms. Assume FFT length
is 2

Above equations are
frequently represented in butterfly format. The butterfly of a Radix
2-algorithm is shown in fig.12 (a). The complete flow graph of an N-point Radix-2
FFT can be constructed by applying the basic butterfly structure (fig.1.a)
recursively, where N=2,4,8…. For an n-point Radix-2 FFT , it has stages. Within stages s, for
s=1,2,3… , there are groups of butterflies, with 2^{s-1}
butterflies per group. The computation of the 8-point DFT, for instance, can be
accomplished by the algorithm depicted in Fig. 12(b).