Main Content

Multistage Rate Conversion

Multistage rate conversion is an approach that splits rate conversion into several stages. For example, instead of decimation by a factor of 18, decimate by factor of 3, followed by another decimation by 3, and and then by a factor of 2. Using multiple stages reduces the computational complexity of filtered rate conversion. Furthermore, if one already has the converter units for the different prime factors, they can be used as building blocks for higher rates. This example demonstrates multistage rate conversion designs.

Single-Stage v.s. Multistage Conversion: Cost Analysis

Consider decimation system of rate M = 8. One can implement such a system in two ways:

  • A single decimator of rate M = 8.

  • A cascade of three half-rate decimators ( M = 2)

A multistage cascade of filtered decimators (or interpolators) has a reduced single-stage form. The filter in the reduced form is called the single-stage equivalent filter, which encapsualtes the filters of all the stages. Thus, any multistage cascade FIR decimator can be represented as a single-stage FIR decimator. For more details, see [1]. However, while the two alternatives effectively perform the same decimation, they differ in their numerical complexites.

Evaluate the cost of implementing a multistage decimator using the cost function, and compare to the cost of implementing a single-stage decimator.

firDecim2_1 = dsp.FIRDecimator(2);
firDecim2_2 = dsp.FIRDecimator(2);
firDecim2_3 = dsp.FIRDecimator(2);
firDecim2cascade = dsp.FilterCascade(firDecim2_1,firDecim2_2,firDecim2_3);

cost2cascade = cost(firDecim2cascade)

firDecim8 = dsp.FIRDecimator(8);
cost8 = cost(firDecim8)
cost2cascade = 

  struct with fields:

                  NumCoefficients: 75
                        NumStates: 138
    MultiplicationsPerInputSample: 21.8750
          AdditionsPerInputSample: 21


cost8 = 

  struct with fields:

                  NumCoefficients: 169
                        NumStates: 184
    MultiplicationsPerInputSample: 21.1250
          AdditionsPerInputSample: 21

Cascading three decimators of rate M=2 consumes less memory (states and coefficients) compared to a single-stage decimator of M=8, making the multistage converter more memory efficient. The arithmetic load (operations per sample) of the single-stage and multistage implementation are equivalent. Note that the number of samples drops by half after each decimation stage. In conclusion, it is often better to split the decimation into multiple stages (given that the rate change factor is not a prime number, of course).

There is usually more than one way to factor a (non-prime) conversion rate, and even more degrees of freedom multistage design. The DSP System Toolbox (TM) offers several tools to simplify the design process. We will examine two of them in what follows.

Using designMultistageDecimator and designMultistageInterpolator Functions

The designMultistageInterpolator and designMultistageDecimator functions automatically determine an optimal configuation, that includes determining the number of stages along with their arrangements, lowpass parameters, etc. The result is a filter cascade system object, which encapsualtes all the stages. To illustrate, let us design a decimator of rate M=12.

M = 12;
fcDecMulti = designMultistageDecimator(M);
disp(cascadeInfoSummary(fcDecMulti))
Multistage FIR Decimator, M=12 (48.0kHz to 4.0kHz)
Equivalent lowpass cutoff: 4.0kHz, transition Width: 800.0Hz

Number of stages: 3
Stage1: FIR Decimator, M = 2 (48.0kHz to 24.0kHz), FIR Length = 11                                                                  
Stage2: FIR Decimator, M = 2 (24.0kHz to 12.0kHz), FIR Length = 15                                                                  
Stage3: FIR Decimator, M = 3 (12.0kHz to 4.0kHz),  FIR Length = 79                                                                  

This particular design has 3 stages ($12=2\times 2\times 3$), where the lowpass of the last stage is the longest.

Repeat the design with a single-stage.

fcDecSingle = designMultistageDecimator(M,'NumStages',1);
disp(cascadeInfoSummary(fcDecSingle))
Multistage FIR Decimator, M=12 (48.0kHz to 4.0kHz)
Equivalent lowpass cutoff: 4.0kHz, transition Width: 800.0Hz

Number of stages: 1
Stage1: FIR Decimator, M = 12 (48.0kHz to 4.0kHz), FIR Length = 307                                                                 

Compare the cost of the two implementations. Obivously, the multistage approach is more efficient.

costMulti  = cost(fcDecMulti)
costSingle = cost(fcDecSingle)
costMulti = 

  struct with fields:

                  NumCoefficients: 69
                        NumStates: 102
    MultiplicationsPerInputSample: 10.1667
          AdditionsPerInputSample: 9.3333


