Solution Found!

The grade-school algorithm for multiplying two n-bit binary numbers x and y consists of

Chapter 1, Problem 1.30

(choose chapter or problem)

Get Unlimited Answers
QUESTION:

The grade-school algorithm for multiplying two n-bit binary numbers x and y consists of adding together n copies of x, each appropriately left-shifted. Each copy, when shifted, is at most 2n bits long. In this problem, we will examine a scheme for adding n binary numbers, each m bits long, using a circuit or a parallel architecture. The main parameter of interest in this question is therefore the depth of the circuit or the longest path from the input to the output of the circuit. This determines the total time taken for computing the function. To add two m-bit binary numbers naively, we must wait for the carry bit from position   before we can figure out the  bit of the answer. This leads to a circuit of depth   . However carry lookaheads circuits (see wikipedia.com if you want to know more about this) can add in  depth.

(a) Assuming you have carry look ahead circuits for addition, show how to add n numbers each m bits long using a circuit of depth .

(b) When adding three m-bit binary numbers  There is a trick we can use to parallelize the process. Instead of carrying out the addition completely, we can re-express the result as the sum of just two binary numbers  , such that   the bits of r and s can be computed independently of the other bits. Show how this can be done. (Hint: One of the numbers represents carry bits.)

(c) Show how to use the trick from the previous part to design a circuit of depth  for multiplying two n-bit numbers.

Questions & Answers

QUESTION:

The grade-school algorithm for multiplying two n-bit binary numbers x and y consists of adding together n copies of x, each appropriately left-shifted. Each copy, when shifted, is at most 2n bits long. In this problem, we will examine a scheme for adding n binary numbers, each m bits long, using a circuit or a parallel architecture. The main parameter of interest in this question is therefore the depth of the circuit or the longest path from the input to the output of the circuit. This determines the total time taken for computing the function. To add two m-bit binary numbers naively, we must wait for the carry bit from position   before we can figure out the  bit of the answer. This leads to a circuit of depth   . However carry lookaheads circuits (see wikipedia.com if you want to know more about this) can add in  depth.

(a) Assuming you have carry look ahead circuits for addition, show how to add n numbers each m bits long using a circuit of depth .

(b) When adding three m-bit binary numbers  There is a trick we can use to parallelize the process. Instead of carrying out the addition completely, we can re-express the result as the sum of just two binary numbers  , such that   the bits of r and s can be computed independently of the other bits. Show how this can be done. (Hint: One of the numbers represents carry bits.)

(c) Show how to use the trick from the previous part to design a circuit of depth  for multiplying two n-bit numbers.

ANSWER:

Step 1 of 3

a) Consider  where k is some fixed value. It is considered for a minimalism and steps for adding n numbers as follows:

         1. Firstly split the  number into  different pairs.

         2. Values of each pair should be added for this lockheed circuits should be used.

         3. Complete Binary tree produced with log n levels and a tree is not completed when n was not a power of 2.

         4. Perform addition operation so each level uses log m extra levels.

      Hence, The depth  by this operation is equal to .

 

Add to cart


Study Tools You Might Need

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

Forgot password?
Register Now

×

Register

Sign up for access to all content on our site!

Or login if you already have an account

×

Reset password

If you have an active account we’ll send you an e-mail for password recovery

Or login if you have your password back