Fast Fourier Transform (Discrete Fourier Transform)

Some knowledge of complex number is assumed, but not much. Hence you may just read a few chapters of text-books on Complex Analysis (e.g. R.V.Churchill's "Complex Variables and Applications") and be able to understand the material here.

Fast Fourier Transform (another name, discrete Fourier Transform) is TOTALLY DIFFERENT FROM FOURIER TRANSFORM DEFINED ON THE REAL LINE, or that on Rⁿ. You will know it after reading this web page.

Suppose f:{0,1,2,3,...,N-1} -> C is a complex valued function defined only on N points. Discrete Fourier Transform of "f" will give another function F:{0,1,2,3,...,N-1} -> C . Applying the reverse transform to "F" will give back the function f.

In a previous Chapter, when we discussed "inner product space", we have discussed briefly Fourier Series. The coefficients of a Fourier Series can be evaluated, numerically, very quickly and easily with the use of Discrete Fourier Transform.

Discrete Fourier Transform is very useful is synchronous digital communication, in digital filtering, ....

THEOREM OF DISCRETE FOURIER TRANSFORM

(*) [Home]