0
$\begingroup$

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

$\endgroup$
2
1
$\begingroup$

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} $$

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user3921
    Apr 9 at 21:10
  • 1
    $\begingroup$ 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})$). $\endgroup$
    – ZR Han
    Apr 12 at 2:24

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.