costSingle = 

  struct with fields:

                  NumCoefficients: 283
                        NumStates: 300
    MultiplicationsPerInputSample: 23.5833
          AdditionsPerInputSample: 23.5000

Now, let us compare the combined frequency response of the decimation filters. While the filters of the two implementations differ in the stopband, the passband and transition band are nearly identical.

hfv = fvtool(fcDecMulti, fcDecSingle);
legend(hfv,'Multistage Combined Response', 'Single-Stage Response');

The same methodology applies for designMultistageInterpolator. Create two interpolators (single-stage and multistage) and compare their outputs. Note that the outputs are nearly identical, except a slightly longer latency of the multistage interpolator.

n = (1:20)';
x = (abs(n-5)<=5).*(5-abs(n-5));

L = 12;
fcIntrMulti  = designMultistageInterpolator(L);
fcIntrSingle = designMultistageInterpolator(L,'NumStages',1);

xInterpSingle = fcIntrSingle(x);
xInterpMulti  = fcIntrMulti(x);

release(fcIntrMulti);
release(fcIntrSingle);

subplot(3,1,1); stem(x); xlim([1,20]); title('Input Sequence');
subplot(3,1,2); stem(xInterpSingle); title('Single-Stage Interpolated')
subplot(3,1,3); stem(xInterpMulti); title('Multistage Interpolated')

Additional Design Parameters for the designMultistageDecimator and designMultistageInterpolator Functions

You can specify filter design parameters such as transition width and stopband attenuation to the designMultistageDecimator and designMultistageInterpolator functions. Such additional parameters allow for better control of the filter characteristics. The input sample rate Fs is assumed to be 1 by default, but this value can be customized as well.

Design a filter that reduces the input rate from 48 MHz to 1 MHz, a decimation factor of 48. The following are typical specifications for a lowpass filter that reduces the bandwidth accordingly.

Fs    = 48e6;
TW    = 100e3;
Astop = 80;     % Minimum stopband attenuation
M     = 48;     % Decimation factor

Here is a simple multistage design for these specs.

multiDecim = designMultistageDecimator(M,Fs,TW,Astop);
disp(cascadeInfoSummary(multiDecim))
Multistage FIR Decimator, M=48 (48.0MHz to 1.0MHz)
Equivalent lowpass cutoff: 1.0MHz, transition Width: 100.0kHz

Number of stages: 5
Stage1: FIR Decimator, M = 2 (48.0MHz to 24.0MHz), FIR Length = 7                                                                    
Stage2: FIR Decimator, M = 2 (24.0MHz to 12.0MHz), FIR Length = 7                                                                    
Stage3: FIR Decimator, M = 2 (12.0MHz to 6.0MHz),  FIR Length = 11                                                                   
Stage4: FIR Decimator, M = 3 (6.0MHz to 2.0MHz),   FIR Length = 33                                                                   
Stage5: FIR Decimator, M = 2 (2.0MHz to 1.0MHz),   FIR Length = 95                                                                   

This is a 5-stage decimator cascade with the factors $2 \rightarrow 2 \rightarrow 2 \rightarrow 3 \rightarrow 2$ whose product is $2^4\times 3~ = ~48$ as expected.

Design a similar filter with the default transition width and attenuation. The overall conversion rate is similar, but the transition width (and perhaps the ordering of the stages) can be different.

multiDecim_default = designMultistageDecimator(M,Fs);
disp(cascadeInfoSummary(multiDecim_default))
Multistage FIR Decimator, M=48 (48.0MHz to 1.0MHz)
Equivalent lowpass cutoff: 1.0MHz, transition Width: 200.0kHz

Number of stages: 5
Stage1: FIR Decimator, M = 2 (48.0MHz to 24.0MHz), FIR Length = 7                                                                    
Stage2: FIR Decimator, M = 2 (24.0MHz to 12.0MHz), FIR Length = 7                                                                    
Stage3: FIR Decimator, M = 2 (12.0MHz to 6.0MHz),  FIR Length = 11                                                                   
Stage4: FIR Decimator, M = 2 (6.0MHz to 3.0MHz),   FIR Length = 15                                                                   
Stage5: FIR Decimator, M = 3 (3.0MHz to 1.0MHz),   FIR Length = 79                                                                   

Design a single-stage decimator using the same parameters.

