How to perform right shifting binary multiplicatio

问题:

This is a homework problem which I tried to solve by myself but I couldn't. The homework is to implement a circuit that multiplies two binary numbers by using right shifting. I don't have any problems with Verilog, my only problem is how to conclude the algorithm so I can implement it by myself.

回答1:

Example multiplies. Note 4 bit adder produces a 5 bit sum (top bit is carry). Input to adder is multiplicand plus bits 3 to 6 of product register, the sum including carry, goes to bits 3 to 7 of product register.

multiplicand 1100, multiplier 0101

7 6 5 4 3 2 1 0         product bit index

0 0 0 0 0 1 0 1         initial 8 bit register

0 0 0 0 0 0 1 0    1    shift right, 1 bit shifted out
  1 1 0 0               add multiplicand
0 1 1 0 0 0 1 0         
0 0 1 1 0 0 0 1    0    shift right, 0 bit shifted out
  0 0 0 0               no add
0 0 1 1 0 0 0 1
0 0 0 1 1 0 0 0    1    shift right, 1 bit shifted out
  1 1 0 0               add multiplicand
0 1 1 1 1 0 0 0
0 0 1 1 1 1 0 0    0    shift right, 0 bit shifted out
  0 0 0 0               no add
0 0 1 1 1 1 0 0

multiplicand 1111, multiplier 1111

0 0 0 0 1 1 1 1         initial 8 bit register

0 0 0 0 0 1 1 1    1    shift right, 1 bit shifted out
  1 1 1 1               add multiplicand
0 1 1 1 1 1 1 1
0 0 1 1 1 1 1 1    1    shift right, 1 bit shifted out
  1 1 1 1               add multiplicand
1 0 1 1 0 1 1 1
0 1 0 1 1 0 1 1    1    shift right, 1 bit shifted out
  1 1 1 1               add multiplicand
1 1 0 1 0 0 1 1
0 1 1 0 1 0 0 1    1    shift right, 1 bit shifted out
  1 1 1 1               add multiplicand
1 1 1 0 0 0 0 1