GATE CSE 2003 | Question: 11

Question

Consider an array multiplier for multiplying two $n$ bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

• A. $\Theta(1)$
• B. $\Theta(\log n)$
• C. $\Theta(n)$
• D. $\Theta(n^2)$

Comments

Similar question: https://gateoverflow.in/1474/gate1999-1-21

---

5 min will be enough 

---

Thnx buddy !

Answer 1

 

Thus to MULTIPLY two $4-bit$ numbers the total delay is delay of three $4-bit$ adders plus one AND gate delay.

For $n-bits,$ total delay will be delay of $n-bit$ adders (assume ripple-carry as its difficult to do carry propagation beyond $4-bits$) plus one AND gate delay $=\left[2(n-1)+3\right] + 1 = 2(n+1)$    

So, Total Delay $=\Theta(n).$

Correct Answer: $C$

Comments

In the diagram they are using simple adder only (having carry propagated to next bit level sequentially). But then also the adder will take O(1) time instead of O(n) time can be explained by implementation below. We are not propagating carry to the same level rather we are propagating that carry to next level.Which helps us to implement the adder in O(1) by parallely generating the sum as (Ai xor Bi) and carry as (Ai and Bi) for ever i.

 

The implementation is using the fact that when we have to add the three bits and an outstanding carry the result is independent of when we add carry. Example we have to add 5,4 and 3 with carry as 1, then we can add first (5+4+carry)  and then add 3 or we can add first (5+4) and then add (9+3+carry) result would be same.

---

Cant all and gates works in parallel and the effective delay caused by them would be 1

---

Why is there  \(+3\) in \([2(n-1)+3]+1=2(n+1)\) in the best answer (I also made a comment here)?

Answer 2

Take A = A1 A2 A3 A4

        B=   B1 B2 B3 B4

NOW TO MULTIPLY THESE TWO NUMBER .  

1 AND GATE REQUIRE B1 MULTIPLY WITH A1 A2 A3 A4.

1 AND GATE REQUIRE B2 MULTIPLY WITH A1 A2 A3 A4.

1 AND GATE REQUIRE B3 MULTIPLY WITH A1 A2 A3 A4.

1 AND GATE REQUIRE B4 MULTIPLY WITH A1 A2 A3 A4.  

 NOW 3 OR GATE REQUIRE.

TOTAL 7 GATE REQUIRE FOR 4 BIT TAKE N BIT U FIND 2N-1.

SO TIME COMPLEXITY WILL BE = ϴ(n)

Comments

Diagramatic answer seems to helpful. But still dont know how to drive the equation "So the delay is approxiamtely sqrt(2)*(2n-1)."

http://stackoverflow.com/questions/27095216/time-complexity-in-n-bit-array-multiplication

---

how b1 multply with a1a2a3a4 take only 1 and .. it wil be 4 yes they can perform at same level

Answer 3

C. $\Theta(n)$
 

Ref: http://eee.guc.edu.eg/Courses/Electronics/ELCT706%20Microelectronics%20Lab/winter%202014/Multipliers.pdf

Comments

 if Td = Θ(1) , then the total delay of multiplexer is Θ(n) 
worst case delay would be (2n+1)td .where td is the time delay of gates. , is it correct ???

---

Can you give another link of array multiplier ? This link given is not working !

---

@arjun sir : another link for array multiplier please :(

Answer 4

Answer: C

The no. of gates used in a n bit array multiplier (n*n) is 2n-1.

So, if every single gate takes unit delay, then total delay O(2n-1) = O(n).

Comments

How number of gates are 2n-1,I am getting n^2 Gates

---

I think they mean GATE levels.