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

The maximum gate delay for any output to appear in an array multiplier for multiplying two $n$ bit numbers is

  1. $O(n^2)$
  2. $O(n)$
  3. $O(\log n)$
  4. $O(1)$
asked in Digital Logic by Veteran (59.5k points) | 1.8k views
+1
this que is belong to which topic??
0
Combinational Logic

2 Answers

+12 votes
Best answer

In an $N \times M$ array multiplier we have $N \times M$ AND gates and $(M-1),$ $N-bit$ adders are used.  



Total delay in $N \times M (N\geq M)$ array multiplier due to AND gate in partial products at all level is just $1$ unit AND gate delay as the operation is done parallel wise at each step. Now delays at level $1$ to $(M-1) = (M-1) \times $ delay due to $1$ unit of $N-bit$ adder.  Therefore the maximum gate delay is $O(M)$ but here $M=N \therefore O(N).$

http://www.dauniv.ac.in/downloads/CArch_PPTs/CompArchCh03L06ArrayMult.pdf

Refer this article page 16.

answered by Loyal (7.4k points)
edited by
0
Not able to understand the solution :(
Any simple way ?
0
someone explain?
0
what about carry propagating from one adder to next adder

according to this it will take O(n) in one level of computation??
0
Answer is right but need better explanation for this question
0

this may help, in last 10 mins of the video, time complexity is explained!

 

+3 votes
maximum Gate delay should be O(2n-1) = O(n)
answered by Veteran (55.1k points)
0
I think O(n2) 2n gate delay at each n-1 bit parallel adder level There'll be n-1 such levels Extra 1 and gate level So total 2n*(n-1) +1
0
@Digvijay

can you please elaborate the explanation ?
0
2n-1 ?? how ??
+1


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

38,174 questions
45,676 answers
132,605 comments
49,560 users