Hardware Architecture of DFT:
The Discrete Fourier Transform (DFT) of discrete signal x(n) can be directly computed as:
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= Rv, i.e., is the product of identical factors, the corresponding FFT algorithms are called Radix-R algorithms. Assume FFT length is 2M, where M is the number of stages. The radix-2 DIF FFT divides an N-point DFT into 2 N/2-point DFTs, then into 4 N/4-point DFTs, and so on. That is, the radix-2 DIF FFT expresses the DFT equation as two summations, and then divides it into two equations, each of which computes every two output samples. To arrive at a two-point DFT decomposition, considering and the following equations are derived by
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 2s-1 butterflies per group. The computation of the 8-point DFT, for instance, can be accomplished by the algorithm depicted in Fig. 12(b).