GATE IT 2004 | Question: 10

Question

What is the minimum size of ROM required to store the complete truth table of an $8-bit \times 8-bit$ multiplier?

• A. $32 K \times 16$ bits
• B. $64 K \times 16$ bits
• C. $16 K \times 32$ bits
• D. $64 K \times 32$ bits

Comments

repeated question in GATE 2019 or i think gate 2020

---

One was from 1996. -https://gateoverflow.in/2725/gate1996-1-21

Answer 1

Answer - B.

Multiplying $2\ 8$ bit digits will give result in maximum $16$ bits

Total number of multiplications possible $= 2^8 \times 2^8$

Hence, space required $= 64K \times 16$ bits

Comments

My dear friend  @ijnuhb , i said minimum because even 64K x 32 bit ROM can also store the given information but it will not be the minimum size ROM to perform this job. So please don’t jump to your conclusions straight away.

---

Can we use multiplication commutative identity to reduce truth table size, as question is asking or miminimum table size? If we write out entire truth table, we know approximately half of the rows are duplicate because A*B = B*A

---

I think @commenter commenter meant that we should also be storing the 16 bit inputs, which would make the ROM size 64K x (8+8+16) bits, as the question does mention 'required to store the complete truth'
I had the same doubt.

But I have read that in ROM, to access it we use a decoder, and that 16 bits worth of input will be the input to the decoder, which will give us the corresponding result.
Therefore the inputs will not get stored in the ROM, only the possible results.

Answer 2

I think the answer should be 64K x 32 bits. Because we have an output for each of 2^8 x 2^8 combinations of inputs. But in question, they have asked to store the total truth table which includes inputs as well to tell which output corresponds to which input

Comments

Yeah exactly what I was thinking.