## Fourier & co

### 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 fs , Nyquist theorem tells us that you con only recover frequency between fc and – f with This has two consequences. First, if a function s(t) is bandwith limited to frequencies within the range [ -fc ,  fc ], then s is completely determined by its samples. The other  one is that if s(t) is NOT bandwith limited in [ -fc ,  fc ], 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 [ -fc ,  fc ]. Therefore, it should lean to 0 when the frequencies lean to fc . 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(Nlog2(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 sn that has been successively even or odd log2(N) times. According to the equation of the discrete fourier transform, S is equal to its corresponding  sn. 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 Nlog2(N) operations.

Publicités