I would like to get some concepts cleared on DFT. I will use a single tone signal (say of frequency f0) in time domain to explain my questions.

DFT equation for reference - X(k) = sum (x(n)*exp(-j(*k*n)/N))

1) The N points of X is the observation window in frequency domain. Is this correct?

2) assuming the single tone signal in time domain is sampled 4*f0 (just as an example). So, a single cycle is fully described by 4 samples. Given this signal, I can compute DFT of 4 points and my N points in frequency domain cannot go below 4 points. Is this correct?

3) Referring to question 2 above, I can take 8 samples instead of 4 samples and compute 8 point DFT. I assume there won't be any change in the end results. Is this correct?

4) So, instead of taking 8 samples, if I take 4 samples of the time domain signal and pad 4 zeros, how would the result vary?

1) For an N-point DFT, the input can be "windowed".   Even with a rectangular window the window will be N-points, or less if zero-padding is used.

2-4)  You need to rephrase these so that they make sense.   Whatever it is that you're asking, it isn't clear to me at all.

You can find answers to most of your questions by working on tools like matlab.

1) Do not use the term "observation window". That does not make any sense and even confused Slartibartfast into the "window" reply. N is DFT resolution.

2) what is 4*fo???. Whether single tone or not if you apply resolution of 4 you get 4 samples at DFT output.

3)you get 8 samples. The numerical resuts will be different from the case of 4 but DFT should imply same frequency domain with now higher resolution

4) You can do that, again it should convey same frequency information

Hi,

1) You are correct.  If you have 4 time domain points, then you will have 4 frequency domain points. The frequency domain points will be complex even if the time domain points are real. The bins will be DC, f0, Fs/2 and conj(f0).

2) Based on you assumption of simply one cycle of F0 in 4 samples and thus a 4 point DFT, you will have 0 in a DC bin (bin[0]), a complex value in bin[1], 0 in bin[2] (Fs/2) and a conjugate of bin[1] in bin[3]. If the samples were a sine wave, then the bin[1] and bin[3] will be pure imaginary. If the samples were a cosine wave, then bin[1] and bin[3] will be real and the same.

3) Not quite enough information given.  We will now have bin[0-7].  If the 8 samples constitute a repetition of the same 4 samples from 2), then we will have non-zero data in bin[2] an bin[6].  If the new samples are still one cycle, then we will have non-zero data in bin[1] and bin[7].

4) If we pad 4 samples from 2 with 4 zeros, then we effectively have a rectangular window over the time domain samples, which will translate into a sync function in the frequency domain.  This will mean that the data in the frequency domain will be "smeared" across multiple bins.  I believe that DC will still be empty, and Fs/2 will also be empty, by I would think that all other bins have some content, but bin[2] and bin[6] will have the largest magnitude.

Probably more than you wanted to know.

David

Thanks, Dgshaw6.

1) You are correct.  If you have 4 time domain points, then you will have 4 frequency domain points. The frequency domain points will be complex even if the time domain points are real. The bins will be DC, f0, Fs/2 and conj(f0).

I am able to now appreciate DC, f0, Fs/2 but I don't know how conj(f0) comes into picture? I expected it to be 3*f0 actually.

3) Not quite enough information given.  We will now have bin[0-7].  If the 8 samples constitute a repetition of the same 4 samples from 2), then we will have non-zero data in bin[2] an bin[6].  If
the new samples are still one cycle, then we will have non-zero data in bin[1] and bin[7]

Sorry, that is my mistake. I meant taking 2 cycles of the signal. Thanks your response answers both my questions (when sampling frequency is increased as well as when multiple cycles of signal is used for computation)

Hi,

In answer to the question about conj(f0) vs. 3*f0.  Remember, that in the digital domain, there is a limit of Fs/2 for the highest representable frequency.  Since the case you have described is a tone at Fs/4, then 3*Fs/4 will be greater than Fs/2.

The value in bin[3] is actually the DFT of tone(-f0).  The best way to view the results would be:

bin[0] = Fourier(DC)

bin[1] = Fourier(tone(f0))

