Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

Everyone discusses the Fourier transform when discussing signal processing. Why is it so important to signal processing and what does it tell us about the signal?

Does it only apply to digital signal processing or does it apply to analog signals as well?

share|improve this question
7  
Recently a discussion about Fourier transforms was revived on math.SE, and I thought that people on this site might find some of it worthwhile, and might even want to participate. –  Dilip Sarwate Oct 14 '11 at 1:35

7 Answers 7

up vote 79 down vote accepted

This is quite a broad question and it indeed is quite hard to pinpoint why exactly Fourier transforms are important in signal processing. The simplest, hand waving answer one can provide is that it is an extremely powerful mathematical tool that allows you to view your signals in a different domain, inside which several difficult problems become very simple to analyze.

Its ubiquity in nearly every field of engineering and physical sciences, all for different reasons, makes it all the more harder to narrow down a reason. I hope that looking at some of its properties which led to its widespread adoption along with some practical examples and a dash of history might help one to understand its importance.

History:

To understand the importance of the Fourier transform, it is important to step back a little and appreciate the power of the Fourier series put forth by Joseph Fourier. In a nut-shell, any periodic function $g(x)$ integrable on the domain $\mathcal{D}=[-\pi,\pi]$ can be written as an infinite sum of sines and cosines as

$$g(x)=\sum_{k=-\infty}^{\infty}\tau_k e^{\jmath k x}$$ $$\tau_k=\frac{1}{2\pi}\int_{\mathcal{D}}g(x)e^{-\jmath k x}\ dx$$

where $e^{\imath\theta}=\cos(\theta)+\jmath\sin(\theta)$. This idea that a function could be broken down into its constituent frequencies (i.e., into sines and cosines of all frequencies) was a powerful one and forms the backbone of the Fourier transform.

The Fourier transform:

The Fourier transform can be viewed as an extension of the above Fourier series to non-periodic functions. For completeness and for clarity, I'll define the Fourier transform here. If $x(t)$ is a continuous, integrable signal, then its Fourier transform, $X(f)$ is given by

$$X(f)=\int_{\mathbb{R}}x(t)e^{-\jmath 2\pi f t}\ dt,\quad \forall f\in\mathbb{R}$$

and the inverse transform is given by

$$x(t)=\int_{\mathbb{R}}X(f)e^{\jmath 2\pi f t}\ df,\quad \forall t\in\mathbb{R}$$

Importance in signal processing:

First and foremost, a Fourier transform of a signal tells you what frequencies are present in your signal and in what proportions.

Example: Have you ever noticed that each of your phone's number buttons sounds different when you press during a call and that it sounds the same for every phone model? That's because they're each composed of two different sinusoids which can be used to uniquely identify the button. When you use your phone to punch in combinations to navigate a menu, the way that the other party knows what keys you pressed is by doing a Fourier transform of the input and looking at the frequencies present.

