L15: Adders

Faster ways to do addition.

Objective
Practice usage of theorems 5-17 of Boolean algebra.

Additional Materials & Formats
Check Box for the most up-to-date versions of this lecture’s materials.

Before the Lecture

Required Textbook Reading:

• 3.4 (Fast Adders)

Optional Supplemental Instruction:

• x

Verilog Examples
The example code is for reference only. We’ll cover Verilog implementations in more detail in L17.

Recall Basic Adder Building Blocks

To add two $N$-bit binary numbers, we must first understand how to add single bits.

The Half Adder (HA)

A Half Adder takes two 1-bit inputs ($A$ and $B$) and produces two 1-bit outputs: a Sum ($S$) and a Carry-out ($C$). It does not account for a carry-in from a previous stage.

Boolean Equations:

$$S = A \oplus B$$

$$C = AB$$

Verilog Implementation:

module half_adder (
	input  wire A,
	input  wire B,
	output wire S,
	output wire C
);
	assign S = A ^ B;
	assign C = A & B;
endmodule

The Full Adder (FA)

A Full Adder takes three 1-bit inputs ($A$, $B$, and $C_{in}$) and produces a Sum ($S$) and a Carry-out ($C_{out}$). This allows for cascading multiple stages.

Boolean Equations:

$$S = A \oplus B \oplus C_{in}$$

$$C_{out} = AB + C_{in}(A \oplus B) = AB + AC_{in} + BC_{in}$$

Verilog Implementation:

module full_adder (
	input  wire A,
	input  wire B,
	input  wire C_in,
	output wire S,
	output wire C_out
);
	assign S = A ^ B ^ C_in;
	assign C_out = (A & B) | (C_in & (A ^ B));
endmodule

Linear-Time Adder: Ripple Carry Adder (RCA)

To add two $N$-bit numbers, we can chain $N$ Full Adders together by connecting the $C_{out}$ of bit stage $i$ directly to the $C_{in}$ of bit stage $i+1$.

Critical Path Analysis

• The Problem: The carry signal must “ripple” all the way from the least significant bit ($LSB$) to the most significant bit ($MSB$).
• Delay: If each Full Adder takes $t_{carry}$ to produce its carry output, the total carry propagation delay for an $N$-bit adder is:

$$t_{RCA} \approx N \cdot t_{carry}$$

• Time Complexity: $\mathcal{O}(N)$. This is painfully slow for 32-bit or 64-bit architectures!

Verilog Implementation (Parameterized RCA):

module ripple_carry_adder #(
	parameter N = 8
) (
	input  wire [N-1:0] A,
	input  wire [N-1:0] B,
	input  wire         C_in,
	output wire [N-1:0] S,
	output wire         C_out
);
	wire [N:0] C;
	assign C[0] = C_in;

	genvar i;
	generate
		for (i = 0; i < N; i = i + 1) begin : FA_STAGE
			full_adder fa (
				.A    (A[i]),
				.B    (B[i]),
				.C_in (C[i]),
				.S    (S[i]),
				.C_out(C[i+1])
			);
		end
	endgenerate

	assign C_out = C[N];
endmodule

Advanced Designs for Fast Adders

To break the linear delay bottleneck, we must compute carries faster. Here are the prominent architectures used to achieve sub-linear time complexity.

A. Carry Lookahead Adder (CLA)

Instead of waiting for the carry to ripple through every stage, the CLA precomputes the carry signals using two intermediate concepts:

1. Generate ($G_i$): Bit stage $i$ will definitely generate a carry-out if both inputs are 1, regardless of the carry-in.

$$G_i = A_i B_i$$

2. Propagate ($P_i$): Bit stage $i$ will propagate an incoming carry to the next stage if at least one input is 1.

$$P_i = A_i \oplus B_i \quad \text{(or } A_i + B_i\text{)}$$

Using these, the carry-out for any stage can be written without waiting for sequential evaluation:

$$C_1 = G_0 + P_0 C_0$$

$$C_2 = G_1 + P_1 C_1 = G_1 + P_1 G_0 + P_1 P_0 C_0$$

$$C_3 = G_2 + P_2 G_2 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$$

Trade-off: It reduces execution time drastically ($\mathcal{O}(\log N)$), but requires massive amounts of irregular wiring and large-input logic gates as $N$ grows. Practically, CLAs are usually grouped into 4-bit blocks.

Verilog Implementation:

