Using Booth algorithm perform the multiplication on the following 6-bit unsigned integer 10110011 * 11010101

The numbers are two 8-bit unsigned integers, $10110011 = 179$ and $11010101 = 213$. Booth's algorithm works on signed numbers. So we first add a 0 on the left of each number. That makes them 9-bit non-negative numbers with the same value. The product then needs 18 bits.

The multiplicand is $M = 010110011$ and the multiplier is $Q = 011010101$. We also need $-M$, found by taking the 2's complement of $M$:

$$-M = 101001101$$

Registers $A$ (9 bits) and $Q_{-1}$ start at 0. In each cycle we look at the pair $Q_0 Q_{-1}$. If it is $10$, we do $A = A - M$. If it is $01$, we do $A = A + M$. If it is $00$ or $11$, we do nothing. Then we shift $A$, $Q$ and $Q_{-1}$ one place right, keeping the sign bit of $A$ (arithmetic shift right, ASR). We repeat this 9 times.

After 9 cycles, the product is held in $A$ and $Q$ joined together:

$$AQ = 001001010,011101111$$

This is the 18-bit number $001001010011101111_2$. Its value is:

$$2^{15} + 2^{12} + 2^{10} + 2^{7} + 2^{6} + 2^{5} + 2^{3} + 2^{2} + 2^{1} + 2^{0} = 38127$$

Therefore $10110011 \times 11010101 = 38127$. Check: $179 \times 213 = 38127$, so the working is correct.

The reason Booth's method helps here is that runs of 1s in the multiplier are handled by one subtraction at the start of the run and one addition after its end. The multiplier $011010101$ has many isolated 1s, so there are many operations. Even so, the answer is correct for every pattern.