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

Fourier

Keeping in mind that   b4e65f691d38a02a11091fac6285276b. 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

nyquist_limitThis 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

eq12-1-5

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

eq12-1-7_9

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.

eq12-2-3_1

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.

eq12-2-4

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.

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

Publicités

Répondre

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l'aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s