bin[2] = Fourier(Fs/2)

bin[3] = Fourier(tone(-f0))  % This is where the conj comes from.

In Matlab, there is a function fftshift which reorders the bins so that DC is in the middle. Then the bins represent frequencies -Fs/2+Fs/N, ..., DC, Fs/N, ..., Fs/2.  This is the correct way to view the results.

David

First off, your definition is incorrect.  You are missing a 2Pi in the exponent.  It is also important to specify whether your signal is real or complex valued.

Second, I agree with kaz in that you apparently have the tool (Matlab) to see the answers of your questions directly.  You should play around with different signals with different sized DFTs and get a feel for how it works.  Then when you read the theory you will better understand what is being described.

Third, you can completely [edit: I meant standalone] understand the behaviour of the DFT from different theoretical constructs.  Many, if not most, of the readers and posters on this forum come from an EE background and have learned the DFT as the sampled discrete case of the continuous FT.  This approach has Calculus as a prerequisite and in my opinion comes bundled with a bunch of preconceptions about how the DFT "ought" to behave vs how it actually behaves.  (Hence the hunt for window functions to prevent leakage.)  A second approach is to understand the DFT entirely within a Linear Algebra context.  This is the matrix multiplication version.  It lends a depth of understanding to the behavior of the DFT, such as a very easy proof for Perseval's theorem (preservation of the sum of squares), but doesn't lend itself well to frequency estimation.  Another approach, which I detail in my series of blog articles, sees the DFT as a center of mass calculation and doesn't require a whole lot of other math than basic algebra and knowing what a complex number is.
Funny thing is that these three different approaches all use a different normalization factor in the DFT definition.  Your definition aligns with the first approach (and is the most common) with a normalization factor of 1 (or none at all, if you prefer).  The linear algebra approach uses a normalization factor of 1/sqrt(N) in order to make the DFT matrix unitary.  My approach uses a factor of 1/N in order to make the result an "average" instead of a "sum".  This makes the results of the DFT using different N sizes more consistent.

Of course I think my approach is best, particularly for a beginning student.  The results of my approach are exact formulas for the behavior of a single tone within a DFT (I call them bin value formulas) and a slew of exact frequency formulas for single pure tones.  Prior to my discoveries, only approximations were known and it was generally considered impossible to find an exact formula.  Recognition of this is coming, but it happening a lot slower than I would have thought.

I am working up to a method for the complete tonal decomposition of a multiple tone signal.  You (and others) can find all my blog articles here:

https://www.dsprelated.com/blogs-1/nf/Cedron_Dawg....

I recommend that you read them in order from the start.  

Having a rough working understanding of the DFT's behavior will greatly facilitate the uptake of this material.  This is true no matter which approach you take.  Ultimately, you want to understand the DFT from all these perspectives.

Ced

1) I do not know if this term "observation window" is normally used, but I guess you got the idea correctly here.

2) I guess you mean that your tone frequency is 1/(4*fs), where fs is the sample frequency. 

I did not understand what you mean by "I can compute DFT of 4 points and my N points in frequency domain cannot go below 4 points."

3) False. Your peak position and amplitude will change. A 8-point DFT has a higher frequency resolution.

4) You will now notice the spectral leakage problem. There will be some non-null amplitude points in DFT result beside your expected peak. 

Thanks a lot. Some follow-up questions below.

I did not understand what you mean by "I can compute DFT of 4 points and my N points in frequency domain cannot go below 4 points."

My question was if a signal is fully described for 1 period using N samples then Am I required to use at least N point DFT? In a way, is the requirement on N point somehow related to sampling frequency?

4) You will now notice the spectral leakage problem. There will be some non-null amplitude points in DFT result beside your expected peak. 

So, if a signal is completely described for 1 cycle by N points and then I compute 2*N point DFT by padding N zeros to the signal then I would observe spectral leakage?

Am I required to use at least N point DFT? In a way, is the requirement on N point somehow related to sampling frequency?

