Take the 2-minute tour ×
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It's 100% free, no registration required.

I recently encountered a DSP system which did some internal upsampling via zero padding. Expecting zero-order-hold, I was surprised to find that a DC signal did not produce a DC output; many harmonics of the internal (lower) sampling frequency were also present in the output.

This leads to my question: What upsampling techniques are commonly used, and what are their relative merits? Why would I choose zero padding, zero order hold, or first order hold, and what other techniques are available?

Some clarifications:

  • The system is real-time, so the upsampling scheme must be causal.
  • The upsampler is followed by a an anti-aliasing filter that can also be specified.
share|improve this question

3 Answers 3

up vote 11 down vote accepted

For the purposes of this answer I will use Matlab's terminology and define "upsampling" as the process of inserting $m-1$ zeros in between the input samples, and "interpolation" as the combined process of upsampling and filtering to remove the $m-1$ aliases ($m$ being the interpolation factor) that upsampling introduces. For an explanation of how/why upsampling introduces aliases, please see this thread.

It is important to understand that any low-pass filter can be used to get rid of the aliases and thus complete the interpolation. Some filters have advantages when used in interpolation, though. I'll discuss the various flavors of interpolation filtering below.

FIR Filter

Interpolating FIR filters are efficient because they combine upsampling and alias filtering into one step. This is most easily seen in an example. Suppose we have a data sequence $x[n]$ and we want to interpolate it by a factor of two. The first step is to upsample by a factor of two. This changes the original data sequence from $x_0, x_1, ... x_N$ to $x_0, 0, x_1, 0, ... x_N$.

Now suppose we have a low-pass FIR filter, $h[n]$, that we will use to remove the alias. When we convolve the upsampled data sequence with the filter, half the filter taps are stimulated by the non-zero samples, and half the taps are inactive because they correspond to the zero samples. The half that is stimulated and the half that is inactive flips back and forth as the filter goes through the data. These two sets of taps are sometimes referred to as the filter phases.

This same effect can be achieved implicitly by eliminating the upsampling, and filtering the original data sequence with an interpolating FIR filter. The interpolating FIR filter produces $m$ outputs for every input sample. For all $m$ outputs the filter will operate on the same $ceil(K/m)$ input samples (where K is the number of filter taps and "ceil" is the ceiling function).

An example will hopefully illustrate how this works. Suppose that we have a six tap filter and we are interpolating by a factor of two. The filter taps are [1 -2 4 4 -2 1]. If we literally interpolated and then filtered the samples and filter taps would line up (once there was full overlap) as follows:

$$ 0 : 1\\ x_2 : -2 \\ 0 : 4 \\ x_1 : 4 \\ 0 : -2 \\ x_0 : 1 \\ $$ Next sample...

$$ x_3 : 1\\ 0 : -2 \\ x_2 : 4 \\ 0 : 4 \\ x_1 : -2 \\ 0 : 1 \\ $$ Next sample...

$$ 0 : 1\\ x_3 : -2 \\ 0 : 4 \\ x_2 : 4 \\ 0 : -2 \\ x_1 : 1 \\ $$ And so on. The point of the interpolating filter is that it skips actually inserting the zeros and just alternates which set of taps it uses at the moment instead. Thus, the preceding sequence would now look like the following:

$$ x_2 : -2 \\ x_1 : 4 \\ x_0 : 1 \\ $$

$$ x_3 : 1 \\ x_2 : 4 \\ x_1 : -2 \\ $$

$$ x_3 : -2 \\ x_2 : 4 \\ x_1 : 1 \\ $$

Zero Order Hold

A zero-order hold interpolator is one that simply repeats each sample $m-1$ times. So a factor of two zero-order hold interpolator converts $x_0, x_1, ... x_N$ into $x_0, x_0, x_1, x_1, ... x_N, x_N$. This method is attractive because it is exceedingly easy, both in terms of coding and computational load, to implement.

