Question on DFT and DTFT

[DSPro]

Hey,

I am new here, and currently trying to work my way through the "The Scientist and Engineer's Guide to Digital Signal Processing" by Smith. There is one question that keeps bugging me about this whole FFT thing, and I think it's elementary in understanding it. I don't ever intend to be a coder or mathematician, but I want to understand these things in general.

So my question relates to the difference between DFT, and DTFT. As far as I understand the DTFT is DFT which is just padded by infinite amount of samples with 0 amplitude, instead of the periodic signal repeating infinitely. Both of these should represent the original sample EXACTLY, at least if you use rectangular window on DFT-

Now, consider a sine wave with a single cycle, and consider that our period being sampled is that same exact single cycle of sine wave. DFT of the infinte periodic sine wave is going to be one occupied bin or one sine wave, no problems here. However DFTF of the now aperiodic sine wave can't possibly be only a single occupied bin since there is now bunch of silence that also needs to be reconstructed. In this type of fashion:
(infinite silence)________________________________ (One cycle sine wave) ___________________________(Infinite silence). That can't possibly be represented by single bin, as otherwise you would have an infinite sine wave, right?

This also becomes obvious if you consider a dirac delta function, if you take the DFT with 2 samples in it it will look like high frequency sine wave, the DTFT on the other hand would be the noise burst. As you increase the padding it will start to resemble the noise burst more and more.


The problem is I always thought that the zero padding just added definition to the DTFT. The other problem I have is that I thought that the sine waves actually represented something you could hear and that sine waves of one frequency could not be cancelled by sines of other frequency. Obviously in the DTFT case the infinite sine waves of different frequencies have to be added to create the silence and then the single cycle of sine wave in the middle of it... Am I completely offbase here?


By the way I actually generated the sine wave example above. First of all, the one cycle of sine wave sounds nothing like a sine wave, if I use FFT with some padding, the frequencies do seem to be all over the place.

I also generated an example where a sine of couple of cycles plays, still padded with silence. It sounds like a sine, but there is always the sound of an attack and release there, that isn't sinelike. The FFT is far from sine wave. (The sine waves starts and ends at zero phase, so they are perfect in that sense).





Ok, I am sidetracking a bit here, anyway to summaraize, here are the questions I basically have:

#1 The DTFT is not simply an increase in resolution over DFT, but instead could change the frequencies present radically. The signal at the sampled period will remain the exactly the same as one would expect though. Correct?
#2 Can frequencies be cancelled in DTFT by other frequencies to produce silence?
#3 What is it that I actually hear when a sine wave of one cycle is played, surrounded by silence? I don't have infinite time to wait for it, but nor is it continuous as it is surrounded by silence. Is FFT terrible at representing the actual frequencies we hear, even if we account for the nonlinear nature of our hearing?

Thanks a lot.

 

[DSPro]

I have completed reading the book but still wonder about this. It would be absolutely amazing if someone could help me understand it : ).

 

[weetabixharry]

I'm not sure I fully understand your questions, and I don't know so much about the DTFT, but perhaps I can say a few things to help.

Neither can change the frequencies present. After all, computing the inverse transform will get us back to exactly where we started. In fact, what do we even mean by "the frequencies present"? If we observe a million perfect 1kHz sine waves in a row (discretely sampled at interval Tsamp), then it may be practical to treat this as a periodic signal, x[n] = sin[2*pi*1000*n*Tsamp] (so, "only 1kHz is present"). That is, for any n; not just within the million cycles we observed, but last week or next year too. This may seem stupid, but it does sometimes have important consequences.

Consider, for example, that we don't observe exactly 1,000,000 sine periods, but instead observe 1,000,000.1. Intuitively, "the frequencies present" are still exactly the same -- always a perfect 1kHz tone (but this time we just recorded it for a tiny bit longer). However, if we compute the DFT, we now find some other frequencies are present in the spectrum. Why? Because the DFT is based on the assumption that the observed signal will repeat periodically forever. So, when we have an exact integer number of cycles (e.g. 1,000,000), we can start again at the beginning (i.e. repeat the signal periodically) and the sine wave continues perfectly in its cycle. However, with 1,000,000.1 cycles recorded, there is a misalignment; the end does not continue neatly back into the start -- there is a discontinuity (i.e. the non-zero end value has to jump suddenly to zero-valued sin(0), creating something that is not a perfect sine).

