The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
2.5k views

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

  1. $\Theta(1)$
  2. $\Theta(\log n)$
  3. $\Theta(n)$
  4. $\Theta(n^2)$
asked in Digital Logic by Veteran (69k points) | 2.5k views

4 Answers

+17 votes
Best answer

 

NOW TO MULTIPLY THESE TWO NUMBERs:


1 ) 4 AND GATEs REQUIRED B0 MULTIPLY WITH A3 A2 A1 A0.

2 ) 4 AND GATEs REQUIRED B1 MULTIPLY WITH A3 A2 A1 A0.

 3) 4 BIT ADDER

4) 4 AND GATEs REQUIRED B2 MULTIPLY WITH A3 A2 A1 A0.

 5) 4 BIT ADDER

6) 4 AND GATEs REQUIRED B3 MULTIPLY WITH A3 A2 A1 A0.

 7) 4 BIT ADDER

 For 4 bits-->Total Delay= 3+4=7

For n bits--->Total Delay=n-1+n = 2n-1 

SO TIME COMPLEXITY WILL BE = ϴ(n)

answered by Boss (7.9k points)
selected by

@VS ji. Thanks for valuable effort. Just small addition if look ahead carry adder is used then 4-Unit of delay in each adder. But it will  not change answer because 4 is  a constant with respect to n.

16 AND gates are used, but in the calculation 4 are considered...is it because every time 4 AND gates will work simultaneously? (Like for multiplication of B0 with A3A2A1A0, the AND gates used work simultaneously and so the total delay is 1?)

+16 votes
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)
answered by Veteran (60.4k points)

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
+6 votes
answered by Veteran (346k points)

 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 :(
+4 votes
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).
answered by Veteran (36.4k points)
edited by
How number of gates are 2n-1,I am getting n^2 Gates


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
114,174 comments
38,662 users