Analyse combinational arithmetic circuits that compute the sum of n k-bit numbers.

The sum of n k-bit numbers can be computed by a combinational arithmetic circuit as follows.

Assume that n is an exact power of 2. The circuit consists of a complete binary tree of ripple-carry adders, in which each node in the tree adds two numbers and produces a sum which is fed to its parent. The n/2 leaves of the tree input the n k-bit numbers, and the total sum is produced as output by the root. Each ripple-carry adder is as small as possible while still ensuring that the sum is correctly computed.

[a] What is the maximum number of bits in the sum of the n k-bit numbers?
What is the number of full adders in any ripple-carry adder at height h in the tree, where we view leaves as having height 0?

[b] Give a tight asymptotic upper (big-Oh) bound in terms of n and k, on the size of this circuit (definition below). Briefly explain your answer.

[c] Give a tight asymptotic upper bound in terms of n and k on the depth of this circuit (definition below). Briefly explain your answer.

[d] Describe a combinational circuit that computes the sum of n k-bit numbers more efficiently. Analyze the size and depth of this circuit.


Circuit Depth :

As in the case of the comparison networks, we measure the propagation delay of a combinational circuit in terms of the largest number of combinational elements on any path from the inputs to the outputs. Specifically, we define the depth of a circuit, which corresponds to its worst-case "running time", inductively in terms of the depths of its constituent wires. The depth of an input wire is 0. If a combinational element has inputs x1, x2,..., xn at depths d1, d2,...,dn respectively, then it's outputs have depth (max{d1, d2,..., dn}+1).

The depth of a combinational element is the depth of its outputs. The depth of a combinational circuit is the maximum depth of any combinational element in it. Since we prohibit combinational circuits from containing cycles, the various notions of depth are well defined. If each combinational element takes constant time to compute its output values, then the worst-case propagation delay through a combinational circuit is proportional to its depth.

A combinational circuit can sometimes compute faster that its depth. Suppose that a large sub-circuit feeds into one input of a 2-input AND gate but that the other input of the AND gate has a value of 0. The output of the gate will then be 0, independent of the input being applied to the circuit, and the abstraction of depth as the "running time" of the circuit is therefore quite reasonable.


Circuit Size :

Besides circuit depth, there is another resource that we typically wish to minimize when designing circuits - the size of a combinational circuit, which is defined as the number of combinational elements it contains. Intuitively, circuit size corresponds to the memory space used by an algorithm.

This definition of circuit size is not particularly useful for small circuits. After all, since a full adder has a constant number of inputs and outputs and computes a well-defined function, it satisfies the definition of a combinational element. A full adder built from a single full adder combinational element therefore has size 1. In fact, according to this definition, any combinational element has size 1.

Attached file(s):

The SUM.doc  View File