Not a member?

# DSP Documents > Fundamentals of the DFT (fft) Algorithms

In this section, our goal is to keep a comprehensive and organised list of DSP related documents (papers, theses, etc) available for free on the web. Most of the documents are available in pdf format, so you'll need a pdf reader to view them. Add a document to the list.

To narrow the list, you can filter the documents by 'type':
All Types | Books | Master Theses | Others | Papers/Articles | PhD Theses

Page of Sorted by

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

(This item is protected by original copyright)

Rate this document:
5

# selvaram wrote:[ delete comment ]

12/17/2009

i want project topics related to DSP

# d_sundararajan wrote:[ delete comment ]

12/18/2009

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.

# kathir87 wrote:[ delete comment ]

1/28/2010

Thank you sir this is a nice document..

# ajaishukla wrote:[ delete comment ]

4/15/2010

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

# d_sundararajan wrote:[ delete comment ]

5/12/2010

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.

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

# pravin pawar wrote:[ delete comment ]

7/26/2010

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

# d_sundararajan wrote:[ delete comment ]

8/2/2010

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.

# harishg00 wrote:[ delete comment ]

9/9/2010

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

# yogesh1487 wrote:[ delete comment ]

9/11/2010

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

# d_sundararajan wrote:[ delete comment ]

10/29/2010

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

# d_sundararajan wrote:[ delete comment ]

10/29/2010

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.

# rashmi venugopal wrote:[ delete comment ]

1/20/2011

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

# SRI88SNS wrote:[ delete comment ]

3/16/2011

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 ?