A Synthesizing Method for Large Parallel Counters with a Network of Smaller Ones

Abstract

This correspondence introduces an extended method of parallel counting which enables small parallel counters to generate larger ones. It is an extension of the Method of Carry Showers by Foster and Stockton to a (u,v)-counter network. A (u,v) counter is a small parallel counter with u inputs and v outputs, u = 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">v</sup> − 1. It is shown that the counter delay is proportional to the log of the number N of inputs and the total number of elements is approximated by N/(u-v).