10
$\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$

1 Answer 1

13
$\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$
13
  • $\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
    Commented Jun 29, 2015 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.
    Commented Jun 30, 2015 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
    Commented Jul 1, 2015 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.
    Commented Jul 2, 2015 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.
    Commented Jul 3, 2015 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.