Fast Fourier Transform Introduction

Contents

Introduction

The Discrete Fourier Transform (DFT) today is one of widespread analysis tools which is used in all branches of science and engineering. However before emergence of computers the DFT was seldom used as the DFT calculation of 32 samples requires 1024 operations of complex multiplication and summing.

The first mention of the function expansion algorithm in a trigonometric series where periodicity properties of trigonometric functions for the accelerated analysis were used refers to Gauss’s work [1].
Nobody had paid attention to this work until the fast Fourier transform algorithms were widely adopted.

The first program realization of the FFT algorithm was carried out in the early sixties of the XXth century by James Cooley in the computer IBM center under the supervision of John Tukey, and in 1965 they published the article [2] devoted to the fast Fourier transform algorithm.
From that point the real FFT-mania has begun.
Many works devoted to the FFT algorithm are being published, monographs are being issued one by one, programmers are competing in efficiency of the algorithm realization. The FFT becomes the main tool of the spectrum signal analysis.

It is necessary to note that the development principle of fast algorithms by means of recursive reducing to smaller problems was used by the Soviet mathematician Anatoly Karatsuba to implement the fast algorithm of number multiplication (the Karatsuba multiplication) for the first time [3].
As a result the “hypothesis $n^2$” formulated by Kolmogorov to assess complexity of $n-$valued multiplication was disproved.
Today the development principle of fast algorithms bears the name “divide and conquer” [4] and it is used for a wide range of tasks: FFT, instant search, fast matrix multiplication and others.

FFT Algorithm Development Principle

Consider the equation for the discrete Fourier transform:

$$
S(k) = \sum_{n= 0}^{N-1} s(n) \cdot \exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k\right), \text{ } k = 0 \ldots N-1.
$$

(1)

The DFT associates $N$ complex spectrum samples $S(k)$, $k=0 \ldots N-1$ with $N$ signal samples $s(n)$, $n=0 \ldots N-1$ (in general a complex one).
To calculate one spectrum sample $N$ operations of complex multiplication and summing are required.
Thus, computational complexity of the DFT algorithm consists of $N^2$ complex multiplication and summing.

As the algorithm complexity grows in a quadratic correlation concerning the size of an input signal, it is possible to reach essential calculation acceleration if we manage to reduce the $N-$point DFT calculation to two $\frac{N}{2}-$point DFT as it is shown in Figure 1.

Figure 1. Replacement of the $N-$point DFT with Two $\frac{N}{2}-$point DFT

Replacement of one $N-$point DFT with two $\frac{N}{2}-$point DFT will lead to halving the number of operations, but operations of halving the sequence and association of two $\frac{N}{2}-$point DFT into one $N-$point are additionally required.

At the same time each of the $\frac{N}{2}-$point DFT can also be calculated by replacement the $\frac{N}{2}-$point DFT with two $\frac{N}{4}-$point which in their turn can be calculated by means of the $\frac{N}{8}-$point DFT. This recursion can be continued, so far it is possible to divide the input sequence into two.

In our case if $N = 2^L$, $L$ is a positive integer, we can halve the sequence $L$ times. For $N = 8$ ($L=3$) such dividing is presented in Figure 2.

Figure 2. Dividing and Conquering of the Sequence for $N=8$

The FFT algorithms which use selections with the length $N = 2^L$, are called “radix-2 FFT algorithms”. These algorithms have gained the greatest distribution because of their efficiency and the relative simplicity of the program realization.

We will consider two ways of dividing and conquering: decimation in time and decimation in frequency.

Inverse Fast Fourier Transform

The efficient direct FFT calculation algorithm can be used for the inverse transform too.
Pay attention that complex exponents in the equations for the direct and inverse DFT are complex conjugated:

$$
\exp \left( j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) = \Biggl(\exp \left( -j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) \Biggr)^{*},
$$

(2)

where $(\bullet)^*$ is a complex conjugate operator.

It is easy to show that the following equation is correct for two complex numbers $x = a+j \cdot b$ and $y = c+j \cdot d$:

$$
x \cdot y^* = \left(x^* \cdot y \right)^*.
$$

(3)

In connection with the IDFT equation it is possible to write down:

$$
s(n) = \frac{1}{N} \sum_{k = 0}^{N-1} S(k) \cdot \Biggl(\exp \left(-j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) \Biggr)^* = \frac{1}{N} \Biggl(\sum_{k = 0}^{N-1} S^*(k) \cdot \exp \left(-j \cdot \frac{2\pi}{N} \cdot n \cdot k \right) \Biggr)^*.
$$

(4)

Thus, take the complex conjugated spectrum $S^*(k)$, the direct DFT is carried out and the result is exposed to complex conjugate. The IDFT calculation when using the DFT is given in Figure 3.

Figure 3. Calculation of the Inverse FFT

If instead of the DFT we use the FFT, we will get the inverse fast Fourier transform (IFFT). At that, for carrying out complex conjugate it is necessary only to change a sign before an imaginary spectrum part before the FFT function call and the result after the FFT.

Conclusions

Thus, we considered an acceleration way of calculations upon calculating the DFT, and also converted the IFFT to the direct one. Now it is necessary to consider ways of dividing and conquering providing essential reduction of calculations. In the following sections we will consider FFT algorithms in detail on grounds of two decimation in time and decimation in frequency.

You can provide your any feedbacks, questions and wishes in the message board or в guestbook.

Reference

[1]
M. Heideman, D. Johnson, C. Burrus
Gauss and the history of the fast fourier transform.
IEEE ASSP Magazine, Vol. 1, Issue 4, October 1984, p. 14-21

[2]
James W. Cooley and John W. Tukey
An Algorithm for the Machine Calculation of Complex Fourier Series.
Mathematics of Computation, 1965 p. 297–301.

[3]
A. Karatsuba and Yu. Ofman
Multiplication of Many-Digital Numbers by Automatic Computers.
Proceedings of the USSR Academy of Sciences. Vol. 145, p.293–294

[4]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
Data structures and algorithms.
Menlo, Addison-Wesley, 1983 .

[5]
Richard E. Blahut
Fast Algorithms for Signal Processing.
Cambridge University Press, 2010.

[6]
Nussbaumer Henri J.
Fast Fourier Transform and Convolution Algorithms.
Second Corrected and Updated Edition.
Springer-Verlag, 1982.

[7]
Oppenheim Alan V. and Schafer Ronald W.
Discrete-Time Signal Processing
Second Edition.
Prentice-Hall, New Jersey, 1999.