GATE CS 2012 Q.19 (CS Q.19): Combinational Circuits

The amount of ROM needed to implement a 4 bit multiplier is

64 bits

128 bits

1 Kbits

2 Kbits

Official answer and solution

Solution

Determine the required address lines and word size of a Read-Only Memory (ROM) used as a lookup table for a 4-bit binary multiplier.

A 4-bit multiplier takes two 4-bit unsigned binary numbers as inputs, say $A = a_3 a_2 a_1 a_0$ and $B = b_3 b_2 b_1 b_0$ .
Total number of input bits to the multiplier is $4 + 4 = 8$ bits. When implemented using a ROM lookup table, these 8 bits serve as address lines.
The number of addressable locations (words) in the ROM is:

\text{Number of words} = 2^8 = 256

15 \times 15 = 225

Since $225 < 256 = 2^8$ , the product requires at most 8 output bits (data lines) to represent any possible result.

\text{Capacity} = (\text{Number of words}) \times (\text{Word width}) = 256 \times 8 \text{ bits} = 2048 \text{ bits} = 2 \text{ Kbits}

Thus, 2 Kbits of ROM are needed.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.