Apart from some very useful elementary properties which make the mathematics involved simple, some of the other reasons why it has such a widespread importance in signal processing are:

  1. The magnitude square of the Fourier transform, $\vert X(f)\vert^2$ instantly tells us how much power the signal $x(t)$ has at a particular frequency $f$.
  2. From Parseval's theorem (more generally Plancherel's theorem), we have $$\int_\mathbb{R}\vert x(t)\vert^2\ dt = \int_\mathbb{R}\vert X(f)\vert^2\ df$$ which means that the total energy in a signal across all time is equal to the total energy in the transform across all frequencies. Thus, the transform is energy preserving.
  3. Convolutions in the time domain are equivalent to multiplications in the frequency domain, i.e., given two signals $x(t)$ and $y(t)$, then if

    $$z(t)=x(t)\star y(t)$$ where $\star$ denotes convolution, then the Fourier transform of $z(t)$ is merely

    $$Z(f)=X(f)\cdot Y(f)$$

    For discrete signals, with the development of efficient FFT algorithms, almost always, it is faster to implement a convolution operation in the frequency domain than in the time domain.

  4. Similar to the convolution operation, cross-correlations are also easily implemented in the frequency domain as $Z(f)=X(f)^*Y(f)$, where $^*$ denotes complex conjugate.
  5. By being able to split signals into their constituent frequencies, one can easily block out certain frequencies selectively by nullifying their contributions.

    Example: If you're a football (soccer) fan, you might've been annoyed at the constant drone of the vuvuzelas that pretty much drowned all the commentary during the 2010 world cup in South Africa. However, the vuvuzela has a constant pitch of ~235Hz which made it easy for broadcasters to implement a notch filter to cut-off the offending noise.[1]

  6. A shifted (delayed) signal in the time domain manifests as a phase change in the frequency domain. While this falls under the elementary property category, this is a widely used property in practice, especially in imaging and tomography applications,

    Example: When a wave travels through a heterogenous medium, it slows down and speeds up according to changes in the speed of wave propagation in the medium. So by observing a change in phase from what's expected and what's measured, one can infer the excess time delay which in turn tells you how much the wave speed has changed in the medium. This is of course, a very simplified layman explanation, but forms the basis for tomography.

  7. Derivatives of signals (nth derivatives too) can be easily calculated(see 106) using Fourier transforms.

Digital signal processing (DSP) vs. Analog signal processing (ASP)

The theory of Fourier transforms is applicable irrespective of whether the signal is continuous or discrete, as long as it is "nice" and absolutely integrable. So yes, ASP uses Fourier transforms as long as the signals satisfy this criterion. However, it is perhaps more common to talk about Laplace transforms, which is a generalized Fourier transform, in ASP. The Laplace transform is defined as

$$X(s)=\int_{0}^{\infty}x(t)e^{-st}\ dt,\quad \forall s\in\mathbb{C}$$

The advantage is that one is not necessarily confined to "nice signals" as in the Fourier transform, but the transform is valid only within a certain region of convergence. It is widely used in studying/analyzing/designing LC/RC/LCR circuits, which in turn are used in radios/electric guitars, wah-wah pedals, etc.


This is pretty much all I could think of right now, but do note that no amount of writing/explanation can fully capture the true importance of Fourier transforms in signal processing and in science/engineering

share|improve this answer
2  
Nice answer in giving some realworld application using FT and its properties. +1. –  goldenmean Aug 19 '11 at 10:31
    
"This idea that a function could be broken down into its constituent frequencies was a powerful one" I think the Taylor series was first. en.wikipedia.org/wiki/Taylor_series#History en.wikipedia.org/wiki/Fourier_analysis#History "a Fourier transform of a signal tells you what frequencies are present in your signal and in what proportions." Like a prism shows you what frequencies of light are present in a light source –  endolith Aug 19 '11 at 14:10
2  
@endolith I didn't say the Fourier transform was first, just that it is powerful. Note that a Taylor series is not an expansion in terms of the constituent frequencies. For e.g., the Taylor series of $\sin(\alpha x)$ about $0$ is $\alpha x-\alpha^3x^3/3!+\alpha^5x^5/5!\ldots$, whereas the Fourier transform of $\sin(\alpha x)$ is $\left[\delta(\omega-\alpha)-\delta(\omega+\alpha)\right]/(2\jmath)$ (give or take some normalization factors). The latter is the correct frequency representation, so I'm not sure if any comparisons with Taylor series is apt here. –  Lorem Ipsum Aug 19 '11 at 14:34
    
@yoda: Yes, I miscomprehended as "broken down into a sum of simpler functions", and was just pointing out an alternative way to do that –  endolith Aug 19 '11 at 15:04
4  
When I started reading this response, somehow I knew @yoda wrote it before I scrolled down to see who it actually was = ) –  Phonon Aug 19 '11 at 16:06

Yoda's great answer misses one thing: The Fourier transform decomposes signals into constituent complex exponentials:

$$ e^{\jmath \omega t}$$

and complex exponentials are the eigenfunctions for linear, time invariant systems.

