29
$\begingroup$

Even after having studied these for quite sometime, I tend to forget [if I'm out of touch for a while] how they are related to each other and what each stands for [since they have such similar sounding names]. I'm hoping you'd come up with an explanation that is so intuitive and mathematically beautiful that they'll get embedded into my memory for ever and this thread will serve as a super quick refresher whenever I [or anyone else] needs it.

$\endgroup$
  • 2
    $\begingroup$ Probably should start with the Fourier series $\endgroup$ – endolith Nov 14 '11 at 17:36
  • $\begingroup$ Are you familiar with Pontryagin duality? $\endgroup$ – Lorem Ipsum Nov 14 '11 at 18:29
  • $\begingroup$ @yoda - No. Could you please elaborate or point me to some good references? [I'll of course google it out.] $\endgroup$ – Vighnesh Nov 14 '11 at 18:56
  • 1
    $\begingroup$ "Steve on Image Processing": Fourier transforms addresses exactly this question. $\endgroup$ – nobar Apr 18 '14 at 5:11
  • $\begingroup$ I don't when to rewrite an answer here (unless required to). Yet, a possible answer is given in Can I study continuous time Fourier Transform and treat the rest as special cases following the Pontryagin duality track proposed by @LoremIpsum $\endgroup$ – Laurent Duval Sep 6 '17 at 22:19
23
$\begingroup$

I wrote this handout as a complement to Oppenheim and Willsky. Please take a look at Table 4.1 on page 14, reproduced below. (Click for larger image.) I wrote that table specifically to answer questions such as yours.

Comparison of Fourier series and Fourier transform.

Note the similarities and differences among the four operations:

  1. "Series": periodic in time, discrete in frequency
  2. "Transform": aperiodic in time, continuous in frequency
  3. "Continuous Time": continuous in time, aperiodic in frequency
  4. "Discrete Time": discrete in time, periodic in frequency

I hope you find these notes helpful! Please feel free to distribute as you wish.

$\endgroup$
  • 1
    $\begingroup$ Good summary. Note that the "Discrete Time Fourier Series" referenced in the table above is typically referred to as the discrete Fourier transform (DFT). $\endgroup$ – Jason R Nov 15 '11 at 12:35
  • $\begingroup$ To nitpick a little, this answer is indeed a good summary as Jason R says, and something that is worth having permanently on dsp.SE so that everyone can link to it for future reference, but it is not really responsive to the question which asked for an intuitive explanation of these issues (lucidity presumably being an added bonus and not absolutely reqjuired since it is mentioned in the title but not in the text of the question). $\endgroup$ – Dilip Sarwate Nov 15 '11 at 13:32
  • 2
    $\begingroup$ A great response Steve - I believe this is what the OP is looking for. Short, sweet, and to the point. $\endgroup$ – Spacey Nov 15 '11 at 16:49
  • $\begingroup$ Is it a misprint at the vary bottom of the page 2 of your handout? It's stated: $x(t)b(t-t_0)=x(t_0)b(t-t_0)$. Wasn't it meant $\int_{-\infty}^{\infty}x(t)b(t-t_0)dt = x(t_0)$? $\endgroup$ – mbaitoff Nov 17 '12 at 8:18
  • 1
    $\begingroup$ Not a misprint. Both of your statements are true, but I intended to write the first one because that section of the guide describes the basic, axiomatic definitions of the unit impulse. The second statement is then derived from those definitions: $\int_{\infty}^{\infty} x(t)\delta(t-t_0) dt = \int_{\infty}^{\infty} x(t_0)\delta(t-t_0) dt = x(t_0) \int_{\infty}^{\infty} \delta(t-t_0) dt = x(t_0)$. $\endgroup$ – Steve Tjoa Nov 20 '12 at 19:19
9
$\begingroup$

For a lucid and correct explanation of these concepts, you would have to go through some of the standard textbooks (Oppenheim-Schafer, Proakis-Manolakis or "Understanding Digital Signal Processing" by Richard Lyons which is a very good but relatively less popular book). But assuming a coffee-table discussion, I will be making some extremely loose statements in what follows. :)

For a general continuous time signal, you wouldn't expect any particular frequency to be absent, so its Fourier Transform (or the Continuous Fourier Transform) would be a continuous curve with support possibly -inf to +inf.

For a periodic continuous signal (period T), Fourier expressed the signal as a combination of sines and cosines having the same period (T, T/2, T/3, T/4, ...). Effectively, the spectrum of this signal is a series of spikes at locations 1/T, 2/T, 3/T, 4/T, ... This is called the Fourier Series representation. There is a theorem that says that the Fourier series representation of any periodic continuous time signal converges to the signal as you include more and more sines and cosines (or complex exponentials) in the mean square sense.

Moral so far: periodicity in time => spiky spectrum

On to discrete time... What happens if you sample a continuous time signal? It should be clear that for a sufficiently high signal, you wouldn't be able to reconstruct the signal. If you make no assumption about the frequencies in the signal, then given the sampled signal, there is no way you can say what the true signal is. In other words, different frequencies are represented equivalently in the discrete-time signal. Going through some math tells you that you can obtain the spectrum of the sampled signal from the original continuous signal. How? You shift the spectrum of the continuous time signal by amounts +-1/T, +-2/T, ... and add all the shifted copies (with some scaling). This gives you a continuous spectrum that's periodic with period 1/T. (note: the spectrum is periodic as a result of sampling in time, the time signal doesn't have to be periodic) Since the spectrum is continuous, you can as well represent it with just one of its periods. This is the DTFT ("Discrete-Time" Fourier Transform). In the case where your original continuous time signal has frequencies no higher than +-1/2T, the shifted copies of the spectrum don't overlap and hence, you can recover the original continuous-time signal by selecting one period of the spectrum (the Nyquist sampling theorem).

Another way to remember: spiky time signal => periodicity in spectrum

What happens if you sample a continuous-time periodic signal with sampling period T/k for some k? Well, the spectrum of the continuous-time signal was spiky to being with, and sampling it by some divisor of T means that the spikes in the shifted copies fall exactly on multiples of 1/T, so the resulting spectrum is a spiky periodic spectrum. spiky periodic time signal <=> spiky periodic spectrum (assuming that the period and sampling frequency are "nicely related" as above.) This is what is known as the DFT (Discrete Fourier Transform). FFT (Fast Fourier Transform) is a class of algorithms to compute the DFT efficiently.

The way DFT is invoked is as follows: Say you want to analyze a sequence of N samples in time. You could take DTFT and deal with one of its periods, but if you assume that your signal is periodic with period N, then DTFT reduces to DFT and you have just N samples of one period of DTFT which completely characterize the signal. You can zero-pad the signal in time to get a finer sampling of the spectrum and (many more such properties).

All of the above is useful only if accompanied by a study of DSP. The above are just some very rough guidelines.

$\endgroup$
7
$\begingroup$

Let $x(t)$ denote a bounded function with period $T$, that is, for all real numbers $t$, $x(t+T) = x(t)$. As a particular example, $\cos(2\pi t/T)$ is such a function. We want to find the "best" approximation $a_n\cos(2\pi nt/T)$ for this function where we wish to choose the coefficient $a_n$ so that $$\int_0^T (x(t) - a_n\cos(2\pi nt/T))^2\,\mathrm dt,$$ the squared error is as small as possible. Expanding out the integrand, we have $$\text{squared error} = \int_0^T x^2(t)\,\mathrm dt - 2a_n \int_0^T x(t)\cos(2\pi nt/T)\,\mathrm dt +(a_n)^2\int_0^T \cos^2(2\pi nt/T)\,\mathrm dt.$$ The leftmost integral is the energy $E$ delivered by one period of $x(t)$ while rightmost integral has value $T/2$ and so we see that $$\text{squared error} = E - 2a_n \int_0^T x(t)\cos(2\pi nt/T)\,\mathrm dt +(a_n)^2\frac{T}{2}.$$ Now. for $a > 0$, the quadratic function $az^2 + bz + c$ has a minimum at $z = -b/2a$ (midway between the roots $(-b/2a) \pm \sqrt{b^2 - 4ac}/2a$ !!) and so, since we have expressed the squared error as a quadratic function of $a_n$, the choice of $a_n$ that minimizes the squared error is $$a_n = \frac{2}{T}\int_0^T x(t)\cos(2\pi nt/T)\,\mathrm dt.$$ Similarly, choosing $b_n$ as $$b_n = \frac{2}{T}\int_0^T x(t)\sin(2\pi nt/T)\,\mathrm dt$$ minimizes the squared error between $x(t)$ and $b_n\sin(2\pi nt/T)$. Thus we see that Fourier series is nothing but a cheap trick to find the minimum squared error approximation to a periodic function $x(t)$ in terms of the sine and cosine signals of the same period and harmonics thereof.

$\endgroup$
4
$\begingroup$

Endolith is correct in that, if you actually start with the Fourier series, and see how it is extended to the Fourier transform, then things start beginning to make a lot of sense. I give a brief explanation for this in the first half of this answer.

A good (perhaps not simple) way to look at the Fourier transform family (by which I mean the 4 you've listed above), is through the Pontryagin duality goggles. It gives you a nice way to remember the different transforms by the original and transformed domains.

For a complex valued function on $\mathbb{R}$ (assuming other necessary conditions for the F.T. to exist), its Fourier transform is also a complex valued function on $\mathbb{R}$. The space $\mathbb{R}$ is a Pontryagin self-dual and you can say that if a transform in the entire family has $\mathbb{R}$ as both the original and transformed domain, then it is the Fourier transform (or CFT, as you called it).

A complex valued sequence of $n$ numbers can be viewed as a periodic complex valued function on $\mathbb{Z}/n\mathbb{Z}$, which is a cyclic integer modulo $n$ group (see finite abelian groups for more info). The transform for this sequence also has the domain $\mathbb{Z}/n\mathbb{Z}$ (self-dual) and this is the discrete Fourier transform.

The domain of the unit circle, $\mathbb{T}$ (all complex numbers with absolute value 1; also see circle group) and the set of integers $\mathbb{Z}$ are Pontryagin duals of each other. Similar to the first two, a transform between $\mathbb{Z}$ to $\mathbb{T}$ exists and is what we call the discrete-time Fourier transform and the other way round is the Fourier series, from which everything started.

This answer isn't fully complete and I'll perhaps build on this answer to make a few points clear when I have the time, but until then, this might be something to chew on until you get a more intuitive explanation from someone else. Also try reading variants of Fourier analysis on Wikipedia.

$\endgroup$
3
$\begingroup$

I think the foremost thing is to fundamentally understand why do we need fourier transforms. They are one of many possible signal transforms, but also one of the most useful ones. A transform basically transforms a signal into another domain which may give us insight about the signal in that domain, or or it may be that the domain is mathematically easy to work. Once we are done working in that domain, we can take inverse transform to get to the desired result more easily.

The most basic building block in fourier theory are monotones (sines and cosines). We can decompose a signal into its frequency components(monotones) using the fourier math. So, fourier transform basically transforms a signal from time domain to frequecy domain. The coefficient of each of the monotones in the fourier series tells us about the strength of that frequency component in the signal. Fourier transforms(CFT, DFT) explicitly gives us a frequency domain view of the signal. In nature, sines and cosines are the prominent waveforms. Synthetic signals like square wave, or signals having sharp fluctuations are less likely to occur naturally and not surprisingly compose of infinite range of frequencies as very clearly explained by fourier transforms. People had doubts whether any signal can be wretten as sum of sines/cosines. Fourier showed square waveform(which is far away from sines/cosines) can indeed be. White noise contains all the frequencies with equal strength.

Also, if you are working with fourier series, then the coefficients along with the phase term can be seen as that required to properly superimpose the constituent sinosoidal waveforms so that the superposition is indeed the required signal of which you are taking the transform. When working with fourier transforms, the complex numbers implicitly have the phase terms and the required magnitude of each of the monotones. (integration is roughly like summation. continuous=>integration, discrete=> summation)

I think once you have the understanding of the theme of a concept, rest all are just details that you will yourself have to understand by reading books. Reading about the application of fourier transforms to various fields will give you better perceptive.

$\endgroup$
2
$\begingroup$

A DFT is a transform of a vector of numbers pairs from one orthogonal space to another. Very commonly done as a numerical computation. For some reason, when taking one bunch of numbers from the real world, the 2nd bunch of numbers often turns out to be close enough to something quite useful.

I am reminded of the The Unreasonable Effectiveness of Mathematics in the Natural Sciences, especially regarding applying the DFT to many systems the seem to be approximated by various kinds of 2nd degree differential equation, even the sound of the coffee spoon I just dropped.

The other 3 XYZ-FTs make assumptions about the existence of some mythical infinite entities to help symbolic solutions fit on the whiteboard before the coffee gets too cold. They are the "spherical cows" of signal processing. The DTFT and Fourier Series pretend that one vector can be extended infinitely at the cost of infinite density of the other entity. The Fourier Series pretends that both entities can be infinite continuous functions.

Take enough math courses and one might even determine all the definitions and assumptions required to make these fictional entities exact and complete duals in some sense.

$\endgroup$
  • $\begingroup$ What is meant by "orthogonal space" in your first sentence? What is the space orthogonal to, or what special property does the space have that you are distinguishing it from other run-of-the-mill spaces by bestowing on it the adjective "orthogonal"? $\endgroup$ – Dilip Sarwate Nov 15 '11 at 3:40
  • $\begingroup$ Maybe "orthonormal" the more correct term for the vector spaces? $\endgroup$ – hotpaw2 Nov 15 '11 at 4:00
  • $\begingroup$ I have generally seen "rthogonal" and "orthonormal" applied as adjectives to small collections of vectors or matrices. $\mathbf x$ and $\mathbf y$ are orthogonal if $\langle\mathbf{x},\mathbf{y}\rangle=0$ and orthonormality requires in addition that the vectors have unit length. A matrix $A$ is called orthogonal if $AA^T$ is a diagonal matrix and orthonormal if $AA^T$ is the identity matrix. Does orthogonal or orthonormal space mean that all the vectors in the space are orthogonal to each other or are orthogonal and have unit length too? If so, can you give an example of such a space? $\endgroup$ – Dilip Sarwate Nov 15 '11 at 12:42
  • $\begingroup$ The dot product between all sines or cosines that are exactly periodic in a DFT aperture length is zero, except for identical frequency functions. Even if N is larger than the number of coffee beans in the bag. Make them unit amplitude for orthonormal. $\endgroup$ – hotpaw2 Nov 15 '11 at 21:21
  • $\begingroup$ Your space is the space of $N$-vectors of complex numbers (since you said "vectors of pairs of numbers"). There are no sines and cosines in the space, only $N$-tuples of complex numbers, and any orthogonal or orthonormal set of such $N$-vectors can contain at most $N$ such $N$-tuples. I would recommend deleting your comment above, and possibly even your whole answer. $\endgroup$ – Dilip Sarwate Nov 15 '11 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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