Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
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".
If you want to implement a multiplier in a lookup table in memory of any sort, then for 4x4, you'd need address space that covers the width of both source operands. In this case, you'd 8 bits. That is 256 addresses, and room for every combination. When you multiply, you double the bits needed of each operand in the result.
The type of memory you use doesn't really matter. While you can use a ROM, you could build the chart in RAM. It would be harder if you have not ROM to copy to it since you'd have to first build the chart there. And you wouldn't need a RAM-based chart unless the CPU didn't provide that functionality. So you'd have to use many addition loops (or shifting in some cases if you have that, or a different type of specialized instruction such as LEA) to build the chart. That would be a lot of overhead, so you'd want to make sure if you create a LUT multiplier in software, that the software uses multiplication extensively.
But since the RAM-based LUT is not on a discreet chip and likely shares with other things. Then you'd have to first compute the addresses and then offset your way into the table. In a higher-level language, you'd likely use a matrix (and array of arrays) for this. While the programming to use the table would be easier for the coder, matrices tend to pull in lengthy library functions which have their own overhead. So if you are trying to replace a slow multiplication function in the CPU with a faster one, you may end up disappointed.
Just so I am not misunderstood, just having a ROM to do multiplication is not what would improve speed over using RAM. ROM itself is slower than RAM. But what would be faster is if you had a CPU with a ROM like this inside or you made a homebrew CPU using discrete logic and you had an opcode to put the multiplicand and multiplier on the address bus of the ROM (or an SRAM shadowing the ROM) and put the product on the data bus of the RAM. No calculation of addresses would be needed as that is directly assembled from the numbers supplied. So what I said earlier about issues addressing the RAM have to do with sharing the RAM with other things and needing to compute the addresses. As a minimum, doing it in software would require knowing where it is in memory and adding the numbers to multiply to it in a concatenated form (like high nibble is A and low nibble is B). So it would be a matter of setting the page register to the correct page and adding the assembled address to the offset and reading the memory there.
Now, if you have more than 8 address bits into your ROM, you could use that for other things. If you use a ROM (or RAM copied from a ROM) for an entire ALU, then the remaining upper bits would be used to select the operation other than multiplication.