singleDecim = designMultistageDecimator(M,Fs,TW,Astop,'NumStages',1);
disp(cascadeInfoSummary(singleDecim))
Multistage FIR Decimator, M=48 (48.0MHz to 1.0MHz)
Equivalent lowpass cutoff: 1.0MHz, transition Width: 100.0kHz

Number of stages: 1
Stage1: FIR Decimator, M = 48 (48.0MHz to 1.0MHz), FIR Length = 2411                                                                 

Compare the filter costs for the single-stage and the multistage implementations. The number of multiplications per input sample for the multistage approach is about 7, and roughly 49 for the single-stage implementation. In other words, using the multistage implementation reduces the number of multiplications by a factor of 7, which makes a significant difference. Similar differences can be observed in the number of coefficints (89 v.s. 2361), number of states (146 v.s. 2400), and additions per input sample (6 v.s. 49).

costMultiDecim  = cost(multiDecim)

costSingleDecim = cost(singleDecim)
costMultiDecim = 

  struct with fields:

                  NumCoefficients: 89
                        NumStates: 146
    MultiplicationsPerInputSample: 6.6042
          AdditionsPerInputSample: 5.6667


costSingleDecim = 

  struct with fields:

                  NumCoefficients: 2361
                        NumStates: 2400
    MultiplicationsPerInputSample: 49.1875
          AdditionsPerInputSample: 49.1667

Compare the frequency responses of the single-stage implementation and the single-stage equivalents of the two multistage designs. The gain responses of the three implementations are very similar on the passband and transition band, and have negligible differences on the stopband. In spite of the significant cost difference, the lowpass filtering in all three designs is almost the same.

hfv = fvtool(multiDecim, multiDecim_default, singleDecim);
legend(hfv, 'Multistage (Custom Parameters)','Multistage (Default parameters)','Single stage')

The default design has a slightly larger transition width.

hfv = fvtool(multiDecim, multiDecim_default, singleDecim);
legend(hfv, 'Multistage (Custom Parameters)','Multistage (Default parameters)','Single stage')
xlim([0 0.8])

Optimial Designs for a Minimimal Total Number of Coefficients

By default, the design minimizes multiplications per input sample. It is also possible to minimize the number of coefficients. Set the property MinTotalCoeffs = true to use the latter cost.

minCoeffDecim = designMultistageDecimator(M,Fs,TW,Astop,'MinTotalCoeffs',true);
disp(cascadeInfoSummary(minCoeffDecim))
cost(minCoeffDecim)
Multistage FIR Decimator, M=48 (48.0MHz to 1.0MHz)
Equivalent lowpass cutoff: 1.0MHz, transition Width: 100.0kHz

Number of stages: 5
Stage1: FIR Decimator, M = 2 (48.0MHz to 24.0MHz), FIR Length = 7                                                                    
Stage2: FIR Decimator, M = 3 (24.0MHz to 8.0MHz),  FIR Length = 17                                                                   
Stage3: FIR Decimator, M = 2 (8.0MHz to 4.0MHz),   FIR Length = 11                                                                   
Stage4: FIR Decimator, M = 2 (4.0MHz to 2.0MHz),   FIR Length = 23                                                                   
Stage5: FIR Decimator, M = 2 (2.0MHz to 1.0MHz),   FIR Length = 95                                                                   

ans = 

  struct with fields:

                  NumCoefficients: 87
                        NumStates: 147
    MultiplicationsPerInputSample: 6.8125
          AdditionsPerInputSample: 6

Compared to multiDecim, the number of coefficients in minCoeffDecim is lower, but the number of multiplications per input sample is higher.

Estimate vs. Design for Determining Cost

The objective function of the optimal design (either the number of coefficients or multiplications) that the designMultistageDecimator function uses depends on the FIR length of every stage. By default, this function evaluates the cost using an estimate of the FIR length rather than a true length, sometimes leading to a sub-optimal filter design.

A slower, but more precise method uses a cost based on the true FIR lengths obtained through actual designs of all filter candidates. Use the property CostMethod='design' to optimize for the accurate cost. Setting this property ensures that the design cost is indeed minimal.

trueMinCostDecim = designMultistageDecimator(M,Fs,TW,Astop, 'CostMethod','design');

disp(cascadeInfoSummary(trueMinCostDecim))
Multistage FIR Decimator, M=48 (48.0MHz to 1.0MHz)
Equivalent lowpass cutoff: 1.0MHz, transition Width: 100.0kHz

