Multipliers

Thread Starter

cazz0026

Joined Sep 6, 2012
7
Hi all,

I need help with this question as I was sick for the lecture and can't solve it.
Thank you in advance for your help.

a. Using an appropriate diagram, show how an 8x8 bit multiplier can be implemented using 256x8bit ROM modules and any additional circuitry.
b. Briefly describe the architecture of a cellular binary multiplier. Illustrate your explanation by drawing a block diagram of a 2x2 bit cellular multiplier.

I can solve the rest of the problem off some notes from a friend. :)
 

WBahn

Joined Mar 31, 2012
29,978
What have you done so far? You need to show that you've made an effort first both because we won't just do your homework for you, but more importantly because that will let us get a glimpse of what you approach is and where you are going astray so that we can better help you.
 

Thread Starter

cazz0026

Joined Sep 6, 2012
7
Thank you WBahn for your reply.

As I said I was sick for the lecture and I haven't got notes on multipliers. Don't worry I don't want to have my homework made as I need to understand multipliers also for the exam.

Can you point me in the right direction regarding some tutorials on the web? I have tried to find some tutorials but can't seem to find. I have found tutorials on multiplexers, decoders etc but tutorials on multipliers seem scarce.

Thank you in advance. :)
 

absf

Joined Dec 29, 2010
1,968
a. Using an appropriate diagram, show how an 8x8 bit multiplier can be implemented using 256x8bit ROM modules and any additional circuitry.
I think I might have clues for this one.

an 8 bit number (255) multiply by another 8 bit number (255) would yield a product of 16 bit number (65535). So you can use 2x 256x8 ROM (or EPROM). The 8 address lines of one ROM would act as a multiplicand while that of the other ROM act as a multplier. The 8+8 data lines would be the product. Then you can either write a program or use Excel to calculate the data (product) to be programmed into both ROM.

Hope you can get the picture. :D I would leave the connections and the extra gates for you to figured out.

Allen
 

WBahn

Joined Mar 31, 2012
29,978
I think I might have clues for this one.

an 8 bit number (255) multiply by another 8 bit number (255) would yield a product of 16 bit number (65535). So you can use 2x 256x8 ROM (or EPROM). The 8 address lines of one ROM would act as a multiplicand while that of the other ROM act as a multplier. The 8+8 data lines would be the product. Then you can either write a program or use Excel to calculate the data (product) to be programmed into both ROM.

Hope you can get the picture. :D I would leave the connections and the extra gates for you to figured out.

Allen
As you've described it, the 8-bit value coming out of one ROM depends ONLY on the multiplicand while the 8-bit value coming out of the other ROM depends ONLY on the multiplier. That doesn't capture the interaction of the two operands during the multiplication process. Think of it this way - if you change either one of the inputs, then you need, in general, all 16 bits of the output to change.

Forgetting, for the moment anyway, the structure of the operation and how that might be leverages, you can implement an arbitrary 8-bit by 8-bit function that produces a 16-bit output by using 256x256x16 bits of ROM, which would require 512 256x8 bit ROMs.

But we can do much better. Think of each 8-bit input as composed of two 4-bit nibbles. Now multiply the values together keeping track of the four nibbles involved. Notice how you have four 4-bit x 4-bit multiplications that are then added together in a very simple way. Since each of these smaller multiplications produces an 8-bit result, a single 256x8 bit ROM can store the entire table. You can either design a state machine to access it sequentially four times, or you can keep the entire thing combinatorial and use four such tables to implement an 8-bit x 8-bit multiplier.
 

absf

Joined Dec 29, 2010
1,968
But we can do much better. Think of each 8-bit input as composed of two 4-bit nibbles. Now multiply the values together keeping track of the four nibbles involved. Notice how you have four 4-bit x 4-bit multiplications that are then added together in a very simple way. Since each of these smaller multiplications produces an 8-bit result, a single 256x8 bit ROM can store the entire table. You can either design a state machine to access it sequentially four times, or you can keep the entire thing combinatorial and use four such tables to implement an 8-bit x 8-bit multiplier.
After your explanation, I realized that my assumption was totally wrong. I did a simulation on a 2 bit x 2 bit multiplier with a 4 bit product using a 27C64 eprom and it runs fine, so I thought it would be the same with the 2x 256x8 PROM.

