## Thursday, 12 December 2013

### Understanding Fourier Transform

Integral transforms are extremely essential to learning any subject related to signal processing. Moreover, they have immense applications in almost every engineering discipline related to electronics or computers. If you want to learn about anything related to signals, you would come across mentions of one integral transform or the other.

Although the family of integral transforms has quite a few of such transforms. This article addresses one of them, i.e. the fast fourier transform. It is probably the most widely used signal transformation techniques in which a digital signal is transformed from the time domain to the frequency domain and vice versa.

However, the subject of Fourier transform is normally orchestrated to the student in such a way so as to obscure the whole idea on as to what this simple and highly effective technique actually is all about. In as much as the student fails to understand the underlying concepts whereby the signal is transformed from one domain to the other, the student completely fails to understand the utility of this highly useful mathematical tool.

The aim of this article is to explain how Fourier transform actually works in as much of a lucid way as possible. It is assumed that the student has a basic familiarity with complex numbers and also with cross-correlation. Although it is not essential at this point for the student to have a good conceptual grasp over complex numbers. It is the aim of this article to deliver the conceptual caveats of the Fourier transform without the use of complex numbers. Complex numbers normally completely baffle the keen student. And that is probably one reason why they are called complex.

So lets begin our discourse with a revision of cross correlation. If you have read about it, that is fine. Otherwise, if you have read linear algebra, we shall leverage from that a little bit. From a linear algebraic point of view, the cross correlation equation is tantamount to the inner product of two vectors. We may further make our lives easy by assuming and saying that a vector is an array of real numbers.

So what does a correlation equation do? As the name suggests, the primary function of the correlation function is to find on as to how much two vectors or arrays correspond or resemble with each other. In other words, it tries to find out that how much two vectors or array are similar to each other. If the two arrays have a higher similarity, the result is usually a large number. If the two arrays do not have a high similarity, or if they have very low similarity, the result is usually a very small number. For instance, you can assume the result to be zero if the arrays are totally dissimilar to each other. I hope that understanding the role of cross correlation has been easy for you up to this point. If you have further curiosity about the correlation equation, please read (link).

Now how is correlation correlated with the Fourier transform? The answer is that the Fast Fourier Transform is actually a correlation function.What we actually do in this is that we take time domain signal of a certain length and try to find its correlation with another signal of a well known frequency and a well known magnitude. Let us call the former signal the signal under test. It could be a speech signal or signal from the cosmic microwave background. Let us also call the latter signal the reference signal for the purpose of lucidity. For the sake of simplicity let us assume it to be a speech signal in time domain. This simplifies our work because a speech signal is two dimensional. The horizontal axis shows the time and that is why we call it a time domain axis. The vertical axis represents the magnitude of the signal and is known as the magnitude or the amplitude of the signal.

A speech signal in the time domain is also a multi-spectral signal meaning that it has many frequency components in it. Asserting this is also important because it makes the application of Fourier transform a lot more sensible on such a signal. The very fact that a speech signal, or any other such signal, such as a signal from our local cell phone company, has many components of different frequencies embedded in it is the very reason we apply Fourier or such transforms on them. Clearly, we want to figure out which frequency components are embedded in them so that we could use them for some suitable purpose.

So how does Fourier Transform work? Given that it is basically a correlation function, we can conceive its function as follows. What we really do is that take a time domain signal of a given frequency and a given magnitude, we use it to apply a correlation operation on the signal under test. For instance, if our signal under test is a speech signal then applying the correlation operation returns to us the magnitude (or strength) of that particular frequency  of which our reference signal was made. This is how we compute the magnitude of one desired frequency in the signal.

In other words, if we wanted to know that whether our signal under test had a frequency component of, let us say, 90 hertz in it or not, we would choose our reference signal to be of 90 hertz. Performing cross correlation between this signal and the signal under test would return to us the magnitude of a 90 hertz component in the latter possibly multi-spectral signal.

If you have understood the explanation this far well, then it should be fairly easy for you to understand the rest of the Fourier transform. In rest of the transform what we simply do is that we choose various reference signals of differing frequencies and perform cross correlations between them and the signal under test one by one. At the end of each cross correlation we store the results in a separate place. These are the magnitudes of those frequencies. Assembling together the whole array of magnitudes in possibly an ascending order of frequency gives us what we may call it as the frequency domain outlook of the signal under test. Reiterated, what it simply tells us that what frequencies are present in the underlying signal and what are their magnitudes.

You may be getting slightly uneasy by the idea of doing all the calculations by hand. This may indeed be a cumbersome thing. However, you do not have to worry about that. Normally all the Digital signal processing packages, like the one that can be found in Matlab, can accomplish this with one line subroutines. Understanding the concept is however important.