On the History of the DFT (fft) Algorithms

Posted by Duraisamy Sundararajan on Nov 11 2009   

In dsp and many other areas of science and engineering, the Fourier transform is an indispensable tool. One of the major reasons for this is the availability of regular and fast algorithms for approximating its different versions by the finite and discrete version, the discrete Fourier transform (DFT). In this blog, a brief history of the DFT algorithms is presented.

The history essentially consists of a single line in that Gauss invented the radix-2 DFT algorithm in 1805 [1] and, surprisingly, it still remains the practically most efficient DFT algorithm for vast majority of applications, but with a more suitable data structure.

Let us see why it is so. Since it was invented by Gauss, it appeared in the books and journals, but went mostly unnoticed. It was after the publication of the paper by Cooley and Tukey [2], that the algorithm became so popular that, along with developments in computer hardware, the subject of digital signal processing was firmly established. As the multiplication operation was much more time consuming than other operations in the computers available at that time, higher-radix and prime factor algorithms [3], with less number of multiplications, came into prominence.

With a single cycle execution of the multiplication and multiply-accumulate operations in modern processors, the number of additions and overhead operations became a dominant factor in determining the execution of algorithms to the extent that in some processors, the radix-2 algorithm executes faster than the other algorithms with less number of total arithmetic operations. In addition, this algorithm is regular and simplest to understand, code, and debug. For these reasons, radix-2 DFT algorithm is most often used still.

It is known that the number of additions (actually additions/subtractions) in the radix-2 DFT algorithm is optimum. The addition/subtraction always occur as a pair. In the PM DFT algorithms, data and transform values are stored in an array of two-element vectors [4,5]. Using this data structure, the execution of the addition/subtraction can be optimized, resulting in reduced execution time. That is, two operands are read in, the sum and difference computed, and both the results stored at the same address.

In conclusion, the radix-2 DFT algorithm is practically most efficient for vast majority of applications. The DIF version is easier to understand in terms of waveform decomposition [6]. The DIT version is obtained by transposing the signal flow-graph of the DIF algorithm.

 

 

1. Heidaman, M. T., Johnson, D. H., and Burrus, C. S., (1984) Gauss and the History of the Fast Fourier Transform, it IEEE ASSP Magazine, 1(4):14-21

2. Cooley, J. W., and Tukey, J. W., (1965) An algorithm for the Machine Computation of Complex Fourier Series,” Math. Comp., vol. 19, pp. 297-301, April

3. Burrus, C. S. and Parks, T.W. (1985) DFT/FFT and Convolution Algorithms, Wiley, New York.

4. Sundararajan, D., Ahmad, M. O. and Swamy, M. N. S. (1994) “Computational Structures for Fast Fourier Transform Analyzers”, U.S. Patent, No. 5,371,696.

5. Sundararajan, D. (2001) Discrete Fourier Transform, Theory, Algorithms, and Applications, World Scientific, Singapore.

6. Sundararajan, D., November 9, 2009, ”Fundamentals of the DFT (fft) Algorithms”, http://www.dsprelated.com/showabstract/93.php

Rate this article:
posted by Duraisamy Sundararajan
Dr Sundararajan holds a Ph.D degree in Electrical Engineering from Concordia University, Montreal, Canada. He is the author of several DSP books and a dsp consultant. He jointly holds a U.S, a Canadian, and a British patent on DFT algorithms.

all articles by Duraisamy Sundararajan

Would you like to be notified by email when Duraisamy Sundararajan publishes a new blog?

  

What do PM and DIT stand for?

PM stands for plus-minus. DIT stands for
decimation-in-time and DIF stand for
decimation-in-frequency.

consider the following signal types
period, aperiod discrete continuous
what are the relations between a time domain signal and frequency domain when we take fourier transform?

are there any difference between dft and dtft?

The DFT is the frequency-domain representation of a discrete periodic
sequence. As it is periodic in the time-domain, its spectrum
is discrete. Remember that a finite sequence is assumed
to be periodic in DFT computation.

