Is Every Arithmetic Operation Just Addition in Hardware?

At the transistor level, digital silicon does not know how to subtract, multiply, or divide. It only knows how to sum bits.

Every fundamental arithmetic operation in an execution unit maps directly back to addition. Subtraction is addition with inverted bits and an asserted carry-in ($A - B = A + \sim B + 1$). Multiplication is a two-dimensional grid of shifted additions ($\sum A \cdot B[i] \cdot 2^i$). Even division, the slowest operation in the datapath, reduces to an iterative sequence of trial subtractions and conditional additions, or converts into reciprocal multiplications via Newton-Raphson iterations.

When calculating $99 \times 43$ on paper, evaluating $(100 - 1) \times 43 = 4300 - 43 = 4300 + (-43)$ replaces a multi-digit multiplication with a shift and an addition. The hardware underneath your HDL does the exact same thing: generating bit vectors and resolving carries. The execution latency of any processor or accelerator datapath is governed by how fast and cheaply a circuit can evaluate these carries across wide vectors without stalling the clock period.

Number Representations: Why Hardware Uses Two’s Complement

Before designing adders or multipliers, we must establish how positive and negative numbers are encoded in binary registers.

One’s Complement and Its Physical Limitations

In an $N$-bit one’s complement system, negating a number is performed by inverting every bit:

For a 4-bit value $+3 = 0011_2$, its one’s complement negation is $\sim 0011_2 = 1100_2$ (representing $-3$).

While bitwise inversion requires only inverter gates with zero carry propagation, one’s complement has two physical drawbacks in hardware:

