Show the multiplication process using Booth algorithm, when the following binary numbers, (+13) x (-15) are multiplied.

We need 5-bit registers, because $-15$ needs 5 bits in 2's complement. The numbers are:

$$M = +13 = 01101 \qquad -M = 10011 \qquad Q = -15 = 10001$$

$A$ starts at $00000$ and $Q_{-1}$ at 0. In each cycle, we look at $Q_0$ and $Q_{-1}$. The pair $10$ means $A = A - M$ (we add $-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 as a whole, and the sign bit of $A$ is copied (arithmetic shift right, ASR). There are 5 cycles, one for each multiplier bit.

The product is in $AQ$ joined:

$$AQ = 1100111101$$

The leading bit is 1, so the result is negative. Take the 2's complement to find its size:

$$\overline{1100111101} + 1 = 0011000010 + 1 = 0011000011 = 195$$

Therefore $(+13) \times (-15) = -195$.

We can also read $AQ$ directly as a 10-bit signed number, where the leftmost bit has the weight $-512$:

$$-512 + 256 + 32 + 16 + 8 + 4 + 1 = -195$$

The shift is an arithmetic shift, so the sign of the partial product is never lost. When $A - M$ makes $A$ negative, the copied sign bit keeps it negative after the shift.

The method works because the pairs of bits turn the multiplier into signed digits. Here $Q = 10001$ becomes the digits $-1$ at bit 0, $+1$ at bit 1 and $-1$ at bit 4, so its value is:

$$-16 + 2 - 1 = -15$$

In the table, cycle 1 subtracts $M$ (digit $-1$), cycle 2 adds $M$ (digit $+1$), and cycle 5 subtracts $M$ again, but now it counts $16$ times as much because of the shifts. The cycles 3 and 4 only shift. Adding these shifted copies of $M$ gives $13 \times (-15)$.

The check is $13 \times 15 = 195$ and the signs differ, so the sign is negative. The result agrees.