In practice, we are not interested in this discontinuity -- we would prefer to see a spectrum with only 1kHz showing up... the rest is just artifacts of the measurement process. Therefore, we commonly use a "window" function (e.g. Blackman, Hanning, Hamming, Gaussian, etc.) which basically attenuates the edges of the time-domain signal, so that these discontinuities contribute less to the final spectrum.

I don't know if you have Matlab or GNU Octave, but this short code demonstrates what I have said. Just change "N_sines" from an integer (e.g. 2) to a non-integer (e.g. 2.3) to see the effects on the spectrum:

close all; clear all; clc;

% Discrete sample frequency 10kHz
fsamp = 10e3;
Tsamp = 1/fsamp;
% Sine frequency 1 kHz
fsine = 1000;
Tsine = 1/fsine;
% Number of complete sine periods to simulate
N_sines = 2.3;
% Number of samples needed
Nsamps = N_sines*Tsine/Tsamp;

% Vector of all sampling times
t = 0:Tsamp:Tsamp*(Nsamps-1);
% Time-domain signal
x = sin(2*pi*fsine*t);
% Compute FFT (i.e. DFT)
Y = fft(x);

% Plot time-domain signal
plot(t,x); title('Time-domain x[n]'); grid on;

% Sort out frequency axis and plot magnitude spectrum
df = fsamp/Nsamps;
f = [ -(ceil((Nsamps-1)/2):-1:1)*df 0 (1:floor((Nsamps-1)/2))*df ];
figure();
plot(f, fftshift(abs(Y)),'--x'); title('DFT Magnitude Spectrum, |Y[f]|');
grid on;

This is an interesting question:

Is FFT terrible at representing the actual frequencies we hear, even if we account for the nonlinear nature of our hearing?

For our hearing, it doesn't matter what came in the past or what will come in the future... our perception of a sound within a given time interval is somewhat unaffected by what happened long before or after that interval (excluding extreme things like getting deafened by a loud bang, etc etc). If we are listening to a perfect 1kHz sine, then a properly-configured FFT (i.e. where discontinuities have been accounted for with correct alignment or windowing) will draw a nice picture of what we perceive.
Similarly, if the signal is really a continuous loop of 2.3 sines making a strange clicky hum (perfectly plausible in theory)... then a differently-configured FFT will draw a very nice picture of that too.
At some point we'll stop listening to this annoying sound, or go crazy or die... at which point the FFT will cease to provide a useful picture of what we perceive.

 

[DSPro]

Thanks a lot for yourr esponse weetabixharry!

I will try to clarify my question a bit at the end of this response, maybe the question was not fully understod by everyone.

I'm not sure I fully understand your questions, and I don't know so much about the DTFT, but perhaps I can say a few things to help.

Neither can change the frequencies present. After all, computing the inverse transform will get us back to exactly where we started. In fact, what do we even mean by "the frequencies present"? If we observe a million perfect 1kHz sine waves in a row (discretely sampled at interval Tsamp), then it may be practical to treat this as a periodic signal, x[n] = sin[2*pi*1000*n*Tsamp] (so, "only 1kHz is present"). That is, for any n; not just within the million cycles we observed, but last week or next year too. This may seem stupid, but it does sometimes have important consequences.

"Exactly" is the important word here.

Consider, for example, that we don't observe exactly 1,000,000 sine periods, but instead observe 1,000,000.1. Intuitively, "the frequencies present" are still exactly the same -- always a perfect 1kHz tone (but this time we just recorded it for a tiny bit longer). However, if we compute the DFT, we now find some other frequencies are present in the spectrum. Why? Because the DFT is based on the assumption that the observed signal will repeat periodically forever. So, when we have an exact integer number of cycles (e.g. 1,000,000), we can start again at the beginning (i.e. repeat the signal periodically) and the sine wave continues perfectly in its cycle. However, with 1,000,000.1 cycles recorded, there is a misalignment; the end does not continue neatly back into the start -- there is a discontinuity (i.e. the non-zero end value has to jump suddenly to zero-valued sin(0), creating something that is not a perfect sine).

