Discrete-time Fourier transform

I am a junior high school student who has a general fascination for electronics, programming, and the like. Recently, I have been learning about signal processing.

Unfortunately, I haven't done much calculus yet (forgive me), so I am a little fuzzy on things.

• If you were to compute the DTFT of a signal, what would be the difference between a $\sin$ or $\cos$ representation of that signal?

• With the DTFT I understand that the signal you input would be discrete in time, but how in the world can you achieve a continuous signal in the frequency domain?

• This leads to my second question, which is: how is the DTFT useful? Where has it been used with most applications and why?

I would appreciate any help.

• For my first question, I would guess that it is merely 90° out of phase. However, I have produced some graphs that indicate otherwise: i974.photobucket.com/albums/ae227/ElectroNerdy/… i974.photobucket.com/albums/ae227/ElectroNerdy/… – ElectroNerd Feb 4 '12 at 1:50
• Excellent questions. I created an answer(s) to those issues especially as they pertain to how DSP is brought to the minds of young people. (This is esp true at the university level). Shoot me an email and I can show you some of the material (too involved to post on here). – Spacey Feb 5 '12 at 22:53
• @Mohammad : Hi, can you share those materials with me at abidrahman2@gmail.com ? – Abid Rahman K Nov 7 '12 at 15:56

It's great that you are interested in signal processing at that early stage of your educational path.

The best path to get there is to read some introduction books on the topic. There are a lot of good and free online resources to get you started. [Note to the esteemed editor: good introduction books may a really good topic for a "sticky"]. I sometimes use

One of the most important mathematical concepts you will need to get your arms around are “complex” numbers”. It’s clearly a misnomer since it’s really not that complicated and clearly makes nearly all engineering math a lot simpler. Another great free resource for all things math related is http://www.khanacademy.org and in this case specifically http://www.khanacademy.org/video/complex-numbers--part-1?topic=core-algebra

Back to your first question: There are actually four different flavors of the Fourier Transform: Fourier Series (most likely to show up in high school), Fourier Transform, Discrete Fourier Transform and Discrete Fourier Series. All of them of them use a combination of both sine and cosine (or a complex exponential, which is essentially the same thing). You will need both.

Let’s say you calculate the sine and cosine Fourier coefficients of an input sine wave. (Under certain conditions) you’ll find that all Fourier coefficients will be zero except for one cosine and one sine coefficient. However, depending on the phase of the input sine wave you these two numbers will move around. You may get [0.707 0.707], or [1 0], or [0 -1], or [-0.866 0.5] etc. You will see that the sum of the squares of those two numbers will always be 1, but the actual values depend on the phase of the input sine wave.

If you want to deep dive, try this: http://www.dsprelated.com/dspbooks/mdft/

• Hi Hilmar, thanks for the reply! I have done quite a bit with complex numbers and have to agree: they are relatively simple. That is good to hear. After messing around a little more, I calculated the magnitude of both a sin and cos input signal to the DTFT and found that the amplitude was the same for both sin and cos. Thanks especially for the reference books, I will be busy for a while now. – ElectroNerd Feb 5 '12 at 20:49

You might want to look at the materials available through

The INFINITY Project: expanding signal-processing-based engineering education to the high school classroom

available here

• This looks very interesting; I may try and recommend it to my school. – ElectroNerd Feb 5 '12 at 21:00

DTFT Discrete Time Fourier Transform takes a discrete Infinite Signal as its input and its output in frequency domain is continuous and has a period 2*pi. Coming to the usage of it,in my experience DFT (Discrete Fourier Transform) is the one that gets used for practical purposes. Under Certain conditions, it is easy to show that DFT of a finite non-periodic Signal is nothing but equi-spaced samples of DTFT. In general, if we zero pad the sequence in time (or space) domain we get more and more samples of the DTFT.

Bottom line is DFT is very useful and DFT can be seen as equally spaced samples of DTFT, to get more samples of DTFT, doing a zero pad of the signal helps.

