Adders and Arithmetic Circuits

Understanding how computers perform basic arithmetic is essential to digital logic design. At the heart of every processor lies a network of circuits that add, subtract, and manipulate binary numbers, forming the foundation for all complex computations.

From Half Adders to Full Addition

The most fundamental arithmetic operation in binary is adding two single bits. A half adder is the circuit that performs this task. It has two inputs, typically labeled $A$ and $B$, and produces two outputs: a Sum bit and a Carry bit. The truth table is straightforward: if $A$ and $B$ are both 0, the Sum is 0 and the Carry is 0. If one input is 1, the Sum is 1 and Carry is 0. Only when both inputs are 1 does the Sum become 0 and the Carry become 1. This directly mirrors binary addition: $1+1=10_2$ (where the 1 is the carry-out). You can implement a half adder with an XOR gate for the Sum output and an AND gate for the Carry output.

However, a half adder is incomplete for multi-bit addition because it cannot account for a carry input from a previous, less significant bit addition. This is where the full adder comes in. A full adder has three inputs: $A$, $B$, and a Carry-In ($C_{in}$). It still produces a Sum and a Carry-Out ($C_{out}$). You can think of it as adding three bits together. The full adder's logic can be implemented by combining two half adders and an OR gate. The Sum is the XOR of $A$, $B$, and $C_{in}$. The $C_{out}$ is true if at least two of the three inputs are 1. This circuit is the essential, indivisible unit for building adders of any width.

Building Multi-Bit Adders: The Ripple Effect

To add binary numbers with multiple bits, you chain full adders together. The simplest method is the ripple-carry adder. In this design, you connect the $C_{out}$ of the full adder for bit position $i$ directly to the $C_{in}$ of the full adder for position $i+1$. The least significant bit's $C_{in}$ is typically tied to 0. The binary numbers $A$ and $B$ are fed in parallel, with each bit pair going to its corresponding full adder.

While logically correct and simple to design, the ripple-carry adder has a major performance flaw: carry propagation delay. Because the $C_{in}$ for a higher-order bit depends on the completion of the addition and carry generation of all lower-order bits, the carry signal must physically "ripple" through the entire chain of gates. For an $n$-bit adder, the worst-case delay is proportional to $n$. This makes ripple-carry adders slow for wide data paths, such as 32 or 64 bits, creating a critical bottleneck in a processor's speed.

Accelerating Addition with Carry-Lookahead

To overcome the speed limitation of ripple-carry adders, engineers developed the carry-lookahead adder (CLA). The key insight is to compute the carry signals for all bits in parallel, rather than waiting for them to ripple sequentially. This is done by deriving the logic for each $C_{out}$ directly from the primary inputs $A$ and $B$, not from the previous carry.

The CLA logic is based on two auxiliary signals generated for each bit position:

• Generate ($G_i$): $G_i=A_i\cdot B_i$. If true, this bit pair generates a carry-out regardless of the carry-in.
• Propagate ($P_i$): $P_i=A_i+B_i$ (or $A_i\oplus B_i$ in some designs). If true, this bit pair will propagate an incoming carry to the next stage.

The carry-out for a given stage can then be expressed as: $$C_{i+1}=G_i+(P_i\cdot C_i)$$ By recursively substituting, you can write $C_1$, $C_2$, $C_3$, and so on, purely as a function of $G_0$, $P_0$, $G_1$, $P_1$, ... and the initial $C_0$. For example: $$C_1=G_0+(P_0\cdot C_0)$$ $$C_2=G_1+(P_1\cdot G_0)+(P_1\cdot P_0\cdot C_0)$$ $$C_3=G_2+(P_2\cdot G_1)+(P_2\cdot P_1\cdot G_0)+(P_2\cdot P_1\cdot P_0\cdot C_0)$$

While this logic becomes very large for many bits, it computes all carries simultaneously after a short gate delay. In practice, CLAs are built in hierarchical groups (e.g., 4-bit lookahead units) that are then connected with ripple or a second level of lookahead, providing an optimal balance between speed and circuit complexity.

Subtraction and the Arithmetic Logic Unit (ALU)

A subtractor circuit can be built similarly to an adder, but a more efficient method leverages existing adder hardware using complement arithmetic. The two's complement representation of a binary number is used for subtraction. To compute $A-B$, the ALU will:

1. Invert all bits of $B$ (finding its one's complement).
2. Add 1 to this value (forming the two's complement of $B$).
3. Add this result to $A$ using a standard adder.

Crucially, this means you don't need a separate subtractor circuit. By placing a multiplexer at the $B$ input of the adder to select either the original $B$ or its two's complement, and by setting the initial $C_{in}$ to 0 (for addition) or 1 (to complete the two's complement for subtraction), the same adder performs both operations. This principle of hardware reuse is central to the ALU organization.

An Arithmetic Logic Unit (ALU) is the core execution unit of a CPU. A basic ALU integrates the adder/subtractor circuit with logic gates (AND, OR, XOR, NOT) and a barrel shifter. A control unit uses a multi-bit operation select line to choose which function (ADD, SUB, AND, OR, etc.) is routed to the output. The adder we've designed is the workhorse for the arithmetic portion of the ALU, handling addition, subtraction, and, by extension, comparison operations (which are essentially subtractions whose result is checked).

Common Pitfalls

1. Confusing Sum and Carry Logic: A frequent error is misremembering which gate produces the Sum output in a half adder. Remember: Sum requires an XOR gate (output 1 when inputs are different), while Carry requires an AND gate (output 1 only when both inputs are 1). Applying this incorrectly will break the fundamental logic of addition.

1. Ignoring Carry Propagation in Timing Analysis: When analyzing circuit timing, it's tempting to only consider a single gate delay. For ripple-carry adders, you must trace the critical path, which is the path the carry signal takes from the least significant bit to the most significant bit's $C_{out}$. Failing to account for this cumulative delay leads to an overly optimistic assessment of the circuit's maximum operating speed.

1. Misapplying Two's Complement for Subtraction: A common mistake when building a subtractor is to forget to add the initial $C_{in}$ of 1 when performing the $A$ plus (two's complement of $B$) operation. The one's complement (inverted bits) plus the forced $C_{in}$ of 1 is what correctly forms the two's complement. Without that +1, the subtraction result will be off by one.

1. Overlooking ALU Integration: Students often design the adder in isolation. The key practical step is understanding how it fits into the broader ALU. This includes how the operation select lines control input multiplexers and the initial carry-in, and how status flags (like Zero, Carry, Overflow) are generated from the adder's outputs for use by the processor's control unit.

Summary

• A half adder adds two bits, producing Sum and Carry outputs, but lacks a carry input, making it insufficient for chaining.
• A full adder adds three bits (two inputs plus a carry-in) and is the essential building block for multi-bit adders like the ripple-carry adder, which suffers from linear carry propagation delay.
• The carry-lookahead adder (CLA) dramatically speeds up addition by computing carry signals in parallel using Generate ($G$) and Propagate ($P$) logic, trading increased gate complexity for reduced delay.
• Subtraction is efficiently performed using the same adder hardware by applying complement arithmetic, specifically by adding the two's complement of the subtrahend.
• These circuits form the arithmetic core of an Arithmetic Logic Unit (ALU), where multiplexers and control lines select between arithmetic and bitwise logical operations, showcasing fundamental principles of digital system design and hardware reuse.