The problem with it is that its low-pass filtering is quite poor. We can see that when we recognize that the zero-hold interpolator is a special case of FIR interpolation. It corresponds to upsampling followed by an $m$-wide rectangle filter. The Fourier transform of a rectangle filter is a sinc function, which is a rather shabby low-pass filter. It's shabbiness can be fixed with a compensating FIR filter, but if you are going to do that you might as well just use a good low-pass filter to begin with.

First Order Hold

First order hold is a step up from the zero-hold interpolator in that it linearly interpolates the upsamples using the two nearest input samples. So, a factor of two first-order hold interpolator would convert $x_0, x_1, ... x_N$ into $x_0, \frac{x_0+x_1}{2}, x_1, \frac{x_1+x_2}{2}, ... x_N$.

Like the zero-order hold interpolator, the first-order hold interpolator is a special case of FIR interpolation. It corresponds to upsampling and filtering with a triangle filter. For factor-of-two interpolation the filter is $[\frac{1}{2} 1 \frac{1}{2}]$, for factor-of-three interpolation the filter is $[\frac{1}{3} \frac{2}{3} 1 \frac{2}{3} \frac{1}{2}]$, and so on.

The triangle filter is two rectangle filters convolved together, which corresponds to sinc squared in the frequency domain. This is a definite step up from the zero-order hold, but is still not great.

IIR Filter

I have never used an interpolating IIR filter so I won't say a lot about them. I assume that the same arguments apply as in regular filtering- IIR filters are more efficient, can be unstable, don't have linear phase, etc. I do not believe that they can combine the upsampling and filtering steps like a FIR filter can, but I could be wrong about that.

FFT Interpolation

I'll throw this one in even though it's not very common (of course, I don't think the zero-hold is common either). This thread discusses FFT resampling, where resampling is both interpolation and decimation.

Higher Order Holds

Second-order hold interpolators are usually referred to as "quadratic interpolators". They are non-linear and thus cannot be implemented as FIR filters, which are linear. I do not understand the math behind them well, so I won't discuss their performance. I will say, though, that I believe that they are somewhat common outside of signal processing.

Higher order (three or more) methods also exist. These are referred to as "polynomial regressions".

EDIT:

Cascade Integrator Comb (CIC) Filters

I forgot to mention CIC Filters. CIC filters are used for two reasons: they use only adders/subtracters (not as big a deal now that multiplies are fast and cheap), and they can do really large sample rate changes pretty efficiently. Their down side is that they are essentially an efficient implementation of a cascaded rectangle filter, so they have all of the disadvantages of rectangle filters as discussed above. CIC interpolators are pretty much always preceded by a compensating FIR filter that pre-distorts the signal to cancel out the distortion introduced by the CIC. If the sample rate change is large enough the cost of the pre-distortion filter is worth it.

share|improve this answer
    
Fantastic survey Mr Jim. To add to your higher-order-holds category, I believe that this is also referred to as "polynomial regression". In that, given a specific set of points, we compute a line, parabola, cubic, higher-order polynomial of best fit. Once we have the equation, we can easily figure out what intermediate points are. –  Mohammad Oct 10 '12 at 15:09
    
Questions: 1) I am not entirely clear about the last paragraph of the FIR Filter part. You mentioned that the 2nd and 3rd outputs corresponding to the 1st input sample use filter tapes 1, 4, 7, and then 2, 5, 8. However you also mention that they are all zeros... so arent the 2nd and 3rd output samples just zeros in this case? 2) This 'FIR Interpolating Filter', does it look something like, say, [1 0 0 3.2 0 0 -2.1 0 0 1.1 0 0] for m = 3? (Numbers are made up). –  Mohammad Oct 10 '12 at 15:31
    
