Show the systemic multiplication process of (20) X (-19) using Booth's algorithm

We use 6-bit registers, because $-19$ needs 6 bits in 2's complement. The numbers are:

$$M = +20 = 010100 \qquad -M = 101100 \qquad Q = -19 = 101101$$

$A$ starts at $000000$ and $Q_{-1}$ starts at 0. In each cycle we read the pair $Q_0 Q_{-1}$. The pair $10$ means subtract $M$ from $A$. The pair $01$ means add $M$ to $A$. The pairs $00$ and $11$ mean no operation. After that, $A$, $Q$ and $Q_{-1}$ are shifted one place right, and the sign bit of $A$ is copied (arithmetic shift right, ASR). The process runs for 6 cycles, one for each bit of the multiplier.

The product is in the joined register $AQ$:

$$AQ = 111010000100$$

The leftmost bit is 1, so the answer is negative. To find its size, take the 2's complement:

$$\overline{111010000100} + 1 = 000101111011 + 1 = 000101111100 = 380$$

Therefore $(+20) \times (-19) = -380$.

The result is correct because $20 \times 19 = 380$, and the signs differ. Booth's method gave the right sign automatically, and we did not need to treat the sign separately. This is the main strength of the algorithm. It works directly on numbers in 2's complement form. It also skips over strings of 0s and 1s in the multiplier, so it uses fewer additions when the multiplier has long runs of equal bits.

In this example the multiplier $101101$ has no long runs, so only the pair $11$ in cycle 4 causes a skip.

The table can be understood in another way. The pairs of bits turn the multiplier into the signed digits $-1, +1, 0, -1, +1, -1$ (from the leftmost bit down). So the multiplier is worth:

$$-32 + 16 + 0 - 4 + 2 - 1 = -19$$

Each digit decides whether we subtract $M$, add $M$, or do nothing at that bit position. Adding up the shifted copies gives $20 \times (-19) = -380$.