When (for how large an operand size) does the area of a multiplier
implemented by ROM become larger than the area of a multiplier
implemented by adders ??
Or is there a clear advantage of having adder based multipliers ??
Question :
--------------
To realise a 2 input(each input is 4 bit) multiplier using a ROM and
what will be the size of the ROM. How can you realise it when the
outputs are specified.
Hint
Use the ROM as LUT (look up table );
Inputs will be assigned as ROM address lines of 8 bits .
each memory word will be 8 bits as the maximum output of the
multplication is 15X15 = 225 (fits in 8 bits )
for instance if we multpliy 15 X 2 the address line will be 1111-0010
the word corresponding to this address in memory should store a value
of 30 decimal in binary 0001-1110 What is tricky here is that the
multiplication is cummutative , i.e , 15 X 2 = 2 X 15
what if the address has now 0010-1111 it should point to a word in the
lower half of the ROM table and what is tricky is that it should hold
the same binary value of 30 decimal =0001-1110 .
The ROM size in my point of view is 2 ^^ 8 = 256 words though we store
only 128 word but we have to duplicate every word ; one time at the
lower half and the other time at the upper part.
Although it seems to make sense , the above observation is wrong we
need to store (256-16)/2 +16 = 120 + 16 = 136 values.
We can still implement this using a 128 entry ROM , using a complex
mapping mechanism of the addresses if we can somehow take care of all
the trivial cases of multiplication by 1 and 2.
-Rajan