GATE CSE 1996 | Question: 1.21

Question

A ROM is used to store the table for multiplication of two $8$-bit unsigned integers. The size of ROM required is

• A. $256 \times 16$
• B. $64 K \times 8$
• C. $4 K \times 16$
• D. $64 K \times 16$

Comments

max no after multiplication will be of 16bits

and any no can be multiplied with any bit,

in total we have to multiply 256 * 256 no.s with each taking 16 bits.

thus, total size will be of 2^8 * 2* 8 * 16 bits.

 

similarly if the question were for addition,

there will be  256 * 256 rows with each 9 bit.

Answer 1

When we multiply two $8$ bit numbers result can go up to $16$ bits. So, we need $16$ bits for each of the multiplication result. Number of results possible $= 2^8 \times 2^8 = 2^{16} = 64 \ K$ as we need to store all possible results of multiplying two $8$ bit numbers. So, $64 \ K \times 16 $is the answer.

Correct Answer: $D$

Comments

@arjun sir

Had it been signed integers then we would have required $64 \ K \times 17$. Right?

---

How? I am getting 15 bit bcz the range is decreased. The maximum negative no is -2^7 * 2^7 = -2^14. so 14 bits no and 1 extra bit for sign bit. I am using signed magnitude representation.

---

@reboot

Both the product of two unsigned or signed numbers of n bits will take at max 2n bits.

Correct me if I am wrong

Answer 2

• Two 8-bit unsigned integers can each have $2^8 = 256$ possible values.
• The total number of possible input combinations is $256 *256 = 65,536$.
• The product of two $8-bit$ numbers can be up to $16 bits$ wide ($8 bits + 8 bits = 16 bits$).
• To access $65,536$ unique combinations, we need $16$ address lines ($2^16 = 65,536$).
• To store $16-bit$ values, we need 16 data lines.
• $16$ address lines to specify the input combination (65,536 possible combinations).
• $16$ data lines to output the 16-bit product value.
• 64K x 16, where $64K$ represents the number of addressable locations (65,536) and $16$ represents the width of each location (in bits)

Answer 3

Answer : D