3
$\begingroup$

The bin width is given by the $F_s / N$ and the maximum frequency is given by $F_s / 2$ where $F_s$ is the sample rate and $N$ is the number of samples of the DFT.

Going between these is trivial, but I'm having trouble seeing why these formulas are correct.

I see that these formulas imply that for this image:

halving the window duration would remove every second frequency bin, but keeping the same window duration and removing every second sample (halving the sample rate) would correspond to removing the right half of the bins.


Edit

Thank's to Dan's answer I now understand that the DTF is $N$ bins periodic ($N/2$ bins periodic for a real signal). But I want to see why either the bin width is $1/T$ where $T$ is the duration the samples are taken over, or why the DTF is $F_s$ Hz periodic. (I think bin width as $F_s / N$ is a red herring)


Aside Sam informed me that my question assumes that the DFT size is equal to the window length and this is just a special case.

$\endgroup$
  • $\begingroup$ "halving the window duration would remove every second frequency bin" this is true when you halve your FFT size also along with window size. If you halve only window size(keeping FFT size same), you are just retaining the resolution of DFT as same ($N$) but now the sinc profile will be visible. $\endgroup$ – jithin Apr 14 at 8:20
  • $\begingroup$ @tom Huntington:) I think Dan also addresses parts of your question, Jithin's answer also addresses part of your question not complete, should probably upvote people who have given meaningful contribution to the question and spent time in meaningful discussions. That's just my humble thoughts. $\endgroup$ – Dsp guy sam Apr 14 at 8:44
  • $\begingroup$ @sam I have up-voted everyone but they are not publicly displayed because my rep is not 15 yet. Jithin's is the answer I was looking for. BTW would you like me to ask a new question tomorrow about the case when DFT size is not equal to the window size? If you want to do it right. Otherwise I'll figure it out myself $\endgroup$ – Tom Huntington Apr 14 at 8:50
  • $\begingroup$ @tom, please ask as many questions ask you want here, we are all here to contribute and learn together, you welcome with new questions. $\endgroup$ – Dsp guy sam Apr 14 at 8:57
3
$\begingroup$

But I want to see why either the bin width is 1/T where T is the duration the samples are taken over, or why the DTF is Fs Hz periodic. (I think bin width as Fs/N is a red herring)

The fourier transform of a finite length sequence $x[n]$ ,$0 \le N \le N-1$ is $$ X(e^{j\omega}) = \sum_0^{N-1}x[n]e^{-j\omega n} $$ This function is continuous and its argument $\omega$ is also continuous. Even though $x[n]$ is not period, $X(e^{\omega})$ can easily be seen as period with $2\pi$ because $X(e^{j(\omega + 2\pi)} )= \sum_0^{N-1}x[n]e^{-j(\omega+2\pi) n}=\sum_0^{N-1}x[n]e^{-j\omega n}e^{-j2\pi n} = X(e^{j\omega})$ because $e^{-j2\pi n} = 1$.

Now, an important thing to note is that DTFT exists only on paper because we cannot represent real number on computer with infinite precision. Hence the need to represent discrete values of frequencies. Historically, the DFT evolved from representing DTFT at equal intervals of $\omega = 2\pi k/N$. This is like "sampling" a DTFT on its horizontal axis. So naturally there will be periodic extension in time domain. Hence the periodic extension of $x[n]$. That is $\tilde{x}[n]=\sum_{r=-\infty}^{r=+\infty} x[n+rN]$. We take one period to compute the DFT. DFT is also period with $N$ because its original underlying sequence $X(e^{j\omega})$ is periodic anyway. $$ X[k] = \sum_0^{N-1}x[n]e^{-j2\pi kn/N}\\ x[n] = \frac{1}{N}\sum_0^{N-1}X[k]e^{j2\pi kn/N} $$

When you sample a signal, you are multiplying the signal $x(t)$ by a period pulse train $s(t) = \delta(t-nT)$ with period $T$. The value at those period are your discrete time samples $x[n] = x(nT)$. The operation corresponding to this in frequency domain is convolution of $X(f)$ and $S(f-k/T)$ $$ X_s(f)=X(f)*S(f) $$ where $S(f)$ is also again a period pulse train in frequency domain $\frac{1}{T}\sum_{-\infty}^{+\infty}\delta(f-k/T)$. So $$ X_s(f) = \frac{1}{T}\sum_{-\infty}^{+\infty}X(f-k/T) $$ The spectrum are repeated copies of $X(f)$ shifted by $1/T$. Your sampling frequency $F_s$ is $1/T$ which is the period. When you normalize $nT \rightarrow n$ in time domain, in frequency domain your axis normalizes from $F_S \rightarrow 2\pi$. Which is exactly why the DTFT is a period repetition with period $2\pi$. DFT is only one period of it, equally spaced by $N$ samples.

To extend answer to address OP's other concern surrounding Window size(w) and FFT size(N).

If $W=N$ and $W$ multiple of period, then you will see only 2 peaks. For a signal $x[n]=\cos(\omega_0 n)$, the peaks will be at $\pm \omega_0/(2\pi/N)$.

If $W \lt N$, $W$ multiple of period, then you will see a sinc profile appearing in DFT output because resolution is same but original underlying DTFT has changed. It expanded because window size in time domain contracted.

If $W \lt N$, $W$ not multiple of period, then you will see the scalloping because of peak of sinc now will not be at multiple of $2\pi /N$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Probably forgot a $k$ in you last Expression $\endgroup$ – Dsp guy sam Apr 14 at 7:51
  • $\begingroup$ Ah yes, thanks. $\endgroup$ – jithin Apr 14 at 7:55
  • 1
    $\begingroup$ @jithin $\displaystyle S(f) = \frac{1}{T} \sum^{\infty}_{k=-\infty} \delta(f - \frac{k}{T})$, You have missed the amplitude scaling of $\frac{1}{T}$. It has very important implications when you are dealing with changes in Sampling rates. $\endgroup$ – DSP Rookie Apr 14 at 8:25
  • $\begingroup$ Period pulse train $s(t) = \delta(t - Nt)$? is this a typo. Thanks for this detailed answer $\endgroup$ – Tom Huntington Apr 14 at 8:25
  • $\begingroup$ @DSPRookie thanks, I will include it. The answer was intended to give a first hand idea of sampling specific to his questions. I will correct it. $\endgroup$ – jithin Apr 14 at 8:27
3
$\begingroup$

The maximum frequency for a real waveform is $F_s/2$, while the maximum frequency for a complex waveform is $F_s$. The DFT is a transformation of N samples in time to N samples in frequency, with bins numbers $0$ to $N-1$, with bin $0$ representing "DC", and bin $N-1$ representing 1 bin less than the sampling rate.

Complex signals are resented as phasors rotating in time in either a counterclockwise ($e^{j\omega t}$) or clockwise ($e^{-j\omega t}$) direction representing positive and negative frequencies specifically. Know that each bin in the DFT represents a single complex frequency ($e^{j\omega t}$), and given Euler's Identity you need two complex frequencies to represent a sinusoidal tone:

$$2\cos(\omega t) = e^{j\omega t} + e^{-j\omega t}$$

Hence the reason why you only need $F_s/2$ for real waveforms since the second tone is redundant (always the complex conjugate for real signals).

Also importantly, the DFT is cyclical as it is a sampled system, no different than how aliasing occurs when we use an A/D converter.

The simplest way to see all of this is to consider a bicycle wheel representing a complex tone, and a strobe light as our sampling clock.

The wheel can spin counter-clockwise or clock-wise, and we will refer to counter-clockwise as a negative frequency, and clockwise as a positive frequency.

If the wheel is spinning 2 cycles per second clockwise, and our strobelight is going at 10 cycles per second, we will witness the 2 cycles per second spin rate. However if our wheel is spinning 12 cycles per second clockwise, it will appear just as if it is spinning 2 cycles per second. If our wheel was spinning 10 cylces per second, it would appear as it is not spinning at all (DC!).

This is just like the DFT, and why bin N-1 is the highest frequency. The next bin N (if we had more bins) would be the sampling frequency itself and would be no different than bin 0. This is the cyclical nature of the DFT, and how for complex signals we can map them either from $-F_s/2$ to $+F_s/2$ or as is done in the DFT from $0$ to $F_s$. (since it is cyclical either can be a unique span).

So we have N bins with each frequency as $0/F_s, 1/F_s, 2/Fs ... (N-1)/F_s$, we see that the bin width is $F_s/N$.

Ultimately and more universally a time sample of duration $T$ has a frequency resolution of $1/T$ (Time Frequency Duality). So if our sampling rate is $F_s$ samples / sec and we have $M$ samples, then the duration $T$ will be $N/F_s$ and then our frequency resolution is the inverse of this which is $F_s/M$. If we zero pad that out to $N$ total samples, the frequency spacing of each bin will decrease to $F_s/N$ but we have not done anything to improve the frequency resolution, or our ability to discern two closely spaced frequencies- it will still be $F_s/M$! So here we note the interesting point that our frequency resolution is really not to do with the sampling rate but to do with the total duration in time of our actual (non-zero padded) data set. Here $T$ is the length of time for the actual data within the window. With zero padding we increase the number of DFT bins which therefore increases the number of frequency samples but it does not increase the frequency resolution! See this post for more details on that with a specific example:

What happens when N increases in N-point DFT

This assumes a rectangular window, which has the narrowest frequency resolution as given by the relationship above (and specifically this is the equivalent noise bandwidth). Any other window used will decrease the frequency resolution further, as detailed in many other posts on here with regards to windowing specifically.

Here is an example demonstrating real and complex frequencies and their DFT:

N = 10;        # Total number of samples
n = 0:9;       # sample index
k = 3;         # frequency index (Fs = N) 
y = cos(2*pi*k*n/N);
stem(n,fft(y))

fft of real signal

The plot above is for the DFT of the function $y = \cos(3\omega_n)$ where $\omega_n$ is $2\pi/N$. Note that this is the same as $\frac{1}{2}e^{j3\omega_n} +\frac{1}{2}e^{-j3\omega_n}$. Because of the cyclical nature of the DFT described above, $e^{-j3\omega_n} = e^{j(10-3)\omega_n} = e^{j7\omega_n}$, so we see the two DFT bins representing this at bin 3 and bin 7.

Think of the bicylce wheel and the strobe light, if it was rotating 7 cycles per second in the positive direction with the strobe light at 10 cycles per second, it would visually appear to be rotating 3 cycles per second in the negative direction! The upper bins of the DFT represent the negative frequencies. For real signals the negative frequencies are the complex conjugate (equal magnitude, opposite phase) of the positive frequencies, hence we only need to show the frequencies from $0$ to $F_s/2$ in the case of real signals, as we already know what the negative frequencies are.

Below shows the same result for a complex tone at at bin 3 only.

y2 = exp(j*2*pi*k*n/N);
stem(n,fft(y2))

fft of complex signal

As for the statement by the OP:

halving the window duration would remove every second frequency bin, but keeping the same window duration and removing every second sample (halving the sample rate) would correspond to removing the right half of the bins.

Halving the DFT duration (not the window duration but the window duration will be modified if the DFT duration is less than double the window) would remove every second frequency bin and not impact the remaining bins only under the condition the condition that the contents remaining in the window are either cyclically invariant to the original data set (cascading the remainng window with itself results in the same original data) or there is nothing in the portion of the data that was removed (removing zeros only). Please this post which details this further, knowing what is shown in frequency at that post can equally be described as the time domain.

Effect of changing sample rate, window duration and zero padding on DTFT and DFT

| improve this answer | |
$\endgroup$
  • $\begingroup$ "The next bin N (if we had more bins) would be the sampling frequency itself and would be no different than bin 0." Thanks I'll think about this. Could you explain what you mean my "you only need Fs/2 for real waveforms". What exactly do you only need two of and what are you holding constant? $\endgroup$ – Tom Huntington Apr 14 at 3:42
  • $\begingroup$ @TomHuntington For a real signal such as $2cos(\omega t)$ you need two exponentials: $e^{j\omega t}$ and $e^{-j\omega t}$. Take the DFT of an integer number of cycles of a sinusoid and you'll see that the DFT result is non-zero in 2 bins. Each bin is an $e^{j\omega t}$. Make sense? $\endgroup$ – Dan Boschen Apr 14 at 3:46
  • $\begingroup$ I will add an example $\endgroup$ – Dan Boschen Apr 14 at 3:47
  • $\begingroup$ Thanks, your comment was quite helpful $\endgroup$ – Tom Huntington Apr 14 at 3:53
  • $\begingroup$ @Dan Boschen regarding "Any other window used will increase the frequency resolution further", you surely meant decrease the resolution further! $\endgroup$ – Dsp guy sam Apr 14 at 4:44
2
$\begingroup$

"halving the window length would remove every second frequency bin, but keeping the same window length and removing every second sample (halving the sample rate) would correspond to removing the right half of the bins."

Window length and FFT length are two different things, halving the window length does not remove every second bin. You could simply look at the formula of frequency bin resolution it depends on the size of FFT and sampling frequency. Your window length and FFT size, need not be the same.

Halving the sampling rate would indeed halve the frequency resolution. However, the resolution decide by FFT size and sampling frequency is the resolution of "representation". But actually it is the window main lobe resolution that decides whether two nearby frequency can be actually resolved or not. So even if we had an extremely high resolution in frqeuency(i.e. finer granularity in frequency representation), but the window length (main lobe width is long) is short, we would still not be able to differencate nearby frequencies falling in adjacent bins.

For real signals the DFT is symmetric around the mid point $N/2$ or $N-1/2$ for even and odd length DFTs respectively , $k$ being the DFT index. Hence only half the frequency components from $0$ to $Fs/2$, are required to be calculated and represented.

When you say duration of window is T, then I ask you how many samples does it have? We have T=M/Fs, where M is length of window, now you take a N point DFT, consider N>M, so what is the frequency resolution, it is Fs/N, according to your equation it is 1/T, I e. Fs/M, which is wrong, so unless the special case of window size equal to FFT length, your definition of binwidth is incorrect.That is why you always define it in terms of sampling frequency and FFT size. I repeat sampling frequency is fundamental to this.

A definition should hold in all cases, which in this case it the one which involves sampling frequency and FFT size, it's not a red herring, it's in every standard textbook.

| improve this answer | |
$\endgroup$
  • $\begingroup$ By window length I meant the duration of time the $N$ samples are taken over. In that quote I was trying to explain what Dan also explained that " So here we note the interesting point that our frequency resolution is really not to do with the sampling rate but to do with the total duration in time of our data set, or what we select for the DFT duration." Could you define what you mean by Window length, FFT length, and the formula of frequency bin resolution? $\endgroup$ – Tom Huntington Apr 14 at 5:23
  • $\begingroup$ I understand your point that frequency resolution is not just determined by bin width but also by window main lobe resolution. $\endgroup$ – Tom Huntington Apr 14 at 5:23
  • 1
    $\begingroup$ @TomHuntington and DSP guy sam- the frequency resolution is not affected by how many zeros you append to a data set that is of duration T, it only interpolates more samples but in all cases the resolution is dictated by the duration of the actual samples you have, independent of the sampling rate $\endgroup$ – Dan Boschen Apr 14 at 19:06
  • 1
    $\begingroup$ I have another post where I detailed this that I will try to find--- zero padding interpolates between the frequency samples you have but it doesn't give you any more information --it doesn't allow you to select another distinct frequency that is in between for example. $\endgroup$ – Dan Boschen Apr 14 at 19:10
  • 1
    $\begingroup$ @TomHuntington This may help: dsp.stackexchange.com/questions/41058/… $\endgroup$ – Dan Boschen Apr 14 at 19:11
0
$\begingroup$

If you understand the Fourier transform as described by 3b1b in this video, then this is actually pretty simple.

Let $x(t)$ be our continuous signal, $w(t)$ our window function non-zero between $t \in [0,T]$. Then the Fourier transform is the limit ($T \rightarrow \infty) $ of $$\int_0^T x(t)e^{-2\pi i t f} dt = \int_{-\infty}^{\infty} x(t)w(t)e^{-2\pi i t f} dt$$ which corresponds to the integral of the winding $x(t)w(t)$ around the complex plain (see the gif below. In our case $x(t)w(t)$ is the magnitude and $e^{-2\pi f t}$ winds this magnitude around the complex origin). Now the first lobe of the Fourier transform of $x(t)$ corresponds to the value of the integral for the first winding of $x(t)w(t)$

