Free Books

Linear Interpolation

Linear interpolation works by effectively drawing a straight line between two neighboring samples and returning the appropriate point along that line.

More specifically, let $ \eta$ be a number between 0 and 1 which represents how far we want to interpolate a signal $ y$ between time $ n$ and time $ n+1$. Then we can define the linearly interpolated value $ \hat y(n+\eta)$ as follows:

$\displaystyle \hat y(n+\eta) = (1-\eta) \cdot y(n) + \eta \cdot y(n+1) \protect$ (5.1)

For $ \eta=0$, we get exactly $ \hat y(n)=y(n)$, and for $ \eta=1$, we get exactly $ \hat y(n+1)=y(n+1)$. In between, the interpolation error $ \left\vert\hat y(n+\eta)-y(n+\eta)\right\vert$ is nonzero, except when $ y(t)$ happens to be a linear function between $ y(n)$ and $ y(n+1)$.

One-Multiply Linear Interpolation

Note that by factoring out $ \eta$, we can obtain a one-multiply form,

$\displaystyle \hat y(n+\eta) = y(n) + \eta\cdot\left[y(n+1) - y(n)\right].

Thus, the computational complexity of linear interpolation is one multiply and two additions per sample of output.

Fractional Delay Filtering by Linear Interpolation

Figure 4.1: Linearly interpolated delay line.

A linearly interpolated delay line is depicted in Fig.4.1. In contrast to Eq.$ \,$(4.1), we interpolate linearly between times $ n-M$ and $ n-M-1$, and $ \eta$ is called the fractional delay in samples. The first-order (linear-interpolating) filter following the delay line in Fig.4.1 may be called a fractional delay filter [267]. Equation (4.1), on the other hand, expresses the more general case of an interpolated table lookup, where $ y(n)$ is regarded as a table of samples and $ \hat y(n+\eta)$ is regarded as an interpolated table-lookup based on the samples stored at indices $ n$ and $ n+1$.

The difference between a fractional delay filter and an interpolated table lookup is that table-lookups can ``jump around,'' while fractional delay filters receive a sequential stream of input samples and produce a corresponding sequential stream of interpolated output values. As a result of this sequential access, fractional delay filters may be recursive IIR digital filters (provided the desired delay does not change too rapidly over time). In contrast, ``random-access'' interpolated table lookups are typically implemented using weighted linear combinations, making them equivalent to nonrecursive FIR filters in the sequential case.5.1

The C++ class implementing a linearly interpolated delay line in the Synthesis Tool Kit (STK) is called DelayL.

The frequency response of linear interpolation for fixed fractional delay ($ \eta$ fixed in Fig.4.1) is shown in Fig.4.2. From inspection of Fig.4.1, we see that linear interpolation is a one-zero FIR filter. When used to provide a fixed fractional delay, the filter is linear and time-invariant (LTI). When the fractional delay $ \eta$ changes over time, it is a linear time-varying filter.

Figure 4.2: Linear interpolation frequency responses for delays between 0 and 1. Note the higher accuracy at low frequencies, reaching zero error at dc for all fractional delays.

Linear interpolation sounds best when the signal is oversampled. Since natural audio spectra tend to be relatively concentrated at low frequencies, linear interpolation tends to sound very good at high sampling rates.

When interpolation occurs inside a feedback loop, such as in digital waveguide models for vibrating strings (see Chapter 6), errors in the amplitude response can be highly audible (particularly when the loop gain is close to 1, as it is for steel strings, for example). In these cases, it is possible to eliminate amplitude error (at some cost in delay error) by using an allpass filter for delay-line interpolation.

Next Section:
First-Order Allpass Interpolation
Previous Section:
Further Extensions