Fast Fourier Transform (FFT)



  3F3_3_Fast_ Fourier_Transform.pdf (Size: 3.38 MB / Downloads: 0)

Operation Count

How do we evaluate computational complexity?
count the number of real multiplications and
additions
by ¨real¨ we mean either fixed-point or floating point
operations depending on the specific hardware
subtraction is considered equivalent to additions
divisions are counted separately
Other operations such as loading from memory, storing in
memory, loop counting, indexing, etc are not counted
(depends on implementation/architecture) – present
overhead


Operation Count – Modern DSP

Modern DSP:

a real multiplication and addition is a single machine
cycle y=ax+b called MAC (multiply/accumulate)
maximum number of multiplications and additions must
be counted, not their sum
traditional claim ¨multiplication is much more timeconsuming
than addition¨ becomes obsolete


DFT Computational Complexity

Thus, for the input sequence of length N the number of
arithmetic operations in direct computation of DFT is
proportional to N 2.
For N=1000, about a million operations are needed!
In 1960s such a number was considered prohibitive
in most applications.


Discovery of the Fast Fourier Transform (FFT)

When in 1965 Cooley and Tukey ¨first¨ announced
discovery of Fast Fourier Transform (FFT) in 1965 it
revolutionised Digital Signal Processing.
They were actually 150 years late – the principle of the
FFT was later discovered in obscure section of one of
Gauss’ (as in Gaussian) own notebooks in 1806.
Their paper is the most cited mathematical paper ever
written.


Computational Load of full FFT algorithm

The type of FFT we have considered, where N = 2M, is
called a radix-2 FFT.
It has M = log2 N stages, each using N / 2 butterflies
Complex multiplication requires 4 real multiplications
and 2 real additions
Complex addition/subtraction requires 2 real additions
Thus, butterfly requires 10 real operations.
Hence the radix-2 N-point FFT requires 10( N / 2 )log2 N
real operations compared to about 8N2 real operations
for the DFT.