15
$\begingroup$

Suppose we wish to interpolate a periodic signal with an even number of samples (e.g. N=8) by zero-padding in the frequency domain.

Let the DFT X=[A,B,C,D,E,F,G,H]
Now let's pad it to 16 samples to give Y. Every textbook example and online tutorial I have seen inserts zeros at [Y4...Y11] giving
Y=[2A,2B,2C,2D,0,0,0,0,0,0,0,0,2E,2F,2G,2H].
(Then y = idft(Y) is the interpolated signal.)

Why not instead use Y=[2A,2B,2C,2D,E,0,0,0,0,0,0,0,E,2F,2G,2H]?

As far as I can tell (my math knowledge is limited):

  • It minimises the total power
  • It ensures that if x is real-valued then so is y
  • y still intersects x at all the sample points, as required (I think this is true for any p where Y=[2A,2B,2C,2D,pE,0,0,0,0,0,0,0,(2-p)E,2F,2G,2H])

So why is it never done this way?


Edit: x is not necessarily real-valued or band-limited.

$\endgroup$
  • $\begingroup$ You write "Every textbook example and online tutorial I have seen inserts zeros at...", can you update your post with some references? Just curious because you also write that x is not necessarily real-valued and the first construction you mention does not (in general) produce a real result by inverse DFT. $\endgroup$ – niaren Sep 29 '11 at 19:26
  • $\begingroup$ @niaren here's one example: dspguru.com/dsp/howtos/… $\endgroup$ – finnw Sep 29 '11 at 20:52
  • 1
    $\begingroup$ It's worth noting that in order for $y$ to be real-valued, then you would need to let $Y=[2A,2B,2C,2D,E,0,0,0,0,0,0,0,E^*,2F,2G,2H]$ (i.e. when you duplicate E for the "negative-frequency" half of the frequency-domain vector, you need to conjugate it. Signals that are real in the time domain have conjugate-symmetric DFTs. $\endgroup$ – Jason R Oct 6 '11 at 3:48
  • $\begingroup$ @Jason R, if the input signal is real-valued then so is E so [2A,2B,2C,2D,E,0,0,0,0,0,0,0,E,2F,2G,2H] satisfies this condition. If the input is not real-valued then it is not necessary to force the output to be real-valued. $\endgroup$ – finnw Oct 6 '11 at 12:19
  • $\begingroup$ You are correct. That's what I get for writing a comment too late in the evening. $\endgroup$ – Jason R Oct 6 '11 at 16:27
7
$\begingroup$

Let's look at the frequencies of the bins in your 8-point DFT:

$$ \begin{array}{c} \omega_A = 0,\\ \omega_B = \pi/4,\\ \omega_C = \pi/2,\\ \omega_D = 3\pi/4,\\ \omega_E = \pi = -\pi\ ({\tt mod}\ 2\pi),\\ \omega_F = 5\pi/4 = -3\pi/4\ ({\tt mod}\ 2\pi),\\ \omega_G = 3\pi/2 = -\pi/2\ ({\tt mod}\ 2\pi), \\ \omega_H = 7\pi/4 = -\pi/4\ ({\tt mod}\ 2\pi) \end{array} $$ So when you interpolate by a factor of 2, point $E$'s frequency becomes $-\pi$ or $+ \pi$.

At a first glance, I can't see what the problem is with your approach as it's not clear whether $E$ should be put into the bin associated with $\pi$ or $-\pi$.

On Julius O. Smith III's page, he states a condition:

Furthermore, we require $x(N/2) = x(-N/2) = 0$ when $N$ is even, while odd requires no such restriction.

And his example there is for an odd $N$, which avoids the problem.


Not sure it's required, but here's the full reference to Julius's work:

Smith, J.O. Mathematics of the Discrete Fourier Transform (DFT) with Audio Applications, Second Edition, http://ccrma.stanford.edu/~jos/mdft/, 2007, online book, accessed September 28, 2011.

$\endgroup$
3
$\begingroup$