module cla_4bit (
	input  wire [3:0] A,
	input  wire [3:0] B,
	input  wire       C_in,
	output wire [3:0] S,
	output wire       C_out
);
	wire [3:0] G, P;
	wire [4:0] C;

	assign G = A & B;
	assign P = A ^ B;

	assign C[0] = C_in;
	assign C[1] = G[0] | (P[0] & C[0]);
	assign C[2] = G[1] | (P[1] & G[0]) | (P[1] & P[0] & C[0]);
	assign C[3] = G[2] | (P[2] & G[1]) | (P[2] & P[1] & G[0]) | (P[2] & P[1] & P[0] & C[0]);
	assign C[4] = G[3] | (P[3] & G[2]) | (P[3] & P[2] & G[1]) | (P[3] & P[2] & P[1] & G[0]) | (P[3] & P[2] & P[1] & P[0] & C[0]);

	assign S = P ^ C[3:0];
	assign C_out = C[4];
endmodule

B. Carry-Select Adder

The Carry-Select Adder avoids waiting for the true carry-in by anticipating both possibilities.

• How it works: It duplicates the hardware for the upper bits of an adder block. One sub-adder calculates the sum assuming the incoming carry is 0, while the other sub-adder calculates the sum assuming the incoming carry is 1.
• When the real carry-in finally arrives from the lower bits, a multiplexer (MUX) instantly selects the correct precomputed sum.
• Time Complexity: $\mathcal{O}(\sqrt{N})$ when block sizes are optimized.
• Trade-off: High area overhead (nearly double the hardware cost for the duplicated sections).

Verilog Implementation (8-bit, 4+4 split):

module carry_select_adder_8bit (
	input  wire [7:0] A,
	input  wire [7:0] B,
	input  wire       C_in,
	output wire [7:0] S,
	output wire       C_out
);
	// Lower 4 bits (true carry path)
	wire [3:0] s_lo;
	wire       c4;
	cla_4bit lo (
		.A(A[3:0]), .B(B[3:0]), .C_in(C_in),
		.S(s_lo), .C_out(c4)
	);

	// Upper 4 bits precomputed for Cin=0 and Cin=1
	wire [3:0] s_hi0, s_hi1;
	wire       c8_0, c8_1;
	cla_4bit hi0 (
		.A(A[7:4]), .B(B[7:4]), .C_in(1'b0),
		.S(s_hi0), .C_out(c8_0)
	);
	cla_4bit hi1 (
		.A(A[7:4]), .B(B[7:4]), .C_in(1'b1),
		.S(s_hi1), .C_out(c8_1)
	);

	assign S[3:0] = s_lo;
	assign S[7:4] = c4 ? s_hi1 : s_hi0;
	assign C_out  = c4 ? c8_1  : c8_0;
endmodule

C. Carry-Skip (Bypass) Adder

Instead of precomputing every possible sum like the Carry-Select Adder, the Carry-Skip Adder looks for opportunities to fast-forward the carry signal across groups of bits.

• How it works: Bits are divided into blocks. For a 4-bit block, a block-level propagate signal is calculated:

$$P_{block} = P_3 P_2 P_1 P_0$$

• If $P_{block} = 1$, it means a carry entering this block will definitely exit it. A MUX uses $P_{block}$ to skip the carry completely past the 4-bit ripple chain directly to the next block.
• Time Complexity: $\mathcal{O}(\sqrt{N})$.
• Trade-off: Highly efficient alternative that costs far less area than a Carry-Select adder while still beating raw RCA speeds.

Verilog Implementation (8-bit, 4-bit skip blocks):

module carry_skip_adder_8bit (
	input  wire [7:0] A,
	input  wire [7:0] B,
	input  wire       C_in,
	output wire [7:0] S,
	output wire       C_out
);
	// Block 0 ripple (bits 3:0)
	wire [4:0] c0;
	wire [3:0] p0;
	assign c0[0] = C_in;
	assign p0 = A[3:0] ^ B[3:0];

	genvar i;
	generate
		for (i = 0; i < 4; i = i + 1) begin : B0
			assign S[i]    = p0[i] ^ c0[i];
			assign c0[i+1] = (A[i] & B[i]) | (p0[i] & c0[i]);
		end
	endgenerate

	// Skip logic after block 0
	wire p_block0;
	wire c4_ripple, c4_skip;
	assign p_block0 = &p0;
	assign c4_ripple = c0[4];
	assign c4_skip   = p_block0 ? C_in : c4_ripple;

	// Block 1 ripple (bits 7:4)
	wire [4:0] c1;
	wire [3:0] p1;
	assign c1[0] = c4_skip;
	assign p1 = A[7:4] ^ B[7:4];

	generate
		for (i = 0; i < 4; i = i + 1) begin : B1
			assign S[i+4]  = p1[i] ^ c1[i];
			assign c1[i+1] = (A[i+4] & B[i+4]) | (p1[i] & c1[i]);
		end
	endgenerate

	assign C_out = c1[4];
endmodule

Summary Matrix of Adder Performance