What is the minimum size of ROM required to store the complete truth table of an 8 x 8 multiplier? A. 32K x 16 bits B. 64K x 16 bits C. 16K x 32 bits D. 64K x 32 bits

GATE 2004 · Digital Logic · ROM · medium

Answer: Minimum ROM size = 64K x 16 bits. Answer: B.

1. Compute ROM depth: Two 8-bit operands -> 16-bit address -> 2^16 = 65536 = 64K words.
2. Determine minimum word width: Maximum product = 255 x 255 = 65025. ceil(log_2(65026)) = 16 bits. So minimum width = 16 bits.
3. Select minimum size option: Minimum ROM size = 64K x 16 bits. This matches option B. Option A (32K x 16) is too small (only 15-bit address). Option D (64K x 32) is larger than necessary.