Show the multiplication process using Booth's algorithm when the following numbers are multiplied: (-12) * (-18).
Show the multiplication process using Booth's algorithm when the following numbers are multiplied: (-12) * (-18).
We use 6-bit registers, because $-18$ needs 6 bits in 2's complement. The numbers are:
$$M = -12 = 110100 \qquad -M = +12 = 001100 \qquad Q = -18 = 101110$$
$A$ and $Q_{-1}$ start at 0. In each cycle we read the pair $Q_0Q_{-1}$. The pair $10$ means $A = A - M$. The pair $01$ means $A = A + M$. The pairs $00$ and $11$ mean no operation. Then $A$, $Q$ and $Q_{-1}$ shift one place right with the sign bit of $A$ copied (arithmetic shift right, ASR). There are 6 cycles.
| Cycle | Q0 Q-1 | Operation | A | Q | Q-1 |
|---|---|---|---|---|---|
| Start | - | initial | 000000 | 101110 | 0 |
| 1 | 0 0 | no change, ASR | 000000 | 010111 | 0 |
| 2 | 1 0 | A = A - M, ASR | 000110 | 001011 | 1 |
| 3 | 1 1 | no change, ASR | 000011 | 000101 | 1 |
| 4 | 1 1 | no change, ASR | 000001 | 100010 | 1 |
| 5 | 0 1 | A = A + M, ASR | 111010 | 110001 | 0 |
| 6 | 1 0 | A = A - M, ASR | 000011 | 011000 | 1 |
The product is in $AQ$ joined:
$$AQ = 000011011000$$
The leading bit is 0, so the product is positive. Its value is:
$$2^7 + 2^6 + 2^4 + 2^3 = 128 + 64 + 16 + 8 = 216$$
Therefore $(-12) \times (-18) = +216$.
Check: $12 \times 18 = 216$, and two negative numbers give a positive product, so the answer is correct. Booth's algorithm gave the correct sign without any separate sign handling, because it works on 2's complement numbers directly. Cycles 1, 3 and 4 needed no addition or subtraction, so the multiplier $101110$ was handled with only three arithmetic operations instead of four.
Short on time? The 1, 5 and 10 mark versions of this answer, flashcards and practice sets come with a program pass.
Up nextWhat is pipelining? What are the different stages of pipelining? Explain in detail.