Required is a very strong word. If you use less than N point, your signal frequency position will be between X(0) and X(1) DFT bins. Again, you will see DFT spectral leakage, but this can be acceptable.

So, if a signal is completely described for 1 cycle by N points and then I compute 2*N point DFT by padding N zeros to the signal then I would observe spectral leakage? 

Yes. Trie it at MatLab.

sure. Thanks a lot

1) The N points of X is the observation window in frequency domain. Is this correct?

No.  As others have mentioned, I'd not call this an "observation window" but, perhaps inelegantly, the frequency domain period.  The distinction being "points" vs. "window" or "extent".  The extent of this is fs.  Starting at zero, N points only covers a frequency span of (N-1)*fs/N. The value at f=fs is the same as the value at fs=0, so you might say it's implied.  But the full frequency range covered remains 0 - fs.  As long as you understand this, you will be able to handle it. And, with large N you may or may not notice it.  With small N, it will very likely be noticeable.
It's best to think of DFT pairs in time and frequency as being periodic (as if arranged on a circle) with the last point in the span being implied (equal to the first point).

2) assuming the single tone signal in time domain is sampled 4*f0 (just as an example). So, a single cycle is fully described by 4 samples. Given this signal, I can compute DFT of 4 points and my N points in frequency domain cannot go below 4 points. Is this correct?

You should be careful about what you mean by "fully described".  Mathematically that may be fine.  You state fs=4*f0.  And, 4 samples only covers a time span of 4/fs = 1/f0.  And the frequency sample interval is only going to be f0; consider what happens if the sinusoid is slightly different than f0.  There will be nonzero values at all 4 sample points in frequency.  How useful would that be?  How many samples is necessary to "fully describe" pi Hz?

3) Referring to question 2 above, I can take 8 samples instead of 4 samples and compute 8 point DFT. I assume there won't be any change in the end results. Is this correct?

There will be a difference.  Now we have fs=8*f0.  The time span will be 8/fs = 2/f0.  And the frequency sample interval is going to be f0/2.

4) So, instead of taking 8 samples, if I take 4 samples of the time domain signal and pad 4 zeros, how would the result vary?

The time span will now be 2/f0.  And the frequency sample interval is now going to be f0/2.  And the result from the first case with 4 samples will be interpolated in frequency.  So, if there is but one nonzero sample in the first case then I believe there will be but one nonzero sample in this case with the other zero-valued samples being interpolated with zero values as well.  You can easily try it.

You should be careful about what you mean by "fully described".  Mathematically that may be fine.  You state fs=4*f0.  And, 4 samples only covers a time span of 4/fs = 1/f0.  And the frequency sample interval is only going to be f0; consider what happens if the sinusoid is slightly different than f0.  There will be nonzero values at all 4 sample points in frequency.  How useful would that be?  How many samples is necessary to "fully describe" pi Hz?

Thanks a lot for your response.

Sure, I get your point. I was using a single tone of exactly f0 to make my point. I understand that sampling frequency has to be >= highest frequency (in theory at least).

The sampling frequency has to be > 2X the highest frequency.

And, getting back to your example of 4 samples, I'm afraid that I overlooked something that I only alluded to re: the frequency domain.

If you are going to do a DFT and have 4 samples then the signal is represented by 4 intervals and not 3 intervals as one might think.  That's because the first sample is effectively also the last sample of the time window (and is assumed).  I'm sure there's a more elegant way to say it.

Consider this:

The DFT result is made up of discrete samples.  That means the temporal version or IDFT is periodic.  Some do argue against this point of view but I, and others, find it useful and intuitively helpful.  Same thing going back the other way.  The frequency samples are periodic because the time samples are discrete.  Both being periodic, we can deal with but a single period's worth of samples.

1) The N points of X is the observation window in frequency domain. Is this correct?

I've never heard the term "observation window" applied to the frequency domain.  It may be correct in some philosophical way, but it'll confuse people.

2) assuming the single tone signal in time domain is sampled 4*f0 (just as an example). So, a single cycle is fully described by 4 samples. Given this signal, I can compute DFT of 4 points and my N points in frequency domain cannot go below 4 points. Is this correct?

