Do you really want to know how to do binary multiplication?
We have two 32 bit numbers we want to multiply, a and b.
Doing 32 bit multiplication in a single step is very difficult. It has 64 bit input and 64 bit output . We can simulate this by cutting the inputs in half.
The answer is:
a0*b0
+a1*b0<<8
+a0*b1<<8
+a1*b1<<16.
Doing 16 bit multiplication in a single step is difficult. It has 32 bits of input and 32 bits of output. Good thing we can split it in half.
The answer is:
a0*b0
+a1*b0<<4
+a0*b1<<4
+a1*b1<<8.
Doing 8 bit multiplication in a sing step is hard...
The answer is:
a0*b0
+a1*b0<<2
+a0*b1<<2
+a1*b1<<4.
Doing 4 bit multiplication in a sing step is reasonable, but lets continue the trend...
The answer is:
a0*b0
+a1*b0<<1
+a0*b1<<1
+a1*b1<<2.
Doing 2 bit multiplication in a sing step is easy...
We will name the digits of the first input number a and b. We will name the digits of the second input number x and y. We will name the digits of the output number A, B, C, D. All names are from highest order to lowest.
xy xy xy xy
ab 00 01 10 11
00 0000 0000 0000 0000
01 0000 0001 0010 0011
10 0000 0010 0100 0110
11 0000 0011 0110 1001
Now we make our rules.
The easiest rule is for A. It is all inputs and'd together.
A = abxy
B is a little trickier, as there are more options. including nots (!) and or's.
B = a!b x!y
B = a b x!y
B = a!b x y
The b!b in the first two rules cancel.
B = a x!y
B = a x y
The y!y cancel.
B = ax
D is pretty simple as well.
D = !a b!x y
D = !a b x y
D = a b!x y
D = a b x y
Cancel x!x in the first 2 and the last 2.
D = !a b y
D = a b y
Cancel a!a.
D = by
C is even worse.
C = a!b!x y
C = a b!x y
C = !a b x!y
C = a b x!y
C = !a b x y
C = a!b x y
The a!a in the first two rules cancel.
C = b!x y
C = !a b x!y
C = a b x!y
C = !a b x y
C = a!b x y
The a!a in the 2nd and 3rd rule cancel.
C = b!x y
C = b x!y
C = !a b x y
C = a!b x y
Now I add an xor (+) to keep simplifying the first two rules.
C = b(x+y)
C = !a b x y
C = a!b x y
Apply xor again to the last two.
C = b(x+y)
C = (a+b)x y
Combine with an or (|).
C = b(x+y)|(a+b)xy
Congradulations, we just turned 2 bit multiplication into 3 simple rules and one moderate rule in binary algebra.
A = abxy
B = ax
C = b(x+y)|(a+b)xy
D = by
You could scale this process up to 4 bit, and 8 bit relatively easilly. But to reduce 16, 32 or 64 bit multiplication to rules like this? No human can do it and even machine designs for the higher numbers are likely to complex to be useful. Using 8 bit multipliers, you need 16 multiplications and 15 shifts and 15 adds to multiply 2 32 bit numbers. You could arrange 20 such 8 bit multiplers with 16 in the first stage and 4 in the second stage with output fed from the first stage into second stage input and get that multiplication for a 32 bit number done in only 2 clock ticks.
Note that if you were to be implementing this in silicon, you would use additional algebra to turn everything into NAND operations because NAND ops because NAND gates are cheap.
Author
Topic: Binary Multiplication (Read 5967 times)