0
$\begingroup$

It's said to "sample the DTFT", revealing what "DFT fails to see". And I fail to see how this sampling isn't distortion.

The "spectrum" aims to provide the sinusoidal frequencies comprising a signal. If we're getting a nonzero distribution from 1 to 63Hz for a pure 1Hz tone, that's by definition different.

Further, adding zeros changes the signal; who is to tell that these zeros didn't occur naturally as a part of it? If they did, the spectrum must look different - and it does. That it mathematically happens to be equivalent to sampling a related but different altogether transform is only a coincidence.

What's the deal?

$\endgroup$
  • $\begingroup$ Perhaps the issue is semantics, and I will need to read through your answer and can comment there further. Your question would be improved if you defined then what you mean by "the spectrum". For me the "spectrum" is only the DFT samples since as you suggest that is all we have and know. Zero padding does NOT distort these samples, it just interpolates more samples in between. Those samples are on the DTFT. This is the biggest problem I immediately have with any statement that the spectrum is distorted---can you address or clarify that in your answer? $\endgroup$ – Dan Boschen Sep 24 '20 at 2:45
  • $\begingroup$ @DanBoschen It's addressed, yes. Ultimately, "you're probably right", but there's tons of detail and caveats there that no summary-statement can convey. I intended the Q and the A as two parts of a whole, so part of the question is in the answer to avoid repeating; may reformulate later if necessary. -- @ spectrum, the question premises it as stated (The "spectrum" aims to ...), which is expanded upon in the answer. $\endgroup$ – OverLordGoldDragon Sep 24 '20 at 2:51
  • $\begingroup$ Ok got it, fair enough - I need to step back and read it with eyes wide open, I am too pre-dispositioned in the application space spelled out by your "fallacy" (limitation may be a better word there), but looks like it might be an interesting viewpoint if I can let go of that. Will need to read tomorrow or later this weekend. $\endgroup$ – Dan Boschen Sep 24 '20 at 2:54
  • 1
    $\begingroup$ @DanBoschen Major point of the answer is exactly to show how and why it's a fallacy, and what that implies in various contexts. And sounds good, look forward to it. $\endgroup$ – OverLordGoldDragon Sep 24 '20 at 2:56
  • 4
    $\begingroup$ I keep repeating myself here: you CAN'T do a DFT on a 1 Hz sine wave, since a 1Hz sine wave is infinitely long and the DFT implies either finite length or periodic repitition. You can only do a a DFT on a section of a 1Hz sine wave, but the results depend heavily how the section is created with respect to the DFT parameters $\endgroup$ – Hilmar Sep 24 '20 at 12:29
0
$\begingroup$

Yes.

All windows distort spectrum, whether they be due to the inherent length of the DFT, or a zero-padding rectangle. That's because nothing of finite length (e.g. of finite support) consists of a single frequency in the frequency domain (or is even bounded in bandwidth). So you choose your preferred distortion (or window artifact).

One often preferred distortion is using a DFT length that is an exact integer multiple of one constituent sinusoid, which has the strange windowing artifact of being zero for all but one matrix transform basis vector. Or some linear combination of exact integer periodic sinusoids thereof.

$\endgroup$
  • $\begingroup$ Does zero padding “distort” the rectangular windowed spectrum? $\endgroup$ – Dan Boschen Sep 24 '20 at 18:33
  • $\begingroup$ I read that as similar to the question: is it possible to interpolate samples without distorting the samples? But maybe some can view interpolating new values as distortion... $\endgroup$ – Dan Boschen Sep 24 '20 at 18:36
0
$\begingroup$

DFT vs DTFT, Fourier Transform

The problem appears rooted in viewing DFT as a 'special case' of the continuous Fourier Transform, and of its input as some signal with legitimate frequency contents. That's a fallacy.

The DFT is a standalone mathematical transformation which does not condition itself upon anything but the input being finitely long, and having finite values. It's an information encoding algorithm. It operates on any and all finite information - be it signals, Shakesperean sonnets, or a cup of water - as long as represented numerically.

DFT can be shown to be equivalent to solving $N$ simultaneous equations defining an $N$ long input; it's a complete, lossless transform.


What the spectrum "should be" is not what we get

  • Should be: amounts of sinusoidal frequencies comprising the input data.$^1$
  • Is: amounts of sinusoidal frequencies that sum to the input data.$^1$

