what is the sequence and how it is going?

Question

I have been trying to understand the hardware implementation for booth's algorithm and here is a diagram i came across trying to explain but i didn't understand this :

How it is going ? I know that B,A,Q are registers.

Answer 1

Long (multi-digit) multiplication in binary is the same as it is in decimal, just simpler. For example, in decimal:

  15
x 12
----
  30
 15
----
 180

and in binary:

    1111 (15)
  x 1100 (12)
  ------
    0000
   0000
  1111
 1111
--------
10110100 (180)

Note that you multiply the entire multiplicand by each digit of the multiplier, then add the results, taking care to keep track of the decimal. Binary multiplication (the one-bit-at-a-time method at least) does the same thing.

In Figure 3.11, the multiplier works by looking at the LSB of Q and setting A to A + B if it's a 1 or leaving A alone if it's a 0. Then it shifts Q one bit right and B one bit left. Repeat this until Q runs out of valid bits. You could even stop early when Q is all 0 bits:

    1111 (B)
  x 1100 (Q)
  ------
    0000 (Cycle 0: Q[0] == 0: A => 00000000, B => 00011110, Q => 0110)
   0000  (Cycle 1: Q[0] == 0: A => 00000000, B => 00111100, Q => 0011)
  1111   (Cycle 2: Q[0] == 1: A => 00111100, B => 01111000, Q => 0001)
 1111    (Cycle 3: Q[0] == 1: A => 10110100, B => 11110000, Q => 0000)
--------
10110100 (A)

The downside is that the A and B registers have to be as big as the result, which is twice as many bits as the inputs (a fact the C language ignores).

Now Figure 3.13 shows an optimization of this process. Instead of shifting the multiplicand (B) left, it shifts the result right, and it uses the bits that are freed up in Q to store the bits that fall off the right side of A:

    1111 (B)
  x 1100 (Q)
  ------
    0000 (Cycle 0: Q[0] == 0: A => 0000, Q => 0110)
   0000  (Cycle 1: Q[0] == 0: A => 0000, Q => 0011)
  1111   (Cycle 2: Q[0] == 1: A => 0111, Q => 1001)
 1111    (Cycle 3: Q[0] == 1: A => 1011, Q => 0100)
--------
10110100 (A:Q)

Note that you can't stop early if Q is all 0 bits; you would have to keep track of how many bits left in Q were the multiplier, which is enough extra combinational logic to slow the cycle time down.

Finally, note that neither of these are the single-cycle multiplier algorithms found in modern CPUs. Those are based on having N adders and doing the whole process in one fell swoop, and Booth's algorithm wouldn't make any difference. (A would have to be 2N bits and B would only need to be N bits.)