Combinational Circuits

In a combinational circuit the outputs depend only on the current inputs; there is no memory. (Circuits with memory, whose outputs also depend on the past, are sequential, the subject of the next lesson.)

Adders

A half adder adds two bits: Sum = A ⊕ B, Carry = AB.

A full adder adds two bits and an incoming carry:

• Sum = A ⊕ B ⊕ C_in (1 when an odd number of inputs are 1)
• C_out = AB + C_in(A ⊕ B) = AB + BC_in + AC_in (the majority function)

A full adder can be built from two half adders and an OR gate.

Ripple-carry adder

Chain n full adders, each carry-out feeding the next carry-in.

It is simple, but the carry may have to ripple through every stage. If a stage produces its carry after t_c and its sum after t_s (once its inputs are ready), the last sum is ready after

(n − 1) · t_c + max(t_s, t_c), which grows linearly with n.

def full_adder(a, b, cin):
    s = a ^ b ^ cin
    cout = (a & b) | (cin & (a ^ b))
    return s, cout

def ripple_add(x, y, n=8):
    carry, bits = 0, []
    for i in range(n):                       # least significant bit first
        s, carry = full_adder((x >> i) & 1, (y >> i) & 1, carry)
        bits.append(s)
    return sum(b << i for i, b in enumerate(bits)), carry

for x, y in [(100, 27), (200, 100), (255, 1)]:
    total, cout = ripple_add(x, y)
    print(f"{x} + {y} = {total} (8 bits), carry out {cout}")
n, tc, ts = 16, 3, 4
print(f"{n}-bit ripple adder delay: {(n - 1) * tc + max(ts, tc)} ns")

100 + 27 = 127 (8 bits), carry out 0
200 + 100 = 44 (8 bits), carry out 1
255 + 1 = 0 (8 bits), carry out 1
16-bit ripple adder delay: 49 ns

Carry-lookahead adder

Each stage can compute in advance whether it generates a carry, G_i = A_iB_i, or propagates an incoming one, P_i = A_i ⊕ B_i. Then C_i+1 = G_i + P_iC_i, which expands to

C₄ = G₃ + P₃G₂ + P₃P₂G₁ + P₃P₂P₁G₀ + P₃P₂P₁P₀C₀,

a two-level AND–OR expression. Every carry is ready after a constant number of gate delays (with unlimited fan-in), at the price of many more gates. Real adders use lookahead within groups of 4 bits and ripple or lookahead between groups.

Subtraction

A − B = A + B′ + 1: invert B (XOR gates controlled by a "subtract" signal) and set the first carry-in to 1. One circuit then adds and subtracts.

Multiplexers

A multiplexer (MUX) selects one of 2ⁿ data inputs using n select lines. A 4:1 MUX computes Y = S₁′S₀′I₀ + S₁′S₀I₁ + S₁S₀′I₂ + S₁S₀I₃.

• Building larger MUXes: a 2ⁿ:1 MUX can be built from 2:1 MUXes arranged as a tree, using 2ⁿ − 1 of them (16:1 needs 8 + 4 + 2 + 1 = 15).
• Implementing a function: a 2ⁿ:1 MUX implements any function of n variables (connect the variables to the selects and the truth table column, as constants, to the inputs). A function of n variables also fits on a 2ⁿ⁻¹:1 MUX: use n − 1 variables as selects and feed each data input with 0, 1, the last variable, or its complement.

from itertools import product

def mux(inputs, selects):
    index = int("".join(map(str, selects)), 2)
    return inputs[index]

# F(A, B, C) = Σm(1, 2, 6, 7) on a 4:1 MUX with selects A, B; inputs are functions of C.
F = lambda a, b, c: int(4 * a + 2 * b + c in (1, 2, 6, 7))
data = []
for a, b in product([0, 1], repeat=2):
    col = (F(a, b, 0), F(a, b, 1))
    data.append({(0, 0): "0", (1, 1): "1", (0, 1): "C", (1, 0): "C'"}[col])
print("data inputs I0..I3:", data)
value = {"0": lambda c: 0, "1": lambda c: 1, "C": lambda c: c, "C'": lambda c: 1 - c}
print(all(mux([value[d](c) for d in data], [a, b]) == F(a, b, c)
          for a, b, c in product([0, 1], repeat=3)))

data inputs I0..I3: ['C', "C'", '0', '1']
True

A demultiplexer does the reverse: it routes one input to one of 2ⁿ outputs.

Decoders and encoders

• An n-to-2ⁿ decoder activates exactly one of its 2ⁿ outputs: output i is the minterm mᵢ of the inputs. Any function can therefore be built from a decoder and an OR gate per output: a full adder needs one 3-to-8 decoder and two OR gates (Sum = Σm(1, 2, 4, 7), C_out = Σm(3, 5, 6, 7)).
• Larger decoders are built from smaller ones with enable inputs: a 4-to-16 decoder uses one 2-to-4 decoder to enable four 2-to-4 decoders (5 in all).
• An encoder does the reverse: 2ⁿ inputs (exactly one active) to an n-bit code. A priority encoder handles several active inputs by reporting the highest-priority one, plus a "valid" output.

Comparators

A magnitude comparator produces A > B, A = B and A < B. Bitwise equality is xᵢ = (Aᵢ ⊕ Bᵢ)′ (XNOR), and A = B is the AND of all xᵢ. A > B is decided by the most significant bit where they differ.

Practice questions

from itertools import product
F = lambda a, b, c: int(4 * a + 2 * b + c in (1, 2, 6, 7))
names = {(0, 0): "0", (1, 1): "1", (0, 1): "C", (1, 0): "C'"}
print(", ".join(names[(F(a, b, 0), F(a, b, 1))] for a, b in product([0, 1], repeat=2)))