GATE CS 2012 Q19 — Combinational Circuits

To implement a combinational circuit using a Read-Only Memory (ROM), the inputs of the circuit act as the address lines of the ROM, and the outputs of the circuit correspond to the data bits stored at each address.

Step 1: Determine the number of address lines (inputs)

• A $4\text{-bit}$ multiplier multiplies two $4\text{-bit}$ numbers, say $A$ and $B$.
• Total number of input bits = $4 \text{ bits (for } A) + 4 \text{ bits (for } B) = 8 \text{ bits}$.
• Therefore, the ROM requires $8$ address lines, which gives $2^8 = 256$ addressable locations (words).

Step 2: Determine the word size (outputs)

• The output of the multiplier is the product of two $4\text{-bit}$ numbers.
• The maximum value of a $4\text{-bit}$ unsigned integer is $15$ ($1111_2$).
• The maximum possible product is $15 \times 15 = 225$.
• To represent $225$ in binary, we need $\lceil \log_2(225 + 1) \rceil = 8$ bits (or generally, the product of two $n\text{-bit}$ numbers requires at most $2n$ bits, so $2 \times 4 = 8$ bits).
• Thus, each word in the ROM must be $8$ bits wide.

Step 3: Calculate the total ROM capacity

Since $1\text{ Kbit} = 1024\text{ bits}$:

Hence, the correct option is D.