The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
1.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 in Digital Logic by Veteran (69k points) | 1.4k views
this que is belong to which topic??

2 Answers

+11 votes
Best answer

In a N X M array multiplier we have N * M AND gates and (M-1), N bit adders used.  



Total delay in N X M (N>=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) is = (M-1)*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 Boss (7.5k points)
edited by
Not able to understand the solution :(
Any simple way ?
someone explain?
what about carry propagating from one adder to next adder

according to this it will take O(n) in one level of computation??
Answer is right but need better explanation for this question
+3 votes
maximum Gate delay should be O(2n-1) = O(n)
answered by Veteran (53.7k points)
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
@Digvijay

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


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

33,705 questions
40,253 answers
114,352 comments
38,862 users