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

3 Answers 3

up vote 5 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

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

To address your last point (albeit late): whether the lookup table is stored in RAM or ROM makes no difference to the size needed (although it would almost never make sense to store a multiplication table like this in RAM).

If it were stored in RAM you would either have to load it from ROM or populate it manually, neither of which make much sense in the typical situations where you might use a lookup-table.

Copying a ROM table to RAM would typically only be used if the contents were to be updated over time, and the ROM copy is just the starting point (not the case with multiplication). The only other likely use-case that comes to mind would be where you use a ROM to "bootstrap" the system -- copying programs and data to RAM -- and then switch the ROM out of normal address-space and run everything from RAM.

As for populating manually: using a look-up table for multiplication would tend to imply that you're on fairly low-level hardware, where you either don't have a full-blown CPU (in which case there would be nothing to populate the table) or it's a fairly basic CPU (in which multiplication is slow). In the latter case, it could make sense to populate a RAM table at start-up (essentially creating a cache), but since you would have to evaluate all combinations, this would lead to a lengthy delay before you could do "real work".

share|improve this answer

Your Answer

 
discard

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.