Chapter 12 of 32

Half & Full Adders

Every processor adds numbers billions of times per second, and every one of those additions comes down to a tiny circuit that adds just a few bits. In this chapter we design those circuits, the half adder and the full adder, using the procedure from Combinational Circuit Design. Once you have a full adder, you can build an adder of any width, which is what the next chapters do.

Let us start with how you add binary numbers by hand:

  carries:   1 1 1
             0 1 1 1     (7)
           + 0 0 1 1     (3)
           ---------
             1 0 1 0     (10)

Look at one column. The rightmost column adds just two bits (1 + 1), giving a sum bit 0 and a carry 1. Every other column adds three bits: the two number bits plus the carry from the column on its right. So we need two circuits:

  • one that adds 2 bits (the half adder), and

  • one that adds 3 bits (the full adder).

Adding up to three 1-bit values gives at most 3 = 112, so both circuits have exactly two outputs: a sum bit and a carry bit.


Half Adder

A half adder is a combinational circuit that adds two bits A and B and produces a sum bit S and a carry bit C, where 2C + S = A + B.

Truth Table

A

B

C (carry)

S (sum)

Meaning

0

0

0

0

0 + 0 = 0

0

1

0

1

0 + 1 = 1

1

0

0

1

1 + 0 = 1

1

1

1

0

1 + 1 = 102

Equations

S = Σm(1, 2) = A′B + AB′ = A ⊕ B
C = Σm(3)    = AB

The sum column is exactly the XOR truth table and the carry column is exactly the AND truth table, so the half adder is one XOR gate and one AND gate:

A ──┬──────────┐
    │        [XOR]──────── S = A ⊕ B
B ──┼──┬───────┘
    │  │
    └──┼───────┐
       │     [AND]──────── C = AB
       └───────┘

Why is it called "half"? Because it has no input for a carry coming from a lower column. It can only be used in the least significant position, or wherever exactly two bits must be added.

Half Adder Using Only NAND Gates

From Universal Gates: NAND & NOR, XOR needs 4 NAND gates. The trick is that the first NAND gate, (AB)′, is reused for the carry: one more NAND acting as an inverter gives AB.

n1 = (A·B)′
n2 = (A·n1)′
n3 = (B·n1)′
S  = (n2·n3)′   = A ⊕ B
C  = (n1·n1)′   = AB

Total: 5 NAND gates

Half Adder Using Only NOR Gates

n1 = (A + A)′   = A′
n2 = (B + B)′   = B′
C  = (n1 + n2)′ = (A′ + B′)′ = AB
n3 = (A + B)′   = A′B′
S  = (C + n3)′  = (AB + A′B′)′ = A ⊕ B

Total: 5 NOR gates

Both netlists were checked against the truth table for all inputs. Five is the number usually quoted for both NAND-only and NOR-only half adders.


Full Adder

A full adder is a combinational circuit that adds three bits A, B and Cin (the carry from the previous column) and produces a sum S and a carry Cout, where 2Cout + S = A + B + Cin.

Truth Table

Row

A

B

Cin

Number of 1s

Cout

S

0

0

0

0

0

0

0

1

0

0

1

1

0

1

2

0

1

0

1

0

1

3

0

1

1

2

1

0

4

1

0

0

1

0

1

5

1

0

1

2

1

0

6

1

1

0

2

1

0

7

1

1

1

3

1

1

The "number of 1s" column is the key to understanding the outputs: the two output bits are simply that count written in binary.

Sum: K-map and Equation

S = Σm(1, 2, 4, 7)

          B Cin
  A     00   01   11   10
  0  |  0  |  1  |  0  |  1  |
  1  |  1  |  0  |  1  |  0  |

A checkerboard: no two 1s are adjacent, so the K-map cannot simplify anything and the minimal SOP has four 3-literal terms:

S = A′B′Cin + A′BCin′ + AB′Cin′ + ABCin

A checkerboard pattern is the signature of XOR. S is 1 when an odd number of inputs are 1, which is exactly what a 3-input XOR computes. Algebraically:

S = Cin′(A′B + AB′) + Cin(A′B′ + AB)
  = Cin′(A ⊕ B) + Cin(A ⊕ B)′
  = (A ⊕ B) ⊕ Cin
  = A ⊕ B ⊕ Cin

Carry: K-map and Equation

Cout = Σm(3, 5, 6, 7)

          B Cin
  A     00   01   11   10
  0  |  0  |  0  |  1  |  0  |
  1  |  0  |  1  |  1  |  1  |

  pair (3,7) → B·Cin     pair (5,7) → A·Cin     pair (6,7) → AB

Cout = AB + A·Cin + B·Cin

This is the majority function from Combinational Circuit Design: a carry comes out when at least two of the three inputs are 1. That makes sense: two or three 1s add up to 2 or 3, both of which have a 1 in the 2s place.

A Second Form of the Carry

There is another useful way to write Cout. Split on whether A and B are equal:

Cout = AB + Cin·(A ⊕ B)

Proof: Cin(A ⊕ B) = A′B·Cin + AB′·Cin
       AB + A′B·Cin + AB′·Cin
     = AB + AB·Cin + A′B·Cin + AB·Cin + AB′·Cin     (AB = AB + AB·Cin, twice)
     = AB + B·Cin(A + A′) + A·Cin(B + B′)
     = AB + B·Cin + A·Cin                            ✓

Read it in words; these two ideas return in the carry look-ahead adder:

  • AB: the column generates a carry on its own (both bits are 1), whatever Cin is.

  • Cin(A ⊕ B): exactly one of A, B is 1, so the column propagates the incoming carry to the next column.


Full Adder from Two Half Adders

The two equations S = (A ⊕ B) ⊕ Cin and Cout = AB + Cin(A ⊕ B) describe exactly two half adders and an OR gate:

             +---------+  S1 = A⊕B   +---------+
  A ───────> |         |───────────> |         |──────────────────> S = A⊕B⊕Cin
             |   HA1   |             |   HA2   |
  B ───────> |         |   Cin ────> |         |
             +---------+             +---------+
                  │ C1 = AB               │ C2 = Cin·(A⊕B)
                  │                       │
                  └─────────>[ OR ]<──────┘
                               │
                               └──────────────────────────────────> Cout

Can C1 and C2 be 1 at the same time? C1 = 1 needs A = B = 1, which makes A ⊕ B = 0 and therefore C2 = 0. They are mutually exclusive, so the OR gate could even be replaced by an XOR gate and the circuit would still be correct. Exam questions like to test this.

Gate Count and Delay

Implementation

Gates

Notes

Two half adders + OR

2 XOR, 2 AND, 1 OR = 5

Most common textbook form

Two-level SOP

S: 4 AND3 + 1 OR4; Cout: 3 AND2 + 1 OR3 (plus inverters)

Fastest (2 levels after inverters), largest

NAND only

9 NAND

Two 4-NAND XORs + 1 NAND for Cout

NOR only

9 NOR

Two 4-NOR XNORs + 1 NOR for Cout

The NAND-only version follows directly from the half adder trick: build A ⊕ B with 4 NANDs (n1 = (AB)′ inside), build (A ⊕ B) ⊕ Cin with 4 more (with n5 = ((A ⊕ B)·Cin)′ inside), and then Cout = (n1 · n5)′ = AB + (A ⊕ B)Cin with one more NAND: 9 NAND gates.

Delay (two half adders + OR, each gate counted as 1 unit, all inputs ready at time 0):

S1 = A ⊕ B         ready at 1
C1 = AB            ready at 1
S  = S1 ⊕ Cin      ready at 2
C2 = S1 · Cin      ready at 2
Cout = C1 + C2     ready at 3

But if Cin arrives late (at time t), S is ready at t + 1 and Cout at t + 2.

That last line is what matters when full adders are chained: in a multi-bit adder, the carry input is almost always the last signal to arrive, so the Cin → Cout delay (2 gate delays here) is repeated once per bit. Ripple-Carry & Carry Look-Ahead Adders builds on exactly this number.


Describing Adders in Verilog

Here is a structural full adder made from two half-adder modules, with a testbench that checks all 8 rows against ordinary arithmetic:

module half_adder (input  logic a, b,
                   output logic s, c);
  assign s = a ^ b;
  assign c = a & b;
endmodule

module full_adder (input  logic a, b, cin,
                   output logic s, cout);
  logic s1, c1, c2;
  half_adder ha1 (.a(a),  .b(b),   .s(s1), .c(c1));
  half_adder ha2 (.a(s1), .b(cin), .s(s),  .c(c2));
  assign cout = c1 | c2;
endmodule

module tb;
  logic a, b, cin, s, cout;
  full_adder dut (.a(a), .b(b), .cin(cin), .s(s), .cout(cout));
  initial begin
    $display("a b cin | cout s");
    for (int i = 0; i < 8; i++) begin
      {a, b, cin} = i; #1;
      $display("%b %b  %b  |   %b  %b", a, b, cin, cout, s);
      if ({cout, s} !== a + b + cin) $display("MISMATCH");
    end
  end
endmodule

Output (Icarus Verilog with -g2012):

a b cin | cout s
0 0  0  |   0  0
0 0  1  |   0  1
0 1  0  |   0  1
0 1  1  |   1  0
1 0  0  |   0  1
1 0  1  |   1  0
1 1  0  |   1  0
1 1  1  |   1  1

No "MISMATCH" lines were printed, so {Cout, S} equals A + B + Cin in every row. In real projects you would usually just write assign {cout, s} = a + b + cin; and let the synthesis tool pick the gates; the structural version is how you show you understand what those gates are.


Half Adder vs Full Adder

Point

Half adder

Full adder

Inputs

2 (A, B)

3 (A, B, Cin)

Outputs

S, C

S, Cout

Sum

A ⊕ B

A ⊕ B ⊕ Cin

Carry

AB

AB + ACin + BCin = AB + Cin(A ⊕ B)

Basic gates

1 XOR + 1 AND

2 XOR + 2 AND + 1 OR

NAND-only

5

9

Accepts a carry in?

No

Yes

Typical use

LSB of an adder, incrementers, building full adders

Every bit of a multi-bit adder, multipliers


Where Full Adders Are Used

  • Multi-bit adders: n full adders chained carry-to-carry add two n-bit numbers (next chapters).

  • Subtractors: with inverted B and Cin = 1, an adder computes A − B in 2's complement (see Subtractors).

  • Counting 1s: a full adder outputs, in binary, how many of its 3 inputs are 1. That is why it is also called a 3:2 counter or 3:2 compressor; fast multipliers use trees of them to add many partial products.

  • Majority and parity: Cout alone is a 3-input majority voter; S alone is a 3-input odd-parity function.


Common Mistakes

  • Writing S = A + B (OR) for the half adder. The sum is XOR: 1 + 1 gives sum 0, not 1.

  • Swapping sum and carry. Carry is the AND/majority; sum is the XOR/parity.

  • Using three half adders for a full adder. It takes two half adders and one OR gate.

  • Trying to simplify the sum K-map. The checkerboard has no adjacent 1s; recognise it as XOR instead.

  • Forgetting that C1 and C2 are never both 1. That is why OR and XOR both work for the final gate.

  • Reporting the full adder delay as one number. State which path: A/B → S, A/B → Cout, or Cin → Cout. The last one dominates in chained adders.


GATE and Interview Questions

Q1. What is the minimum number of 2-input NAND gates needed to build a half adder and a full adder?

Half adder: 5 (4 for the XOR, reusing the first NAND (AB)′ plus one inverter-NAND for AB). Full adder: 9.

Q2. How many half adders and other gates make a full adder?

Two half adders and one OR gate. The OR gate can be replaced by an XOR gate, because the two half-adder carries are never 1 together.

Q3. A full adder has inputs A = 1, B = 0, Cin = 1. Give S and Cout.

Two inputs are 1, so 1 + 0 + 1 = 2 = 102: Cout = 1, S = 0.

Q4. Express the full adder outputs in Σm form.

S = Σm(1, 2, 4, 7) and Cout = Σm(3, 5, 6, 7), with inputs ordered A, B, Cin.

Q5. In a full adder made from two half adders and an OR gate, the XOR, AND and OR gates have delays of 20 ns, 10 ns and 10 ns. All inputs arrive at t = 0. When are S and Cout valid?

S1 = A ⊕ B at 20 ns; S = S1 ⊕ Cin at 20 + 20 = 40 ns. C1 = AB at 10 ns; C2 = S1·Cin at 20 + 10 = 30 ns; Cout = C1 + C2 at 30 + 10 = 40 ns.

Q6. Why is the full adder called a 3:2 counter?

It takes 3 input bits of equal weight and produces a 2-bit binary number (Cout S) equal to how many of them are 1. Trees of such counters (Wallace and Dadda trees) reduce many partial products to two rows in fast multipliers.

Q7. If the Cin input of a full adder is tied to 0, what circuit do you get?

A half adder: S = A ⊕ B ⊕ 0 = A ⊕ B and Cout = AB + 0 + 0 = AB.


Summary

  • A half adder adds 2 bits: S = A ⊕ B, C = AB. It has no carry input. NAND-only: 5 gates.

  • A full adder adds 3 bits: S = A ⊕ B ⊕ Cin (odd parity), Cout = AB + ACin + BCin (majority) = AB + Cin(A ⊕ B). NAND-only: 9 gates.

  • Full adder = 2 half adders + 1 OR gate (an XOR also works, since the two carries are mutually exclusive).

  • AB is the generate term and A ⊕ B the propagate term: remember them for fast adders.

  • In chained adders, the Cin → Cout delay of one full adder is the number that matters.

  • Next: Subtractors, the borrow-based twins of these circuits, and then Ripple-Carry & Carry Look-Ahead Adders.