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.
Description of Integer Fast Fourier Transform
This is called the invertibility property. But on most occasions, disappointment is the result. This is due to the finite word length of the registers used to store the samples and the coefficients. This seminar 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 implementation, 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.
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.