I'm trying to grasp some intuition about why zero-padding the time domain sequence $$x[n]$$ interpolates the frequency domain bins of the $$DFT\{x[n]\} = X[k]$$ and how does this relate to the $$DTFT$$ of $$x[n]$$.

Let's say we have $$N$$ point signal $$x[n]$$ and we pad it with 0's in the time domain as usual. So, as we append more and more zeros to $$x[n]$$ and perform the $$DFT$$, we know that $$DFT$$ makes the assumption that the signal is periodic, hence the period tends to infinity, hence we get frequency samples (more and more and padding increaes) of the $$N$$ point $$DTFT$$ applied to the original $$x[n]$$ ?

I'd love some insights and intution please. Thanks

• Related Apr 9 at 4:27
• Please also see this post detailing an intuitive view of the DTFT vs DFT which gives insight into how zero padding approximates the DTFT: dsp.stackexchange.com/questions/73781/… Apr 10 at 11:59

Say a discrete signal $$x(n)$$ and its Z-transform $$X(z)$$, discrete time Fourier transform $$X(e^{j\omega})$$, and discrete Fourier transform $$X(k)$$. The relationships between DFT and ZT / DTFT are respectively:

$$X(k) = X(z)|_{z=e^{j2\pi k/N}} \tag{1.1}$$

$$X(k) = X(e^{j\omega})|_{\omega=2\pi k/N} \tag{1.2}$$

Since the original signal $$x(n)$$ can be perfectly reconstructed by IDFT, yes you can certainly obtain DTFT from DFT. However, you can't get DTFT by padding zeros as long as possible but by a technique called frequency domain interpolation. First is reconstruction of ZT from DFT:

$$X(z) = \sum_{n=0}^{N-1}x(n)z^{-n}=\sum_{n=0}^{N-1}\Big[\frac{1}{N}\sum_{k=0}^{N-1}X(k)W_N^{-nk} \Big]z^{-n} \\ = \frac{1}{N}\sum_{k=0}^{N-1}X(k)\Big[ \sum_{n=0}^{N-1}W_N^{-nk}z^{-n} \Big] \\ = \frac{1}{N}\sum_{k=0}^{N-1}X(k)\frac{1-W_N^{-Nk}z^{-N}}{1-W_N^{-k}z^{-1}} = \frac{1-z^{-N}}{N} \sum_{k=0}^{N-1}\frac{X(k)}{1-W_N^{-k}z^{-1}} \tag{2}$$

where $$W_N^{nk} = e^{j\frac{2\pi}{N}nk}$$. Define the interpolation function

$$\varPhi_k(z) = \frac{1}{N}\frac{1-z^{-N}}{1-W_N^{-k}z^{-1}} = \frac{z^N-1}{Nz^{N-1}(z-W_N^{-k})} \tag{3}$$

and $$X(z)$$ can be written as

$$X(z) = \sum_{k=0}^{N-1}X(k)\varPhi_k(z) \tag{4}$$

Now let $$z = e^{j\omega}$$ we can derive that

$$X(e^{j\omega}) = \sum_{k=0}^{N-1}X(k)\varPhi_k(e^{j\omega}) \tag{5}$$

and the interpolation function

$$\varPhi_k(e^{j\omega}) = \frac{1-e^{-j\omega N}}{N(1-W_N^{-k}e^{-j\omega})} = \frac{1-e^{-j\omega N}}{N(1-e^{-j(\omega-2\pi k/N)})}\\ = \frac{1}{N}\frac{\sin(N\omega/2)}{\sin\big[(\omega-2\pi k/N)/2\big]} e^{-j[\omega(N-1)/2 + k\pi/N]} \\ =\frac{1}{N}\frac{\sin(N\omega/2)}{\sin\big[(\omega-2\pi k/N)/2\big]} e^{jk\pi(N-1)/N} e^{-j(N-1)\omega/2} \tag{6}$$

Let's write it in a more convinient form as

$$\varPhi_k(e^{j\omega}) = \varPhi(\omega - 2\pi k/N) \tag{7}$$

where $$\varPhi(\omega)$$ is the Fourier transform of a $$N$$-point rectangle window divided by $$N$$

$$\varPhi(\omega) = \frac{1}{N} \frac{\sin(\omega N/2)}{\sin(\omega/2)} e^{-j(N-1)\omega/2} \tag{8}$$

Finally, we get the equation of reconstructing DTFT by interpolating DFT

$$X(e^{j\omega}) = \sum_{k=0}^{N-1}X(k)\varPhi(\omega-2\pi k/N) \tag{9}$$

• 1) So basicaly you are saying that for finite length sequence $x[n]$, there is an interpolation such that I can get the DTFT out of the DFT bins? 2) But how does this relate to zero padding? Isn't the zero padding sort of interpolation on its own? Apr 9 at 21:10
• 1) Yes, but recall the definition of DTFT, the summation extends from $-\infty$ to $\infty$. Mathematically, the interpolation can only reconstruct truncated DTFT. 2) And yes, the zero padding is a sort of interpolation approaching to DTFT, but the result it returns is still DFT (it's $X(k)$ not $X(e^{j\omega})$). Apr 12 at 2:24