The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
2.8k 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 (59.4k points) | 2.8k views

4 Answers

+19 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 Loyal (8.7k points)
selected by
+1

@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.

0

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 (59.6k points)
+2

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

0
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 (342k points)
0

 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 ???

+1
Can you give another link of array multiplier ? This link given is not working !
0
@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 Boss (34.1k points)
edited by
+1
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

35,506 questions
42,827 answers
121,678 comments
42,181 users