Building Blocks: Adders, Multiplexers & Decoders

Boolean Algebra & Digital Logic

Chapter 7 · Building Blocks: Adders, Multiplexers & Decoders

Chapter 6 built one specific circuit. This chapter builds three genuinely reusable ones — standard components wired into essentially every real digital system, including the exact logic a CPU uses to add numbers.

The Half Adder: Chapter 2's XOR Promise, Delivered

Chapter 2 called XOR "the basis of binary addition without carry." A half adder adds two single bits and produces exactly that: a SUM bit and a CARRY bit.

The circuit

SUM = x ⊕ y. CARRY = x · y. Two gates, total.

Verified directly against real binary addition

1+1=2, i.e. binary 10: SUM=0, CARRY=1 — matches. 0+1=1, binary 01: SUM=1, CARRY=0 — matches. Every one of the 4 input combinations produces the exact CS (carry, sum) digits of the real binary sum.

The Full Adder — and a Genuine Reuse of Chapters 4-6

A half adder can't be chained — real multi-bit addition needs each column to also accept a carry in from the column before it. A full adder takes three inputs (x, y, cin) and produces SUM and COUT: SUM = x ⊕ y ⊕ cin, COUT = xy + cin(x⊕y).

A genuine finding, verified directly: COUT is exactly the majority function

Checked for all 8 input combinations of (x,y,cin): COUT equals 1 in precisely the same cases as majority(x,y,cin) — because a carry genuinely does occur exactly when at least two of the three bits being added are 1. This isn't a coincidence worth noting in passing: the full adder's carry-out logic is Chapter 5-6's own simplified xy+xz+yz circuit, with the variables simply renamed. The exact 5-gate circuit already built and traced in Chapter 6 is a real full adder's carry logic, reused wholesale.

Chaining Full Adders: A Real Multi-Bit Adder

Wire the COUT of one full adder into the cin of the next, and multi-bit numbers add correctly, column by column, exactly like doing long addition by hand — this is a real ripple-carry adder, and it's genuinely how simple ALU addition works.

Verified directly — a 2-bit ripple-carry adder

11₂ + 10₂ (3+2): first stage adds the low bits with cin=0, its carry feeds the second stage — result 101₂ (5). 10₂ + 10₂ (2+2): result 100₂ (4). 01₂ + 01₂ (1+1): result 010₂ (2). All three verified correct against real binary addition.

Multiplexers: A Selectable Wire

A multiplexer (MUX) routes exactly one of several data inputs through to a single output, chosen by a separate select input. A 2-to-1 MUX: output = sel'·in0 + sel·in1.

Verified directly, all 8 combinations

With sel=0, the output always exactly matches in0, regardless of in1. With sel=1, the output always exactly matches in1, regardless of in0 — confirmed for every combination.

Decoders: Physically Wired Minterms

A decoder takes n select inputs and activates exactly one of 2ⁿ output lines. A 2-to-4 decoder's four outputs are literally Chapter 4's own four possible 2-variable minterms — a'b', a'b, ab', ab — each wired to its own physical output line.

Verified directly — the outputs correspond exactly to the binary input value

ab=00 activates D0. ab=01 activates D1. ab=10 activates D2. ab=11 activates D3 — the active output number always equals the binary value of the select inputs, confirmed for all 4 combinations.

Real Relevance

Ripple-carry addition is the literal mechanism behind a CPU's own integer addition (real ALUs use faster carry-lookahead variants at scale, but the correctness principle is identical). Multiplexers select which data path is active on every clock cycle inside a real processor. Decoders turn a binary address into "activate exactly this one memory location" — the basic mechanism behind RAM addressing itself.

Building Blocks in Code

def half_adder(x, y):
    return x ^ y, x & y   # sum, carry

def full_adder(x, y, cin):
    s = x ^ y ^ cin
    cout = (x & y) | (cin & (x ^ y))   # == majority(x,y,cin)
    return s, cout

def add_2bit(a1, a0, b1, b0):
    s0, c0 = full_adder(a0, b0, 0)
    s1, c1 = full_adder(a1, b1, c0)   # carry ripples in
    return c1, s1, s0

print(add_2bit(1,1,1,0))   # (1, 0, 1) -- 3+2=5, binary 101

def mux2(sel, in0, in1):
    return ((1-sel) & in0) | (sel & in1)

def decoder_2to4(a, b):
    return ((1-a)&(1-b), (1-a)&b, a&(1-b), a&b)

Hands-On Exercises

Exercise 1

Using this chapter's own full adder, add the 2-bit binary numbers 10 and 11 (decimal 2 and 3) via a ripple-carry chain, showing each full adder's inputs and outputs, and confirm the result equals 101 (decimal 5).

📄 View solution

Exercise 2

Using this chapter's own MUX formula (sel'·in0 + sel·in1), trace the output for sel=1, in0=1, in1=0, and explain in one sentence why the value of in0 doesn't matter at all once sel=1 is fixed.

📄 View solution

Exercise 3

Explain, using this chapter's own finding about the full adder's carry-out logic, why a chip designer who already has a working, well-tested majority-function circuit could reuse it directly as the carry-out logic of a full adder — without redesigning anything from scratch.

📄 View solution

Chapter 7 Quick Reference

Half adder: SUM=x⊕y, CARRY=xy — exactly Chapter 2's own XOR promise, delivered
Full adder: adds x, y, cin; SUM=x⊕y⊕cin, COUT=majority(x,y,cin) — a genuine, verified reuse of Chapters 4-6's own circuit
Ripple-carry adder: chain full adders, COUT of one feeds cin of the next — verified on real 2-bit binary addition
Multiplexer: routes exactly one of several inputs to the output based on a select line
Decoder: activates exactly one of 2ⁿ outputs — physically wires Chapter 4's own minterms, one per output line
Next chapter: Sequential logic — latches, flip-flops, and memory