Put simply, if a system, $H$ is linear and time-invariant, then its response to a complex exponential will be a complex exponential of the same frequency but (possibly) different phase, $\phi$, and amplitude, $A$, --- and the amplitude may be zero:

$$y = H[e^{\jmath \omega t}] = A e^{\jmath \phi} e^{\jmath \omega t} $$

So the Fourier transform is a useful tool for analyzing linear, time-invariant systems.

share|improve this answer
    
excellent point! –  nibot Aug 25 '11 at 20:45

Additional to Peter's answer, there is another reason which is also related to the eigenfunction. That's, $e^{kx}$ is the eigenfunction of the differential operator $\frac{d^n}{dx^n}$. That's why Fourier transform (corresponding to pure imaginary $k$) and Laplace transform (corresponding to complex $k$) can be used to solve differential equations.

Since $e^{kx}$ is the eigenfunction of both convolution and differential operator, maybe that's one the of the reasons why LSIV system can be represented by differential equations.

share|improve this answer

Another reason:

It's fast (e.g. useful for convolution), due to its linearithmic time complexity (specifically, that of the FFT).
I would argue that, if this were not the case, we would probably be doing a lot more in the time domain, and a lot less in the Fourier domain.

Edit: Since people asked me to write why the FFT is fast...

It's because it cleverly avoids doing extra work.

To give an concrete example of how it works, suppose you were multiplying two polynomials, $a_0 x^0 + a_1 x^1 + \ldots + a_nx^n$ and $b_0 x^0 + b_1 x^1 + \ldots + b_nx^n$.

If you were to do this naively (using the FOIL method), you would need approximately $n^2$ arithmetic operations (give or take a constant factor).

However, we can make a seemingly mundane observation: in order to multiply two polynomials, we don't need to FOIL the coefficients. Instead, we can simply evaluate the polynomials at a (sufficient) number of points, do a pointwise multiplication of the evaluated values, and then interpolate to get back the result.

Why is that useful? After all, each polynomial has $n$ terms, and if we were to evaluate each one at $2n$ points, that would still result in $\approx n^2$ operations, so it doesn't seem to help.

But it does, if we do it correctly! Evaluating a single polynomial at many points at once is faster than evaluating it at those points individually, if we evaluate at the "right" points. What are the "right" points?

It turns out those are the roots of unity (i.e. all complex numbers $z$ such that $z^n = 1$). If we choose to evaluate the polynomial at the roots of unity, then a lot of expressions will turn out the same (because a lot of monomials will turn out to be the same). This means we can do their arithmetic once, and re-use it thereafter for evaluating the polynomial at all the other points.

We can do a very similar process for interpolating through the points to get back the polynomial coefficients of the result, just by using the inverse roots of unity.

There's obviously a lot of math I'm skipping here, but effectively, the FFT is basically the algorithm I just described, to evaluate and interpolate the polynomials.
One of its uses, as I showed, was to multiply polynomials in a lot less time than normal. It turns out that this saves a tremendous amount of work, bringing down the running time to being proportional to $n \log n$ (i.e. linearithmic) instead of $n^2$ (quadratic).

Thus the ability to use the FFT to perform a typical operation (such as polynomial multiplication) much faster is what makes it useful, and that is also why people are now excited by MIT's new discovery of the Sparse FFT algorithm.

share|improve this answer
    
What is linearithmic time complexity? I won't downvote this answer but I don't think it adds anything of value to this discussion on Fourier transforms. –  Dilip Sarwate May 8 '12 at 11:05
1  
@DilipSarwate I suspect he's using it as shorthand for O(n*log(n)). –  Jim Clay May 8 '12 at 12:50
    
@DilipSarwate: Jim is right. It has everything to do with (discrete) Fourier transforms. Without the FFT, your Fourier transforms would take time proportional to the square of the input size, which would make them a lot less useful. But with the FFT, they take time proportional the size of the input (times its logarithm), which makes them much more useful, and which speeds up a lot of calculations. Also this might be an interesting read. –  Mehrdad May 8 '12 at 13:01
    
