4
$\begingroup$

There are many question related to the zero padding a time domain signal to get more frequency bins after performing Fourier transform. As I understand this process is equivalent to trigonometric interpolation in the frequency domain. However, I am not certain of this fact. Can anyone verify this correct or incorrect mathematically?

$\endgroup$
8
$\begingroup$

It's true that zero-padding in the time domain corresponds to interpolation in the frequency domain. If you have a length $N$ signal $x[n]$, its discrete Fourier transform (DFT) is given by

$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nk/N}\tag{1}$$

The signal $x[n]$ can be expressed in terms of its DFT coefficients $X[k]$ by the inverse DFT

$$x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j2\pi nk/N}\tag{2}$$

Since the coefficients $X[k]$ contain the same information as the signal $x[n]$, anything that can be computed from $x[n]$ can also be computed from $X[k]$.

Let $\tilde{X}(\omega)$ denote the discrete-time Fourier transform (DTFT) of $x[n]$:

$$\tilde{X}(\omega)=\sum_{n=0}^{N-1}x[n]e^{-jn\omega}\tag{3}$$

Note that $\omega$ is a continuous variable. Comparing (1) and (3) shows that the DFT is simply a sampled version of the DTFT:

$$X[k]=\tilde{X}(2\pi k/N),\quad k=0,\ldots,N-1\tag{4}$$

Furthermore, a length $L$ DFT ($L>N$) of $x[n]$ simply corresponds to a more densely sampled version of $\tilde{X}(\omega)$:

$$X_L[l]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi nl/L}=\tilde{X}(2\pi l/L),\quad l=0,\ldots,L-1\tag{5}$$

Now let's express $\tilde{X}(\omega)$ in terms of the length $N$ DFT of $x[n]$. Rewriting (3) using (2) gives

$$\begin{align}\tilde{X}(\omega)&=\sum_{n=0}^{N-1}\frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j2\pi nk/N}e^{-jn\omega}\\ &=\sum_{k=0}^{N-1}X[k]\underbrace{\frac{1}{N}\sum_{n=0}^{N-1}e^{-jn(\omega-2\pi k/N)}}_{G(\omega-2\pi k/N)} \end{align}\tag{6}$$

where $G(\omega)$ is an interpolation function which can be expressed by

$$G(\omega)=\frac{1}{N}\sum_{n=0}^{N-1}e^{-jn\omega}=\frac{e^{-j\omega(N-1)/2}}{N}\frac{\sin(N\omega/2)}{\sin(\omega/2)}\tag{7}$$

By setting $\omega=2\pi l/L$ in (6) and using (5) you can see that the length $L$ zero-padded DFT of $x[n]$ can be computed from the length $N$ DFT using the interpolation function given by (7):

$$X_L(l)=\tilde{X}(2\pi l/L)=\sum_{k=0}^{N-1}X[k]G(2\pi l/L-2\pi k/N)\tag{8}$$

$\endgroup$
  • $\begingroup$ Can we think that zero padding (from length N to L) is equivalent to considering the time signal is made up of L number of sinusoidal instead of N? L>N $\endgroup$ – Creator Jun 29 '15 at 21:44
  • $\begingroup$ @Creator: By the inverse DFT formula the zero-padded signal can be represented by a sum of $L$ complex exponentials. But they add up such that the last $L-N$ values are zero, so the non-zero values of $x[n]$ can be represented by a sum of only $N$ complex exponentials. $\endgroup$ – Matt L. Jun 30 '15 at 7:02
  • $\begingroup$ Thank you for your comment. Can we say anything about G, the interpolate function for example :It is the minimum entropy solution or minimum energy solution or something else? I am looking for a condition under which it is optimal or is derived from? $\endgroup$ – Creator Jul 1 '15 at 2:16
  • 1
    $\begingroup$ @Creator: I'm not sure what you're trying to do. Why would you want to replace $G$? The most efficient way to interpolate is to do IFFT -> zero pad -> FFT, so you normally wouldn't use $G$ or any other function in practice. $\endgroup$ – Matt L. Jul 2 '15 at 9:15
  • 2
    $\begingroup$ @Creator: The limitation is in the number of time domain data points. Zero padding doesn't increase the amount of information which would be necessary to increase resolution. Frequency resolution increases with (time domain) window length; for a fixed window length resolution is fixed; zero-padding just gives you a denser sampling of an already smeared out frequency response function. $\endgroup$ – Matt L. Jul 3 '15 at 7:03

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.