2
$\begingroup$

I am trying to implement a CIC filter and was reading through the literature and found that CIC filter cannot be implemented using floating point. I am unable to understand why that would happen. The reasoning that is given everywhere seems to be that the integrators are not stable when using floating point but I am not able to understand why that would be. Can someone explain how that would happen?

I also found that using polyphase decomposition would allow for floating point implementation but I am not sure how that would happen since the transfer function is still the same. I am not able to find a satisfactory explanation for this. Is this the only way to do floating point implementation?

Also I read that CIC filter is good if the decimation factor is high, but I am looking for a decimation factor of about 5 to 20. Why wont using a CIC filter be a good approach in this case.

$\endgroup$
7
  • $\begingroup$ See this dsprelated.com/showthread/comp.dsp/364544-1.php I think the author posts on this stack exchange group. $\endgroup$
    – Ben
    May 5 at 12:24
  • $\begingroup$ For problems about floating-point arithmetics see stackoverflow.com/questions/10371857/…. $\endgroup$
    – Ben
    May 5 at 12:25
  • $\begingroup$ Can you post a reference to a source that actually states floating point cannot be used and that describes its assumption behind that statement? $\endgroup$
    – Hilmar
    May 5 at 12:33
  • $\begingroup$ I don't think that floating-point numbers cannot be used, but I think that the comb filter stage must be placed first and the integrator stage last. And I think you need to validate the behavior of the implementation with a long sequence of numbers to make sure you don't get stuck with residuals in your integrator. $\endgroup$
    – Ben
    May 5 at 12:35
  • $\begingroup$ @Hilmar I've seen a recursive floating-point moving-average filter implementation with a soft reset in the integrator. $\endgroup$
    – Ben
    May 5 at 12:40
2
$\begingroup$

Heh. I've just worked this out, and I think you can implement a CIC using floating point -- but it wouldn't be perfect, and in most processing environments it would be a waste of resources.

The basic CIC stage is an integrator implemented modulo a maximum number -- in an integer implementation, this would be $x_{max} = 2^n$ where $n$ is the word length, in a non-integer fixed-point implementation it would be the maximum span of values that the data type could hold.

$$x_k = \left(x_{k-1} + u_k \right) \mod x_{max} \\ y_k = \left(x_k - x_{k - N} \right) \mod x_{max}$$

where "$y = x \mod x_{max}$" maps $x$ onto the interval $y \in \left[ -\frac{x_{max}}{2}, \frac{x_{max}}{2} \right )$.

You choose $x_{max}$ so that over $N$ samples, there's no chance that the value of $x_k$ can roll over more than once.

The thing that makes the CIC less than practical in a floating point environment is that you have to do the modulo operation explicitly, either by actually doing a floating point modulo, or by detecting that $x_k$ or $y_k$ is outside of $\left[ -\frac{x_{max}}{2}, \frac{x_{max}}{2} \right )$ and adjusting them by adding or subtracting $x_{max}$.

The thing that makes the CIC less than exact in a floating point operation is that floating point arithmetic truncates more or less depending on the exponent.

The reason that the CIC is so attractive for fast, computationally efficient DSP is because with fixed point (integer or not) math, is because with typical adder hardware and 2's part arithmetic, the modulo operation comes for free -- it's just the fixed-word-width overflow that's usually the bane of fixed-point arithmetic. So you pay nothing -- in a sense, less than nothing* -- for the modulo.

The reason that CIC is exact is because if all the arguments are fixed point with the same radix (i.e., integers), then all of the operations are bit-exact. This can't be said for floating point.

So -- in a floating point environment you can implement a CIC filter. But, you'll be larding on so much extra computational resources to do the two modulo operations, that you may as well do something else, like half-band filters. The only place where it would make sense to use a CIC in floating point, in my opinion, would be if you're working on a test bench and you want to simulate a system that you're going to implement later.

* because you don't have to worry about detecting it, or preventing it.

$\endgroup$
4
  • $\begingroup$ Please correct me if I am wrong. So the main obstacle seems to be what happens in case the registers overflow. However, if I designed the filter (or controlled the input) in such a way that it would not near impossible for the values to reach the maximum, would that effectively be a solution? I read somewhere that another reason is that the poles do not exactly fall on the unit circle when using floating point which makes the integrators unstable. Is that wrong? $\endgroup$
    – arun_kol
    May 5 at 21:47
  • $\begingroup$ I thought about this a little bit more and I think I am wrong. Its not possible to limit your input signal in such a manner. If you have DC, then your integrator sums will keep adding till you reach maximum and have to do the modulo operation. Am I correct in my understanding? $\endgroup$
    – arun_kol
    May 5 at 21:52
  • $\begingroup$ If you scale the gains so that the integrators don't overflow, then you lose precision. If you make the integrators wider (i.e. quad precision), then you add cost. If the scaling is such that at maximum input the integrators traverse most of their range, overflowing nearly all the time, then you minimize the effects of quantization. $\endgroup$
    – TimWescott
    May 6 at 2:46
  • $\begingroup$ Rather than thinking that "the poles don't fall exactly on the unit circle", think that the system is nonlinear in a way that -- if you're being utterly strict about it -- renders the concept of poles nonsensical. However, a more sensible way of thinking about it is that the poles crawl around in an uncontrolled and inconvenient manner. So a system that's designed to have poles on the unit circle will sometimes act like it has poles that are a bit inside, and sometimes act like it has poles that are a bit outside the unit circle. $\endgroup$
    – TimWescott
    May 6 at 2:51
