11,434 views
29 votes
29 votes

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)$

3 Answers

Best answer
27 votes
27 votes

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 or archive

Refer this article page 16.

Correct Answer: $B$

edited by
4 votes
4 votes
maximum Gate delay should be O(2n-1) = O(n)
1 votes
1 votes

Answer is (b) $O(n)$.

In $1\ unit$ we can find all the the partial products (if we assume we have enough space to store the partial products).

Then for subsequent n-1 additions we will have n-1 unit 

so total is O(1+n-1) = O(n)

Answer:

Related questions

48 votes
48 votes
4 answers
1
Kathleen asked Sep 16, 2014
15,054 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$\Theta(1)$$\Theta(\lo...
29 votes
29 votes
4 answers
2
Kathleen asked Sep 23, 2014
13,175 views
Booth's coding in $8$ bits for the decimal number $-57$ is:$0-100+1000$$0-100+100-1$$0-1+100-10+1$$00-10+100-1$
41 votes
41 votes
6 answers
3
Kathleen asked Sep 23, 2014
22,178 views
The number of full and half-adders required to add $16$-bit numbers is$8$ half-adders, $8$ full-adders$1$ half-adder, $15$ full-adders$16$ half-adders, $0$ full-adders$4$...
37 votes
37 votes
5 answers
4
Kathleen asked Sep 23, 2014
14,994 views
Which of the following sets of component(s) is/are sufficient to implement any arbitrary Boolean function?XOR gates, NOT gates$2$ to $1$ multiplexersAND gates, XOR gatesT...