Part 2: Arithmetic Logic Unit (ALU) Design & IEEE 754 Floating-Point Arithmetic

1. Adders: The Ripple-Carry Delay Bottleneck

A 1-bit Full Adder accepts inputs $A_i$, $B_i$, and an incoming carry $C_i$, producing a sum $S_i$ and outgoing carry $C_{i+1}$:

In an $N$-bit Ripple-Carry Adder (RCA), $N$ full adders are cascaded serially: the carry output $C_{i+1}$ of stage $i$ feeds into the carry input of stage $i+1$. Consequently, the highest-order sum bit $S_{N-1}$ cannot stabilize until the carry bit ripples through all $N$ stages. In a 64-bit adder, if each gate introduces a delay of $t_g = 50\text{ ps}$, the total worst-case carry latency is $2N \cdot t_g \approx 6.4\text{ ns}$—capping the CPU clock frequency at an unacceptable 156 MHz.

2. Carry-Lookahead Adder (CLA): $\mathcal{O}(1)$ Parallel Logic

To eliminate ripple propagation delay, the Carry-Lookahead Adder (CLA) defines two auxiliary Boolean terms for every bit position:

• Generate ($G_i$): A carry is generated internally if both inputs are 1: $G_i = A_i \cdot B_i$.
• Propagate ($P_i$): An incoming carry is propagated to the next stage if either input is 1: $P_i = A_i \oplus B_i$.

The carry output can then be expressed recursively:

Every carry bit $C_i$ is computed simultaneously in parallel through a two-level AND-OR gate array directly from the primary inputs $A, B$ and initial carry $C_0$. The carry propagation delay drops from $\mathcal{O}(N)$ to a constant $\mathcal{O}(1)$ gate delay, enabling multi-gigahertz ALU execution.

3. Multiplication: Booth's Radix-2 & Radix-4 Algorithms

Elementary binary multiplication mimics paper-and-pencil shift-and-add arithmetic, requiring $N$ additions for an $N$-bit multiplier. In 1951, Andrew Donald Booth introduced an algorithm that accelerates signed two's complement multiplication by recoding strings of consecutive binary 1s.

For example, multiplying by the bit string $01111000_2$ ($120_{10}$) naively requires four additions. Booth recognizes that $01111000_2 = 10000000_2 - 00001000_2$ ($128 - 8$). By replacing continuous runs of 1s with a single subtraction at the beginning of the run and a single addition at the end, Booth's algorithm slashes intermediate addition cycles. Modern ALUs deploy Modified Booth Radix-4 recoding combined with Wallace / Dadda Tree reduction networks to compress partial products in $\mathcal{O}(\log_2 N)$ latency.

4. IEEE 754 Floating-Point Arithmetic Architecture

Real numbers (non-integers) are represented in hardware using the IEEE 754 Standard for Floating-Point Arithmetic. A floating-point number $V$ is encoded as: