GATE CS 1996 Q1.21 — Combinational Circuits

To find the required ROM size, we need to determine the number of address lines (inputs) and the word size (outputs) of the ROM.

1. Number of Address Lines (Inputs):

   The ROM takes two $8$-bit unsigned integers as inputs to perform multiplication. Therefore, the total number of input bits is:

   $$\text{Total input bits} = 8 \text{ bits} + 8 \text{ bits} = 16 \text{ bits}$$

   With $16$ address lines, the number of addressable locations (words) in the ROM is:

   $$2^{16} = 65,536 = 64\text{ K words}$$
2. Word Size (Output Bits):

   The ROM stores the product of two $8$-bit unsigned integers. The maximum possible value of an $8$-bit unsigned integer is $2^8 - 1 = 255$.

   The maximum product is:

   $$255 \times 255 = 65,025$$

   To represent this maximum product, the number of bits required is:

   $$\lceil \log_2(65,025) \rceil = 16 \text{ bits}$$

   (Alternatively, multiplying an $n$-bit number by an $m$-bit number yields a product of at most $n + m$ bits. Here, $8 + 8 = 16$ bits.)

Thus, the required ROM size is $64\text{ K} \times 16$.