Exactly, the 1,000,000.1 cycle sine is not a perfect sine wave, and as such does not only contain the frequency of a single sine wave. You have to add sine waves of other frequencies to make such a shape. If you presented the signal you described to the ear, for example, it would hear a long sine wave first, and "click" at the end. (I believe a smaller click at the start as well due to the discontinuity?). More on this later...

In practice, we are not interested in this discontinuity -- we would prefer to see a spectrum with only 1kHz showing up... the rest is just artifacts of the measurement process. Therefore, we commonly use a "window" function (e.g. Blackman, Hanning, Hamming, Gaussian, etc.) which basically attenuates the edges of the time-domain signal, so that these discontinuities contribute less to the final spectrum.

I don't know if you have Matlab or GNU Octave, but this short code demonstrates what I have said. Just change "N_sines" from an integer (e.g. 2) to a non-integer (e.g. 2.3) to see the effects on the spectrum:

close all; clear all; clc;

% Discrete sample frequency 10kHz
fsamp = 10e3;
Tsamp = 1/fsamp;
% Sine frequency 1 kHz
fsine = 1000;
Tsine = 1/fsine;
% Number of complete sine periods to simulate
N_sines = 2.3;
% Number of samples needed
Nsamps = N_sines*Tsine/Tsamp;

% Vector of all sampling times
t = 0:Tsamp:Tsamp*(Nsamps-1);
% Time-domain signal
x = sin(2*pi*fsine*t);
% Compute FFT (i.e. DFT)
Y = fft(x);

% Plot time-domain signal
plot(t,x); title('Time-domain x[n]'); grid on;

% Sort out frequency axis and plot magnitude spectrum
df = fsamp/Nsamps;
f = [ -(ceil((Nsamps-1)/2):-1:1)*df 0 (1:floor((Nsamps-1)/2))*df ];
figure();
plot(f, fftshift(abs(Y)),'--x'); title('DFT Magnitude Spectrum, |Y[f]|');
grid on;

How do you define an "artifact"? Because as far as I know, a rectangular window doesn't create any artifacts. Like you stated before, the FFT represents the signal or pieces of it exactly and perfectly. There are no artifacts in that sense.

