The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 559
- Exam Queries 555
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,932 questions

52,335 answers

182,384 comments

67,817 users