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.
feedback
|
|
When I co-lectured Signals and Systems, 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:
I hope you find these notes helpful! Please feel free to distribute as you wish. | |||||||||
feedback
|
|
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. | |||
|
feedback
|
|
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. | |||
|
feedback
|
|
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. | |||
|
feedback
|
|
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. | ||||
|
feedback
|
|
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. | |||||||||||
feedback
|
