日志
多速率滤波器Part 3
||
Part 3: Interpolation
3.1 Basics
3.1.1 What are "upsampling" and "interpolation"?
"Upsampling" is the process of inserting zero-valued samples between original samples to increase the sampling rate. (This is called "zero-stuffing".) Upsampling adds to the original signal undesired spectral images which are centered on multiples of the original sampling rate.
"Interpolation", in the DSP sense, is the process of upsampling followed by filtering. (The filtering removes the undesired spectral images.) As a linear process, the DSP sense of interpolation is somewhat different from the "math" sense of interpolation, but the result is conceptually similar: to create "in-between" samples from the original samples. The result is as if you had just originally sampled your signal at the higher rate.
3.1.2 Why interpolate?
The primary reason to interpolate is simply to increase the sampling rate at the output of one system so that another system operating at a higher sampling rate can input the signal.
3.1.3 What is the "interpolation factor"?
The interpolation factor is simply the ratio of the output rate to the input rate. It is usually symbolized by "L", so output rate / input rate=L.
Tip: You can remember that "L" is the symbol for interpolation factor by thinking of "interpo-L-ation".
3.1.4 Is there a restriction on interpolation factors I can use?
Yes. Since interpolation relies on zero-stuffing you can only interpolate by integer factors; you cannot interpolate by fractional factors. (However, you can combine interpolation and decimation to achieve an overall rational factor, for example, "4/5"; see Part 4: Resampling.)
3.1.4 Which signals can be interpolated?
All. There is no restriction.
3.1.5 When interpolating, do I always need to do filtering?
Yes. Otherwise, you're doing "upsampling". ;-)
3.1.6 OK, you know what I mean...do I always need to do interpolation (upsampling followed by filtering) or can I get by with doing just upsampling?
Upsampling adds undesired spectral images to the signal at multiples of the original sampling rate, so unless you remove those by filtering, the upsampled signal is not "the same" as the original: it's "distorted".
Some applications may be able to tolerate that (for example, if the images get removed later by an analog filter), but in most applications you will have to remove the undesired images via DSP filtering. Therefore, interpolation is far more common that upsampling alone.
3.2 Multistage
3.2.1 Can I interpolate in multiple stages?
Yes, so long as the interpolation ratio, L, is not a prime number. For example, to interpolate by a factor of 15, you could interpolate by 3, then interpolate by 5. The more factors L has, the more choices you have. For example you could interpolate by 16 in:
one stage: 16
two stages: 4 and 4
three stages: 2, 2, and 4
four stages: 2, 2, 2, and 2
3.2.2 Cool. But why bother with all that?
Just as with decimation, the computational and memory requirements of interpolation filtering can often be reduced by using multiple stages.
3.2.3 OK, so how do I figure out the optimum number of stages, and the interpolation ratio at each stage?
There isn't a simple answer to this one: the answer varies depending on many things. However, here are a couple of rules of thumb:
Using two or three stages is usually optimal or near-optimal.
Interpolate in order of the smallest to largest factors. For example, when interpolating by a factor of 60 in three stages, interpolate by 3, then by 4, then by 5. (Use the largest ratio on the highest rate.)
The multirate book references give additional, more specific guidance.
3.3 Implementation
3.3.1 How do I implement interpolation?
Interpolation always consists of two processes:
Inserting L-1 zero-valued samples between each pair of input samples. This operation is called "zero stuffing".
Lowpass-filtering the result.
The result (assuming an ideal interpolation filter) is a signal at L times the original sampling rate which has the same spectrum over the input Nyquist (0 to Fs/2) range, and with zero spectral content above the original Fs/2.
3.3.2 How does that work?
The zero-stuffing creates a higher-rate signal whose spectrum is the same as the original over the original bandwidth, but has images of the original spectrum centered on multiples of the original sampling rate.
The lowpass filtering eliminates the images.
3.3.3 Why do interpolation by zero-stuffing? Doesn't it make more sense to create the additional samples by just copying the original samples?
This idea is appealing because, intuitively, this "stairstep" output seems more similar to the original than the zero-stuffed version. But in this case, intuition leads us down the garden path. This process causes a "zero-order hold" distortion in the original passband, and still creates undesired images (see below).
Although these effects could be un-done by filtering, it turns out that zero-stuffing approach is not only more "correct", it actually reduces the amount of computation required to implement a FIR interpolation filter. Therefore, interpolation is always done via zero-stuffing.
3.4 FIR Interpolators
3.4.1 How does zero-stuffing reduce computation of the interpolation filter?
The output of a FIR filter is the sum each coefficient multiplied by each corresponding input sample. In the case of a FIR interpolation filter, some of the input samples are stuffed zeros. Each stuffed zero gets multiplied by a coefficient and summed with the others. However, this adding-and-summing processing has no effect when the data sample is zero--which we know in advance will be the case for L-1 out of each L input samples of a FIR interpolation filter. So why bother to calculate these taps?
The net result is that to interpolate by a factor of L, you calculate L outputs for each input using L different "sub-filters" derived from your original filter.
3.4.2 Can you give me an example of a FIR interpolator?
Here's an example of a 12-tap FIR filter that implements interpolation by a factor of four. The coefficients are h0-h11, and three data samples, x0-x2 (with the newest, x2, on the left) have made their way into the filter's delay line:
h0 h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 Result
x2 0 0 0 x1 0 0 0 x0 0 0 0 x2·h0+x1·h4+x0·h8
0 x2 0 0 0 x1 0 0 0 x0 0 0 x2·h1+x1·h5+x0·h9
0 0 x2 0 0 0 x1 0 0 0 x0 0 x2·h2+x1·h6+x0·h10
0 0 0 x2 0 0 0 x1 0 0 0 x0 x2·h3+x1·h7+x0·h11
3.4.3 What can I generalize from that example?
The table suggests the following general observations about FIR interpolators:
Since the interpolation ratio is four (L=4), there are four "sub-filters" (whose coefficient sets are marked here with matching colors.) These sub-filters are officially called "polyphase filters".
For each input, we calculate L outputs by doing L basic FIR calculations, each using a different set of coefficients.
The number of taps per polyphase filter is 3, or, expressed as a formula: Npoly=Ntotal / L.
The coefficients of each polyphase filter can be determined by skipping every Lth coefficient, starting at coefficients 0 through L-1, to calculate corresponding outputs 0 through L-1.
Alternatively, if you rearranged your coefficients in advance in "scrambled" order like this:
h0, h4, h8, h1, h5, h9, h2, h6, h10, h3, h7, h11
then you could just step through them in order .
We have hinted here at the fact that N should be a multiple of L. This isn't absolutely necessary, but if N isn't a multiple of L, the added complication of using a non-multiple of L often isn't worth it. So if the minimum number of taps that your filter specification requires doesn't happen to be a multiple of L, your best bet is usually to just increase N to the next multiple of L. You can do this either by adding some zero-valued coefficients onto the end of the filter, or by re-designing the filter using the larger N value.
3.4.4 What computational savings do I gain by using a FIR interpolator?
Since each output is calculated using only N/L coefficients (rather than N coefficients), you get an overall computational "savings" of (N - N/L) per output .
A simple way to think of the amount of computation required to implement a FIR interpolator is that it is equal to the computation required for a non-interpolating N-tap filter operating at the input rate. In effect, you have to calculate L filters using N/L taps each, so that's N total taps calculated per input.
3.4.5 How much memory savings do I gain by using a FIR interpolator?
Compared to the straight-forward implementation of interpolation by upsampling the signal by stuffing it with L-1 zeros , then filtering it, you save memory by a factor of (L-1)/L. In other words, you don't have to store L-1 zero-stuffed "upsamples" per actual input sample.
3.4.6 How do I design a FIR interpolator?
Just use your favorite FIR design method. The design criteria are:
TBD
3.5 Implementation
3.5.1 How do I implement a FIR interpolator?
An interpolating FIR is actually the same as a regular FIR, except that, for each input, you calculate L outputs per input using L polyphase filters, each having N/L taps. More specifically:
Store a sample in the delay line. (The size of the delay line is N/L.)
For each of L polyphase coefficient sets, calculate an output as the sum-of-products of the delay line values and the filter coefficients.
Shift the delay line by one to make room for the next input.
Also, just as with ordinary FIRs, circular buffers can be used to eliminate the requirement to literally shift the data in the delay line.
3.5.2 Where can I get source code to implement a FIR interpolator in C?
Right here. Our "multirate_algs" package includes an interpolation routine. You can download it from dspGuru's DSP Algorithm Library.
3.5.3 Where can I get assembly code to implement a FIR interpolator?
The major DSP vendors provide examples of FIR interpolators in their data books and application notes, so check their web sites.
3.5.4 How do I test a FIR interpolator?
You can test an interpolating FIR in most of the ways you might test an ordinary FIR:
A special case of an interpolator is an "ordinary" FIR. When given a value of "1" for L, an interpolator should act exactly like an ordinary FIR. You can then do impulse, step, and sine tests on it just like you can on an ordinary FIR.
If you put in a sine whose frequency is within the interpolator's passband, the output should be distortion-free (once the filter reaches steady state), and the frequency of the output should be the same as the frequency of the input, in terms of absolute Hz.
You can use a step response test. Given a unity-valued step input, every group of L outputs should be the same as the sums of the coefficients of the L individual polyphase filters, once the filter has reached steady state.
3.1 Basics
3.1.1 What are "upsampling" and "interpolation"?
"Upsampling" is the process of inserting zero-valued samples between original samples to increase the sampling rate. (This is called "zero-stuffing".) Upsampling adds to the original signal undesired spectral images which are centered on multiples of the original sampling rate.
"Interpolation", in the DSP sense, is the process of upsampling followed by filtering. (The filtering removes the undesired spectral images.) As a linear process, the DSP sense of interpolation is somewhat different from the "math" sense of interpolation, but the result is conceptually similar: to create "in-between" samples from the original samples. The result is as if you had just originally sampled your signal at the higher rate.
3.1.2 Why interpolate?
The primary reason to interpolate is simply to increase the sampling rate at the output of one system so that another system operating at a higher sampling rate can input the signal.
3.1.3 What is the "interpolation factor"?
The interpolation factor is simply the ratio of the output rate to the input rate. It is usually symbolized by "L", so output rate / input rate=L.
Tip: You can remember that "L" is the symbol for interpolation factor by thinking of "interpo-L-ation".
3.1.4 Is there a restriction on interpolation factors I can use?
Yes. Since interpolation relies on zero-stuffing you can only interpolate by integer factors; you cannot interpolate by fractional factors. (However, you can combine interpolation and decimation to achieve an overall rational factor, for example, "4/5"; see Part 4: Resampling.)
3.1.4 Which signals can be interpolated?
All. There is no restriction.
3.1.5 When interpolating, do I always need to do filtering?
Yes. Otherwise, you're doing "upsampling". ;-)
3.1.6 OK, you know what I mean...do I always need to do interpolation (upsampling followed by filtering) or can I get by with doing just upsampling?
Upsampling adds undesired spectral images to the signal at multiples of the original sampling rate, so unless you remove those by filtering, the upsampled signal is not "the same" as the original: it's "distorted".
Some applications may be able to tolerate that (for example, if the images get removed later by an analog filter), but in most applications you will have to remove the undesired images via DSP filtering. Therefore, interpolation is far more common that upsampling alone.
3.2 Multistage
3.2.1 Can I interpolate in multiple stages?
Yes, so long as the interpolation ratio, L, is not a prime number. For example, to interpolate by a factor of 15, you could interpolate by 3, then interpolate by 5. The more factors L has, the more choices you have. For example you could interpolate by 16 in:
one stage: 16
two stages: 4 and 4
three stages: 2, 2, and 4
four stages: 2, 2, 2, and 2
3.2.2 Cool. But why bother with all that?
Just as with decimation, the computational and memory requirements of interpolation filtering can often be reduced by using multiple stages.
3.2.3 OK, so how do I figure out the optimum number of stages, and the interpolation ratio at each stage?
There isn't a simple answer to this one: the answer varies depending on many things. However, here are a couple of rules of thumb:
Using two or three stages is usually optimal or near-optimal.
Interpolate in order of the smallest to largest factors. For example, when interpolating by a factor of 60 in three stages, interpolate by 3, then by 4, then by 5. (Use the largest ratio on the highest rate.)
The multirate book references give additional, more specific guidance.
3.3 Implementation
3.3.1 How do I implement interpolation?
Interpolation always consists of two processes:
Inserting L-1 zero-valued samples between each pair of input samples. This operation is called "zero stuffing".
Lowpass-filtering the result.
The result (assuming an ideal interpolation filter) is a signal at L times the original sampling rate which has the same spectrum over the input Nyquist (0 to Fs/2) range, and with zero spectral content above the original Fs/2.
3.3.2 How does that work?
The zero-stuffing creates a higher-rate signal whose spectrum is the same as the original over the original bandwidth, but has images of the original spectrum centered on multiples of the original sampling rate.
The lowpass filtering eliminates the images.
3.3.3 Why do interpolation by zero-stuffing? Doesn't it make more sense to create the additional samples by just copying the original samples?
This idea is appealing because, intuitively, this "stairstep" output seems more similar to the original than the zero-stuffed version. But in this case, intuition leads us down the garden path. This process causes a "zero-order hold" distortion in the original passband, and still creates undesired images (see below).
Although these effects could be un-done by filtering, it turns out that zero-stuffing approach is not only more "correct", it actually reduces the amount of computation required to implement a FIR interpolation filter. Therefore, interpolation is always done via zero-stuffing.
3.4 FIR Interpolators
3.4.1 How does zero-stuffing reduce computation of the interpolation filter?
The output of a FIR filter is the sum each coefficient multiplied by each corresponding input sample. In the case of a FIR interpolation filter, some of the input samples are stuffed zeros. Each stuffed zero gets multiplied by a coefficient and summed with the others. However, this adding-and-summing processing has no effect when the data sample is zero--which we know in advance will be the case for L-1 out of each L input samples of a FIR interpolation filter. So why bother to calculate these taps?
The net result is that to interpolate by a factor of L, you calculate L outputs for each input using L different "sub-filters" derived from your original filter.
3.4.2 Can you give me an example of a FIR interpolator?
Here's an example of a 12-tap FIR filter that implements interpolation by a factor of four. The coefficients are h0-h11, and three data samples, x0-x2 (with the newest, x2, on the left) have made their way into the filter's delay line:
h0 h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 Result
x2 0 0 0 x1 0 0 0 x0 0 0 0 x2·h0+x1·h4+x0·h8
0 x2 0 0 0 x1 0 0 0 x0 0 0 x2·h1+x1·h5+x0·h9
0 0 x2 0 0 0 x1 0 0 0 x0 0 x2·h2+x1·h6+x0·h10
0 0 0 x2 0 0 0 x1 0 0 0 x0 x2·h3+x1·h7+x0·h11
3.4.3 What can I generalize from that example?
The table suggests the following general observations about FIR interpolators:
Since the interpolation ratio is four (L=4), there are four "sub-filters" (whose coefficient sets are marked here with matching colors.) These sub-filters are officially called "polyphase filters".
For each input, we calculate L outputs by doing L basic FIR calculations, each using a different set of coefficients.
The number of taps per polyphase filter is 3, or, expressed as a formula: Npoly=Ntotal / L.
The coefficients of each polyphase filter can be determined by skipping every Lth coefficient, starting at coefficients 0 through L-1, to calculate corresponding outputs 0 through L-1.
Alternatively, if you rearranged your coefficients in advance in "scrambled" order like this:
h0, h4, h8, h1, h5, h9, h2, h6, h10, h3, h7, h11
then you could just step through them in order .
We have hinted here at the fact that N should be a multiple of L. This isn't absolutely necessary, but if N isn't a multiple of L, the added complication of using a non-multiple of L often isn't worth it. So if the minimum number of taps that your filter specification requires doesn't happen to be a multiple of L, your best bet is usually to just increase N to the next multiple of L. You can do this either by adding some zero-valued coefficients onto the end of the filter, or by re-designing the filter using the larger N value.
3.4.4 What computational savings do I gain by using a FIR interpolator?
Since each output is calculated using only N/L coefficients (rather than N coefficients), you get an overall computational "savings" of (N - N/L) per output .
A simple way to think of the amount of computation required to implement a FIR interpolator is that it is equal to the computation required for a non-interpolating N-tap filter operating at the input rate. In effect, you have to calculate L filters using N/L taps each, so that's N total taps calculated per input.
3.4.5 How much memory savings do I gain by using a FIR interpolator?
Compared to the straight-forward implementation of interpolation by upsampling the signal by stuffing it with L-1 zeros , then filtering it, you save memory by a factor of (L-1)/L. In other words, you don't have to store L-1 zero-stuffed "upsamples" per actual input sample.
3.4.6 How do I design a FIR interpolator?
Just use your favorite FIR design method. The design criteria are:
TBD
3.5 Implementation
3.5.1 How do I implement a FIR interpolator?
An interpolating FIR is actually the same as a regular FIR, except that, for each input, you calculate L outputs per input using L polyphase filters, each having N/L taps. More specifically:
Store a sample in the delay line. (The size of the delay line is N/L.)
For each of L polyphase coefficient sets, calculate an output as the sum-of-products of the delay line values and the filter coefficients.
Shift the delay line by one to make room for the next input.
Also, just as with ordinary FIRs, circular buffers can be used to eliminate the requirement to literally shift the data in the delay line.
3.5.2 Where can I get source code to implement a FIR interpolator in C?
Right here. Our "multirate_algs" package includes an interpolation routine. You can download it from dspGuru's DSP Algorithm Library.
3.5.3 Where can I get assembly code to implement a FIR interpolator?
The major DSP vendors provide examples of FIR interpolators in their data books and application notes, so check their web sites.
3.5.4 How do I test a FIR interpolator?
You can test an interpolating FIR in most of the ways you might test an ordinary FIR:
A special case of an interpolator is an "ordinary" FIR. When given a value of "1" for L, an interpolator should act exactly like an ordinary FIR. You can then do impulse, step, and sine tests on it just like you can on an ordinary FIR.
If you put in a sine whose frequency is within the interpolator's passband, the output should be distortion-free (once the filter reaches steady state), and the frequency of the output should be the same as the frequency of the input, in terms of absolute Hz.
You can use a step response test. Given a unity-valued step input, every group of L outputs should be the same as the sums of the coefficients of the L individual polyphase filters, once the filter has reached steady state.
全部作者的其他最新日志
- • IIR基础
- • 多速率滤波器Part 4
- • 多速率滤波器Part 2
- • 多速率滤波器Part 1
- • FIR滤波器基础Part 4