See here. The input can be a pulse, or a single nonzero value and the rest zeros; there's nothing of periodic nature about either of these, nor do they need to stem from a physical source which is sinusoidal. The only truth is that the coefficients we find give us the sinusoids that sum to the input; with another transform, it can be triangle waves.

1: for a real-valued input. For complex, something similar may hold, but it's still a sum of bases (discussion here).


DFT coefficients are not same as DTFT or FT coefficients

Both the forward and inverse transforms to acquire respective coefficients imply very different things for what the coefficients "mean". Under certain assumptions they can be treated equivalently, but not fundamentally.

This is clear from the inverse-transform perspective, or reconstruction; assume for now a rectangular-windowed DTFT:

  • DFT: sum of $N$ bases, each $N$-long, finite in value.
  • DFT coefficient: describes one such basis. $N$ coefficients in total.
  • DTFT: infinitesimal sum (integral) of infinitely many bases, each $N$-long, finite in value.
  • DTFT coefficient: describes one such basis. infinitely many coefficients in total.

From forward-transform:

  • DFT coefficient: obtained by adding (discretized complex phasor at integer frequency) * (input), pointwise products.
  • DTFT coefficient: obtained the same way. Except not really; see below.

Result? If you use one transform's coefficients in another transform, you get nonsense.


Generator vs Data

A generator is a complete descriptor - example: function, continuous. For describing a 1D signal, the signal is infinitely resolved; we can determine every possible intermediate value. From a generator we can get data, but not vice versa; even a truly continuous segment has infinite interpolations.

The DTFT (no windows) works with generators, not data. Its coefficients are described by a function (continuous), which are also determined by an operation between functions (one describing an infinitely long but discrete input, another the complex phasor at a continuous $\omega$).

The rectangular-windowed DTFT, on the other hand, works with both, but only "with permission" from generators - that is, the resulting spectrum happens to be the same whether we compute for $n=0$ to $N-1$ or $-\infty$ to $\infty$.

In contrast, the DFT works with data. No generators. But we can use generators if we wish - it's now the reverse case, generators "with permission" from data.


Zero-padding: DFT coeffs treated as DTFT coeffs -- all code.

Before the meat, last piece of background. Take 1Hz over two seconds; what's the DFT (which freq is nonzero)? 2. Now take 0.1Hz over 10 seconds; what's the DFT? 1. The DFT correlates against basis functions spanning the length of the input signal, with no regard to "actual time". $k=1$ corresponds to 1 cycle over the length of the signal.

We can use this to interpret "treat DFT coeffs as DTFT coeffs". Suppose

$$s[n] = \cos(2 \pi n / N),\ N = 128,\ n=[0, ..., N - 1].$$

Pre-pad, the spectrum is just what we expect: nonzero everywhere but at $k=1$ and $k=128$. Post-pad - a madhouse. What's the deal?

Recall how "0.1Hz over 10 seconds" $\rightarrow k=1$? By the same token, the original $f=1$ is now "seen" as $k=2$ - i.e., it correlates with the $k=2$ basis. Then what does $k=1$ "see"? Let's see:

(Only real component of basis shown for clarity; can add the imaginary component for completeness)

Put differently, the "normalized" frequency of the DFT is divided by two as a result of doubling the original signal's length with the padding, so $k_p=2 \leftrightarrow k = 1$, and $k_p=1 \leftrightarrow k = 0.5$. Or, integer frequencies with a padded signal's spectrum correspond to fractional frequencies in the unpadded's spectrum.

Is there more evidence? Yes; first, see this. If above is true, then we can correlate the original signal with a $k=0.5$ basis directly, and yield the same coefficient as with $k_p=1$. And indeed:

Why one window for both padded and unpadded? ... because they look identical - check the code. Mean absolute difference: 6e-14 (within float).


In what sense do we "sample the DTFT"? What's the role of zero-padding?

Former should be clear now; the DTFT evaluates itself for every $\omega$. For any given $\omega$, this exactly the same as taking DFT with an equivalent $k$ basis. In other words, DTFT correlates with neighboring fractional frequencies, just like DFT correlates with integer frequencies. Simpler, "DTFT is DFT with $k$ spanning continuously" (but not quite; see caveats in above sections).

So why does zero-padding "result in" the DFT sampling DTFT's spectrum? The answer is closer if we reformulate the question: Why does zero-padding result in the DFT correlating with fractional frequency bases?

