The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 837
- Others 1.2k
- Admissions 284
- Exam Queries 397
- Tier 1 Placement Questions 17
- Job Queries 51
- Projects 7

33,705 questions

40,253 answers

114,352 comments

38,862 users