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.
