Integer Fast Fourier Transform
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
computer science crazy
Super Moderator

Posts: 3,048
Joined: Dec 2008
21-09-2008, 11:29 AM

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, 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 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 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.
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.

THE DISCRETE FOURIER TRANSFORM (DFT) is one of the most fundamental operations in digital signal processing. Because of the efficiency of the convolutional property, the DFT is often used in linear filtering found in many applications such as quantum mechanics, noise reduction and image re-construction. However, the computational requirements for completing the DFT of a finite length signal are relatively intensive. In particular, if the input signal has length N, directly calculating its DFT requires 2 N complex multiplications2 4 ( N real multiplications) and some additional additions. In 1965, Cooley and Tukey introduced the fast Fourier transform (FFT), which efficiently and significantly reduces the computational cost of calculating N-point DFT from 2 N to Nlog N 2 . Since then, there have been numerous further developments that extended Cooley and Tukey's original contribution.

Many efficient structures for computing DFT have been discovered by taking advantage of the symmetry and periodicity properties of the roots f unity such as the radix-2 FFT, radix-4 FFT,and split-radix FFT. The order of the multiplicative complexity is commonly used to measure and compare the efficiency of the algorithms since multiplications are intrinsically more complicated among all operations.It is well-known in the field of VLSI that among the digital arithmetic operations (addition, multiplication, shiftingand addressing, etc.), multiplication is the operation that consumes most of the time and power required for the entire computation and, therefore, causes the resulting devices to be large and expensive. Therefore, reducing the number of multiplications in digital chip design is usually a desirable task.

In this paper, utilizing the existing efficient structures, a novel structure for approximating the DFT is presented. This proposed structure is shown to be a reversible integer-to-integer mapping called Integer FFT (IntFFT). All coefficients can be represented by finite-length binary numbers. The complexity of the proposed IntFFT will be compared with the conventional fixed-pointimplementation of the FFT (FxpFFT). Moreover, the performances of the new transforms are also tested in noise reduction problem. The invertibility of the DFT is guaranteed by orthogonality.The inverse (the IDFT) is just the conjugate transpose. Inpractice, fixed-point arithmetic is often used to implement the DFT in hardware since it is impossible to retain infinite resolution of the coefficients and operations.

The complex coefficients of the transform are normally quantized to a certain number of bits depending on the tradeoff between the cost (or power) and the accuracy of the transform. However, direct quantization of the coefficients used in the conventional structures, including both direct and reduced-complexity (e.g., radix-2, radix-4, etc.) methods, destroys the invertibility of the transform.
Use Search at wisely To Get Information About Project Topic and Seminar ideas with report/source code along pdf and ppt presenaion

Important Note..!

If you are not satisfied with above reply ,..Please


So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Type your reply to this message here.

Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  curvelet transform ppt jaseelati 0 134 09-01-2015, 03:18 PM
Last Post: jaseelati
  Report on Fast Fourier Transform (FFT) study tips 0 278 25-06-2013, 02:58 PM
Last Post: study tips
  Short Time Fourier Transform ppt study tips 0 309 18-06-2013, 04:01 PM
Last Post: study tips
  FAST SPHERE DECODER FOR MIMO SYSTEMS pdf study tips 0 376 30-05-2013, 12:56 PM
Last Post: study tips
  THE DISCRETE WAVELET TRANSFORM pdf study tips 0 478 20-05-2013, 04:29 PM
Last Post: study tips
  The Discrete Fourier Transform: Notes study tips 0 343 16-05-2013, 04:41 PM
Last Post: study tips
  A Fast Resolving BiNMOS Synchronizer for Parallel Processor Interconnect pdf study tips 0 429 22-03-2013, 03:24 PM
Last Post: study tips
  An Efficient Architecture for 3-D Lifting-based Discrete Wavelet Transform seminar ideas 6 1,769 16-03-2013, 07:16 PM
Last Post: uma_ece07
  The BinDCT: Fast Multiplierless Approximation of the DCT pdf project girl 0 306 06-02-2013, 03:49 PM
Last Post: project girl
  Fourier transform application Report project girl 0 422 02-02-2013, 04:52 PM
Last Post: project girl