Number of stages: 5
Stage1: FIR Decimator, M = 2 (48.0MHz to 24.0MHz), FIR Length = 7                                                                    
Stage2: FIR Decimator, M = 2 (24.0MHz to 12.0MHz), FIR Length = 7                                                                    
Stage3: FIR Decimator, M = 3 (12.0MHz to 4.0MHz),  FIR Length = 21                                                                   
Stage4: FIR Decimator, M = 2 (4.0MHz to 2.0MHz),   FIR Length = 23                                                                   
Stage5: FIR Decimator, M = 2 (2.0MHz to 1.0MHz),   FIR Length = 95                                                                   

The estimated cost performs very well in many cases (as it does in this example).

cost(trueMinCostDecim)

hfv = fvtool(minCoeffDecim,trueMinCostDecim);
legend(hfv, 'Optimize for Estimated FIR Lengths', 'Optimize for True FIR Lengths')
ans = 

  struct with fields:

                  NumCoefficients: 87
                        NumStates: 146
    MultiplicationsPerInputSample: 6.5625
          AdditionsPerInputSample: 5.6667

The dsp.SampleRateConverter System Object

The dsp.SampleRateConverter system object provides a convenient interface for arbitrary rate conversion, combining interpolation and decimation as needed.

src = dsp.SampleRateConverter('InputSampleRate',18,'OutputSampleRate',16,'Bandwidth',13);
info(src)
ans =

    'Overall Interpolation Factor    : 8
     Overall Decimation Factor       : 9
     Number of Filters               : 1
     Multiplications per Input Sample: 24.333333
     Number of Coefficients          : 219
     Filters:                         
        Filter 1:
        dsp.FIRRateConverter - Interpolation Factor: 8
                             - Decimation Factor   : 9 
     '

The different stages can be extracted with the getFilters function:

firs = getFilters(src)
firs = 

  dsp.FilterCascade with properties:

    Stage1: [1x1 dsp.FIRRateConverter]

We can also specify absolute frequencies (rather than ratios). For example, the dsp.SampleRateConverter object can convert audio data sample rate from 48 kHz to 44.1 kHz.

src = dsp.SampleRateConverter('InputSampleRate',48000,'OutputSampleRate',44100);
[L,M] = getRateChangeFactors(src);

firs = getFilters(src);

reader = dsp.AudioFileReader('audio48kHz.wav','SamplesPerFrame',4*M);

x = reader();
xr = src(x);

% Obtain the rate conversion FIR
b = firs.Stage1.Numerator;

% Calculate the resampling delay
i0 = floor(length(b)/2)/L;

figure;
hold on;
stem((1:length(x))+i0,x);
stem(linspace(1,length(x),length(xr)),xr,'r');
hold off;
legend('Input Audio','Resampled Audio');
xlim([150,200])

release(reader);

Simplification by Rate Conversion Slack

Conversion ratios like $48k/44.1k$ (used in the previous section) requires a large upsample and downsample ratios, as even its reduced form is $L/M=160/147$. The filters required for such a conversion are fairly long, introducing a significant latency in addition to the memory and computational load.

cost(src)
ans = 

  struct with fields:

                  NumCoefficients: 8587
                        NumStates: 58
    MultiplicationsPerInputSample: 53.6688
          AdditionsPerInputSample: 52.7500

We can mitigate the costly conversion by approximating the rate conversion factor. For example,

$$48kHz/44.1kHz \approx 48kHz/44kHz = 12/11.$$

The deviation of 100Hz is small, only 0.23 % of the absolute frequencies. The dsp.SampleRateConverter can automatically approximate the rate conversion factor by allowing the output frequency to be perturbed. The perturbation tolerance is specified through the 'OutputRateTolerance' property. The default tolerance is 0, meaning, no slack. In other words, slack means the deviation from the specified output rate value. Clearly, the approximated rate conversion has much smaller computational cost, and suffices for many applications, such as standard definition audio processing.

src_approx = dsp.SampleRateConverter('InputSampleRate',48000,...
            'OutputSampleRate',44100,'Bandwidth',13,...
            'OutputRateTolerance',0.01);
[L_approx,M_approx] = getRateChangeFactors(src_approx)

cost(src_approx)
L_approx =

    11


M_approx =

    12


ans = 

  struct with fields:

                  NumCoefficients: 61
                        NumStates: 5
    MultiplicationsPerInputSample: 5.0833
          AdditionsPerInputSample: 4.1667

References

[1] Oppenheim, A.V., and R.W. Schafer, Discrete-Time Signal Processing, Prentice-Hall, 1989.