Skip to main content

Booth algorithm and 8 × 4

Short answer

Booth multiplication uses multiplier bit pairs Q0,Q-1: subtract for 10, add for 01, shift right otherwise. For 8 times 4 in 5 bits, A:Q becomes 0000100000, which equals 32.

Write an algorithm of Booth multiplication. Perform 8×4 using Booth multiplication algorithm.

Algorithm of Booth multiplication

Booth's algorithm multiplies two signed numbers in 2's complement form. It looks at the multiplier bit pair (Q0, Q-1) and treats a run of 1s as (next higher power − lowest power), so a block of 1s needs only one subtraction and one addition.

  1. Load M = multiplicand, Q = multiplier, A = 0, Q-1 = 0, SC = n (number of bits).
  2. Look at (Q0, Q-1):
    • 00 or 11: no arithmetic.
    • 10 (start of a run of 1s): A = A − M.
    • 01 (end of a run of 1s): A = A + M.
  3. Arithmetic shift right the combined A, Q, Q-1 by one bit (the sign bit of A is kept).
  4. SC = SC − 1. If SC ≠ 0 go to step 2; otherwise stop.
  5. The 2n-bit product is in A:Q.

Flowchart

        +-----------------------+
        | A=0, Q-1=0, SC=n      |
        | M=multiplicand Q=mult |
        +-----------+-----------+
                    v
        +-----------------------+<-----------+
        |   Q0 Q-1 = ?          |            |
        +--+---------+--------+-+            |
         10|       01|     00/11|            |
           v         v         |             |
       A = A - M  A = A + M    |             |
           |         |         |             |
           +----+----+---------+             |
                v                            |
        +-----------------------+            |
        | ASR (A, Q, Q-1)       |            |
        | SC = SC - 1           |            |
        +-----------+-----------+            |
                    v                        |
               SC = 0 ? --- No --------------+
                    | Yes
                    v
              Product in A,Q

8 × 4

Five bits are used so that 8 is a valid positive signed number.

Multiplicand M = 8 = 01000, multiplier Q = 4 = 00100, -M = 11000, n = 5 bits.

Step  Action               A      Q      Q-1
-     Initial              00000  00100  0
1     Q0Q-1=00: no change  00000  00100  0
      ASR                  00000  00010  0
2     Q0Q-1=00: no change  00000  00010  0
      ASR                  00000  00001  0
3     Q0Q-1=10: A = A - M  11000  00001  0
      ASR                  11100  00000  1
4     Q0Q-1=01: A = A + M  00100  00000  1
      ASR                  00010  00000  0
5     Q0Q-1=00: no change  00010  00000  0
      ASR                  00001  00000  0

Result in A,Q = 00001 00000 = 32.

Answer: 8 × 4 = 32

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 5 questions →