Free Books
   Free Books    Mathematics of the DFT  

Periodic Interpolation (Spectral Zero Padding)

The dual of the zero-padding theorem states formally that zero padding in the frequency domain corresponds to periodic interpolation in the time domain:


Definition: For all $ x\in{\bf C}^N$ and any integer $ L\geq 1$,

$\displaystyle \zbox {\hbox{\sc PerInterp}_L(x) \isdef \hbox{\sc IDFT}(\hbox{\sc ZeroPad}_{LN}(X))} \protect$ (7.7)

where zero padding is defined in §7.2.7 and illustrated in Figure 7.7. In other words, zero-padding a DFT by the factor $ L$ in the frequency domain (by inserting $ N(L-1)$ zeros at bin number $ k=N/2$ corresponding to the folding frequency7.21) gives rise to ``periodic interpolation'' by the factor $ L$ in the time domain. It is straightforward to show that the interpolation kernel used in periodic interpolation is an aliased sinc function, that is, a sinc function $ \sin(\pi n/L)/(\pi n/L)$ that has been time-aliased on a block of length $ NL$. Such an aliased sinc function is of course periodic with period $ NL$ samples. See Appendix D for a discussion of ideal bandlimited interpolation, in which the interpolating sinc function is not aliased.

Periodic interpolation is ideal for signals that are periodic in $ N$ samples, where $ N$ is the DFT length. For non-periodic signals, which is almost always the case in practice, bandlimited interpolation should be used instead (Appendix D).

Relation to Stretch Theorem

It is instructive to interpret the periodic interpolation theorem in terms of the stretch theorem, $ \hbox{\sc Stretch}_L(x) \;\longleftrightarrow\;\hbox{\sc Repeat}_L(X)$. To do this, it is convenient to define a ``zero-centered rectangular window'' operator:


Definition: For any $ X\in{\bf C}^N$ and any odd integer $ M<N$ we define the length $ M$ even rectangular windowing operation by

$\displaystyle \hbox{\sc Chop}_{M,k}(X) \isdef \left\{\begin{array}{ll} X(k), ... ...+1}{2} \leq \left\vert k\right\vert \leq \frac{N}{2}. \\ \end{array} \right. $

Thus, this ``zero-phase rectangular window,'' when applied to a spectrum $ X$, sets the spectrum to zero everywhere outside a zero-centered interval of $ M$ samples. Note that $ \hbox{\sc Chop}_M(X)$ is the ideal lowpass filtering operation in the frequency domain. The ``cut-off frequency'' is $ \omega_c = 2\pi[(M-1)/2]/N$ radians per sample. For even $ M$, we allow $ X(-M/2)$ to be ``passed'' by the window, but in our usage (below), this sample should always be zero anyway. With this notation defined we can efficiently restate periodic interpolation in terms of the $ \hbox{\sc Stretch}()$ operator:


Theorem: When $ x\in{\bf C}^N$ consists of one or more periods from a periodic signal $ x^\prime\in {\bf C}^\infty$,

$\displaystyle \zbox {\hbox{\sc PerInterp}_L(x) = \hbox{\sc IDFT}(\hbox{\sc Chop}_N(\hbox{\sc DFT}(\hbox{\sc Stretch}_L(x)))).} $

In other words, ideal periodic interpolation of one period of $ x$ by the integer factor $ L$ may be carried out by first stretching $ x$ by the factor $ L$ (inserting $ L-1$ zeros between adjacent samples of $ x$), taking the DFT, applying the ideal lowpass filter as an $ N$-point rectangular window in the frequency domain, and performing the inverse DFT.


Proof: First, recall that $ \hbox{\sc Stretch}_L(x)\leftrightarrow \hbox{\sc Repeat}_L(X)$. That is, stretching a signal by the factor $ L$ gives a new signal $ y=\hbox{\sc Stretch}_L(x)$ which has a spectrum $ Y$ consisting of $ L$ copies of $ X$ repeated around the unit circle. The ``baseband copy'' of $ X$ in $ Y$ can be defined as the $ N$-sample sequence centered about frequency zero. Therefore, we can use an ``ideal filter'' to ``pass'' the baseband spectral copy and zero out all others, thereby converting $ \hbox{\sc Repeat}_L(X)$ to $ \hbox{\sc ZeroPad}_{LN}(X)$. I.e.,

$\displaystyle \hbox{\sc Chop}_N(\hbox{\sc Repeat}_L(X)) = \hbox{\sc ZeroPad}_{LN}(X) \;\longleftrightarrow\;\hbox{\sc Interp}_L(x). $

The last step is provided by the zero-padding theorem (§7.4.12).

Bandlimited Interpolation of Time-Limited Signals

The previous result can be extended toward bandlimited interpolation of $ x\in{\bf C}^{N_x}$ which includes all nonzero samples from an arbitrary time-limited signal $ x^\prime\in {\bf C}^\infty$ (i.e., going beyond the interpolation of only periodic bandlimited signals given one or more periods $ x\in{\bf C}^N$) by

  1. replacing the rectangular window $ \hbox{\sc Chop}_N()$ with a smoother spectral window $ H(\omega)$, and
  2. using extra zero-padding in the time domain to convert the cyclic convolution between $ \hbox{\sc Stretch}_L(x)$ and $ h$ into an acyclic convolution between them (recall §7.2.4).
The smoother spectral window $ H$ can be thought of as the frequency response of the FIR7.22 filter $ h$ used as the bandlimited interpolation kernel in the time domain. The number of zeros needed in the zero-padding of $ x$ in the time domain is simply length of $ h$ minus 1, and the number of zeros to be appended to $ h$ is the length of $ \hbox{\sc Stretch}_L(x)$ minus 1. With this much zero-padding, the cyclic convolution of $ x$ and $ h$ implemented using the DFT becomes equivalent to acyclic convolution, as desired for the time-limited signals $ x$ and $ h$. Thus, if $ N_x$ denotes the nonzero length of $ x$, then the nonzero length of $ \hbox{\sc Stretch}_L(x)$ is $ L(N_x-1)+1$, and we require the DFT length to be $ N\geq L(N_x-1)+N_h$, where $ N_h$ is the filter length. In operator notation, we can express bandlimited sampling-rate up-conversion by the factor $ L$ for time-limited signals $ x\in{\bf C}^{N_x}$ by

$\displaystyle \zbox {\hbox{\sc Interp}_L(x) \approx \hbox{\sc IDFT}(H\cdot(\hbox{\sc DFT}(\hbox{\sc ZeroPad}_{N}(\hbox{\sc Stretch}_L(x)))).} \protect$ (7.8)

The approximation symbol `$ \approx$' approaches equality as the spectral window $ H$ approaches $ \hbox{\sc Chop}_{N_x}([1,\dots,1])$ (the frequency response of the ideal lowpass filter passing only the original spectrum $ X$), while at the same time allowing no time aliasing (convolution remains acyclic in the time domain).

Equation (7.8) can provide the basis for a high-quality sampling-rate conversion algorithm. Arbitrarily long signals can be accommodated by breaking them into segments of length $ N_x$, applying the above algorithm to each block, and summing the up-sampled blocks using overlap-add. That is, the lowpass filter $ h$ ``rings'' into the next block and possibly beyond (or even into both adjacent time blocks when $ h$ is not causal), and this ringing must be summed into all affected adjacent blocks. Finally, the filter $ H$ can ``window away'' more than the top $ L-1$ copies of $ X$ in $ Y$, thereby preparing the time-domain signal for downsampling, say by $ M\in{\bf Z}$:

$\displaystyle {\footnotesize \zbox {\hbox{\sc Interp}_{L/M}(x) \approx \hbox{\s... ...T}(H\cdot(\hbox{\sc DFT}(\hbox{\sc ZeroPad}_{N}(\hbox{\sc Stretch}_L(x)))))} } $

where now the lowpass filter frequency response $ H$ must be close to zero for all $ \vert\omega_k\vert\geq\pi/\max(L,M)$. While such a sampling-rate conversion algorithm can be made more efficient by using an FFT in place of the DFT (see Appendix A), it is not necessarily the most efficient algorithm possible. This is because (1) $ M-1$ out of $ M$ output samples from the IDFT need not be computed at all, and (2) $ \hbox{\sc Stretch}_L(x)$ has many zeros in it which do not need explicit handling. For an introduction to time-domain sampling-rate conversion (bandlimited interpolation) algorithms which take advantage of points (1) and (2) in this paragraph, see, e.g., Appendix D and [72].

Next Section:
Why a DFT is usually called an FFT in practice
Previous Section:
Zero Padding Theorem (Spectral Interpolation)