Integer Fast Fourier transform
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 computer science crazy Super Moderator Posts: 3,048 Joined: Dec 2008 15-02-2009, 12:29 AM PREFACE The DSP world today is ruled by different transforms. Discrete Fourier transforms are most used. So is the fast Fourier transform, which is the faster version of DFT. Suppose we take FFT of a signal. On taking the inverse fast Fourier transform,we except the output to be the same as the input.This is called the invertibility property.But on most occasions, dissapointment is the result. This is due to the finite word length of the registers used to store the samples and the coefficients. This seminar and presentation introduces a method called integer fast Fourier transforms to give the invertibility property to FFT, without in any way destroying its accuracy and speed. It first reviews the necessary backgrounds to understand the concept including the discrete Fourier transform and split-radix FFT,its fixed point implimentation,and lifting scheme. Then the basics are applied to split radix FFT to describe the integer fast Fourier transforms.The accuracy and complexity of the proposed approach is then discussed.The final section gives the use of the IntFFT in noise reduction application and compares its performance with the FxpFFT. ABSTRACT Fourier transform for approximating the discrete Fourier transform, which is one of the most fundamental operations in digital signal processing, is introduced. Unlike fixed- point fast Fourier transform, the new transform has the properties that it is an integer-to-integer mapping, is power adaptable and is reversible. In this paper, a concept of integer fast Fourier transform for approximating the discrete Fourier transform is introduced . The transform can be implemented by using only bit shifts and additions and no multiplication. A method for minimizing the no of additions required is presented. While preserving the reversibility, the integer FFT is shown experimentally to yield same accuracy as the fixed-point FFT when their coefficients are quantised to a certain number of bits. Complexity of the integer FFT is shown to be much lower than that of fixed point FFT in terms of the no of additions and shifts. Finally, the are applied to noise reduction applications, where the integer FFT provides significantly improvement over the fixed-point FFT at low power and maintains similar results at high power. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion
 computer science crazy Super Moderator Posts: 3,048 Joined: Dec 2008 15-02-2009, 12:36 AM CONCLUSION In this paper, we have presented a concept of IntFFT, which can be used to construct FFT with integer coefficients. It provides a new method for approximating the DFT without using any multiplication and can simply be applied to the case of large-size DFT. Unlike the FxpFFT, which is the fixed-point arithmetic version of FFT, the IntFFT is reversible when the coefficients are quantized. Its inverse IntIFFT can be computed with the same computational cost as that of the forward transform. The new transform is suitable for mobile computing and any handheld devices that run on batteries since it is adaptable to available power resources. Specifically, the coefficients appearing in the proposed structures can be quantized directly for different resolutions, i.e., different computational costs, while preserving the reversibility property. Although a large class of FFT structures such as radix-2, radix-4, and split-radix can be approximated by this approach, the split-radix structure is used to illustrate the technique. An analysis of the dynamic range of the internal nodes is presented. Using an appropriate choice of lifting factorizations, it is proven that lifting approximation of a complex multiplier can increase the resolution of the input by at most one bit. An upper bound of the dynamic range of the internal nodes is estimated and confirmed by a simulation for the case of the split-radix FFT. The computational complexity of the resulting transform is calculated by the numbers of real additions and shifts. A method for minimizing the number of additions is presented and used to compare the computational costs of IntFFT and FxpFFT. According to the simulation, the complexity of IntFFT is lower than that of FxpFFT by a significant margin. The accuracy of the transforms is compared experimentally. It is evident from the simulations that both IntFFT and FxpFFT have approximately the same distortion from ideal FFT when the resolution of the input Ni is greater than Nc . When Nc Ni , the FxpFFT yields 3 dB higher accuracy. The results are different when testing with the convolutional rule, where the IntFFT and the FxpFFT provide essentially the same accuracy for any value of Nc . When the inverse transform is performed after the forward transform, fixed-point arithmetic approach results in reconstruction error, whereas the proposed approach can reconstruct the input perfectly for any fixed resolution of the coefficients. Finally, these two implementations are tested in noise reduction application. At low power, i.e., the coefficients are quantized to low resolution, the IntFFT yields significantly better results than the FxpFFT, and they yield similar results at high power. Use Search at http://topicideas.net/search.php wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion