2
$\begingroup$

The "N" is DFT is understood to be the number of data points in a given sequence or in other words the length of the sequence. We recently have had discussions here Indexing in DFT (from an old paper) and someone's old question How do I measure the time duration of a finite-length discrete sequence?. One of the popular symbolic versions of DFT is

$$ X(j)=\sum_{k=0}^{N-1} x(k) \exp \left(-i 2 \pi\left(\frac{j}{N}\right) k\right) $$

Suppose someone gives us the sequence consisting of N=11 points without telling us the total time or the sampling rate. If we apply DFT on it in MATLAB, the output is 11 points

Sequence

Notational problems start when we wish to determine the time interval $\Delta$t and the frequency step $\frac{1}{N\Delta t}$ when the $\Delta$t is revealed.

a) If we wish to determine the sampling frequency it is (N-1) points collected in 1 seconds. The last point belongs to the next cycle. The correct sampling rate is 10 Hz not 11.

b) The frequency resolution is shown to be $\frac{1}{N\Delta t}$. In order to get the correct frequency step, we to have to put $\frac{1}{10(0.1)}$ NOT $\frac{1}{11(0.1)}$.

Therefore, the frequency resolution, if we accept that N=11, $$\frac{1}{(N-1)\Delta t}$$ but nobody shows this formula.

It seems that we are using N in two ways

  1. N as the length of the sequence
  2. N when we have to determine the frequency step where actually it is one less than N to get the correct result.

A respected colleague says that N should be interpreted as the no of intervals not the number of points. This is inconsistent with defining N as the number of points in the sequence. Unfortunately, I cannot find any reference which says that N is the number of intervals.

How can we make this consistent?

Thanks.

$\endgroup$
10
  • $\begingroup$ Am I accurate to interpret this question as "Why is frequency resolution defined as $(N \Delta t)^{-1}$ when 0.1Hz in my example makes more sense"? $\endgroup$ Nov 22 '20 at 13:44
  • $\begingroup$ I have a problem with the notation rather. Is N=11 or 10 in the Table shown above? $\endgroup$
    – M. Farooq
    Nov 22 '20 at 13:47
  • $\begingroup$ N=11, unambiguously; $N = $ number of samples by definition, and you have 11 samples. I guess instead you ask what $M$ is in $(M \Delta t)^{-1}$ -- $N$ or $(N - 1)$? $\endgroup$ Nov 22 '20 at 13:48
  • $\begingroup$ $f_s=10 \text{Hz}$ is correct here because $\Delta t = .1$, rather than anything to do with $N$, but I can help clarify why the $(N \Delta t)^{-1}$ definition for frequency resolution is used and why there's a distinction with duration. $\endgroup$ Nov 22 '20 at 13:54
  • 2
    $\begingroup$ Note that a trivial answer, if you only seek consistency, is that "duration" here is 1.1sec, since $\Delta t = \text{Total duration} / N$. But this again is a different question than frequency resolution - but to spoil it, you do have a point, and resolution can be taken with $(N-1)$. What I offer is to show why $N$ is used and in which sense it's more accurate, and what using $(N - 1)$ instead entails. $\endgroup$ Nov 22 '20 at 14:01
2
$\begingroup$

FREQUENCY RESOLUTION and DFT BIN FREQUENCY SPACING are two different (but related) concepts.

In the following graph I have plotted, two and a half periods of a, 7-point DFT of a 7-point sequence x[n].

As the graphics speaks for itself, that the SPACING between each DFT sample (aka DFT bins) is given by:

$$ \Delta_\omega = \frac{2\pi}{N} \tag{1}$$

Where $N = 7$ is the number of samples in DFT $X[k]$.

This value is the discrete-time frequency spacing ($\omega$ in radian per sample) between consecutive DFT samples; mistakenly referred to as the DFT frequency-resolution through internet.

The continuous-time spacing between those frequency samples, in Hertz, is computed using the same formula, using the fact that the samples $X[0]$ and $X[7]$ (the first sample of the second period plotted in cyan) are separated by $F_s$, we have:

$$ \Delta_f = \frac{F_s}{N} \tag{2}$$

Also writing equation 2 in terms of the period $T_s = 1/F_s$ you get:

$$ \Delta_f = \frac{1}{N \cdot T_s} = \frac{1}{ \Delta t} \tag{3}$$

And this is the formula that you have mistakenly referred to as the "frequency resolution". No, it's not. It's just the DFT-bin frequency spacing in Hertz. And that value $\Delta t$ is NOT about the duration of the sequence, but just a consequence of the algebra there; yes the duration of $N$ samples is also $(N-1)\cdot T_s$; hence they are similar quantities. That's why the duration of the sequence may be used to get a shortcut into DFT bin frequency spacing.

enter image description here

$\endgroup$
23
  • $\begingroup$ Thanks. Would you also add what is "frequency resolution" if we contrast it with "DFT BIN FREQUENCY SPACING." $\endgroup$
    – M. Farooq
    Nov 22 '20 at 17:06
  • $\begingroup$ I was also thrown off by that, thought I was missing some terminology - but noone's correcting this answer. In a way it does make sense, in that more DFT bins correspond to greater discrimination of continuous-time frequencies. $\endgroup$ Nov 22 '20 at 17:07
  • 2
    $\begingroup$ Frequency Resolution does not have a precise formula or description. Rather qualitatively it's defined as the ability to distinguish two closest frequencies (borrowed from physics), and it's dependent on the duration of the observation and the type of windowing applied on it. You cannot get a sharp formula to express it. But the DFT bin Frequency spacing is a very clear and sharply defined concept. As arule of thumb: Frequency-Resolution is always worse than the DFT bin frequency spacing. Hence the DFT bin freuqency spacing gives an optimistic estimate of the max reolution attainable. $\endgroup$
    – Fat32
    Nov 22 '20 at 17:10
  • 1
    $\begingroup$ @M.Farooq YES! you take N=11 samples at Fs=10 Hz, and compute N=11 point DFT, then the DFT bin freq-spacing is : $ \frac{1}{11 \times 0.1} = \frac{1}{N \times T_s}$ Hz. Rigorously correct ! $\endgroup$
    – Fat32
    Nov 22 '20 at 18:24
  • 1
    $\begingroup$ @M.Farooq Yes if $N$ samples are gathered on the time interval $[t_a , t_b]$ (including both ends) then your sampling-period is $T_s = \frac{ t_b - t_a}{N-1} $ . This is it. Now you answer: why don't you accept the corect answers (mine) in your two (this and previous) questions ? $\endgroup$
    – Fat32
    Nov 22 '20 at 18:38
3
$\begingroup$

The key is to understand what the DFT says, vs what we seek. Consider a cosine, where we change $f \text[Hz]$, $N$, and $t$ and observe the effect on DFT:

  • [1]: DFT "sees" 1 cycle in the "analysis frame" (i.e. what we feed it), so nonzero at $k=1$, as expected.
  • [1] to [2]: we double our time duration without changing $f$ or $N$; DFT sees this as two cycles spanning the analysis frame, so $k=2$.
  • [1] to [3]: we double the physical frequency without changing $N$ or $t$; DFT sees this as two cycles spanning the frame.
  • [1] to [4]: we double the number of samples, $N$, without changing $f$ or $t$; DFT sees this as still 1 cycle spanning the frame; bin location, $k$, remains unchanged, but (unnormalized) correlation strength doubles (not relevant here).
  • [4] to [5]: now we also double duration, yielding two cycles in analysis frame.

You should be seeing a pattern. Without reading further, try to establish a relationship between $k$, $N$, $t$, and $f$. Hint: units.


Here's the deal: DFT has no idea what Hz, or physical frequency, is. All it knows is samples and cycles spanning the analysis frame. In [1], the "DFT frequency" is

$$ f_{\text{DFT}} = \frac{k}{N} = \frac{1 \text{ cycle}}{10 \text{ samples}} = .1 \left[ \frac{\text{cycles}}{\text{samples}} \right] $$

[2] = [3] = 2 cycles / 10 samples, [4] = 1 cycle / 20 samples, [5] = 2 cycles / 20 samples. Now let's take what we know about physical frequency, $f_p$ and DFT frequency, and relate them. In [2], DFT says $k=2$, but we know $f_p = 1$. It could also be (not shown in any [1]-[5]) $f_p=2$ and $k=1$. How to convert?

The unifying relation is:

\begin{align} f_p \left[ \frac{\text{cycles}}{\text{second}} \right] & = \left( f_{\text{DFT}} \left[ \frac{\text{cycles}}{\text{samples}} \right] \right) \cdot \left( f_s \left[ \frac{\text{samples}}{\text{second}} \right] \right) \end{align}

So, for [2]:

$$ f_{\text{DFT}} \cdot f_s = \left( \frac{2 \text{ cycles}}{10 \text{ samples}} \right) \cdot \left( \frac{10 \text{ samples}}{2 \text{ seconds}} \right) = 1 \left[ \frac{\text{cycles}}{\text{second}} \right] = 1\ \text{Hz} = f_p $$


But how to determine $f_s$?

By a simple definition, it's the reciprocal of sampling period, $\Delta t$, making everything above consistent. However, one must ask, if "sampling frequency" is defined as "# of samples / total duration", and "total duration" of

$$ [0, .1, .2, .3, .4, .5, .6, .7, .8, .9]\ \text{sec} $$

is clearly $0.9\ \text{sec}$, then isn't $f_s$ actually $.9 / 10 = 0.9\ \text{Hz}$? No; the duration is actually 1 sec. Here's why: $0.9\ \text{sec}$ here is actually the duration of something else entirely. Namely, "what is the duration of the signal?" can ask two things:

  1. For how long have we been sampling?
  2. How much time's worth of information is contained in our signal?

The answer to former is $0.9\ \text{sec}$, but to latter is $1\ \text{sec}$. Former computed via $(N-1)\Delta t$, latter via $N \Delta $, and if we insist on 0.9 for #2, we're saying that one sample holds no time-representative information, which implies all signals have duration of zero.

I clarify this with examples here. In a nutshell, the end-goal is description of information, not of process used to obtain it.


So what is the frequency resolution (rather DFT bin spacing)${}^{1}$?

It's defined as spacing between DFT bins, $df$; the answer depends on units of choice. For Hertz, per all of the above,

$$ df_p = \frac{1}{N \Delta t} \tag{1} $$

meaning, for [2], $k=1$ corresponds to $f_p = 0.5\ \text{Hz}$, $k=2$ corresponds to $f_p = 1\ \text{Hz}$, and so on. Alternatively, if you insist on defining duration via $(N-1)$, then it'll be per $(N-1)$ in Hertz, but not in DFT frequencies; latter is unambiguous:

$$ k=1 \rightarrow \frac{1\ \text{cycle}}{N\ \text{samples}} = \frac{1}{N} \left[ \frac{\text{cycles}}{\text{sample}} \right] $$

You can again convert between DFT frequency resolution and physical; taking [2], $\text{Duration} / N = 2 \text{ sec} / 10 = .2 \text{ sec}$, so bin spacing is

$$ df_p = \frac{1}{N \Delta t} = .5\ \text{Hz} $$

The spacing can change, but it's by redefining $\Delta t$ rather than changing $N$ to $(N - 1)$ in $(1)$. Suppose we say $\text{Duration} = 1.8\ \text{sec}$; then, $\Delta t = 0.18\ \text{sec}$, and

$$ df_p = \frac{1}{N \Delta t} = 0.\bar{5}\ \text{Hz} $$

So in [2], $k=1$ corresponds to $0.56\ \text{Hz}$, and $k=2$ corresponds to $1.1\ \text{Hz}$, which agrees with completing 2 cycles in 1.8 secs = 1.1 Hz.


Your specific example: $N=11$, $\Delta t = 0.1\ \text{sec}$:

$$ df_p = \frac{1}{N \Delta t} = \frac{1}{11 \cdot 0.1\ \text{sec}} = 0.909\ \text{Hz} $$

So $k=1$ corresponds to $0.909\ \text{Hz}$, not to 1Hz, since you've included a sample from the next cycle in the analysis frame.


1: NOTE: $df$ is DFT bin spacing, not "frequency resolution". DFT has perfect frequency resolution and no time resolution. But if you define it as discrimination of continuous-time frequencies, then the resolution and bin spacing are inversely-related (lesser spacing -> more bins -> more granular resolution). This is its own topic so I'll avoid clarifying in detail, feel free to open new q.