What sinusoidal wave (when windowed) will have a peak (main lobe) when wound exactly once? $\sin(2\pi t/T)$. Thus the first winding capture the $1/T$ Hz frequencies of $x(t)w(t)$ and this is the frequency resolution (the windings correspond to lobes).

enter image description here

Animation credit: Grant Sanderson

enter image description here

Maximum Frequency

In the discrete Fourier transform we are now summing a winding of a sampling $x(k)$ of our function $x(t)w(t)$. Notably we do not require that $0 < k$ or $k < T$ (we allow prepending and appending zeros to a full sampling of $x(t)w(t)$). However, this prepending and appending zeros will not effect the value of our DFT $$\sum_{k =-M}^{M }x[k]e^{\frac{-2\pi i k}{M} l}=\sum_0^{F_{s}/T-1}x[k]e^{-\frac{-2\pi i T}{F_s}l}$$

where $F_s$ is the sample rate that $x(k)$ samples $x(t)w(t)$ ($F_s/T$ is the number of samples in $[0,T]$, $M>F_s/T$). Importantly it will take $l=F_s/T$ windings of $x(0),...,x(F_s/T-1)$ before the DFT repeats. Thus multipling the winding width $1/T$ by the number of windings $F_s/T$ we get the maximum frequency $F_s$.

Bin Width

The bin width is then $F_s/N$. For $N>F_s/T$ this means padding zeros and results in interpolating the DFT and for $N=F_s/T$ (no zero padding) our bins align with our windings. As $N\rightarrow \infty$, our DFT approaches the DTFT. This may seam counter intuitive because padding zeros does not add anymore information but we are now getting more information out of the discrete transform. This can be resolved by understanding that the extra information is obtained by the extra computation involved with increasing $N$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Nice animation Tom! What Sam and I resolved was that it is important to use the words "bin width" and not "frequency resolution" as they are indeed two different things. I wanted to make sure that was clear to you (resolution being our ability to distinguish two distinct frequencies that are closely spaced together---this requires a relatively longer T and we can't cheat just by adding zeros--- T is the duration of the actual data only. Hope that was clear! $\endgroup$ – Dan Boschen Apr 15 at 1:24
  • $\begingroup$ Thanks, I got that. I was using Frequency resolution for lobe width, but I probably should just say lobe width. It's not mine, but the creator is extremely well known $\endgroup$ – Tom Huntington Apr 15 at 1:29
  • 1
    $\begingroup$ nice write up and I like how you document how you finally see it as a new answer. I believe as N goes to infinity we are only approaching the DTFT and NOT the CTFT. The DTFT is discrete in time and continuous in frequency while the CTFT is continuous in both. The DTFT is periodic in frequency so only exists uniquely from $f=0$ to $f_s$, and further importantly they will not match exactly: compare a simple rectangular function for example the CTFT is a Sinc but the DTFT will not be until both N goes to infinity and F_s goes to infinity! $\endgroup$ – Dan Boschen Apr 15 at 12:00
  • 1
    $\begingroup$ I don't think that is accurate but we need to be sure we are referring to the same thing when we say N goes to infinity--- If you mean the number of samples within the window does not change and N goes to infinity then we get samples on the DTFT but this is NOT the CTFT of the continuous time window (which is a Sinc). Consider 2 samples on the window, the DTFT is not a Sinc but $1 -e^{-j\omega t}$ for $\omega$ = $0$ to $2\pi$.So it becomes continuous in Frequency as the DTFT, but this is NOT the CTFT (which is a Sinc function for a Rect. Am I missing anything? $\endgroup$ – Dan Boschen Apr 15 at 20:25
  • 1
    $\begingroup$ Right the difference there is $F_s$ is going to infinity. So the CTFT has both infinite time and infinite frequency. The DTFT has infinite time and finite frequency, and the DFT has finite time and finite frequency (which in both domains becomes cyclical when finite). Which then makes me ask what do we get with finite time and infinite frequency --- it would be continuous in time and discrete in frequency. One thing I can think of is the Fourier Series Expansion. $\endgroup$ – Dan Boschen Apr 15 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.