You should mention WHY its fast. Where its fast and why do we care that its fast? –  CyberMen May 8 '12 at 15:03
1  
I think that this answer is legitimate. It should be paraphrased - "Beside all the nice characteristics explained in other peoples answer, FFT allows it to become a feasible approach in real-time applications". –  Andrey Nov 15 '12 at 18:30

The other people have given great, useful answers. Just think about some signal: you only care what frequencies are in it (and their phase), not about the time domain. I do not this that this is a final or complete answer, but just another reason why the Fourier transform is useful.

When you have some signal, it could be composed of an infinite (or close to) number of frequencies, depending on your sampling rate. But, that's not the case: we know that most signals have the fewest number of frequencies possible, or that we're sampling at a high enough rate.

If we know that, why can't we use it? That's what the field of compressed sensing does. They know that the most likely signal is one that has the least error and has the fewest frequencies. So, they minimize the overall error relative to our measurements as well as the magnitude of the Fourier transform.

A signal of a few frequencies often has a minimal Fourier transform, or mostly zeros (aka "sparse," as they say in compressed sensing). A signal of one frequency just has a delta function as the transform, for example.

We can use the formal mathematical definition too.

$\bar{x} = \textrm{arg min } ||y-Ax|| + \lambda||F(x)||$

Here, all we're doing is minimizing the error (first set of $||\cdot||$) and minimizing the Fourier transform (second set of $||\cdot||$). Here, we have

  • $\bar{x}$ as our reconstructed signal (most likely close to the original)
  • $y$, our measurements
  • $A$, a selection matrix
  • $x$, our signal
  • $\lambda$ some constant
  • $F(x)$ the Fourier transform.

You may recall that Nyquist said that you have to measure at twice the highest frequency to get a good representation. Well, that was assuming you had infinite frequencies in your signal. We can get past that!

The field of compressed sensing can reconstruct any signal that's mostly zeros (or sparse) in some domain. Well, that's the case for the Fourier transform.

share|improve this answer

The main importance of the Fourier transform lies with system analysis. The main constituent of our universe is vacuum, and vacuum is a fundamentally linear and time-invariant carrier of fields: different fields superimpose by adding their respective vectors, and regardless of when you repeat the application of certain fields, the outcome will be the same.

As a consequence, a lot of systems also involving physical matter are to a good approximation behaving as linear, time-invariant systems.

Such LTI systems can be described by their "impulse response", and the response to any time-distributed signal is described by convolving the signal with the impulse response.

Convolution is a commutative and associative operation, but it is also quite computationally and conceptually expensive. However, the convolution of functions is mapped by Fourier transform into piecewise multiplication.

That means that the properties of linear time invariant systems and their combinations are much better described and manipulated after Fourier transformation.

As a result, things like "frequency response" are quite characteristic for describing the behavior of a lot of systems and become useful for characterizing them.

Fast Fourier transforms are in the "almost, but not quite, entirely unlike Fourier transforms" class as their results are not really sensibly interpretable as Fourier transforms though firmly routed in their theory. They correspond to Fourier transforms completely only when talking about a sampled signal with the periodicity of the transform interval. In particular the "periodicity" criterion is almost always not met.

There are several techniques for working around that, like the use of overlapping windowing functions.

However the FFT can be employed for doing discrete-time convolution when doing things right, and is it is an efficient algorithm, that makes it useful for a lot of things.

One can employ the basic FFT algorithm also for number theoretic transforms (which work in discrete number fields rather than complex "reals") in order to do fast convolution, like when multiplying humongous numbers or polynomials. In this case, the "frequency domain" is indistinguishable from white noise for basically any input and has no useful interpretation before you do the inverse transform again.

share|improve this answer

the physics relevance of fourier transform is that it tells the relative amplitude of frequencies present in the signal . it can be defined for both discrete time and continuous time signal. Any signal can be represented as mixture of many harmonic frequencies. Fourier transform help in filter applications , where we need only certain range of frequencies then we first need to know what are the amplitudes of frequencies contains in the signal.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.