Saturday, October 13, 2007

Pre-scaled Counters

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.

No comments: