1.4.3 - Adders and D-type flip-flops

Adding two bits with a half adder

A half adder adds two single-bit inputs $A,B$ and produces a sum bit $S$ and carry bit $C$.

The carry has weight 2 and the sum has weight 1, so the two-bit result is $CS$, with numerical value $2C+S=A+B$. Here the plus in this numerical check is ordinary addition; the gate operations below use Boolean symbols. For $1+1=2$, binary 10 means $C=1,S=0$, not two separate sum bits equal to 1.

The sum is true for exactly one true input, so $S=A\oplus B$. The carry is true only when both inputs are true, so $C=A\land B$. OCR's underlined vee $\underline{\lor}$, XOR and $\oplus$ represent the exclusive operation; ordinary OR would give an incorrect sum bit for inputs 1,1.

To draw the half adder, branch each input to a two-input XOR gate and a two-input AND gate. Label the XOR output $S$ and the AND output $C$. A branch distributes the same signal; it does not add a new input bit. The circuit has two independent inputs and therefore four truth-table rows.

A half adder has no carry-in input. Its carry output can pass a value onward, but it cannot include a carry received from a previous bit position. This distinction explains why a half adder alone is insufficient for an arbitrary higher column of a multi-bit addition.

Including carry-in with a full adder

A full adder adds three single-bit inputs: $A,B$ and a carry-in $C_{\mathrm{in}}$.

It still produces just a sum bit and carry-out bit. Their numerical check is $2C_{\mathrm{out}}+S=A+B+C_{\mathrm{in}}$. The possible total is 0,1,2 or 3, represented as 00,01,10 or 11.

A full adder can be built from two half-adder stages and an OR gate. The first stage adds $A,B$, producing intermediate sum $P=A\oplus B$ and carry $G=A\land B$. The second stage adds $P,C_{\mathrm{in}}$, producing final sum $S=P\oplus C_{\mathrm{in}}$ and carry $H=P\land C_{\mathrm{in}}$. Either carry makes the final carry-out true:

[DIAGRAM: A full adder using two XOR gates, two AND gates and OR; asset_slug: full-adder; caption: Intermediate P, G and H connect the two half-adder stages to the final sum and carry-out.]

Read the diagram by following the labelled wires. XOR1 makes $P$; AND1 makes $G$; XOR2 uses $P,C_{\mathrm{in}}$ for $S$; AND2 makes $H$; OR combines $G,H$ for carry-out. Connection dots mark branches; crossing wires without dots are not connected.

For $A=B=C_{\mathrm{in}}=1$, $P=0,G=1,H=0$, so $S=1,C_{\mathrm{out}}=1$, representing total 3. Carry-out is also described by the majority expression $(A\land B)\lor(A\land C_{\mathrm{in}})\lor(B\land C_{\mathrm{in}})$: it is 1 when at least two inputs are 1. The sum is 1 for an odd number of true inputs. Both descriptions agree with all eight rows.

Carrying between binary columns

A multi-bit adder connects each column's carry-out to the next more significant column's carry-in.

In a ripple-carry adder, this dependency propagates from the least significant bit towards the most significant. The first column can use a half adder if no incoming carry is needed; the later columns need full adders because each must include the previous column's carry. Alternatively, full adders can be used throughout with the initial carry-in fixed to 0.