## Posts tagged ‘FFT’

### Why can we have a Fast Fourier Transform ?

The Fourier transform was introduced by Fourier as a tool to solve heat equations, but is now used in its discrete version throughout the computing world more than trillions of times each second. It is probably more, I was assuming an average computer does billions of Discrete Cosine Transforms per day for Web browsing (JPEG images and Youtube) and music listening, but how huge is the contribution of millions of people watching MPEG-2 compressed television programs on satellite or terrestrial digital broadcasting?

It is thus important to know that the Fourier transform (which is always the Fast Fourier Transform) is really fast (especially when it is dozens, hundreds of times faster than the natural algorithm). I am not yet sure about the fast versions of variants of the discrete transform (cosine transforms and its friends), but I guess they can be derived from the classical case.

### What is it ?

The classical Fourier transform takes a T-periodic function f and computes for each integer n the integral

$f_n = \frac 1 {\sqrt T} \int_0^T f(t) \exp(-ni\omega t) dt$

where $\omega = 2\pi/T$. It separates f into components having period $T/n$, and has the property that the energy $E(f) = \frac 1 T \int |f(t)|^2 dt$ is the sum $\sum |f_k|^2$.

The discrete Fourier transform takes a discrete function given by $x = (x_0, x_1, \dots, x_{n-1})$ and computes the discrete analogue

$y_p = \sum_{q = 0}^{n-1} x_q \exp(-2i\pi \frac{pq}{n})$