1
$\begingroup$

See this post from Robert Bristow-Johnson, I think he posts on this stack exchange group by the way.

https://www.dsprelated.com/showthread/comp.dsp/364544-1.php

This post is about moving-average filters, but a CIC filter is basically a RMA filter with decimation or interpolation.

For more info on the problems with floating-point arithmetics

https://stackoverflow.com/questions/10371857/is-floating-point-addition-and-multiplication-associative

You can probably mitigate the issue by putting the comb filter stage on the first stage and the integrator at the second the stage so your integrator will never saturate when you apply a DC value. However, you might still end up with some residual value in your integrator that you can't get rid of.

For your second question, CIC filters don't have a flat pass-band so they are generally used in conjunction with another low-pass FIR filter to get a flatter passband.

Instead of using CIC filters, have you considered using halfband filters for decimation ? They're efficient and have a flatter passband than CIC filters. https://en.wikipedia.org/wiki/Half-band_filter

$\endgroup$
1
  • $\begingroup$ Thanks. That article helped a lot. The answer seems to be that there will be residuals that will cause the filters to behave not accurately because of the inherent randomness of floating point. Is there an upper limit on the residual amounts? Also when using polyphase decomposition, does this problem not affect the filter? $\endgroup$
    – arun_kol
    May 5 at 21:56
0
$\begingroup$

I believe the reasons floating point cannot be used directly in the exact same form is in how a CIC handles roll-overs in addition to creating a quantization error that will vary with the internal level of the CIC accumulator: the CIC essentially subtracts an integrated result (accumulator output) from the same result N samples ago (where N is typically the decimation rate but needn’t be). With fixed point arithmetic the result of the subtraction is the same even after the inevitable overflow of the accumulator - this is not the case with floating point so the accumulator would require additional reset features to prevent overflow or underflow.

The Cascade Comb-Integrator in simplest form is an accumulator (Integrator) followed by a difference of the accumulated output over N-samples (Comb) and for fixed point is equivalent to an N sample moving average, and (for fixed point only) the order of operations can be interchanged (between accumulator and comb):

CIC Implementations

The bottom implementation where the differencing occurs first followed by an accumulator cannot be implemented in floating point since a random walk error would be introduced in the accumulator, however the implementation with the accumulator first (as used in CIC decimators) would have no such issue other than requiring a reset of the accumulator in proximity of overflow/underflow condition.

CIC result

What will occur in floating point is a quantization error that is proportional to the level in the accumulator, such that the accumulator can float up to such a large number that a given difference that would be measured with very high precision for a lower accumulator output value would be of much lower precision when the exponent is higher and even ultimately completely truncated. For example consider a single-precision floating point implementation if the difference was 12.7 but the accumulator has grown to $2 \times 10^{16}$; in this case the difference would be truncated to 12, and once it has grown to $2 \times 10^{17}$ the same difference would be zero.

$\endgroup$
18
  • $\begingroup$ the real problem is, with floating-point, what you add to the accumulator in the current sample might not be exactly what is subtracted from the accumulator $N$ samples later. or, put a slightly different way, the value that is getting subtracted in the current sample is not exactly what was added $N$ samples prior. $\endgroup$ May 5 at 15:40
  • $\begingroup$ You delay the same accumulator output N samples and subtract, so for the CIC i don’t yet see why that would matter even if you introduce a floating point error since you are always monitoring the difference over time (as long as you don’t let the accumulator overflow). The difference of the two outputs is the same (within the floating point precision * N samples) as the sum of those N samples which is what a moving average is $\endgroup$ May 5 at 15:46
  • $\begingroup$ there is one accumulator. there are the samples that are delayed. $\endgroup$ May 5 at 15:47
  • $\begingroup$ I do see how an error is introduced, and that error scales with the signal level for any given sample but this isn’t an instability issue or reason it won’t work as the OP assumes $\endgroup$ May 5 at 15:48
  • $\begingroup$ CIC: accumulate (integrator), then take that output and subtract it from the output of that same accumulator N samples ago (comb) $\endgroup$ May 5 at 15:49

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.