• Dual Representations of Zero: Zero has two distinct bit patterns: positive zero ($+0 = 0000_2$) and negative zero ($-0 = 1111_2$). Comparison circuits ($A == B$) and branch-if-zero instructions must test for both encodings, increasing gate count and critical path delay.
• The End-Around Carry: Adding two one’s complement numbers requires any carry leaving the MSB to be fed back and added into the LSB:

    0101  (+5)
  + 1101  (-2)
  ------
  1 0010  (Carry out = 1)
       1  (End-around carry routed back to LSB)
  ------
    0011  (+3 in one's complement)

In silicon, an end-around carry creates a circular timing loop: the output of the adder ripples back into its own input, requiring either two full addition passes or complex speculative lookahead circuits.

Two’s Complement: The Negative MSB Weight

Two’s complement defines negation as inverting all bits and adding one:

In two’s complement, there is exactly one zero ($0000_2$). Negating zero yields $\sim 0000_2 + 1 = 1111_2 + 1 = 10000_2$, which truncates to $0000_2$ in an $N$-bit register.

The physical meaning of two’s complement is that the most significant bit (MSB) carries negative positional weight:

In a 4-bit register:

• Bit 0 has weight $+2^0 = +1$.
• Bit 1 has weight $+2^1 = +2$.
• Bit 2 has weight $+2^2 = +4$.
• Bit 3 has weight $-2^3 = -8$.

Examples:

• $0111_2 = -0(8) + 4 + 2 + 1 = +7$.
• $1000_2 = -1(8) + 0 + 0 + 0 = -8$.
• $1101_2 = -1(8) + 4 + 0 + 1 = -3$.
• $1111_2 = -1(8) + 4 + 2 + 1 = -1$.

Because the MSB functions as a standard arithmetic bit with negative weight rather than a separate sign flag, an unsigned binary adder sums signed two’s complement numbers with zero modification.

The Unified Adder/Subtractor Circuit

An ALU does not instantiate a separate subtractor block alongside its adder. Subtraction is folded directly into the adder using XOR gates on operand $B$ and driving the carry-in ($C_{\text{in}}$) with a sub control line:

                    Operand B [N-1:0]
                           |
                           v
              sub ------> [XOR] (Bitwise B ^ sub)
              |            |
              |            v
Operand A --->|======> [ Adder ] <--- sub (Fed directly to Cin)
                       [       ]
                           |
                           v
                      Sum / Diff [N-1:0]

• When $\text{sub} = 0$: $B \oplus 0 = B$, and $C_{\text{in}} = 0$. The circuit computes $A + B + 0 = A + B$.
• When $\text{sub} = 1$: $B \oplus 1 = \sim B$, and $C_{\text{in}} = 1$. The circuit computes $A + (\sim B) + 1 = A - B$.

Bit-Level Subtraction Traces (4-Bit)

Case 1: Positive minus Positive ($7 - 3 = 4$)

• $A = 7_{10} = 0111_2$.
• $B = 3_{10} = 0011_2$. With $\text{sub} = 1$, the adder receives $\sim B = 1100_2$ and $C_{\text{in}} = 1$.
• Computation: $0111_2 + 1100_2 + 1 = 10011_2 + 1 = 10100_2$.
• Lower 4 bits: $0100_2 = +4_{10}$.
• Carry-out = 1 (in two’s complement subtraction, carry-out = 1 indicates no borrow occurred).

Case 2: Positive minus Negative ($5 - (-2) = 7$)

• $A = 5_{10} = 0101_2$.
• $B = -2_{10} = 1110_2$. With $\text{sub} = 1$, $\sim B = 0001_2$ and $C_{\text{in}} = 1$.
• Computation: $0101_2 + 0001_2 + 1 = 0111_2 = +7_{10}$.
• Lower 4 bits: $0111_2 = +7_{10}$.

Case 3: Negative minus Positive ($-4 - 2 = -6$)

• $A = -4_{10} = 1100_2$.
• $B = 2_{10} = 0010_2$. With $\text{sub} = 1$, $\sim B = 1101_2$ and $C_{\text{in}} = 1$.
• Computation: $1100_2 + 1101_2 + 1 = 11001_2 + 1 = 11010_2$.
• Lower 4 bits: $1010_2 = -8 + 2 = -6_{10}$.

Hardware Overflow Detection

Signed overflow occurs when an operation produces a result outside the representable $N$-bit signed range ($[-2^{N-1}, 2^{N-1}-1]$).

In hardware, signed overflow ($V$) is evaluated with a single XOR gate comparing the carry entering the sign bit ($C_{N-1}$) with the carry leaving the sign bit ($C_N$):

Equivalently, overflow occurs if two operands with identical signs produce a result with an inverted sign:

How Division Reduces to Subtractions and Reciprocal Multiplications

Unlike multiplication, which generates all partial product rows simultaneously in parallel, division has an inherent sequential dependency: you cannot know the next quotient digit until you determine whether the current remainder is non-negative.

In hardware, division is evaluated through two distinct architectural paradigms:

1. Digit Recurrence: Restoring, Non-Restoring, and SRT

Digit recurrence computes one quotient bit (or a small radix digit) per clock cycle by repeatedly shifting the dividend and testing subtractions against the divisor $D$:

• Restoring Division: At each cycle, the partial remainder $R$ is shifted left by 1 bit, and the divisor is subtracted: $R' = 2R - D$. If $R' \ge 0$, the quotient bit is 1, and $R'$ becomes the new remainder. If $R' < 0$, the subtraction was invalid: the quotient bit is 0, and the circuit must restore the previous remainder by adding $D$ back ($R = R' + D$). The hardware performs a subtraction followed by a conditional addition.
• Non-Restoring Division: The restoring addition penalty is eliminated by observing that restoring and subsequent shifting is equivalent to shifting the negative remainder and adding the divisor on the following cycle. If $R' < 0$, the quotient bit is 0, and the next cycle computes $2R' + D$ instead of $2(R' + D) - D$. Every clock cycle executes strictly one addition or one subtraction, avoiding the restore cycle.
• SRT Division (Sweeney, Robertson, Tocher): Rather than performing full $N$-bit subtractions to test signs, SRT uses a redundant signed digit set for the quotient (such as $\{-1, 0, +1\}$ in Radix-2, or $\{-2, -1, 0, +1, +2\}$ in Radix-4). The hardware inspects only the leading 3 or 4 bits of the partial remainder and divisor. If the leading bits show that the remainder is sufficiently close to zero, the quotient digit is selected as 0, skipping the subtraction/addition entirely and simply shifting.

2. Functional Iteration: Newton-Raphson and Goldschmidt

In high-performance floating-point units, hardware avoids serial digit recurrence by reformulating division as reciprocal multiplication:

The reciprocal $1/B$ is calculated using Newton-Raphson iteration to find the zero of $f(x) = \frac{1}{x} - B$:

An initial estimate $x_0$ is fetched from a small lookup table indexed by the leading bits of $B$. Each iteration performs two multiplications and a subtraction. Because Newton-Raphson converges quadratically, the number of correct bits doubles on every iteration ($8 \to 16 \to 32 \to 64$), requiring only 3 or 4 iterations for 64-bit precision.

Through functional iteration, division transforms entirely into parallel multiplications, which in turn collapse into the compressor trees and prefix adders discussed next.

Carry Propagation in Basic Adders

Adding two $N$-bit numbers produces a sum vector $S$ and a carry-out $C_{\text{out}}$. At each bit position $i$, a 1-bit Full Adder evaluates:

Bit 0                Bit 1                Bit 2                       Bit N-1
[ Full Adder ] ----> [ Full Adder ] ----> [ Full Adder ] ----> ... -> [ Full Adder ] ----> Cout
      |                    |                    |                           |
    Sum[0]               Sum[1]               Sum[2]                      Sum[N-1]

Ripple-Carry Adder Mechanics and Latency

In a Ripple-Carry Adder (RCA), the carry out of bit $i$ serves as the carry in to bit $i+1$.

Consider a 4-bit addition of $A = 1101_2$ ($13_{10}$) and $B = 0111_2$ ($7_{10}$) with $C_0 = 0$:

• Bit 0: $A_0=1, B_0=1, C_0=0 \rightarrow S_0 = 1 \oplus 1 \oplus 0 = 0, \quad C_1 = (1 \cdot 1) + 0 \cdot (1 \oplus 1) = 1$.
• Bit 1: $A_1=0, B_1=1, C_1=1 \rightarrow S_1 = 0 \oplus 1 \oplus 1 = 0, \quad C_2 = (0 \cdot 1) + 1 \cdot (0 \oplus 1) = 1$.
• Bit 2: $A_2=1, B_2=1, C_2=1 \rightarrow S_2 = 1 \oplus 1 \oplus 1 = 1, \quad C_3 = (1 \cdot 1) + 1 \cdot (1 \oplus 1) = 1$.
• Bit 3: $A_3=1, B_3=0, C_3=1 \rightarrow S_3 = 1 \oplus 0 \oplus 1 = 0, \quad C_4 = (1 \cdot 0) + 1 \cdot (1 \oplus 0) = 1$.
• Result: $C_4 = 1, S = 0100_2 \rightarrow 10100_2$ ($20_{10}$).

Bit 3 cannot compute its sum or carry-out until the carry has rippled through bits 0, 1, and 2.

If a CMOS Full Adder requires 2 gate delays per carry step (e.g., an AND-OR-INVERT complex gate), an $N$-bit addition takes $2N$ gate delays. For 64-bit vectors, this is 128 gate delays. At a 2 GHz clock rate (a 500 ps cycle budget, allowing roughly 15 to 20 gate delays per pipeline stage), a 64-bit ripple-carry adder cannot resolve within a single clock cycle.

Carry-Skip (Bypass) Adder

A carry generated at bit $i$ only ripples through bit $i+1$ if bit $i+1$ propagates that carry. The propagate condition is:

If four consecutive bits all have $P_i = 1$, any carry entering that 4-bit block passes directly through to the output:

                            +-----------------------------------+
                            |  P0 & P1 & P2 & P3 == 1 (Bypass)  |
                            +-----------------+-----------------+
                                              |
                          +-------------------v-------------------+
                          |                  MUX                  |
                          +-------------------+-------------------+
                                              |
Cin --------> [ 4-bit Ripple Adder ] ---------+--------> Cout

Carry-Skip Traces Across Both Cases

Case 1: Carry Generated Internally (Ripple Path)

• Let $A = 0011_2, B = 0001_2, C_{\text{in}} = 0$.
• Propagate signals: $P = [0, 0, 1, 0]$.
• Because $P_0 \cdot P_1 \cdot P_2 \cdot P_3 = 0$, the bypass condition is false.
• Bit 0 generates a carry ($G_0 = 1$), which ripples through Bit 1 to produce the local carry-out. The multiplexer selects the ripple output.

Case 2: All Bits Propagate (Bypass Path Active)

• Let $A = 1010_2, B = 0101_2, C_{\text{in}} = 1$.
• Propagate signals: $P_0 = 1 \oplus 0 = 1$, $P_1 = 0 \oplus 1 = 1$, $P_2 = 1 \oplus 0 = 1$, $P_3 = 0 \oplus 1 = 1$.
• The bypass condition $P_3 \cdot P_2 \cdot P_1 \cdot P_0 = 1$ evaluates to true.
• The 2:1 multiplexer selects $C_{\text{in}}$ directly, forwarding the incoming carry to $C_{\text{out}}$ in 2 gate delays instead of waiting for 8 ripple gate delays.

Carry-Select Adder

Carry-Select adders use hardware redundancy to eliminate the ripple wait time across block boundaries. The adder is partitioned into blocks (e.g., two 16-bit blocks in a 32-bit adder). The lower block computes its sum and carry-out normally.

The upper 16-bit block is instantiated twice:

• One sub-adder calculates the sum assuming $C_{\text{in}} = 0$.
• One sub-adder calculates the sum assuming $C_{\text{in}} = 1$.

                    Upper Block [31:16]                 Upper Block [31:16]
                    +--------------------+              +--------------------+
                    |  Adder (Cin = 0)   |              |  Adder (Cin = 1)   |
                    +---------+----------+              +---------+----------+
                              |                                   |
Lower Block [15:0]            |        +-----------------+        |
+--------------------+        +------->|   2:1 MUX (Sum) |<-------+
|    16-bit Adder    |                 +--------+--------+
+---------+----------+                          |
          |                                     v
          +--- Cout [15] (Select) ---------> Final Sum [31:16]

When the lower block produces its carry-out, that single bit drives multiplexers that select between the precomputed results. The latency scales as $O(\sqrt{N})$, at the expense of roughly 50% higher area and power.

Parallel Prefix Adders

To achieve logarithmic latency ($O(\log_2 N)$), digital arithmetic formulates carry computation as a prefix tree.

From Carry-Lookahead to Parallel Prefix

In a standard Carry-Lookahead Adder (CLA), carries are expressed using Generate ($G_i = A_i \cdot B_i$) and Propagate ($P_i = A_i \oplus B_i$):

Traditional CLA blocks stop at 4 bits because gate fan-in in CMOS is physically limited: gates with more than 4 inputs suffer severe RC delays due to stacked PMOS or NMOS transistors.

Parallel prefix adders overcome this fan-in limit by grouping terms hierarchically using the associative prefix operator $\circ$:

Where:

The operator $\circ$ is strictly associative:

Because the operator is associative, carries can be evaluated using balanced parallel binary trees rather than serial ripple chains. Once all group carries $C_i = G_{i-1:0}$ are known, the final sum bits are generated in parallel:

Prefix Tree Cell Types

Parallel prefix networks are constructed using two basic building blocks:

        Black Cell (BC)                             Gray Cell (GC)
     (G_hi, P_hi)  (G_lo, P_lo)                  (G_hi, P_hi)   G_lo
          \              /                            \          /
           \            /                              \        /
       +--------------------+                      +--------------------+
       |  G = G_hi|P_hi&G_lo|                      |  G = G_hi|P_hi&G_lo|
       |  P = P_hi & P_lo   |                      +---------+----------+
       +---------+----------+                                |
                 |                                           v
              (G, P)                                         G

• Black Cell (BC): Computes both group generate $G$ and group propagate $P$. It is used at all internal nodes whose outputs feed downstream prefix stages.
• Gray Cell (GC): Computes only group generate $G$. It is used at the terminal nodes of the tree to produce the final carry bit $C_i$. Because that carry directly drives the final sum XOR gate, the group propagate is never needed. Omitting the propagate logic saves an AND gate per terminal position.

Architectural Topologies Explained

Prefix adders differ in how they route connections between cells across stages.

       Logic Depth
          ^
          |      [ Brent-Kung ]  (Low area, low tracks, high depth: 2*log2(N) - 1)
          |
          |      [ Han-Carlson ] (Hybrid: log2(N) + 1 depth, balanced wiring)
          |
          |      [ Kogge-Stone ] (Min depth: log2(N), max tracks, low fan-out)
          |      [ Sklansky ]    (Min depth: log2(N), min tracks, HIGH fan-out: N/2)
          +-----------------------------------------------------------------------> Wiring Density

1. Kogge-Stone Adder

• The Concept: At every stage $j$ (where span $= 2^{j-1}$), every bit column $i$ looks back by $2^{j-1}$ positions and combines with that column. No single cell broadcasts to multiple columns; every column computes its own prefix terms in parallel.
• Depth: $\log_2 N$ (minimum possible depth; 3 stages for 8 bits, 6 stages for 64 bits).
• Fan-out: Fixed at 2 at every stage.
• Wiring Density: High ($O(N \log_2 N)$ total wiring tracks). The regular overlapping diagonal wires cause routing congestion in dense standard-cell layouts.

Bit:       7       6       5       4       3       2       1       0
Inputs:  (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)
           |       |       |       |       |       |       |       |
Stage 1:  [BC]    [BC]    [BC]    [BC]    [BC]    [BC]    [GC]     |  (Span 1: stride 1)
          / |     / |     / |     / |     / |     / |     / |      |
         |  |    |  |    |  |    |  |    |  |    |  |    |  |      |
Stage 2: [BC]   [BC]    [BC]    [BC]    [GC]    [GC]     |  |      |  (Span 2: stride 2)
         /  |   /   |   /   |   /   |   /   |     |      |  |      |
        |   |  |    |  |    |  |    |  |    |     |      |  |      |
Stage 3:[GC]  [GC]    [GC]    [GC]     |    |     |      |  |      |  (Span 4: stride 4)
        /   | /     | /     | /     |  |    |     |      |  |      |
Carries: C7    C6      C5      C4      C3   C2    C1     C0       --

2. Brent-Kung Adder

• The Concept: To minimize area and routing tracks, Brent-Kung does not compute carries for every column at every stage. Instead, it uses a two-phase tree:
  1. Forward Reduction Tree: Computes group terms on powers of two ($2, 4, 8, \dots$) using a binary tree.
  2. Reverse Distribution Tree: Distributes the computed power-of-two carries back down to the intermediate odd columns.
• Depth: $2 \log_2 N - 1$ stages (5 stages for 8 bits, 11 stages for 64 bits).
• Area & Wiring: Minimal ($O(N)$ cells; 126 cells for 64 bits). Routing channels remain clear.

Bit:       7       6       5       4       3       2       1       0
Inputs:  (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)
           |       |       |       |       |       |       |       |
Stage 1:  [BC]     |      [BC]     |      [BC]     |      [GC]     |  (Span 1: pairs)
           |       |       |       |       |       |       |       |
Stage 2:   |       |      [BC]     |       |       |      [GC]     |  (Span 2: quads)
           |       |       |       |       |       |       |       |
Stage 3:  [GC]     |       |       |       |       |       |       |  (Span 4: octets, C7 done)
           |       |       |       |       |       |       |       |
Stage 4:   |       |       |       |      [GC]     |       |       |  (Distribute to C3)
           |       |       |       |       |       |       |       |
Stage 5:   |      [GC]     |      [GC]     |      [GC]     |       |  (Distribute to C5, C4, C2)
           |       |       |       |       |       |       |       |
Carries:  C7      C6      C5      C4      C3      C2      C1      C0

3. Sklansky (Divide-and-Conquer) Adder

• The Concept: Sklansky groups bits into power-of-two blocks and broadcasts the carry of the lower block to all bits of the upper block. Bits [1:0] broadcast to bits [3:2]; then bits [3:0] broadcast to bits [7:4].
• Depth: $\log_2 N$ stages.
• Wiring Density: Low.
• Fan-out Issue: High. Because one node broadcasts to an entire block, at stage $k$ a cell drives $2^{k-1}$ downstream gates. For 64 bits, a single cell at stage 6 must drive 32 loads. In deep-submicron CMOS, high fan-out degrades gate transition time and requires large buffer trees, canceling its speed advantage.

Bit:       7       6       5       4       3       2       1       0
Inputs:  (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)   (G,P)
           |       |       |       |       |       |       |       |
Stage 1:  [BC]     |      [BC]     |      [BC]     |      [GC]     |  (Pairs)
           | \     |       | \     |       | \     |       | \     |
Stage 2:  [BC]    [BC]     |  |    |      [GC]    [GC]     |  |    |  (Broadcast to 2)
           |   \   |   \   |  |    |       |   \   |   \   |  |    |
Stage 3:  [GC]    [GC]    [GC][GC] |       |       |       |  |    |  (Broadcast to 4)
           |       |       |   |   |       |       |       |  |    |
Carries:  C7      C6      C5  C4  C3      C2      C1      C0  --

4. Han-Carlson Hybrid Adder

• The Concept: A hybrid bridging Kogge-Stone and Brent-Kung:
  1. Decimation: The first stage evaluates Generate and Propagate terms only on even bit positions ($0, 2, 4, 6, \dots$).
  2. Kogge-Stone Core: Computes prefix carries across the even bits using a Kogge-Stone network. Halving the active columns cuts routing tracks by 50%.
  3. Interpolation: A final stage distributes the computed even carries into the odd bit positions.
• Depth: $\log_2 N + 1$ stages (4 stages for 8 bits, 7 stages for 64 bits, just 1 stage more than Kogge-Stone).
• Area & Wiring: Uses roughly half the cells and half the horizontal wiring tracks of a pure Kogge-Stone adder. For 64-bit ALUs, Han-Carlson is the standard industrial choice.

Step-by-Step 8-Bit Prefix Addition Example

Let $A = 10110110_2$ ($182_{10}$) and $B = 01101101_2$ ($109_{10}$) with $C_0 = 0$.

1. Compute Base Generate ($G_i$) and Propagate ($P_i$)

• $A$: 1 0 1 1 0 1 1 0
• $B$: 0 1 1 0 1 1 0 1
• Bit index: 7 6 5 4 3 2 1 0

Evaluate bitwise:

• $G = A \cdot B$: [G7=0, G6=0, G5=1, G4=0, G3=0, G2=1, G1=0, G0=0]
• $P = A \oplus B$: [P7=1, P6=1, P5=0, P4=1, P3=1, P2=0, P1=1, P0=1]

2. Stage 1 (Span 1: combine bit $i$ with bit $i-1$)

Using $(G_{i:i-1}, P_{i:i-1}) = (G_i + P_i \cdot G_{i-1}, P_i \cdot P_{i-1})$:

• Bit 0: $(G_0, P_0) = (0, 1)$
• Bit 1: $(G_{1:0}, P_{1:0}) = (G_1 + P_1 G_0, P_1 P_0) = (0 + 1 \cdot 0, 1 \cdot 1) = (0, 1) \rightarrow C_1 = 0$
• Bit 2: $(G_{2:1}, P_{2:1}) = (G_2 + P_2 G_1, P_2 P_1) = (1 + 0 \cdot 0, 0 \cdot 1) = (1, 0)$
• Bit 3: $(G_{3:2}, P_{3:2}) = (G_3 + P_3 G_2, P_3 P_2) = (0 + 1 \cdot 1, 1 \cdot 0) = (1, 0)$
• Bit 4: $(G_{4:3}, P_{4:3}) = (G_4 + P_4 G_3, P_4 P_3) = (0 + 1 \cdot 0, 1 \cdot 1) = (0, 1)$
• Bit 5: $(G_{5:4}, P_{5:4}) = (G_5 + P_5 G_4, P_5 P_4) = (1 + 0 \cdot 0, 0 \cdot 1) = (1, 0)$
• Bit 6: $(G_{6:5}, P_{6:5}) = (G_6 + P_6 G_5, P_6 P_5) = (0 + 1 \cdot 1, 1 \cdot 0) = (1, 0)$
• Bit 7: $(G_{7:6}, P_{7:6}) = (G_7 + P_7 G_6, P_7 P_6) = (0 + 1 \cdot 0, 1 \cdot 1) = (0, 1)$

3. Stage 2 (Span 2: combine with node 2 positions to the right)

• Bit 2 combines with Bit 0: $G_{2:0} = G_{2:1} + P_{2:1} \cdot G_0 = 1 + 0 \cdot 0 = 1 \rightarrow C_2 = 1$.
• Bit 3 combines with Bit 1: $G_{3:0} = G_{3:2} + P_{3:2} \cdot G_{1:0} = 1 + 0 \cdot 0 = 1 \rightarrow C_3 = 1$.
• Bit 4 combines with Bit 2: $(G_{4:1}, P_{4:1}) = (G_{4:3} + P_{4:3} G_{2:1}, P_{4:3} P_{2:1}) = (0 + 1 \cdot 1, 1 \cdot 0) = (1, 0)$.
• Bit 5 combines with Bit 3: $(G_{5:2}, P_{5:2}) = (G_{5:4} + P_{5:4} G_{3:2}, P_{5:4} P_{3:2}) = (1 + 0 \cdot 1, 0 \cdot 0) = (1, 0)$.
• Bit 6 combines with Bit 4: $(G_{6:3}, P_{6:3}) = (G_{6:5} + P_{6:5} G_{4:3}, P_{6:5} P_{4:3}) = (1 + 0 \cdot 0, 0 \cdot 1) = (1, 0)$.
• Bit 7 combines with Bit 5: $(G_{7:4}, P_{7:4}) = (G_{7:6} + P_{7:6} G_{5:4}, P_{7:6} P_{5:4}) = (0 + 1 \cdot 1, 1 \cdot 0) = (1, 0)$.

4. Stage 3 (Span 4: combine with node 4 positions to the right)

• Bit 4 combines with Bit 0: $G_{4:0} = G_{4:1} + P_{4:1} \cdot G_0 = 1 + 0 \cdot 0 = 1 \rightarrow C_4 = 1$.
• Bit 5 combines with Bit 1: $G_{5:0} = G_{5:2} + P_{5:2} \cdot G_{1:0} = 1 + 0 \cdot 0 = 1 \rightarrow C_5 = 1$.
• Bit 6 combines with Bit 2: $G_{6:0} = G_{6:3} + P_{6:3} \cdot G_{2:0} = 1 + 0 \cdot 1 = 1 \rightarrow C_6 = 1$.
• Bit 7 combines with Bit 3: $G_{7:0} = G_{7:4} + P_{7:4} \cdot G_{3:0} = 1 + 0 \cdot 1 = 1 \rightarrow C_7 = 1$.

Carries resolved: $C = [C_7=1, C_6=1, C_5=1, C_4=1, C_3=1, C_2=1, C_1=0, C_0=0]$.

5. Final Sum Evaluation

• $S_0 = P_0 \oplus C_0 = 1 \oplus 0 = 1$
• $S_1 = P_1 \oplus C_1 = 1 \oplus 0 = 1$
• $S_2 = P_2 \oplus C_2 = 0 \oplus 1 = 1$
• $S_3 = P_3 \oplus C_3 = 1 \oplus 1 = 0$
• $S_4 = P_4 \oplus C_4 = 1 \oplus 1 = 0$
• $S_5 = P_5 \oplus C_5 = 0 \oplus 1 = 1$
• $S_6 = P_6 \oplus C_6 = 1 \oplus 1 = 0$
• $S_7 = P_7 \oplus C_7 = 1 \oplus 1 = 0$
• Carry Out: $C_{\text{out}} = G_{7:0} = 1$.

Final sum vector: $S = 00100111_2$, with $C_{\text{out}} = 1$. Combined binary: $100100111_2 = 256 + 32 + 2 + 1 = 291_{10}$. Verifying: $182 + 109 = 291_{10}$.

Why Hardware Multipliers Require Three Stages

Multiplying two $N$-bit numbers creates an $N \times N$ matrix of partial product bits. For a 64-bit multiplication, that is 4,096 bits arranged in columns up to 64 bits deep.

No logic gate can sum 64 inputs at once. If you sum them row by row using standard adders, every row addition forces carries to ripple across the entire width, producing an unusable $O(N^2)$ delay.

To make multiplication fast in silicon, the problem must be broken into three distinct stages, each solving one physical bottleneck:

• Row Reduction (Stage 1): Before placing any adders, shrink the height of the matrix. By inspecting groups of multiplier bits with Booth recoding, we cut the number of rows in half (from $N$ to $N/2$) using only hardwired shifts and multiplexers.
• Column Compression (Stage 2): Now you have a tall matrix of $N/2$ rows that must be squashed down without waiting for carries to ripple horizontally. Carry-save compressors sum columns vertically in parallel, passing carries down to the next level with zero horizontal ripple delay. This compression continues until the matrix reaches the absolute minimum height that can represent an unmerged sum: exactly two vectors.
• Vector Merging (Stage 3): You are left with two numbers: a Sum vector and a Carry vector. At this point, horizontal carry propagation can no longer be avoided. Those final two rows are fed into a wide, high-speed carry-propagate adder (such as a Han-Carlson or Kogge-Stone tree) to produce the final single binary product.

+-----------------------------------------------------------------------------------+
|                        Three-Stage Hardware Multiplier Pipeline                   |
+-----------------------------------------------------------------------------------+
|  [ Stage 1: Partial Product Generation ]                                          |
|  Radix-4 Booth recoding reduces row count from N to N/2                           |
|                               |                                                   |
|                               v  (N/2 rows of partial products)                   |
|  [ Stage 2: Partial Product Compression ]                                         |
|  Wallace / Dadda tree or 4:2 compressor slices reduce matrix to 2 vectors         |
|                               |                                                   |
|                               v  (Sum vector and Carry vector)                    |
|  [ Stage 3: Vector Merging ]                                                      |
|  Parallel Prefix Carry-Propagate Adder (Han-Carlson / Kogge-Stone)                |
|                               |                                                   |
|                               v                                                   |
|  Final Product P [2N-1:0]                                                         |
+-----------------------------------------------------------------------------------+

Stage 1: Partial Product Generation and Radix-4 Booth Encoding

In basic unsigned multiplication, multiplying an $N$-bit multiplicand $X$ by an $N$-bit multiplier $Y$ produces $N$ partial product rows:

For 64-bit operands, that produces 64 rows (4,096 bit terms).

Radix-4 Recoding Mechanics

Booth recoding exploits runs of ones in binary numbers. In decimal, $99 \times X$ is computed as $(100 - 1) \times X$. In binary, a sequence of ones like 011110 ($30_{10}$) equals $2^5 - 2^1 = 32 - 2$. Four additions collapse into one subtraction and one addition.

Radix-4 Modified Booth recoding inspects three bits of the multiplier at a time with one bit of overlap: $(Y_{2i+1}, Y_{2i}, Y_{2i-1})$, with $Y_{-1} = 0$.

Each 3-bit window represents a value between $-2$ and $+2$:

Gate-Level Booth Encoder and Selector

Hardware implements Booth recoding using an encoder and a multiplexing selector:

   Y[2i+1] Y[2i] Y[2i-1]
      \      |      /
    +-----------------+
    |  Booth Encoder  | ----> single = (Y[2i] ^ Y[2i-1])
    +-----------------+ ----> double = (Y[2i+1] & ~Y[2i] & ~Y[2i-1]) | (~Y[2i+1] & Y[2i] & Y[2i-1])
             |          ----> neg    = Y[2i+1]
             v
    +-----------------+
    |  Booth Selector | <---- Multiplicand X
    +-----------------+
             |
             v  PP[i] = (X & single) | ((X << 1) & double);  if (neg) PP[i] = ~PP[i]
      Partial Product

Radix-4 requires only shifts and bit inversions:

• Multiplying by $2X$ is a 1-bit hardwired shift.
• Negation is bitwise inversion plus adding $1$ in the compression stage.

Radix-8 inspects 4 bits and cuts rows to $N/3$, but requires $+3X$ ($2X + 1X$). Generating $3X$ requires a dedicated carry-propagate addition before multiplication can begin. In integer ALUs, this serial addition penalty usually outweighs the reduction in row count.

Step-by-Step Walkthroughs Across All Four Sign Combinations

To demonstrate how Booth recoding handles signed multiplication natively, consider 8-bit operands $X = 25_{10}$ (00011001) and $Y = 13_{10}$ (00001101), with $-X = -25_{10}$ (11100111) and $-Y = -13_{10}$ (11110011).

Case 1: Positive $ imes$ Positive ($+25 imes +13 = +325$)

• $X = 00011001_2$ ($+25_{10}$).
• $Y = 00001101_2$ ($+13_{10}$), padded with $Y_{-1} = 0$: 0 0 0 0 1 1 0 1 0.
• Groups:
  • $(Y_1, Y_0, Y_{-1}) = (0, 1, 0) \rightarrow +1 \times X$
  • $(Y_3, Y_2, Y_1) = (1, 1, 0) \rightarrow -1 \times X$
  • $(Y_5, Y_4, Y_3) = (0, 0, 1) \rightarrow +1 \times X$
  • $(Y_7, Y_6, Y_5) = (0, 0, 0) \rightarrow 0 \times X$
• Row evaluation:
  • Row 0 (weight $2^0$): $+1 \times 25 = +25$
  • Row 1 (weight $2^2$): $-1 \times 25 \times 4 = -100$
  • Row 2 (weight $2^4$): $+1 \times 25 \times 16 = +400$
  • Row 3 (weight $2^6$): $0$
• Sum: $+25 - 100 + 400 + 0 = +325_{10}$.

Case 2: Positive $ imes$ Negative ($+25 imes -13 = -325$)

• $X = 00011001_2$ ($+25_{10}$).
• $Y = 11110011_2$ ($-13_{10}$), padded with $Y_{-1} = 0$: 1 1 1 1 0 0 1 1 0.
• Groups:
  • $(Y_1, Y_0, Y_{-1}) = (1, 1, 0) \rightarrow -1 \times X$
  • $(Y_3, Y_2, Y_1) = (0, 0, 1) \rightarrow +1 \times X$
  • $(Y_5, Y_4, Y_3) = (1, 1, 0) \rightarrow -1 \times X$
  • $(Y_7, Y_6, Y_5) = (1, 1, 1) \rightarrow 0 \times X$
• Row evaluation:
  • Row 0 (weight $2^0$): $-1 \times 25 = -25$
  • Row 1 (weight $2^2$): $+1 \times 25 \times 4 = +100$
  • Row 2 (weight $2^4$): $-1 \times 25 \times 16 = -400$
  • Row 3 (weight $2^6$): $0$
• Sum: $-25 + 100 - 400 + 0 = -325_{10}$.

Case 3: Negative $ imes$ Positive ($-25 imes +13 = -325$)

• $X = 11100111_2$ ($-25_{10}$).
• $Y = 00001101_2$ ($+13_{10}$), padded with $Y_{-1} = 0$: 0 0 0 0 1 1 0 1 0.
• Groups:
  • $(Y_1, Y_0, Y_{-1}) = (0, 1, 0) \rightarrow +1 \times X$
  • $(Y_3, Y_2, Y_1) = (1, 1, 0) \rightarrow -1 \times X$
  • $(Y_5, Y_4, Y_3) = (0, 0, 1) \rightarrow +1 \times X$
  • $(Y_7, Y_6, Y_5) = (0, 0, 0) \rightarrow 0 \times X$
• Row evaluation:
  • Row 0 (weight $2^0$): $+1 \times (-25) = -25$
  • Row 1 (weight $2^2$): $-1 \times (-25) \times 4 = +100$
  • Row 2 (weight $2^4$): $+1 \times (-25) \times 16 = -400$
  • Row 3 (weight $2^6$): $0$
• Sum: $-25 + 100 - 400 + 0 = -325_{10}$.

Case 4: Negative $ imes$ Negative ($-25 imes -13 = +325$)

• $X = 11100111_2$ ($-25_{10}$).
• $Y = 11110011_2$ ($-13_{10}$), padded with $Y_{-1} = 0$: 1 1 1 1 0 0 1 1 0.
• Groups:
  • $(Y_1, Y_0, Y_{-1}) = (1, 1, 0) \rightarrow -1 \times X$
  • $(Y_3, Y_2, Y_1) = (0, 0, 1) \rightarrow +1 \times X$
  • $(Y_5, Y_4, Y_3) = (1, 1, 0) \rightarrow -1 \times X$
  • $(Y_7, Y_6, Y_5) = (1, 1, 1) \rightarrow 0 \times X$
• Row evaluation:
  • Row 0 (weight $2^0$): $-1 \times (-25) = +25$
  • Row 1 (weight $2^2$): $+1 \times (-25) \times 4 = -100$
  • Row 2 (weight $2^4$): $-1 \times (-25) \times 16 = +400$
  • Row 3 (weight $2^6$): $0$
• Sum: $+25 - 100 + 400 + 0 = +325_{10}$.

Notice that across all four sign permutations, the identical hardware multiplexer and Booth encoder produce the exact mathematical result without requiring external sign-magnitude conversion wrappers.

Internalizing Signed Arithmetic and Sign Extension Handling

When designing a signed multiplier, a naive instinct might be to take an existing unsigned multiplier, strip the signs at the inputs with negators ($|A| = \sim A + 1, |B| = \sim B + 1$), run the multiplication, and conditionally negate the output product. However, placing three full carry-propagate adders outside the multiplier roughly triples critical path latency and inflates area.

Instead, signed arithmetic is internalized directly into the partial product matrix by deriving the algebraic expansion of two’s complement multiplication.

Let $A$ and $B$ be signed numbers with negative MSB weights:

Multiplying $A$ by $B$ produces:

Notice what this equation reveals:

• The first term is identical to standard unsigned partial products ($a_i b_j$), generated with AND gates.
• The fourth term is a positive product of the two sign bits ($a_{N-1} b_{M-1}$), generated with an AND gate.
• The second and third terms are negatively weighted cross-terms: $-2^{N-1} a_{N-1} b_j$ and $-2^{M-1} b_{M-1} a_i$.

To sum these negative cross-terms in an adder tree of positive full adders, we apply the identity $-X = \sim X + 1 - 2^k$. By replacing the AND gates for the sign-cross terms with NAND gates (which compute $\sim(a_{N-1} b_j)$ and $\sim(b_{M-1} a_i)$), and adding fixed constant $1$s into specific weight columns, the entire matrix becomes positive additions.

Furthermore, in signed two’s complement multiplication, naively sign-extending every row to $2N$ bits creates an area-intensive triangle of sign bits:

Row 0:   S0  S0  S0  S0  S0  S0  S0  S0  P0_7 P0_6 P0_5 P0_4 P0_3 P0_2 P0_1 P0_0
Row 1:       S1  S1  S1  S1  S1  S1  P1_7 P1_6 P1_5 P1_4 P1_3 P1_2 P1_1 P1_0
Row 2:           S2  S2  S2  S2  P2_7 P2_6 P2_5 P2_4 P2_3 P2_2 P2_1 P2_0
Row 3:               S3  S3  P3_7 P3_6 P3_5 P3_4 P3_3 P3_2 P3_1 P3_0

The Baugh-Wooley algebraic transformation eliminates this sign triangle. The sign extension bits can be rewritten as:

In hardware, this means:

• Invert the sign bit of each partial product row ($S \rightarrow \sim S$).
• Place a constant $1$ above the first inverted sign bit, and add constant $1$s at specific offset positions.
• The sign extension triangle disappears, replaced by two bits per row:

Row 0:   0   1  ~S0 P0_7 P0_6 P0_5 P0_4 P0_3 P0_2 P0_1 P0_0
Row 1:       1  ~S1 P1_7 P1_6 P1_5 P1_4 P1_3 P1_2 P1_1 P1_0
Row 2:          ~S2 P2_7 P2_6 P2_5 P2_4 P2_3 P2_2 P2_1 P2_0
Row 3:          ~S3 P3_7 P3_6 P3_5 P3_4 P3_3 P3_2 P3_1 P3_0

Unified Sign Mode Support in RISC-V and ARM ALUs

Modern processors must support four multiplication instructions in the same execution unit: MUL/MULH (signed $\times$ signed), MULHU (unsigned $\times$ unsigned), and MULHSU (signed $\times$ unsigned).

Rather than building separate multiplier arrays, industrial ALUs extend the operands by 1 bit:

wire signed_a = (mode == SIGNED_SIGNED) || (mode == SIGNED_UNSIGNED);
wire signed_b = (mode == SIGNED_SIGNED);

// If signed mode, sign-extend MSB; if unsigned mode, zero-extend
wire [N:0] ext_a = {signed_a & a[N-1], a};
wire [N:0] ext_b = {signed_b & b[N-1], b};

// Feed ext_a and ext_b into a single unified (N+1) x (N+1) signed core
wire [2N+1:0] full_product = ext_a_signed * ext_b_signed;

A single $(N+1) \times (N+1)$ signed multiplier core evaluates all four instruction modes natively with no external adder overhead.

Stage 2: Partial Product Reduction with Compressor Trees

Once Radix-4 Booth generates the $N/2$ rows, they must be compressed down to two vectors without rippling carries.

Carry-Save Addition (3:2 Compression)

A Full Adder functions as a 3:2 compressor: it takes three bits of weight $2^k$ and outputs:

• One Sum bit of weight $2^k$.
• One Carry bit of weight $2^{k+1}$.

      X (2^k)    Y (2^k)    Z (2^k)
         \          |          /
          \         |         /
        +-----------------------+
        |   3:2 Full Adder      |
        +-----------+-----------+
                   / \
                  /   \
                 /     \
       Carry (2^k+1)   Sum (2^k)

The carry bit does not ripple across the vector; it simply steps down to the next column in the next tree stage. The compression delay is constant: 2 gate delays ($O(1)$ time).

Wallace Tree Reduction Schedule

A Wallace tree applies 3:2 compressors greedily to every available group of 3 bits in a column at each stage:

Bit Column:        5   4   3   2   1   0
Initial Height 4:  *   *   *   *   *   *
                   *   *   *   *   *   *
                   *   *   *   *   *   *
                   *   *   *   *   *   *
----------------------------------------
Stage 1 Reduction (Compress groups of 3 with FA, pairs with HA):
Columns height 4 -> compressed to height 3
Stage 2 Reduction:
Columns height 3 -> compressed to height 2
----------------------------------------
Final State: Exactly 2 rows (Sum vector and Carry vector)

Dadda Tree Reduction Schedule

A Dadda tree reduces the number of adders by working backwards from a target height sequence:

Unlike Wallace’s greedy strategy, Dadda only compresses columns that exceed the target height for that stage:

Target Sequence: 2 <- 3 <- 4 <- 6 <- 9

For an initial height of 6:
Level 0: Target height = 4. Compress only columns taller than 4.
Level 1: Target height = 3. Compress only columns taller than 3.
Level 2: Target height = 2. Compress to final 2 rows.

Wallace and Dadda achieve the same logic depth. However, because Dadda does not compress bits prematurely, it requires fewer Full Adders and Half Adders, reducing total gate area.

4:2 Compressor Architecture and Gate-Level Logic

In deep-submicron ASIC silicon, 3:2 Wallace trees produce irregular 3D routing networks that create severe routing congestion.

Modern commercial datapaths use 4:2 compressor slices:

           X1   X2   X3   X4  (Inputs of weight 2^k)
            \    |    |    /
          +-----------------+
Cin ----->|  4:2 Compressor |-----> Cout (To bit slice k+1)
          +--------+--------+
                  / \
                 /   \
      Carry (2^k+1)  Sum (2^k)

A 4:2 compressor accepts four inputs of weight $2^k$, plus an internal carry-in ($C_{\text{in}}$) from the adjacent less significant bit slice. It produces:

• A Sum bit of weight $2^k$.
• A Carry bit of weight $2^{k+1}$.
• An internal carry-out ($C_{\text{out}}$) sent to the adjacent more significant bit slice.

Gate-Level Logic Equations

The Structural Independence Property: Note that $C_{\text{out}}$ depends exclusively on inputs $X_1, X_2, X_3$, and $X_4$. It is independent of $C_{\text{in}}$.

Because $C_{\text{out}}$ does not depend on $C_{\text{in}}$, there is zero horizontal carry rippling across the compressor array. This enables 4:2 compressors to be tiled into regular, rectangular bit-slice layouts with predictable parasitic wiring capacitance.

FPGA Arithmetic: Dedicated Carry Chains and Hard DSP Slices

FPGAs are composed of Configurable Logic Blocks (CLBs) containing Look-Up Tables (LUTs) and general-purpose switch-box routing. Switch-box interconnects introduce substantial RC delays (typically 200 to 400 picoseconds per routing hop).

Because of this, standard ASIC arithmetic structures perform poorly if mapped directly to FPGA LUTs.

Hard Carry Chains (CARRY4 and CARRY8)

To support fast addition, FPGA vendors embed dedicated, hardwired carry chains into every logic slice:

• AMD / Xilinx 7-Series: CARRY4 primitive (4 bits per slice).
• AMD / Xilinx UltraScale / UltraScale+: CARRY8 primitive (8 bits per slice).
• Intel Cyclone / Stratix: Dedicated carry chains inside Adaptive Logic Modules (ALMs).

+-----------------------------------------------------------------------------------+
|                        Xilinx CARRY4/CARRY8 Internal Structure                    |
+-----------------------------------------------------------------------------------+
|                                                                                   |
|  LUT6 (Propagate) ----> [ S MUX ] <----+ Dedicated Carry In (from slice below)    |
|                           |            |                                          |
|  LUT6 (Generate)  --------+            |                                          |
|                           v            |                                          |
|  Dedicated Hard Wire ---> Carry Out ---+ Dedicated Carry Out (to slice above)     |
|                           |                                                       |
|                           v                                                       |
|  Sum Bit <------------- [ XORCY ]                                                 |
+-----------------------------------------------------------------------------------+

These primitives feature dedicated hard multiplexers (MUXCY) and XOR gates (XORCY) connected by private vertical silicon routes that bypass the programmable routing fabric entirely.

The propagation delay through a hard carry line is 10 to 25 picoseconds per bit. A 32-bit addition implemented on a hard carry chain resolves in roughly 1.2 nanoseconds.

Why Prefix Adders Underperform Dedicated Carry Chains on FPGAs

When a designer synthesizes a hand-coded Kogge-Stone or Han-Carlson adder on an FPGA:

• The synthesis tool cannot map the non-linear prefix routing tree onto the dedicated vertical carry chain.
• The prefix network is mapped into general-purpose 6-LUTs.
• Signals must traverse the general-purpose programmable routing fabric.

The hand-coded Kogge-Stone adder ends up two to three times slower than a simple ripple adder written with standard HDL operators:

// Recommended FPGA implementation: maps directly to CARRY4/CARRY8
assign {cout, sum} = a + b + cin;

Dedicated Hard DSP Blocks (DSP48E1 / DSP48E2)

FPGAs handle high-speed multiplication using dedicated silicon DSP tiles (such as the Xilinx DSP48E2):

A [26:0] ---> [ Pre-Adder ] ---> [ 27x18 Multiplier ] ---> [ 48-bit ALU / Acc ] ---> P [47:0]
D [26:0] --------^                     ^
B [17:0] ------------------------------+

A single DSP48E2 primitive contains:

• A $27 \times 18$ signed two’s complement multiplier.
• A 27-bit input pre-adder.
• A 48-bit accumulator and logic unit.
• Dedicated pipeline registers supporting clock frequencies above 700 MHz without utilizing any LUT logic.

Soft-logic multipliers constructed from LUTs and compressor trees are typically used only when:

• All hardware DSP tiles are exhausted.
• Multiplying by small constants that can be factored into a single LUT shift-and-add using Canonical Signed Digit (CSD) encoding.

Architectural Tradeoffs and Implementation Summary

References

• Brent, R. P., & Kung, H. T. (1982). A Regular Layout for Parallel Adders. IEEE Transactions on Computers.
• Kogge, P. M., & Stone, H. S. (1973). A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations. IEEE Transactions on Computers.
• Han, T., & Carlson, D. A. (1987). Fast Area-Efficient VLSI Adders. 8th IEEE Symposium on Computer Arithmetic.
• Sklansky, J. (1960). Conditional-Sum Addition Logic. IRE Transactions on Electronic Computers.
• Wallace, C. S. (1964). A Suggestion for a Fast Multiplier. IEEE Transactions on Electronic Computers.
• Dadda, L. (1965). Some Schemes for Parallel Multipliers. Alta Frequenza.
• Booth, A. D. (1951). A Signed Binary Multiplication Technique. The Quarterly Journal of Mechanics and Applied Mathematics.
• Baugh, C. R., & Wooley, B. A. (1973). A Two’s Complement Parallel Array Multiplication Algorithm. IEEE Transactions on Computers.
• AMD / Xilinx. UltraScale Architecture DSP48E2 User Guide (UG579) and 7 Series FPGAs CLB User Guide (UG474).
• Parhami, B. (2000). Computer Arithmetic: Algorithms and Hardware Designs. Oxford University Press.