CIC decimation bitwidth

hogenauer pruning

Hi all,

I need to implement a CIC decimator in an FPGA in fixed-point format. Everything works fine in floating point format in Matlab simulations. I am now translating the design from floating point to fixed point, and have to design the bit width of each integrator and differentiator. I know the bitwidth at output can be calculated by Bmax = N*ln2(RM) + (# of input bit), but how about bitwidth of the
integrators and differentiators in between? I saw many designs, they set integrators and differentiators to Bmax, seems like it is over design. Read some documents online but still can't fully understand the idea. Anyone has any idea?


Thanks,
Mesfet

cic decimation

Original Hogenauer article


Hogenauer assumed Bmax to be required at any stage

hogenauer pruning

Hogenauer assumed Bmax to be required at any stage

Click to expand...

No, he suggests a reduction of register width that follows a defined error criterion defined in equation (21). U.-Meyer-Baese has a chapter in his excellent DSP with FPGA titled Hogenauer Pruning Theory. He supplied a tool to calculate the bit reduction, also other CIC design tools are using Hogenauers algorithm, e. g. Alteras CIC MegaCore. The pruning can be basically calculated in VHDL code.

cic bit growth

Thanks guys. I did read Hogenauer's paper. My question is, he mentioned Bmax is the upper and also the low bound of bitwidth required for every single integrator and differentiator, without proof. This is found in the two paragraphs under equation 11. Modulo operation is mentioned, but don't get what he meant.


Mesfet

cic bit growth resolution rate

The modulo arithmetic is present at least at each integrator, that is allowed to overflow above Bmax bits (in case of 2^n decimation factor).

setting cic filter bitwidth in simulink

Hi FvM,

I guess your answer is the key to my doubt. Since I am new to DSP, I don't quite understand what "that is allowed to overflow above Bmax bits (in case of 2^n decimation factor)" means. Can you give me an example? or do you have any reference or books on explaining it?


Thanks,
Mesfet

bit width & cic decimator

I've been implementing a CIC filter two year ago, starting with Bmax register bitwidth, using a kind of linear bitwidth reduction later and then exact Hogenauer algorithm. I never considered the dataflow in detail, except implementing the scheme from Hogenauers original paper, which worked for me without any problem.

As said, U.Meyer-Baeses book gives a detailed description of CIC design. A scanned version is present at EDAboard, I think.

site:www.edaboard.com hogenauer

Thanks the prompt reply. I know setting all the integrator and differentiator to Bmax works fine, as proven in simulation. I am trying to figure out what is the reason behind. What trouble me is the fact that Bmax is the required bitwidth at output, but how come bitwidth of the stages in between are also Bmax. Shouldn't they be less than Bmax?


Mesfet

cic pruning

As an example, the bitwidths for a N=3, M=1, R=128, Bin=14,Bout=16 according to Hogenauers algorithm (calculated by U.Meyer-Baeses tool):

-- Stage 1 INTEGRATOR. Bit width : 35
-- Stage 2 INTEGRATOR. Bit width : 28
-- Stage 3 INTEGRATOR. Bit width : 22
-- Stage 1 COMB. Bit width : 20
-- Stage 2 COMB. Bit width : 19
-- Stage 3 COMB. Bit width : 18

An all-Bmax design would use 35 Bits for all register (+68 bits),
a simple linear reduction scheme would calculate 35, 32, 29, 26, 23, 20 (+23 bits)

cic decimator

mesfet said:

Thanks the prompt reply. I know setting all the integrator and differentiator to Bmax works fine, as proven in simulation. I am trying to figure out what is the reason behind. What trouble me is the fact that Bmax is the required bitwidth at output, but how come bitwidth of the stages in between are also Bmax. Shouldn't they be less than Bmax?


Mesfet

Click to expand...

Simple intuitive reason to overflow above Bmax bits is the same as that is used to use for number theoretic transforms (NTT). Obviously any integrator will overflow above Bmax sometimes (modulo arithmetic), but we don't need those higher bits at all...
We know "a priory" from the beginning that all those higher bits are zero (sign bit for 2's complement) in the final result!

While using integer calculations with overflow above Bmax bits (modulo arithmetic, no saturation) we have exactly accurate and stable result. (when using floating-point, result is not very stable). So original Hogenauer algorithm was the first very simple practical number theoretic algorithm.

cic decimation overflow

Hello,

as a premise I am not expert in FPGA design: I suggest you before implementing your design in VHDL to try a simulation in matlab/simulink applying the quantizer block to all data paths to set the word width according to your goal to verify the matching between fixed point and floating point simulations results.
This process could be iterated till you get a reasonable level of confidence that the fixed point implementation you are going to map on the FPGA produces results close to the (ideal) floating point simulation.


Regards
Mowgli

number bits cic decimator

Following fontp's remark, I think that differences between floating point simulation and fixed FPGA synthesis rather reveal a problem of floating point in this case. I didn't yet see a CIC Matlab model, but it should include a modulo operation with the integrator to my opinion. If Bmax is within the double precision mantissa length, the simulation could be expected to almost match the ideal fixed point operation then.

hogenauer model calculation

Thanks for all the valuable inputs.

Just finished the tapeout code and get a chance to check e-mail. In order ensure the design works, I set all integrators and differentiators to Bmax in this tapeout.

For my design, R=8, M=2, N=4, maximum bit growth = 16bits. Since, Bin = 10bits, I set the bitwidth of all integrators and differentiators to 26bits. But what if I do this

integrator_1 = 13bits (first stage)
integrator_2 = 16bits
integrator_3 = 19bits
integrator_4 = 22bits (last stage)

Since all integrator overflows, just a matter of time. Why can't the integrators be configured as above?

Thanks for your help
Mesfet

bitwidth growth & cic

When you want to have bit-exact acurate result, you should follow to original Hogenauer algorithm with Bmax at any stage. You should not try arbitrary bit distribution, you should follow Meyer-Baeses if you want design CIC-filter with controlled error level for signal with zero mean (zero DC)

Looks like that

bit width calculation

No it doesn't work that way. It sounds paradox, but the full bitwidth is required at first integrator stage. You didn' mention the intended output width, here are the bitwidths according to Hogenauer's pruning algorithm for outpu width of 14 and 16(may be meaningful values in your case.

-- Stage 1 INTEGRATOR. Bit width : 26
-- Stage 2 INTEGRATOR. Bit width : 25
-- Stage 3 INTEGRATOR. Bit width : 22
-- Stage 4 INTEGRATOR. Bit width : 20
-- Stage 1 COMB. Bit width : 19
-- Stage 2 COMB. Bit width : 18
-- Stage 3 COMB. Bit width : 17
-- Stage 4 COMB. Bit width : 16
Output width 14

-- Stage 1 INTEGRATOR. Bit width : 26
-- Stage 2 INTEGRATOR. Bit width : 26
-- Stage 3 INTEGRATOR. Bit width : 24
-- Stage 4 INTEGRATOR. Bit width : 22
-- Stage 1 COMB. Bit width : 21
-- Stage 2 COMB. Bit width : 20
-- Stage 3 COMB. Bit width : 19
-- Stage 4 COMB. Bit width : 18
Output width 16

overflow cic decimator

I read Hogenauer's paper and know every stage should be set to Bmax in order to get bit exact accurate result. This is what I have done on the tapeout.

But there are two things bugging me big time
1. The "paradox". Why bit_width_stage_1>=bit_width_stage_2>=bit_width_stage_3>=bit_width_stage_4. I cannot think of any intuitive reasons to understand this. I always think it should be bit_width_stage_4>=bit_width_stage_3>=bit_width_stage_2>=bit_width_stage_1, my reason is bitwidth of latter stages should be wider than former stages to provide dynamic range to hold the integration results. What's wrong with this reasoning?

2. The "intended" output bitwidth? I did notice the final output bitwidth is less than Bmax in other projects. How can we decide the intended output bitwidth? Is it arbitrary?

Sorry for all the questions. I guess what I am asking are very simple and fundamental. I am very new to CIC

Mesfet

cic filter bit growth

The output bitwidth mainly depends on your application. I assume that you are processing the decimated data with a defined bitwidth?

You are correct, that Bmax bitwidth at all stages assures bit accurate results. Usually the purpose of decimation isn't to achieve bit accuracy, cause the input data are real world measurements, carrying a considerable noise part. Usually, also bits are cut from Bmax on output. Since I'm using it (about 2 years), CIC has always been a means in practical measurement problems rather than an object of theoretical considerations , so these usual conditions applied.

Having data partly randomized by noise , Hogenauers pruning theory comes into play, calculating bitwidths that keep the error contribution of individual stages below a defined bound. It is valid for a given output bitwidth only. I represented the bitwidth resulting from this calculation above. As said, I used U.Meyer-Baeses tool for convenience. For my applications, I have a VHDL based calculation in my CIC core.

I think, the reason for the discussed paradox bidwith series with pruning can be seen from Hogenauers paper. My simplified explanation is, that the first integrator stages low bits are amplified by the succeeding integrators. This can be seen from simple number experiments, e. g. in a spreadsheet calculator. Also MatLab should be perfectly suited to evaluate the effects of bit reduction in individual stages.

As a remark, when having completely deterministic input data, e.g. a slowly varying DC voltage, the bitwidth reduction effects show partially different. I found, that using rounding on output and a small resolution overhead (e.g. 0.5) above Hogenauers pruning criterion achieves bit accurate results in deterministic cases though. The results are mainly from numerial ModelSim analysis.