The DTFT is the frequency-domain representation of a discrete aperiodic
sequence. As it is aperiodic in the time-domain, its spectrum
is continuous. Remember that the spectra of both the DFT and the DTFT
are periodic, since the corresponding time-domain sequences are discrete.


Fourier transform:
continuous and aperiodic in the time-domain - continuous and aperiodic in the frequency-domain

Fourier series:
continuous and periodic in the time-domain - discrete and aperiodic in the frequency-domain

DTFT:
discrete and aperiodic in the time-domain - continuous and periodic in the frequency-domain

DFT:
discrete and periodic in the time-domain - discrete and periodic in the frequency-domain

For more details, please refer to the references of the blog.

what is dsp? Is it a digtalsignalprocessing or Is it a discretetimesignalprocessing? If so what is the reason?

dsp stands for digital signal processing. Signals are
processed in digital systems, such as a digital computer,
in the digital form. That is, the signal is sampled and
quantized. A discrete (or discrete-time) signal is a sampled
signal but not quantized. As it is difficult to analyze
a digital signal, the analysis of digital signals is usually
presented in books on digital signal processing in two parts.
For the most part, the discrete (unquantized) signal
analysis is presented. Then, the quantization effects are
taken into account.

Summarizing, practical signals are processed in digital
form and the theory is presented as the combination of
discrete-time signal processing and quantization effects.

Thank you sir for the information you have given.

I have a doubt since long time. What is the exact significance of the Convolution.?
what exactly it represents?

Assume that a savings account in a bank yields 10 percent of interest per year for
deposit. If we deposit one dollar in the bank now,
the money in the account next year will be 1.1 dollar, the year after that
it will be (1.1)(1.1)=1.21 dollar, etc.
The savings account is a process and the rate of growth of money of one dollar is its impulse
response. Let us say we open an account with a deposit of
300 dollars and deposit another 200 dollars at the beginning of the next year.
The deposits are the inputs. Let us try to find the money, which is the output, in
our account for two years assuming that we make no other deposits or
withdrawals in this period.
At the beginning of this year, the balance is 300 dollars that we have deposited. At the
beginning of the next year the balance will be (300)(1.1) + 200.
The year after that the balance will be (300)(1.1)(1.1) + (200)(1.1).
This deposit calculation, which we learned years before our first dsp
or signals and systems course, is a convolution operation.
Formally, we say that the output of a linear time-invariant system
is given by the convolution of the system impulse response with the input.
The convolution operation is finding the sum of products of the impulse response and the
input, after time-reversing one of them.
I have taken this example from reference [5] to this blog, in which you will find
a formal description of the convolution operation (any dsp or signals and systems book
will give a description of the convolution operation in the first few chapters).

One interpretation of the convolution operation is that it is an expression
giving the relationship between the input and output of a system that is determined
by the impulse response.
Another interpretation is that it is an interaction of two functions that generates a
third function.
In system analysis (using the first interpretation) or in signal analysis
(using the second interpretation), the convolution operation is extensively
used and is a fundamental operation in signal processing.

Thank you sir for your kind response.

Can i ask questions from communication part ?
or
I should ask questions from only from DSP?

only from dsp.

sir i would like to publish a technical paper in any magazine or journal. I do not know how to proceed .Could you tell me how to start it. Does it require any qualification.

Good writing is simply putting the right word to describe something so that
it is impossible to find a better word for that purpose.

The first thing you should do to develop your writing is to read as many
well-written books and papers as possible in your area of specialization.

Writing process essentially consists of repeating the two steps of
writing and revision until you are satisfied with the quality of the
document.

Normally, an engineering student's first major writing assignment is the
final year undergraduate project report. Then, at graduate level, the student
will be required to write a thesis and some conference papers. After joining
a Ph. D program, a student has to write papers about his research work in
journals. During this level of writing, a student is guided by his professor
in the writing process.

Only with determination, hard work, and lone-term commitment, it is possible
to reach higher levels of writing (such as books, patents, tutorial papers, etc.)