# Zero padding DFT intuition

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, 2021 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, 2021 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, 2021 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, 2021 at 2:24