03-05-2013, 01:54 PM
4K-point FFT algorithms based on optimized TWIDDLE FACTOR multiplication for FPGAs
4K-point FFT algorithms.pptx (Size: 628.1 KB / Downloads: 24)
What its mean?
FFT stands for fast fourier transform4k stands for 4000But normally we consider 4096 point because of N=12 FFT is an Algorithm that efficiently computes the Discrete Fourier Transform(DFT)An FFT is a DFT, but is much faster for calculations. The whole point of the FFT is speed in calculating a DFT.
Definition of fourier transform
All Periodic Waves Can be Generated by Combining Sin and Cos Waves of Different Frequencies
Number of Frequencies may not be finite
Fourier Transform Decomposes a Periodic Wave into its Component Frequencies
What is FFT ?
FFT = Fast Fourier Transform. The FFT is a faster version of the Discrete Fourier Transform (DFT).The FFT utilizes some clever algorithms to do the same thing as the DTF, but in much less time(In the presence of round-off error, many FFT algorithms are also much more accurate than evaluating the DFT definition directly.)
DFT Definition
Sample consists of n points, wave amplitude at fixed intervals of time:(p0,p1,p2, ..., pn-1) (n is a power of 2)
Result is a set of complex numbers giving frequency amplitudes for sin and cos components
Points are computed by polynomial:P(x)=p0+p1x+p2x2+ ... +pn-1xn-1
Algorithm
At algorithmic level, the focus is on the development and analysis of FFT algorithms. With this goal, a new approach based on binary tree decomposition.*It uses the Cooley Tukey algorithm to generate a large number of FFT algorithms.*These FFT algorithms have identical butterfly operations and data flow but differ in the value of the rotations.*Along with this, a technique for computing the indices of the twiddle factors based on the binary tree representation has been proposed. We have analyzed the algorithms in terms of switching activity, coefficient memory size.
ABSTRACT
Higher point FFT (fast Fourier transform) algorithms for a single delay feedback pipelined FFT architecture considering the 4096-point FFT. These algorithms are different from each other in terms of twiddle factor multiplication. Twiddle factor multiplication complexity comparison is presented when implemented on Field-Programmable Gate Arrays (FPGAs) for all proposed algorithms. We also discuss the design criteria of the twiddle factor multiplication. Finally it is shown that there is a trade-off between twiddle factor memory complexity and switching activity in the introduced algorithms.