ECE 375: Digital Design II
Class 22Left Shift Multiplication
P(0) = 0
P(j+1) = 2P(j) + X(k-j-1) * A
Example 1:
A = 1010 => 10
X = 1011 => 11
K = 4
p0 = 0000_0000
p1 = 0000_0000 << 1 => 0000_0000 + 0000_1010 = 0000_1010
p2 = 0000_1010 << 1 => 0001_0100 + 0000_0000 = 0001_0100
p3 = 0001_0100 << 1 => 0010_1000 + 0000_1010 = 0011_0010
p4 = 0011_0010 << 1 => 0110_0100 + 0000_1010 = 0110_1110
p4 <=> 2^7 + 2^6 + 2^4 + 2^3 + 2^2 = 64 + 32 + 8 + 4 + 2 = 110
Hardware
Is pretty much the same but less efficient hardware. This is because the adder has to be 2k
bits wide and you can't store the multiplicand in the partial product.
Signed multiplication
We can use 2's Complement and the Right Shift algorithm as a base to do signed multiplication.
P(j+1) = [P(j) + X(j) * A * 2^k) 2^-1
A = 10110 => -10
X = 01011 => 11
K = 5
// We have to reserve 2 extra, one for the sign and one for the carry
// You have to sign extend A to match the `2k+2` bit width
p0 => 00_00000_00000
+ x0*a => 11_10110_00000
------------------------
2*p1 => 11_10110_00000
p1 => 11_11011_00000 // Arethmetic right shift
+ x1*a => 11_10110_00000
------------------------
2*p2 => 11_10001_00000
p2 => 11_11000_10000
+ x2*a => 00_00000_00000
------------------------
2*p3 => 11_11000_10000
p3 => 11_11100_01000
+ x3*a => 11_10110_00000
------------------------
2*p4 => 11_10010_01000
p4 => 11_11001_00100
+ x4*a => 00_00000_00000
------------------------
2*p5 => 11_11001_00100
p5 => 11_11100_10010 <=> -110