According to your scheme of connection, how many 256x8 PROM is required? Let me think it over about the connections of your proposal. It might take a few days....

What if I can find a 64Kx16 EPROM (16 bit address with 16 bit data), can I use it (just one chip) to design the multiplier in question?

Allen
 
Last edited:

WBahn

Joined Mar 31, 2012
29,978
After your explanation, I realized that my assumption was totally wrong. I did a simulation on a 2 bit x 2 bit multiplier with a 4 bit product using a 27C512 eprom and it runs fine, so I thought it would be the same with the 2x 256x8 PROM.

According to your scheme of connection, how many 256x8 PROM is required?

What if I can find a 64Kx16 EPROM (16 bit address with 16 bit data), can I use it (just one chip) to design the multiplier in question?

Allen
I don't know if I understand your first question, because I think I answered both variants that come to mind. If you implement it brute force, you need 512 of them. If you implement it using the nibble products approach, you need 4.

Yes, you can do it brute force with a 64Kx16 ROM, but notice that this is 512 times as big as a 256x8 ROM. But you could certainly build the circuit much more easily!
 

absf

Joined Dec 29, 2010
1,968
I don't know if I understand your first question, because I think I answered both variants that come to mind. If you implement it brute force, you need 512 of them. If you implement it using the nibble products approach, you need 4.

Yes, you can do it brute force with a 64Kx16 ROM, but notice that this is 512 times as big as a 256x8 ROM. But you could certainly build the circuit much more easily!
OK now I understand you perfectly. I want to try the nibble products way using 4x 256x8 PROM. I'll take some time cracking at it.

Thank you for enlightening me on this topic and sorry for my poor english...:p

Allen
 

WBahn

Joined Mar 31, 2012
29,978
OK now I understand you perfectly. I want to try the nibble products way using 4x 256x8 PROM. I'll take some time cracking at it.

Thank you for enlightening me on this topic and sorry for my poor english...:p

Allen
You're more than welcome and not a problem. I think your English is pretty darn good. And I guarantee you that you English is far better than me skill in whatever other language(s) you speak!
 

absf

Joined Dec 29, 2010
1,968
After some googling and reading, this is what I have in mind..

Rich (BB code):
Let's say my multiplicand is   "a7,a6,a5,a4,a3,a2,a1,a0"
and my multilipier is          "b7,b6,b5,b4,b3,b2,b1,b0"

And my 4 units of 256x8 nybble multipliers are 

M1 with product = "c c c c c c c c"  MSB….…LSB
M2 with product = "d d d d d d d d"
M3 with product = "e e e e e e e e"
M4 with product = "g g g g g g g g"

Then multiply                    a7 a6 a5 a4 a3 a2 a1 a0
with                          *  b7 b6 b5 b4 b3 b2 b1 b0
          _______________________________________________
to get                            c  c  c  c  c  c  c  c     (a3 a2 a1 a0)*(b3 b2 b1 b0) of M1 
                      d  d  d  d  d  d  d  d                 (a7 a6 a5 a4)*(b3 b2 b1 b0) of M2
                      e  e  e  e  e  e  e  e                 (a3 a2 a1 a0)*(b7 b6 b5 b4) of M3
       +  g  g  g  g  g  g  g  g                             (a7 a6 a5 a4)x(b7 b6 b5 b4) of M4
          ________________________________________________
          p  p  p  p  p  p  p  p  p  p  p  p  p  p  p  p     adding 4 terms 8 bit results to get final product
          ________________________________________________
Am I going on the right track?

Allen
 

WBahn

Joined Mar 31, 2012
29,978
Yep. Notice that if you add the inner terms (dd..dd) and (ee.ee) to form, say (hh..hh), you can simplify the final steps somewhat. You can almost just use an 8-bit adder to get the middle 8 bits, but you do have to deal with any carry out from that and propagate it through the MSN (most significant nibble).
 

absf

Joined Dec 29, 2010
1,968
Thanks for the clues. I need some more time to figure out the connections between the multipliers and the adders.

cheers!

Allen
 
Top