Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

For a 4-bit multiplier there are $2^4 \cdot 2^4 = 2^8$ combinations.

The output of 4-bit multiplication is 8 bits, so the amount of ROM needed is $2^8 \cdot 8 = 2048$ bits.

Why is that? Why does the ROM need all the combinations embedded into it?

What will be the case with RAM?

share|improve this question
Welcome to cs.SE! ROM (Read-Only Memory) and RAM (Random Access Memory) are two non-exclusive types of memory. The first says that the memory cannot be written, the second that all addresses of memory take the same time to be accessed. On an unrelated point, you should provide more context about your question, I don't remember multipliers requiring any memory to work, just logical gates. Are there any constraints that you forgot to mention? –  Khaur Feb 4 '13 at 14:11
At the expense of adding more circuitry at the input, you can reduce the ROM size into half, taking advantage of commutativity of multiplication. To elaborate, 3 * 5 = 5 * 3, so put some combinatorial logic before the input decoder which maps (5, 3) input to the same row as (3, 5). Also note that not all 256 products appear in the output. For example, 202 < 255, but it doesn't appear, neither does 255 itself or any of the prime numbers (>15). For a 4 * 4 multiplication, there are only 90 possible outputs, but the next power of 2 is 128. –  user13027 Jan 22 at 5:05
add comment

2 Answers

up vote 3 down vote accepted

As shown in the figure bellow (general architecture of ROM):

to address 8-bit numbers correctly your ROM size should be: $2^8 \times 8$ bits.

enter image description here

share|improve this answer
does that mean that there is no calculation of the product but the appropriate word is selected from the ROM by the decoder and is outputted. –  Ravi Teja Feb 5 '13 at 15:27
@RaviTeja: Yes, It is something like a big truth table! –  Reza Feb 5 '13 at 16:04
add comment

If you are storing all the value of the function (in this case, multiplication) in a big table, then the size of this table is $2^{\text{# input bits}}\cdot \text{# output bits}$. This becomes impractical rather quickly, so CPUs implement arithmetic operations differently.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.