Frequency-domain zero padding - special treatment of X[N/2]

Question

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.

Answer 1

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.

Answer 2

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^*]$

Answer 3

Please see additional intuitive insights posted at this related question.