Yes, they're indeed one and the same question, which was answered in the previous section. A DFT with $2N$ coefficients is equivalent to a DFT with $N$ coefficients at integer frequency bases, and another DFT with $N$ coefficients at fractional frequency bases$^1$.

But why zero-padding? Why not one-padding, or pi-padding? Because it's the only way for an $M>N$-DFT with integer frequencies to be equivalent to an $M$-DFT with fractional frequencies$^1$. Refer to the blue/orange figure; note how the sum of products of the orange with the blue for $k_p=2$ is the same as for $k=1$ with the unpadded blue (not shown; just imagine). If the zeros were anything else, the values might have been proportional, or somehow similar, but not equal. In technical terms, zero is orthogonal to all basis functions over any interval.

1: if $M=3N$, then the integer-DFT will correlate $k=[0, 1, ..., 3N-1]$ bases with the padded signal, and the "mixed" DFT will correlate $k=[0, 0.33, 0.66, 1, ..., N-1, N - .66, N - .33]$ with the original signal. Note that if $M$ is not an integer multiple of $N$, then the padded's integer-DFT may not have any integer equivalents with the unpadded's DFT.


Does zero-padding distort the spectrum?

The grand-prize. The answer to which is... yes and no:

  • No: zero padding is equivalent to correlating with neighboring, non-integer frequencies; there is no "distortion" here, the coefficients describe exactly what they intend to.
  • Yes: if "the spectrum" is supposed to describe the frequencies in the input signal (e.g. $f=1$), then correlating with bases neighboring $1$ yields non-zero coefficients, implying non-zero frequencies around $1$, whereas the signal has no such frequencies. Further, only integer-ratio frequencies are completely decorrelated (e.g. 1 and 2, 1.5 and 3), so we'll get many high and low non-zero frequencies, whereas the input has only one frequency.

So what's the deal? The deal is - DFT does NOT describe input's spectrum. This is the entire point of this answer, which was so warmly-received because of a technicality I was quick to retract with a NOTE: on top. Ignore the downvotes, they mean nothing without explanation.

Since it's not the spectrum we expect, it's meaningless to speak of a "distortion" as if it ever gave the actual spectrum. The input could be $f=1.1$, and then the unpadded DFT would be "distortion", and the only true spectrum would stem from incrementing the bases by $1.1$.

This also explains why we can't do much better than the DFT; we don't know what the "actual" frequency of a signal is without its generator (function). The DFT is simply our "best guess", one which must be interpreted carefully.


Possible to pad without distorting?

Yes, but in a specific sense: if the number of zeros added is an integer-multiple of the signal's length, then the DFT will contain the unpadded's spectrum. For example, pad by $2N$; then, the DFT, from original's point of view, is doing $k=[0,.33,.66,1,...,N-1,N-.66,N-.33]$. Notice how $[0, 1, ..., N-1]$ are all captured.

In other words, we can pad without losing the original spectrum.


Re: other answers

  • The fact that the input is discrete or finite has virtually nothing to do with this - which this upvoted answer contradicts. Though, a little more work is due to show this; short version is, imagine the "winding machine" winding forever, and why that yields an impulse, and how that relates to the finite spike in DFT. Whatever the answer, it's way besides the point.
$\endgroup$
0
$\begingroup$

Shorter version with more intuitive animation where original signal is fixed in frame, and alternate formulation: zero-padding extends the spectrum.

Here's k=1 basis (sine omitted) over 1Hz signal, N=128 points:

As we zero-pad the signal, this same k=1 basis now spans the total length of the padded signal, while adding values only from the unpadded signal, which is exactly the same as multiplying w/ a cosine of lower frequency in the original frame (details in my first answer).

Ignoring the padding part and thinking purely in terms of the modified cosine, this can be visualized as (try ignoring the right half entirely):

Now showing padding:

This is repeated with every other k, and we have more of k in total (as many as len(x) + pad_length). For example, if pad_length = len(x), then k=2 'becomes' 1Hz, and likewise any padding integer-multiple length of original signal will include the original spectrum entirely in the longer spectrum.

Thus, zero-padding can be interpreted as "extending" the spectrum, i.e. adding additional frequency correlates - atop original, or, if not integer-mult padded, shifting bins to fractions of unpadded (e.g. len(x)=128, pad_length=64, now k=2 in padded frame is k=2/1.5=1.33 in unpadded frame).

$\endgroup$

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.