2
$\begingroup$

Recently I was reading "Optimum FIR Digital Filter Implementations for Decimation, Interpolation, and Narrow-Band Filtering) by Crochiere and Rabiner (1975). To estimate the number of decimation Stages and factors, they are targeting to optimize the total number of multiplies and adds (per second) calling this number $R_T$. With $R_T$ being sum of multiplies and adds of each stage:

$R_T = \sum_i^K R_i$.

When playing around with Matlab, I found the Matlab function designMultistageDecimator, in one example they compare a multistage approach with a single filter by calculating the cost (with the function cost ), here however, it is multiplication and addition per input sample.

I would have assumed that the cost behaves in the manner, that it is the total sum of all cost per stage.

For the single filter, which will be then compared to a cascade, I understand the result, having 753 coefficients and a decimation factor of 48, that roughly there are 16 mults and 16 adds per input sample.

But when it comes to the filter cascade, in the example given by Matlab

  • Stage one has 17 coefficients (13 non zero) and a decimation factor of 3
  • Stage two has 11 coefficients (7 non zero) and a decimation factor of 2
  • Stage three has 15 coefficients (9 non zero) and a decimation factor of 2
  • Stage four has 63 coefficients (49 non zero) and a decimation factor of 4

The estimated multiplications are ~7.2 and additions ~6.6 per input sample.

This confuses me, I would have assumed that is roughly ~25 multiplication and ~25 additions. Just taking the last stage having more or less 50 non zero elements and a decimation factor of 4 would add at least 12.5 operations, or not?

So my questions are,

  • How are the costs, in the sense of multiplies and adds computed for a cascaded design in matlab using the function cost? (Thanks @TimWescott)

  • Why is it not the sum of multiplication and add per stage? A sample at the output has to see at least on o the polyphaser trees of the last stage having at least 12 coefficients or not?

Follow up question:

  • After the answer by @TimWescott, I understand now the math behind the result of the cost funciton. However, I am asking myself how to interpret the output of the cost function? Is on sample, given this example, really only seeing ~7 multiplications / ~7 additions?
  • In therms of dsp-terminolgy what would the calculation of operations int the following way:

13/3 + 7/2 +9/2 +49/4 = ~25

represent?

$\endgroup$
4
$\begingroup$

Their numbers work out right if you do the stated decimation before the stage, and you pay attention to the fact that decimations are cumulative.

So stage one operates at 1/3 of the input rate, stage two operates at 1/6, stage three operates at 1/12, and stage four operates at 1/48. If you scale the adds and multiplies by those numbers, then their stated numbers work.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer, now that you pointed it out I can see how Matlab calculates the multiplication and additions. However, is it the right way to do it? If I would take a input sample and follow it all the way to the output of the cascade, will it really only see ~7 additions and multiplications? I don't understand the rational in calculating the cost per input sample in this way and if it represents the real world behavior. $\endgroup$ – Irreducible Jan 11 at 17:55
  • $\begingroup$ You only care about operations per OUTPUT sample. $\endgroup$ – Hilmar Jan 12 at 1:06
  • $\begingroup$ Or average operations per input sample. Ultimately, there's a 48:1 decimation. So most of the input samples wouldn't make it to the output. $\endgroup$ – TimWescott Jan 12 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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