What is the most lucid, intuitive explanation for the various FTs - CFT, DFT, DTFT and the Fourier Series?

Question

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 forever and this thread will serve as a super quick refresher whenever I (or anyone else) needs it.

Answer 1

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.

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.

Answer 2

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.

Answer 3

I just finished writing an expository note on this topic recently. I hope you would find it useful.

The link between Fourier transform (FT), Fourier series (FS), Discrete-Time Fourier Transform (DTFT) and Discrete Fourier Transform (DFT) is actually hidden in the Poisson summation formula $$ \sum_{n=-\infty}^{\infty} f(x+nT) = \frac{1}{T} \sum_{n=-\infty}^{\infty}\hat{f}\Bigl(\frac{n}{T}\Bigr) \mathrm{e}^{\mathrm{i} 2\pi n x / T}. $$ where $$ \hat{f}(\xi)= \int_{-\infty}^{\infty} f(x) \mathrm{e}^{-\mathrm{i} 2\pi\xi x} \,\mathrm{d}x $$ is the Fourier transform of a signal $f(x)$.

I really think the formula deserves more attention in the DSP community. It is much easier to justify rigorously than the approach using the Dirac comb (impulse train) distribution. The following will be a summary of most of the big ideas, but I would suggest you read the notes directly, because I spent way too much time typesetting it :).

The left-hand side of the formula $$ \sum_{n=-\infty}^{\infty} f(x+nT) $$ is a periodization of $f$ with period $T$. If you are familiar with the Dirac delta distribution, it is the same as convolving $f$ with a $T$-periodic impulse train (can you see why?).

On the right-hand side, $$ \hat{f}\Bigl(\frac{n}{T}\Bigr) $$ is a sampling of the spectrum $\hat{f}$ with sampling period $\frac{1}{T}$.

The formula might be very confusing at first, but it should be much clearer when we summarize it into a diagram.

Essentially, the Poisson summation formula tells us that, when we take the Fourier series expansion of the $T$-periodization of $f(x)$, the Fourier coefficients we get would be exactly a $\frac{1}{T}$-sampling of the spectrum $\hat{f}(\xi)$ (followed by a scaling)!

I hope you can appreciate the significance of this result. It turns out we can obtain the definition and inversion formula for DTFT just from this diagram. Notice the double arrows connecting the time and frequency domain. What if we switch the interpretation of $f$ and $\hat{f}$?, i.e. treating $\hat{f}$ as the signal in the time domain and $f$ as the signal in the frequency domain? If you are convinced that the formula works if we switch $f$ with $\hat{f}$, $\mathrm{i}$ with $-\mathrm{i}$, $x$ with $\xi$, etc., then we can relabel the diagram and obtain (for $T=1$) Notice that since (this version of) the Fourier transform is unitary, the upper half of the diagram stays the same, while for the lower half of the diagram, we somehow obtained a frequency representation of a discrete signal $g[n]$. This is exactly how we can derive the definition and inversion formula for DTFT, though as you might have noticed, it's not exactly the same as the usual definition of DTFT.

We looked at the case for $T=1$ first because I don't want the extra scaling factor to mess up your intuitions. Since sampling is the main operation, we will first switch $T$ with $\frac{1}{T}$. Also, we will keep the scaling in the frequency domain by putting the scaling factor on the other side, though it might not be immediately obvious that we can do so. The diagram for the general case looks like this

Notice there is a problem in our current definition of DTFT, if we want to calculate the spectrum of a discrete signal, we need to know the sampling period $T$ first! This is why we need to introduce the concept of a normalized frequency $\omega$, defined by $$ \omega = 2\pi T \xi $$ for a frequency $\xi$ and sampling period $T$. This gives us the actual definition of the DTFT $$ \hat{f}(\omega) = \sum_{n=-\infty}^{\infty} f[n] \mathrm{e}^{-\mathrm{i}\omega n} $$ and the corresponding inversion formula. The derivations would take some space so please read Section 5.4 if you want to learn more about it.

It turns out that we can extend the relabeling trick even further. What if we replace $f$ with a periodic function and replace Fourier transform with Fourier series? Consider the following diagram, which is constructed by directly mimicking the diagram above.

Can you figure out what the "???" should be in the diagram? If you can answer this question, congratulations, you've discovered the relationship between Fourier series and DFT.

Hint:

It turns out that this is not the only way we can obtain the DFT. What if you switch the time and frequency representation of the diagram above?

Hint:

As a summary, FT, FS, DTFT, DFT is exactly connected by a cube, where periodization in one domain corresponds to sampling in the other domain:

Note that there are two routes to go from the Fourier transform to the DFT.

Please read my write-up for more details. It is exactly inspired by this relabeling trick I discovered a while ago. I hope this can be illuminating.

As a side note, what would you get if you take $T \to \infty$ in the Poisson summation formula?

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.