Sequential Version of Multiplication Hardware

This slide shows a sequential version of the multiplication hardware and algorithm, and an execution example “11002×11012 = 100111002”.

The Multiplicand register, ALU, and Product register are all 64 bits wide, with only the Multiplier register containing 32 bits. The 32-bit multiplicand starts in the right half of the Multiplicand register and is shifted left 1 bit on each step. The multiplier is shifted in the opposite direction at each step. The algorithm starts with the product initialized to 0.

Control decides when to shift the Multiplicand and Multiplier registers and when to write new values into the Product register. If the least significant bit of the multiplier is 1, add the multiplicand to the product. If not, go to the next step. Shift the multiplicand left and the multiplier right in the next two steps. These three steps are repeated 32 times.

If each step took a clock cycle, this algorithm would require almost 100 clock cycles to multiply two 32-bit numbers. Using the above algorithm to complete the following table, which shows a 4-bit multiplication of 
11002 × 11012 = 100111002
Iteration Multiplicand Multiplier Product
0 Initialize
1 Add or do nothing
Shift
2 Add or do nothing
Shift
3 Add or do nothing
Shift
4 Add or do nothing
Shift
5 Add or do nothing
Shift
6 Add or do nothing
Shift
... ... ... ... ... ... ...




      Snake 1: Are we poisonous?    
      Snake 2: I don’t know, why?    
      Snake 1: I just bit my lip.