Rather we purposefully distort the signal, creating artifacts by slicing and windowing each slice (rectangular doesn't cause any distortions as it preserves each slice in original condition), so that the FFT presents us with more meaning. The wndowing creates the only artifacts or in other words "cross fades" in the signal, correct?

This is an interesting question:

For our hearing, it doesn't matter what came in the past or what will come in the future... our perception of a sound within a given time interval is somewhat unaffected by what happened long before or after that interval (excluding extreme things like getting deafened by a loud bang, etc etc). If we are listening to a perfect 1kHz sine, then a properly-configured FFT (i.e. where discontinuities have been accounted for with correct alignment or windowing) will draw a nice picture of what we perceive.
Similarly, if the signal is really a continuous loop of 2.3 sines making a strange clicky hum (perfectly plausible in theory)... then a differently-configured FFT will draw a very nice picture of that too.
At some point we'll stop listening to this annoying sound, or go crazy or die... at which point the FFT will cease to provide a useful picture of what we perceive.

Yes, this is what I thought out as well. Our ear does not in fact "hear" audio in chunks like an FFT would. Rather it's more akin to a filter bank, if you will, and as such must also be lossy, since the signal has to be convolved. I think incorporating these kind of features into analyzers could have uses especially in audio, for exactly the same reason why windowing is done (provides us with meaning, even though it distorts the signal). In fact didn't the old analog RTA's work this way? Although there were only a few bands, in contrast the ear has thousands.


As for my question rephrased: I would simply like to know what is a DFT of a signal with single cycle sine wave in the "middle" padded with infinite amount of silence. I just don't understand how an FFT of such signal could be a single cycle sine wave, when an inverse FFT of infintely narrow point would be an infinite sine wave. Yet I think in the DSP guide somewhere it was stated that this kind of zeropadding process only adds resolution to the FFT. There must be something I am missing here...

If some of you don't understand what I am asking, please let me know!

 

[axcdd]

When processing DTF you assume that signal is periodic with N-captured (windowed) samples as period.

About zeropadding: http://www.control.isy.liu.se/student/tsrt78/zeropadding.pdf

 

[DSPro]

When processing DTF you assume that signal is periodic with N-captured (windowed) samples as period.

About zeropadding: http://www.control.isy.liu.se/student/tsrt78/zeropadding.pdf

Thanks for the article, it was good read.

What I still don't understand is when you add zeroes, it appears that the FFT only gains resolution. I would just intuitively think that say a single cycle of sine wave padded by 1 zero is going to be a radically different signal from a sine wave padded by 2 zeroes, or an infinte amount. Yet it appears that if you pad a signal with infinite amount of zeroes, all the other amounts fall in line with it's FFT (pic on the final page of the document). I guess I am just wrong on this.

But back to the question... what does a single cycle sine wave padded by infinite (or at least some) zeros actually look like on the FFT?

 

[axcdd]

What I still don't understand is when you add zeroes, it appears that the FFT only gains resolution. I would just intuitively think that say a single cycle of sine wave padded by 1 zero is going to be a radically different signal from a sine wave padded by 2 zeroes, or an infinte amount

yes ofc it will, because dtf frequency resolution is equall to fs/N so example:
1Mhz sine wave sampled with 16 Mhz frequency and we got 16 samples from it. Now out DTF resolution is 1Mhz so we'll get only 1 bin at 1mhz spot. If you add 1 zero to the signal now resolution is equall to 0,941 Mhz and your signal tone will spread to other bins (leakage).
They idea of padding zeros is that if u pad in this example 16 zeros res = -.5Mhz 48 zeros => 0.25 Mhz => infinitive number of zeros => DTF equals FFT.

But back to the question... what does a single cycle sine wave padded by infinite (or at least some) zeros actually look like on the FFT?

Now if u got samples of just single sinwave your DTF will get you single bin,(because signal in math operation will be copied form -inf to inf for calculation purpose).
If u pad zeros from inf to inf then you will get DTF that equalls to FFT of signal -inf equals 0 then single sin and then 0. Hard to type it sry.

Ok i found Example on web what im talking about
https://www.ee.iitm.ac.in/~csr/teaching/intro_dsp/lecnotes/dft_spectral_analysis.pdf slide 31-37

 

[DSPro]

What I still don't understand is when you add zeroes, it appears that the FFT only gains resolution. I would just intuitively think that say a single cycle of sine wave padded by 1 zero is going to be a radically different signal from a sine wave padded by 2 zeroes, or an infinte amount

yes ofc it will, because dtf frequency resolution is equall to fs/N so example:
1Mhz sine wave sampled with 16 Mhz frequency and we got 16 samples from it. Now out DTF resolution is 1Mhz so we'll get only 1 bin at 1mhz spot. If you add 1 zero to the signal now resolution is equall to 0,941 Mhz and your signal tone will spread to other bins (leakage).
They idea of padding zeros is that if u pad in this example 16 zeros res = -.5Mhz 48 zeros => 0.25 Mhz => infinitive number of zeros => DTF equals FFT.

But back to the question... what does a single cycle sine wave padded by infinite (or at least some) zeros actually look like on the FFT?

Now if u got samples of just single sinwave your DTF will get you single bin,(because signal in math operation will be copied form -inf to inf for calculation purpose).
If u pad zeros from inf to inf then you will get DTF that equalls to FFT of signal -inf equals 0 then single sin and then 0. Hard to type it sry.

Ok i found Example on web what im talking about
https://www.ee.iitm.ac.in/~csr/teaching/intro_dsp/lecnotes/dft_spectral_analysis.pdf slide 31-37

Okay, I think I understand the zero padding a bit better now, thanks for the link, very nice graphics. So here we have a sine wave fit into FFT on the page 31, and then it starts to get zero padded and indeed the FFT does start to include other frequencies than the fundamental (and of course the fundamental has to change as well).

If u pad zeros from inf to inf then you will get DTF that equalls to FFT of signal -inf equals 0 then single sin and then 0. Hard to type it sry.

Just when I thought I got it it seems like I didn't afterall. Shouldn't the DTFT of sine wave padded with infinite zeroes (or just simply a DFT of a sine where some zeroes are added to the time signal) be exactly the picture we see on page 30 of the document you linked? Why are you splitting the signal into three parts?

 

[DSPro]

Still wondering about this...