The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 votes

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

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

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.4k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,871 questions

47,532 answers

146,046 comments

62,298 users