• That makes sense: I was told that the longer you sample in the time domain, the finer the resolution will be in the frequency domain once you calculate the DTFT. I have graphed this using Python and matplotlib (Sine + zero padding, DTFT of zero padding That is a neat trick to do. – ElectroNerd Feb 6 '12 at 22:47
• I have to say that you have to be careful here. A big misconception is that zero-padding your signal increases your frequency resolution - it doesnt. The only way to truly increase your frequency resolution is to have more data - more time domain samples. Now that being said, zero-padding does help if you want to look at your frequency spectrum with interpolated points between what you truly calculated. – Spacey Feb 7 '12 at 5:14

First of all, it helps to get the terminology sorted out:

A function in time-domain is known as a signal.
A function in frequency-domain is known as a spectrum.

As Hilmar said, there are four different flavors of "Fourier", which convert a signal to a spectrum. The Fourier series is the best to start with to truly understand the frequency domain. The basic premise is this: any periodic signal can be represented as an infinite sum of sines and cosines. In this equation, s(x) is a signal: $$a_n=\frac{1}\pi\int^Ts(x){\cos{nx}}\mkern3mudx$$ $$b_n=\frac{1}\pi\int^Ts(x){\sin{nx}}\mkern3mudx$$ $$s_f(x)=\frac{a_n}2+\sum_{n=1}^\infty{a_n\cos(nx)+b_nsin(nx)}$$ $$s_f(x)=s(x)$$

In this equation, an and bn are the real and imaginary parts of the discrete spectrum, respectively. Therefore as you can see, the Fourier transform of a cosine will be a real number, and for a sine, it will be an imaginary number. The T on the integral means that we are integrating over a full period of the signal. This is primarily used in what's called harmonic analysis, which I've mostly used when analyzing analog circuits with non-sinusoidal signals (square waves, triangular waves, etc.) But what if the signal isn't periodic? This doesn't work, and we have to turn to the Fourier transform.

The Fourier transform converts a continuous signal to a continuous spectrum. Unlike the Fourier series, the Fourier transform allows for non-period function to be converted to a spectrum. A non-periodic function always results in a continuous spectrum.

The discrete-time Fourier transform achieves the same result as the Fourier transform, but works on a discrete (digital) signal rather than an continuous (analog) one. The DTFT can generate a continuous spectrum because because as before, a non-periodic signal will always produce a continuous spectrum--even if the signal itself is not continuous. An infinite number of frequencies will still be present in the signal, even though it is discrete.

So, to answer your question, the DTFT is arguably the most useful one, as it operates on digital signals, and therefore allows us to design digital filters. Digital filters are far more efficient than analog ones. They're much cheaper, much more reliable, and much easier to design. The DTFT is used in several applications. Off the top of my head: synthesizers, sound cards, recording equipment, voice and speech recognition programs, biomedical devices, and several others. The DTFT in its pure form is mostly used for analysis, but the DFT which takes a discrete signal and yields a discrete spectrum is programmed into most of the above applications, and is an integral part of signal processing in computer science. The most common implementation of the DFT is the Fast Fourier Transform. It's a simple recursive algorithm which can be found here. I hope this helps! Feel free to comment if you have any questions.

As pv. said DFT is obtained by sampling the DTFT in "Frequency Domain". As you might know a discrete-time signal is obtained by sampling a continuous-time signal. However, to construct the continuous-time signal perfectly from its discrete-time counterpart, the sampling rate MUST be greater than the Nyquist rate. To make this happen, the continuous-time signal has to be frequency limited.

For the DTFT and DFT the story is somehow reversed. You have DTFT that is continuous in "Frequency" domain. Basically you cannot store a continuous signal and process it in a computer. The solution is sampling! So, you sample from the DTFT and call the result DFT. However, according to sampling theorem to reconstruct the DTFT perfectly from DFT, the time-domain counterpart of DTFT MUST be "time"-limited. That's why one has to use windowing before taking the DFT.