Combinational Arithmetic Circuit : Sum of n k-bit numbers
Not what you're looking for?
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.
Purchase this Solution
Solution Summary
Solution explains in detail (with examples as needed) how the answers are arrived at, be it computing the maximum number of bits in the final sum, or finding the upper bounds on circuit depth and size.
Solution Preview
[a] When you add two numbers of k-bits each, it can result in a number that might require (k+1) bits to store. For example, when you add two 8-bits unsigned numbers, the maximum possible result of addition could be 510 that would require 9 bits to store it.
Given that n is an exact power of 2, so we can write "n = 2^M, where M >= 0".
Consider the following example of n k-bit numbers addition using given combinational circuit, with "n = 8".
M = lg(n) = lg(8) = 3, where lg means log_base_2.
numbers size = (k+3) bits
|
Height(h)=2 : addition of 1 pair (2 numbers)
|
numbers size = (k+2) bits
|
Height(h)=1: addition of 2 pairs (4 numbers)
|
numbers size = (k+1) bits
|
Height(h)=0: addition of 4 pairs (8 numbers)
|
numbers size = (k+0) bits
At leaf level (Height=0), we add (n/2) pairs (n numbers) and thus use (n/2) ripple carry adders (henceforth referred to as RCA) generating (n/2) (k+1)-bit numbers.
At next level (Height=1), we add (n/4) pairs (n/2 numbers generated from additions at lower level) and thus use (n/4) RCA generating (n/4) (k+2)-bit numbers.
And so on, till we add only 2 numbers at root level and generate single number indicating the result of summing initial n numbers.
We can easily notice that at each level of addition the size of numbers increases by 1 bit (to make provision for storing the largest possible number resulting from addition).
Total level of additions = M = lg(n)
Hence, maximum number of bits in the sum of the n k-bit numbers = ...
Purchase this Solution
Free BrainMass Quizzes
Word 2010: Tables
Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.
Basic Networking Questions
This quiz consists of some basic networking questions.
C# variables and classes
This quiz contains questions about C# classes and variables.
Javscript Basics
Quiz on basics of javascript programming language.