@Mohammad I have edited the answer. I hope this helps. And thanks for the information on polynomial regressions. –  Jim Clay Oct 10 '12 at 20:36
1  
@endolith Two reasons, I think: complexity and it only makes sense computationally when the filter length is beyond a certain number (and I'm not sure what that number is). The FFT approach does very well when dealing with blocks of samples, but if you are dealing with a stream of samples then you also have to do overlap-add or overlap-save to maintain continuity. –  Jim Clay Oct 11 '12 at 20:16
1  
@endolith One really nice thing about the FFT approach is that there is virtually no cost to using a large filter. –  Jim Clay Oct 11 '12 at 20:19

Jim's answer covers it quite well. All upsampling methods follow the same basic scheme:

  1. Insert zeros between samples: These results in a periodic repetition of the original spectrum but leaves the spectrum in the original band completely intact
  2. Low pass filter to get rid of all the mirror spectra

The main difference between methods is how the low pass filtering is implemented. The ideal upsampler would be include an ideal low-pass filter but that's impractical. Considering the problem in the frequency domain allows to find the right up-sampling algorithm for your specific requirements:

  1. How much amplitude distortion can I tolerate in the original band? Is that frequency dependent ?
  2. Do I care about phase in the original band? If you need to maintain the phase you need a linear phase FIR. If not a minimum phase does a better job at maintaining "causality" and sharp onsets.
  3. How much do I need to suppress the mirror images? Basically the mirror images will show up as extra noise in the base band.

High order non-linear interpolators (spline , hermitian, Lagrange) typically don't work well since the interpolation error is highly signal dependent and almost impossible to map to specific requirement.

share|improve this answer
    
Thanks for the succinct answer! –  nibot Oct 12 '12 at 18:33
    
What do you mean by "does a better job at maintaining 'causality'"? –  nibot Oct 12 '12 at 18:34

When considering the difference between sample-and-hold (i.e. repetition of sample values) and zero padding, it's helpful to realize (as Jim and Hilmar point out) that sample-and-hold can be interpreted as upsampling by zero padding followed by an FIR filter whose impulse response consists of a rectangular pulse.

For example, when upsampling from 2 kHz to 64 kHz (a factor of 32), we can implement this by inserting 31 zeros between each pair of 2 kHz sampling, and then filtering by an FIR filter which consists of 32 ones, with all other coefficients zero.

Considering the sample-and-hold in this way makes it easy to analyze. We can get the frequency response of the sample-and-hold operation by taking the Fourier transform of the rectangular window. As Jim points out, the Fourier transform of a rectangular pulse is a sinc function with linear phase (since the rectangle is not centered around $\tau=0$).

It turns out that this sinc function has its nulls at exactly the harmonics of the lower sampling frequency. In our example application of upsampling from 2048 Hz to 65536 Hz, the frequency response of the sample-and-hold operation has nulls at 2048 Hz, 4096 Hz, etc .

enter image description here

From this, I conclude that any interpolating filter that totally suppresses the harmonics of the original sampling frequency will look something like "sample and hold". Is this right?

With respect to the criteria of suppressing these harmonics, the sample-and-hold appears to be optimal. However, its anti-aliasing abilities are poor, since, aside from the harmonic nulls, its frequency response only falls off like $1/f$ above the old Nyquist rate.

share|improve this answer
    
The problem is that the nulls are very narrow, so most signals will have energy outside of the nulls. –  Jim Clay Oct 11 '12 at 20:11
    
@JimClay, Aren't the narrow nulls perfect for killing the harmonics of the lower sampling rate? I agree, you would also want a few more poles around 1 kHz in order to get rid of image frequencies. I guess I would expand my question: how does one design a good interpolation filter? –  nibot Oct 12 '12 at 9:42
    
You design a low-pass filter whose pass band includes your signal's bandwidth, and whose stop band includes the aliases that are introduced when you upsample. The frequencies in between the signal's 3dB point and the alias' are your transition band. If your question is "how do I design a low-pass filter?", then ask that in another question and we can discuss it. –  Jim Clay Oct 12 '12 at 14:21
    
I generally understand how to design filters, usually by placing poles and zeros in the s-domain explicitly and then converting them to z-domain filters. I was wondering whether there were any special tricks for interpolation filters. The message I'm taking away is that there aren't really any tricks--interpolation filters are just like any other kind of filters, and their design is a choice of a compromise between the various considerations (ripple, phase, group delay, minimum stop-band attenuation, computational complexity, etc). –  nibot Oct 12 '12 at 18:00
    
On the other hand, I don't know anything about designing FIR filters. –  nibot Oct 12 '12 at 18:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.