## Pre-scaled Counters

October 8, 2007

It is obvious that as a normal binary counter increases in width its maximum operation frequency drops. The critical path going through the carry chain up to the last half-adder element is purely combinational and increases with size. But what if our target frequency is fixed (as is usually the case) and we need to build a very wide counter? Here come to the rescue a variant of the normal binary counter – the pre-scaled counter.

Pre-scaled counters are based on the observation (or fact) that in the binary counting sequence, the LSB will toggle in the highest frequency (half that of the clock when working with the rising edge only). The next bit in line will toggle in half that frequency, the next with half of the previous and so on.
In general, the n-th bit will toggle with frequency 2^(n+1) lower than the clock (we assume that bit 0 is the LSB here). A short look at the figure below will convince you.

We can use this to our advantage by “partitioning” the counter we wish to build. In essence we make the target clock frequency of operation independent of the counter size! This means that given that our clock frequency enables us to have a single flop toggling plus minimal levels of logic, one could in theory build am extremely wide counter.

If you really insist, the above statement is not 100% correct (for reasons of clock distribution and skew, carry collect logic of a high number of partition stages, etc.) , but for all practical reasons it is true and useful. Just don’t try to build a counter with googolplex bits.

The basic technique for a 2-partition is shown below. We have an LSB counter which operates at clock frequency. Its width is set so it could still operate with the desired clock frequency. Once this counter rolls over an enable signal is generated for the MSB counter to make a single increment. Notice how we also keep the entire MSB counter clock gated since we know it cannot change its state.

The distance between the filtered clock edges (marked as “X”) of the MSB counter is determined by the width of the LSB counter. This should be constrained as a multi-cycle path with period X when doing synthesis.

The technique could be extended to a higher amount of “partitions” but then we must remember that the enable for each higher order counter is derived from all enable signals of all previous stages.

An interesting variant is trying to generate and up/down counter which is width independent. It is not so complicated and if you have an idea on how to implement it, just comment.

1. It is a very well know strategy for high duration timers like the one used for the Ethernet MAC’s exponential Random Backoff and its very nice that you have explained it in a very detailed way.

May be you could add some light on the power savings and estimation when using this for low power applications, since the percentage of the idle flops is significant in high width counters if we use this equation, (2^n – 2)/(n2^n) where n is the # of bits.

BTW, i really “liked” the puzzles you have posted.

2. Really good stuff…keep it up!!!

3. You draw truly awesome diagrams. What tool do you use to create these?

Thanks,

Hitesh

4. Hitesh,

I use the most simple tool – visio. I tried using in the past Inkscape which generates svg files (scaled vector graphics) but didn’t like it.
I tend to think that most of my work should be concentrated on the drawings rather than the RTL – the drawings is where 90% the thought is put into.

Nir

5. […] example, try thinking of pre-scaling wide increment logic or pre-decode deep logical clouds with information that might be available a cycle before. This […]

6. I wonder if clock gating is really required(unless the intention is to save power) and hence corresponding multicycle path specification in synthesis. Lets say we have 4 bit lsb counter and 4 bit msb counter. Then enable is generated from the anding of Q3,Q2,Q1,Q0.i.e enable is one only when LSB counter is 1111(which I beileve was the original idea posted here). Since enable is generated from Qs there is no question of timing meeting here. This way an infinite width counter can be generated with subsequent stages of counters. Is there something I am missing here ?