+17 votes
2.4k 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 | 2.4k views
+1
this que is belong to which topic??
0
Combinational Logic

## 2 Answers

+16 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.

Correct Answer: $B$

answered by Loyal (7.5k points)
edited ago
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!

+1
0
great explanation riya mam
+3 votes
maximum Gate delay should be O(2n-1) = O(n)
answered by Veteran (59.8k points)
–1
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
Answer:

+17 votes
4 answers
1
+27 votes
4 answers
2
+22 votes
2 answers
3
+21 votes
4 answers
4
+13 votes
3 answers
5
+25 votes
6 answers
6
+15 votes
2 answers
7