Free Books

Linear Interpolation as Resampling

Convolution Interpretation



Linearly interpolated fractional delay is equivalent to filtering and resampling a weighted impulse train (the input signal samples) with a continuous-time filter having the simple triangular impulse response

$\displaystyle h_l(t) = \left\{\begin{array}{ll} 1-\left\vert t/T\right\vert, & ...
...ght\vert\leq T, \\ [5pt] 0, & \hbox{otherwise}. \\ \end{array} \right. \protect$ (5.4)

Convolution of the weighted impulse train with $ h_l(t)$ produces a continuous-time linearly interpolated signal

$\displaystyle x(t) = \sum_{n=-\infty}^{\infty} x(nT) h_l(t-nT). \protect$ (5.5)

This continuous result can then be resampled at the desired fractional delay. In discrete time processing, the operation Eq.$ \,$(4.5) can be approximated arbitrarily closely by digital upsampling by a large integer factor $ M$, delaying by $ L$ samples (an integer), then finally downsampling by $ M$, as depicted in Fig.4.7 [96]. The integers $ L$ and $ M$ are chosen so that $ \eta \approx L/M$, where $ \eta$ the desired fractional delay.
Figure 4.7: Linear interpolation as a convolution.
\includegraphics[width=0.8\twidth]{eps/polyphaseli}
The convolution interpretation of linear interpolation, Lagrange interpolation, and others, is discussed in [407].

Frequency Response of Linear Interpolation

Since linear interpolation can be expressed as a convolution of the samples with a triangular pulse, we can derive the frequency response of linear interpolation. Figure 4.7 indicates that the triangular pulse $ h_l(t)$ serves as an anti-aliasing lowpass filter for the subsequent downsampling by $ M$. Therefore, it should ideally ``cut off'' all frequencies higher than $ 0.5f_s/M$.

Triangular Pulse as Convolution of Two Rectangular Pulses

The 2-sample wide triangular pulse $ h_l(t)$ (Eq.$ \,$(4.4)) can be expressed as a convolution of the one-sample rectangular pulse with itself.
Figure 4.8: The width $ T$ rectangular pulse.
\includegraphics{eps/rectpulse}
The one-sample rectangular pulse is shown in Fig.4.8 and may be defined analytically as

$\displaystyle p_T(t) \isdef u\left(t+\frac{T}{2}\right) - u\left(t-\frac{T}{2}\right),
$

where $ u(t)$ is the Heaviside unit step function:

$\displaystyle u(t) \isdef \left\{\begin{array}{ll}
1, & t\geq 0 \\ [5pt]
0, & t<0 \\
\end{array}\right..
$

Convolving $ p_T(t)$ with itself produces the two-sample triangular pulse $ h_l(t)$:

$\displaystyle h_l(t) = (p_T\ast p_T)(t) \isdef \int_{-\infty}^{\infty} p_T(\tau)p_T(t-\tau)d\tau
$

While the result can be verified algebraically by substituting $ u(t+T/2)-u(t-T/2)$ for $ p_T(t)$, it seen more quickly via graphical convolution.

Linear Interpolation Frequency Response

Since linear interpolation is a convolution of the samples with a triangular pulse $ h_l(t) = (p_T\ast p_T)(t)$ (from Eq.$ \,$(4.5)), the frequency response of the interpolation is given by the Fourier transform $ H_l(f)$, which yields a sinc$ ^2$ function. This frequency response applies to linear interpolation from discrete time to continuous time. If the output of the interpolator is also sampled, this can be modeled by sampling the continuous-time interpolation result in Eq.$ \,$(4.5), thereby aliasing the sinc$ ^2$ frequency response, as shown in Fig.4.9.
Figure: (a) $ \protect$sinc$ ^2(fT) =
{\cal F}_f^2\{p_T/T\}$.
(b) $ \protect\alias _{10}\{\protect$sinc$ ^2(fT)\} \propto
\protect\dtft \{\protect\sample _{T/10}\{p_T\ast p_T\}\}$.
\includegraphics[width=3in]{eps/sincsquared}
In slightly more detail, from $ h_l(t) = (p_T\ast p_T)(t)$, and $ {\cal F}_f\{p_T\}= T$sinc$ ( f T)$, we have

$\displaystyle H_l(f) \isdef {\cal F}_f\{h_l\} = {\cal F}_f\{p_T\ast p_T\} = {\cal F}^2_f\{p_T\} = T^2$sinc$\displaystyle ^2(fT)
$

where we used the convolution theorem for Fourier transforms, and the fact that $ P_T(f) = T$sinc$ ( f T) = \sin(\pi f T) / (\pi f)$. The Fourier transform of $ h_l(nT/L)$ is the same function aliased on a block of size $ f_s=L/T$ Hz. Both $ H_l$ and its alias are plotted in Fig.4.9. The example in this figure pertains to an output sampling rate which is $ L=10$ times that of the input signal. In other words, the input signal is upsampled by a factor of $ L=10$ using linear interpolation. The ``main lobe'' of the interpolation frequency response $ H_l(f)$ contains the original signal bandwidth; note how it is attenuated near half the original sampling rate ($ f T=1$ in Fig.4.9). The ``sidelobes'' of the frequency response contain attenuated copies of the original signal bandwidth (see the DFT stretch theorem), and thus constitute spectral imaging distortion in the final output (sometimes also referred to as a kind of ``aliasing,'' but, for clarity, that term will not be used for imaging distortion in this book). We see that the frequency response of linear interpolation is less than ideal in two ways:
  • The spectrum is ``rolled'' off near half the sampling rate. In fact, it is nowhere flat within the ``passband'' (-1 to 1 in Fig.4.9).
  • Spectral imaging distortion is suppressed by only 26 dB (the level of the first sidelobe in Fig.4.9.
These qualitative remarks apply to all upsampling factors $ L\geq 2$ using linear interpolation. The case $ L=1$ is considered in the next section.

Special Cases

In the limiting case of $ L=1$, the input and output sampling rates are equal, and all sidelobes of the frequency response $ H_l(f)$ (partially shown in Fig.4.9) alias into the main lobe. If the output is sampled at the same exact time instants as the input signal, the input and output are identical. In terms of the aliasing picture of the previous section, the frequency response aliases to a perfect flat response over $ fT\in[-1,1]$, with all spectral images combining coherently under the flat gain. It is important in this reconstruction that, while the frequency response of the underlying continuous interpolating filter is aliased by sampling, the signal spectrum is only imaged--not aliased; this is true for all positive integers $ L$ and $ M$ in Fig.4.7. More typically, when linear interpolation is used to provide fractional delay, identity is not obtained. Referring again to Fig.4.7, with $ L$ considered to be so large that it is effectively infinite, fractional-delay by $ \tau<1$ can be modeled as convolving the samples $ x(n)$ with $ h_l(t-\tau)$ followed by sampling at $ t=nT$. In this case, a linear phase term has been introduced in the interpolator frequency response, giving,

$\displaystyle H_\tau(f) \isdef e^{-j\tau 2\pi f} H_l(f)
$

so that now downsampling to the original sampling rate does not yield a perfectly flat amplitude response for $ fT\in[-1,1]$ (when $ \tau $ is non-integer). Moreover, the phase response is nonlinear as well; a sampled symmetric triangular pulse is only linear phase when the samples fall symmetrically about the midpoint. Some example frequency-responses for various delays $ \tau $ are graphed in Fig.4.2.
Next Section:
Large Delay Changes
Previous Section:
First-Order Allpass Interpolation