search
Log In
35 votes
6.6k 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)$
in Digital Logic 6.6k views

4 Answers

48 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, Total Delay $=\Theta(n).$

Correct Answer: $C$


edited by
4

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

2
As per the figure, all AND gates can perform their task independently, making all ANDing operation O(1). Only Only adders will face delay of O(n) as last adder will wait for all the above adder to add.
0

for multiply NxN number we will need N-1 , N-bit adders.

one adder has delay of 2n-1 then n-1 will have delay of : (n-1)*(2n-1)=O(n2)

Please solve my doubt...

0

Dharmendra Lodhi

How r u saying that 1 Adder has a delay of 2n-1??

0

@akash.dinkar12

What is the delay per Adder

If it is Ripple carry Adder 

If it is lookahead Adder

23 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)
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
11 votes
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).

edited by
1
How number of gates are 2n-1,I am getting n^2 Gates
Answer:

Related questions

23 votes
2 answers
1
4.3k views
The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is $O(n^2)$ $O(n)$ $O(\log n)$ $O(1)$
asked Sep 23, 2014 in Digital Logic Kathleen 4.3k views
31 votes
5 answers
2
7.2k views
Consider the ALU shown below. If the operands are in $2’s$ complement representation, which of the following operations can be performed by suitably setting the control lines $K$ and $C_0$ only (+ and – denote addition and subtraction respectively)? $A + B$, and $A – B$, but not $A + 1$ $A + B$, and $A + 1$, but not $A – B$ $A + B$, but not $A – B$ or $A + 1$ $A + B$, and $A – B$, and $A + 1$
asked Sep 17, 2014 in Digital Logic Kathleen 7.2k views
36 votes
6 answers
3
6.4k views
The literal count of a Boolean expression is the sum of the number of times each literal appears in the expression. For example, the literal count of $\left(xy+xz'\right)$ is $4.$ What are the minimum possible literal counts of the product-of-sum and sum-of-product representations respectively of the ... following Karnaugh map? Here, $X$ denotes "don't care" $(11, 9)$ $(9, 13)$ $(9, 10)$ $(11,11)$
asked Sep 17, 2014 in Digital Logic Kathleen 6.4k views
36 votes
4 answers
4
5.2k views
A $\text{1-input}$, $\text{2-output}$ synchronous sequential circuit behaves as follows: Let $z_k, n_k$ denote the number of $0'$s and $1's$ respectively in initial k bits of the input $(z_k+n_k=k)$. The circuit outputs $00$ until one of the following conditions holds ... is $01$. What is the minimum number of states required in the state transition graph of the above circuit? $5$ $6$ $7$ $8$
asked Sep 17, 2014 in Digital Logic Kathleen 5.2k views
...