N is N.  You sample N points in the time domain, you get N points in the frequency domain.  If you have four samples that happens to correspond to exactly four points of a sine wave, there are an infinite number of sums of sine waves that can be made to equal those four samples.  So I'm not sure about the point of this question.

3) Referring to question 2 above, I can take 8 samples instead of 4 samples and compute 8 point DFT. I assume there won't be any change in the end results. Is this correct?

The number of points will be different, but assuming that you're sampling at an exact multiple of \(f_0\) then the magnitude (for a correctly formulated FFT), and the bin in which the result appears, will be the same.  This is a question you could answer yourself with some computation -- you don't even need a math package, it's doable on paper.

4) So, instead of taking 8 samples, if I take 4 samples of the time domain signal and pad 4 zeros, how would the result vary?

Yes, because you'll be sampling an entirely different signal.  Again, you can do this yourself.  In fact, you should do this yourself, both numerically and by convolution of the FFT of a sine wave and the FFT of a square wave in the frequency domain -- it'll be fun and educational.

I've never heard the term "observation window" applied to the frequency domain.  It may be correct in some philosophical way, but it'll confuse people.

I think my choice of word here has caused a great deal of confusion. I will be more explicit in future.

N is N.  You sample N points in the time domain, you get N points in the frequency domain.  If you have four samples that happens to correspond to exactly four points of a sine wave, there are an infinite number of sums of sine waves that can be made to equal those four samples.  So I'm not sure about the point of this question.

My question was using a single sine tone as an example. Nevertheless, I take your point.

Yes, because you'll be sampling an entirely different signal.  Again, you can do this yourself.  In fact, you should do this yourself, both numerically and by convolution of the FFT of a sine wave and the FFT of a square wave in the frequency domain -- it'll be fun and educational.

Actually, I posted this question after working out an FFT example. There are certain areas I did not understand. Hence my questions. Anyway, I am going to go back and simplify my example and try again

Actually, I posted this question after working out an FFT example. There are certain areas I did not understand. Hence my questions. Anyway, I am going to go back and simplify my example and try again

It always worries me when people use "FFT" where they should be using "Fourier Transform" or "DFT".  The FFT is (A) a handy algorithm for doing the discrete Fourier transform (DFT), and (B) something that's really easily accessible on Matlab and its kin.  But the DFT and Fourier transforms in general are mathematically rich and subtle.  You will never ever understand this stuff just by dinking around with the FFT and Matlab.  Ever.  You need to sit down with a pencil and paper and the theory, and you need to work through it.

Specifically, for each of the four flavors of the Fourier Transform, multiplication in the time domain is mathematically identical to convolution in the frequency domain, just as convolution is the time domain is mathematically identical to multiplication in the frequency domain.  You can work this out -- but not in Matlab, and not by dinking with vectors of numbers.  You have to work it out on paper and with a pencil.

If you understand this convolution <-> multiplication relationship, then it's an easy thing to see that four points of sine wave followed by four points of zero is just eight points of sine wave being multiplied by a unit-height, four-sample long, rectangular pulse.  Then you'll understand that the Fourier transform of that thing is the Fourier transform of the whole, uninterrupted sine wave convolved with the Fourier transform of the unit, four-sample pulse.  If you don't do the work with a pencil and paper then all you'll have is factoids without foundation and a sea of examples with no underlying framework to tie it together into bedrock.

Thanks to everyone for helping me on this topic.

I have refined my earlier Matlab to include 3 different examples, as follows:

1) example 1 - signal is a single tone; length of the signal is 1 cycle and is made up of 4 samples

2) example 2 - signal is a single tone; length of signal is 2 cycles and is made up of 8 samples

3) example 3 - signal is single tone; length of signal is 8 samples; first 4 samples describe 1 cycle of the signal; next 4 samples are just 0 zeros.

The results are shown below. Comments are welcome.

I would also like to highlight the following URL where FFT is explained a lot in detail:

http://www.gaussianwaves.com/2015/11/interpreting-...