### Continuous Signal

What is the Fourier Transform ? This concept can be quite difficult to grasp at first. The Fourier Transform is a formula linking the spatial representation of a function with its representation in the frequency domain.

A signal s can be represented either by its value at a time t, s(t), or by its amplitude S for the frequency f, S(f). Example; we have a signal s

s(t) = A * cos( w* t )

Its Fourier Transform is equal to

S(f) = √(π/2) * [ A * δ (-w + f) + A * δ(w + f) ]

Which pretty much means that it is worth 0 everywhere but when f = w. Which is normal. Since s is a cosine signal, it only expresses a single frequency. Therefore, when computing S(f) on every frequency, it only has an amplitude if f is the frequency of the cosine of s.

Usually, we consider that s and S are two formulation of the same function. To go back and forth between them, we use the following formulas

Keeping in mind that . You may note that those equations are linear. This means that is we set two functions s and s’ and that we note F(s) the Fourier transform of s, we have

F(s+s’) = F(s) + F(s’)

A * F(s) = F(A*s)

This leads a very nice property when convolving two functions; the Fourier transform of the convolution of a function s and a function s’ is actually equal to the product of their Fourier Transform.

F(s ∗ s’) = F(s)F(s’)

### Discretely sampled data

The analytical functions stated above work well except in one case; when s is not defined analytically but rather as a set of samples.

Let’s do some sampling theory first. When sampling a data with a samplig rate f_{s }, Nyquist theorem tells us that you con only recover frequency between f_{c } and – f_{c } with

This has two consequences. First, if a function s(t) is *bandwith limited* to frequencies within the range [ -f_{c }, f_{c} ], then s is completely determined by its samples. The other one is that if s(t) is NOT bandwith limited in [ -f_{c }, f_{c} ], then aliasing appear. Every frequency outside the range will be aliased (falsely translated). Once you have aliasing, there is pretty much nothing you can do.

To detect aliasing in a function, you can look at its fourier transform. If the function is correctly sampled, this transform should be 0 outside [ -f_{c }, f_{c} ]. Therefore, it should lean to 0 when the frequencies lean to f_{c} . If it leans towards a finite value, there is great chances you have aliasing.

Once you have a correctly sampled signal s, how do you compute its fourier transform ? If you try to use the formulas given above, you will encounter a problem trying to integrate on values that are not given by the sampled. If we have N samples in input, we will be able to determine the Fourier coefficient for no more than N frequencies. We will then f estimate S(f) for

You may notice that the extreme values of n are the critical frequency range. From here, we replace the integrals with discrete sums

### Fast Fourier Transform

Computing the discrete Fourier transform of N points appears to be a O(n²) problem. There is in fact a solution to compute it an a O(Nlog_{2}(N)) process; this is the Fast Fourier Transform.

This algorithm starts with the statement that the Discrete Fourier transform of a set a samples N can be expresses ad the sum of the DFT of the even samples and the DFT of the odd samples. This is known as the Danielson-Laczos lemma.

And, interesting fact, it happens to be recursive ! However, this recursivity comes at the price that N is IMPERATIVELY a power of 2. If N is not a power of 2, you should pad it up with 0 until you get a power of 2.

We apply recursively this Lemma until we get to compute Fourier transforms of length one. This means that we have to compute a S from a single sample s_{n } that has been successively even or odd log_{2}(N) times. According to the equation of the discrete fourier transform, S is equal to its corresponding s_{n}.

Therefore, all we need to do is find which n correspond to the even/odd pattern. Fun fact, this is super easy to get ! Juste reverse the even/odd pattern and set e=0 and o=1. And there you get the binary value of n ! This is because all those even and odd classification are merely tests over the last bit of n.

The whole FFT algorithm starts by rearranging the N samples in bit reversed order; { 00, 01, 10, 11} becomes {00, 10, 01, 11} (you read the bit from right to left). Therefore, you can apply Danielson-Laczos lemma on the values pairs by pairs in this table until you get the final transform, after Nlog_{2}(N) operations.

[1] http://www.nr.com/

[2] http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/