edited by
15,890 views
43 votes
43 votes

The amount of ROM needed to implement a $4\text{-bit}$ multiplier is

  1. $64$ bits
  2. $128$ bits
  3. $1$ Kbits
  4. $2$ Kbits
edited by

3 Answers

Best answer
63 votes
63 votes

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.

edited by
17 votes
17 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


Edit: Alternatively,

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

edited by
14 votes
14 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
Answer:

Related questions

39 votes
39 votes
2 answers
1
33 votes
33 votes
2 answers
2
Kathleen asked Oct 9, 2014
18,549 views
A ROM is used to store the table for multiplication of two $8$-bit unsigned integers. The size of ROM required is$256 \times 16$$64 K \times 8$$4 K \times 16$$64 K \times...
23 votes
23 votes
2 answers
3
20 votes
20 votes
2 answers
4
Ishrat Jahan asked Nov 1, 2014
6,417 views
What is the minimum size of ROM required to store the complete truth table of an $8-bit \times 8-bit$ multiplier?$32 K \times 16$ bits$64 K \times 16$ bits$16 K \times 32...