There are many ways to interpolate data. Interpolation in my mind means that you 'draw' lines between some data points. This can be done many ways. One type of interpolation which is useful in DSP (especially in multirate DSP) is 'Bandlimited interpolation'. If you google that you will get many interesting and useful hits. What you propose is not bandlimited interpolation. In your 'upsampled' x you have frequency components not present in the original x.

Edit (too long to fit into a comment):

There is a quite significant difference between your construction, starting with $X=[A,B,C,D,E,F,G,H]$ and the example in the reference you provide.

Considering real input

$X=[A,B,C,D,E,D^*,C^*,B^*]$

Upsampling by a factor of 2 for fullband input. In this case upsampling can be performed by first placing zeros in the input interleaved (that is $x_0,0,x_1,0,...$. The result is a signal with a frequency spectrum containing a compressed version of the frequency spectrum of x (in range $0-\pi/2$) and an image extending from $\pi/2 - \pi$ (considering only the positive frequency axis). If x2 is the upsampled version then

$X2=[A,B,C,D,E,D^*,C^*,B^*,A,B,C,D,E,D^*,C^*,B^*]$

In the ideal case an ideal brick-wall filter with cutoff frequency $\pi/2$ is required in order to remove the image. That is (for infinite input)

$y_n = \sum_{k=-\infty}^{\infty} x2_k sinc(0.5n - k)$

In practice though there will be some distortion because the brick-wall filter is not realistic. The practical filter can suppress/remove frequencies in the input or it can leave in some of the frequency components in the image in the upsampled signal. Or the filter can make a compromise between the two. I think your frequency-domain construction also reflects this compromise. These two examples, represents two different choices:

$Y=[A,B,C,D,E,0,0,0,0,0,0,0,E^*,D^*,C^*,B^*]$

$Y=[A,B,C,D,0,0,0,0,0,0,0,0,0,D^*,C^*,B^*]$

If the input is bandlimited below the nyquist frequency as in your reference this issue disappears.

Maybe it is possible to find a value of $\rho$ below, such that some error function, for instance the squared error between the input spectrum and the upsampled output spectrum is minimum.

$Y=[A,B,C,D,\rho,0,0,0,0,0,0,0,\rho^*,D^*,C^*,B^*]$

$\endgroup$
  • 1
    $\begingroup$ Sure it's bandlimited interpolation. What do you mean, frequency components not present in the original $x$? $\endgroup$ – leftaroundabout Sep 28 '11 at 13:44
  • $\begingroup$ @leftaroundabout The original x is bandlimited (in this example to the Nyquist frequency). OP wants to upsample x by a factor of 2 (my interpretation). One way to upsample x is to insert zeros in the frequency response as shown by OP (the example without E, the one shown in DSP text books) and do an inverse FFT. I believe the same could have been achived by inserting zeros (interleaved) in x and (low-pass) filter by a sinc. By inserting E as shown by OP, the upsampled x is not bandlimited to the original Nyquist frequency. This is typically not desired (it is distortion). Do you agree? $\endgroup$ – niaren Sep 28 '11 at 15:17
  • 1
    $\begingroup$ Inserting zeroes interleaved and convoluting with a sinc (multiplied by 2) should indeed be the corresponding time-domain operation. — I don't think it's distortion: the two bins the OP put $E$s in represent both the same frequency, $\frac\pi2\sim\frac{-\pi}2$. $\endgroup$ – leftaroundabout Sep 28 '11 at 18:09
  • $\begingroup$ I am assuming the frequency ±N/2 is present in x. If it is not (due to bandlimiting or otherwise) then E would be 0 anyway so there would be no difference between padding with E (or 2E) and padding with 0. $\endgroup$ – finnw Sep 28 '11 at 18:13
  • 1
    $\begingroup$ A bandlimited signal can still have content in bin N/2 due to "spectral leakage" from any non-periodic-in-DFT-aperture spectral content, especially near (but not at) Fs/2. $\endgroup$ – hotpaw2 Sep 29 '11 at 17:45

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.