Fundamentals of the DFT (fft) Algorithms

By D. Sundararajan

Abstract:

In this article, a physical explanation of the fundamentals of the DFT (fft) algorithms is presented in terms of waveform decomposition. After reading the article and trying the examples, the reader is expected to gain a clear understanding of the basics of the mysterious DFT (fft) algorithms.

Download Document
(This item is protected by original copyright)

Rate this document:

i want project topics related to DSP

Project topic is to be selected in consultation with your professor. However, you can make a
list if you go through the exercise sections of
dsp books.

Thank you sir this is a nice document..

Sir I want to know the difference between DIT and DIF,exactly which one is better,in terms of practical purposes?

Many fast algorithms are based on the classical
divide-and-conquer strategy. A problem is broken
down into smaller problems, recursively, until
the size of each problem is sufficiently smaller
so that the solution becomes trivial. Then, the solutions
of the smaller problems are combined, recursively, to
form the solution of the given problem.

In DFT (FFT) algorithms, we can break a given problem
into two smaller problems by either dividing the time-domain
samples or the DFT coefficients. In the first case, the
algorithm is called decimation-in-time (DIT).
In the second case, the
algorithm is called decimation-in-frequency (DIF).

Due to the repeated decomposition of data samples or
coefficients, either the
time-domain samples have to be arranged in a bit-reversed
order or the DFT coefficients will appear in that order.
While both the DIF and DIT algorithms are equivalent in all
respects, combining the task of placing the input data in the
bit-reversed order and the first stage processing is relatively
easier in the DIT version of the algorithm. Therefore, it is more
often used in practice.

For more details, please refer

1. The Discrete Fourier Transform,
Theory, Algorithms, and Applications,
D. Sundararajan
ISBN 981 02 4521 1
World Scientific, 2001.

2. Sundararajan, D., November 9, 2009, \"Fundamentals of the DFT (fft) Algorithms\",
http://www.dsprelated.com/documents.php

Sir,why we use the DFT? I want know its apllication in practical use?

DFT is used when a finite length discrete sequence is to be decomposed
in terms of sinusoids or complex exponentials. IIn many applications, the data
to be analyzed comes in different forms. In those cases, the other versions of
Fourier analysis (Fourier seies, Fourier transform, or Discrete-time
Fourier transform) have to be used. But, as integration of arbitrary signals
is required in these versions, it is difficult to carry out Fourier analysis as
such.
In practice, signals are sampled in time and truncated so that the DFT is
used to analyze the signals with an adequate accuracy.
One example of the application of DFT is to find the convolution of
two finite and discrete signals. If the signals to be convolved are continuous
and/or of infinite duration, the convolution output can be approximated
to a desired accuracy by sampling and/or truncatiing the signals
suitably. Remember that, the DFT is evaluated using fast algorithms with
the computational complexity N log N, where N is the number of samples.

Sir,
Can u please give modern project ideas on dsp especially in image processing.

sir how to calculate computational comlexity of 2D DCT and 2D DFT? plz reply

Projects in image processing
1. Digital image compression using wavelet transform
2. Digital image watermarking using wavelet transform

Computational complexity of 2-D DFT
The order is O((N)(N) log2 N)

The order of computational complexity of computing
2-D DCT is the same. Note that, the data for coputing
DCT is always real. Therefore, the exact number
of operation count will be about half of that of
computing a complex 2-D DFT.

sir, i need to do DFT for the FIR filter coefficeints,,
actually my project is to design a filter in LAB VIEW to measure the TOotal Harmonic Distortion( THD)

SO I THOUGHT to design an FIR filter then coefficents of FIR filter to do DFT, all these by tool lab view, and implement to the meters to measure THD

Hello sir,
My name is srikanth,am doing my PG IN VLSI DESIGN ,am very much interested to doing project in dsp . .i wished to work in a dsp related company in future . .so can u help me please. as how i want to prepare ?