$\endgroup$
6
  • $\begingroup$ Thanks for adding details. Do you think $df_p$ from my Table, as $\frac{1}{N\Delta t}$ of 1/(11)(0.1) is mathematically wrong? As per the other answer, it is rigorously correct. $\endgroup$
    – M. Farooq
    Nov 22 '20 at 20:29
  • $\begingroup$ @M.Farooq It's indeed correct, as I show below "Your specific example" and interpret in context of DFT. $\endgroup$ Nov 22 '20 at 20:31
  • $\begingroup$ Thanks. And then this is an odd point DFT, the frequency spacing would be 0, 1/(11)(0.1), 2/(11)(0.1), until we reach 5/(11)(0.1)=4.54 Hz and there is no Nyquist frequency here (5 Hz). $\endgroup$
    – M. Farooq
    Nov 22 '20 at 20:39
  • 1
    $\begingroup$ @M.Farooq Correct, odd-point DFTs have the dc bin, and same number of positive and negative frequencies, neither of which is half of Nyquist (5.5 Hz actually). Evens, take 12, have 1 dc bin, 6 positives, and 5 negatives, and 6th positive is 6Hz = 12/2. $\endgroup$ Nov 22 '20 at 20:42
  • 1
    $\begingroup$ @M.Farooq My mistake, Nyquist is 5Hz and $f_s=10Hz$. I had forgot how you defined $t$; 5Hz is correct. (But 5.5 is still DFT's Nyquist bin). $\endgroup$ Nov 22 '20 at 20:58
2
$\begingroup$

I think this question comes down to the the concept of sampling, and how discrete samples relate to the continuous-domain signal they were obtained from. This question starts with the assumption that, if one has, for example, 8 samples (|), 1 second apart (----), the samples represent 7 seconds (the space in between the 8 samples):

  |----|----|----|----|----|----|----|

So let's split these 8 samples into two groups of 4 samples:

  |----|----|----|    |----|----|----|

Now we have two sets of samples each representing 3 seconds. 3 + 3 = 7?!? No, of course not!

If we have a sample spacing of 1 second, then each sample represents 1 second. The 8 samples represent 8 seconds, which we can divide into two sets of 4 samples each representing 4 seconds. 4 + 4 = 8. Our math holds! Our model thus should be:

  |----|----|----|----|----|----|----|----

or

  --|----|----|----|----|----|----|----|--

or however you want to place the sample within its interval.

In image processing, a pixel is usually represented as a little square. Each pixel takes up a certain space. But an image is just a 2D signal, and the relationship between samples and the continuous-domain signal they come from is identical to the 1D signal case. There really is no difference between the two. I have always found it strange that image-processing people have a hard time thinking of a digital image as a set of point samples, which is often a useful model. But now I see that always thinking of a digital signal as a set of point samples also can cause confusion.

$\endgroup$
1
$\begingroup$

You should really let go of the notion of a discrete signal being a sequence of periods. It's not. It's a sequence of numbers – nothing more, nothing less.

Notational problems start when we wish to determine the time interval $\Delta t$

exactly. Since that's not a property of a discrete signal.

a) If we wish to determine the sampling frequency it is (N-1) points collected in 1 seconds

That sounds wrong. To gather the first point, you already had to have signal before. If the signal was "suddenly" the value your sample describes, your signal wouldn't be band-limited and hence, sampling it has no sense, and the samples have no meaning, since the continuous-time signal might change arbitrarily between them.

So, all in all, the same I wrote to How do I measure the time duration of a finite-length discrete sequence? and to OverLord's questions stands:

Stop trying to assign the property "duration" to a sequence of numbers. It's just a sequence of numbers. As soon as you add the notion of these numbers representing a time-continuous signal, you need to take into account that this needs to be band-limited, and hence can't have a finite duration. In the context of the DFT as a tool to "measure" something over frequency, the DFT spectrum estimate only agrees with the continuous-time Fourier transform for the observed bandwidth if the signal is DFT-length periodic at the sampling instants. And then there's no question: the frame is $N\Delta t$ long, and any other length won't work.

$\endgroup$
8
  • 1
    $\begingroup$ A) it really corresponds to neither, the signal is infinitely long. But 1.1 s is certainly less wrong. B) yes, points. $\endgroup$ Nov 22 '20 at 15:51
  • 1
    $\begingroup$ It's the number of points. I wrote that three times now. $\endgroup$ Nov 22 '20 at 15:53
  • 1
    $\begingroup$ Sorry, I wrote the comment when you just wrote " It corresponds to neither". My good colleague does not agree with N as the number of points but he calls it the number of intervals, but I cannot find any reference which says that it is number of intervals. N is the number of points and this is what I had gathered by screening at least 5 books on this subject. $\endgroup$
    – M. Farooq
    Nov 22 '20 at 15:56
  • 2
    $\begingroup$ tell your good colleague that he might still be a great colleague but is wrong about that. Nothing I can do to change math to accomodate the fact that the DFT deals with sequences of numbers, not intervals. $\endgroup$ Nov 22 '20 at 16:14
  • 1
    $\begingroup$ @M.Farooq To be clear the DFT certainly deals with points not intervals; my earlier comment was regarding defining duration. $\endgroup$ Nov 22 '20 at 16:39

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.