The Gateway to Computer Science Excellence

+45 votes

Best answer

A ROM cannot be written. So, to implement a $4$-bit multiplier we must store all the possible combinations of $2^4 \times 2^4$ inputs and their corresponding $8$ output bits giving a total of $ 2^4 \times 2^4 \times 8$ bits $= 2048$ bits. So, (**D**) is the answer.

PS: We are not storing the input bits explicitly -- those are considered in order while accessing the output $8$ bits. In this way, by storing all the possible outputs in order we can avoid storing the input combinations.

0

Arjun Suresh sir- Can you tell the book where this topic is covered. It will be great if you can provide some link.

0

I guess Morris Mano book covers this. I don't have the book now to verify. This ppt also gives a very good detail:

http://www.cs.uiuc.edu/class/fa05/cs231/lectures/review(11-4).ppt

http://www.cs.uiuc.edu/class/fa05/cs231/lectures/review(11-4).ppt

0

@Arjun Suresh Sir, I have a doubt here... With 4 bits, 16 numbers (multiplicands) are possibe. Each of this number takes 4 bits in memory.. Similarly each multiplier will also take 4 bits then why dont we multiply the result u found with 4*4... 2^4 is just number of multiplicands.. It is not number of bits used to store those many multiplicands... Please clarify

+11 votes

Since we want to multiply 4bit two number .

Then number of combination of input for multiplication is=16*16

Number of output lines =8

Size of ROM=16*16*8=2048bits=2Kbits

Then number of combination of input for multiplication is=16*16

Number of output lines =8

Size of ROM=16*16*8=2048bits=2Kbits

+5 votes

ROM is Read-Only Memory. We can just read from it, not write to it. Hence, all the possible results need to be already stored in the ROM.

A 4-bit multiplier multiplies two 4-bit numbers.

There can be $2^{4}$ such numbers.

So, total possible multiplication pairs could be $2^{4} * 2^{4}=2^{8}$

The result would be max: $(1111)_{2}*(1111)_{2}$

$=> (15)_{10}*(15)_{10}$

$=> (225)_{10}$

And 225 requires 8 bits.

Hence, we potentially need 8 bits for the $2^{8}$ possible combinations.

$=> 2^{8} * 8 bits$

$=> 2^{11} bits$

So, **Option D**

We know that multiplying an $n$ bit number with and $m$ bit number results in a number which is of at most $(m+n)$ bits.

Hence, maximum result size: $8$ bits.

Total combinations: $2^8$

Memory required: $2^{11} bits$

PS: Addition of two $n$ bit numbers results in a max $n+1$ bit number

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,834 questions

57,838 answers

199,508 comments

108,335 users