Q21Computer Architecture and Organization

Standard binary multiplication is mathematically inefficient. Multiplying an $n$-bit number requires $n$ additions and shifts, consuming massive ALU resources. Furthermore, standard multiplication catastrophically fails when handling negative numbers in 2's complement form. Booth's Algorithm is an advanced mathematical hardware algorithm that perfectly handles signed integers and aggressively reduces the number of ALU additions by identifying blocks of consecutive 1s in the multiplier.

The Mathematical Principle

Consider a multiplier 00111000. In standard multiplication, this requires three separate ALU additions. Booth's algorithm mathematically realizes that a block of 1s from position $n$ to $m$ can be represented as $(2^{n+1}-2^m)$. Therefore, the multiplier 00111000 can be processed with exactly one subtraction and one addition, drastically speeding up the hardware execution.

The hardware tracks a Multiplicand register ($M$), a Multiplier register ($Q$), an Accumulator ($A$, initialized to 0), and a special single-bit register ($Q_{-1}$, initialized to 0). The algorithm executes a strict $n$-step loop by aggressively inspecting the two least significant bits: $Q_0$ and $Q_{-1}$.

• If $Q_0{Q}_{-1}=10$: The hardware mathematically calculates $A=A-M$. (Entering a block of 1s).
• If $Q_0{Q}_{-1}=01$: The hardware mathematically calculates $A=A+M$. (Exiting a block of 1s).
• If $Q_0{Q}_{-1}=00$ or $11$: The ALU does absolutely nothing. (Inside a block of 0s or 1s).
• Final Step: The hardware executes an Arithmetic Right Shift (ASR) on the combined register sequence $A,Q,Q_{-1}$. The sign bit of $A$ is strictly preserved.

Let $M=3\Rightarrow 0011$ (Multiplicand). Let $Q=-4\Rightarrow 1100$ (Multiplier in 2's complement). Let $-M=-3\Rightarrow 1101$. $A=0000$, $Q_{-1}=0$. Count $n=4$.

Cycle 1: - Check $Q_0{Q}_{-1}\Rightarrow 00$. No ALU operation. - ASR Shift: $A=0000,Q=0110,Q_{-1}=0$.

Cycle 2: - Check $Q_0{Q}_{-1}\Rightarrow 00$. No ALU operation. - ASR Shift: $A=0000,Q=0011,Q_{-1}=0$.

Cycle 3: - Check $Q_0{Q}_{-1}\Rightarrow 10$. Execute $A=A-M\Rightarrow A=A+(-M)=0000+1101=1101$. - Status: $A=1101,Q=0011,Q_{-1}=0$. - ASR Shift: $A=1110,Q=1001,Q_{-1}=1$. (Note: ASR duplicated the 1 in MSB of A).

Cycle 4: - Check $Q_0{Q}_{-1}\Rightarrow 11$. No ALU operation. - ASR Shift: $A=1111,Q=0100,Q_{-1}=1$.

Result Verification

The strict $n=4$ loop is complete. The final 8-bit mathematical answer resides in the concatenated $A,Q$ registers. Result: $11110100$. Converting this 2's complement binary back to decimal yields exactly $-12$. The hardware algorithm performed flawlessly.