Combinational Circuits

Combinational circuits have no memory — output depends ONLY on current inputs. Same inputs always give same outputs. These are the building blocks of the ALU and datapath.

Half Adder — adds two 1-bit numbers:
- Inputs: A, B
- Outputs: Sum = A XOR B, Carry = A AND B
- 1+1 = 10 in binary → Sum=0, Carry=1
- Only 2 gates! The foundation of all arithmetic in hardware.

Full Adder — adds three 1-bit numbers (A, B, and carry-in):
- Inputs: A, B, Cin
- Outputs: Sum = A XOR B XOR Cin, Cout = (A AND B) OR (Cin AND (A XOR B))
- Chain full adders together → N-bit ripple carry adder
- 4-bit adder = 1 half adder + 3 full adders

Ripple Carry Adder (RCA):
- Chain N full adders: carry out of each feeds into carry in of next
- Simple but slow — carry must "ripple" through all N stages
- Delay = N × full_adder_delay (linear in N)
- 64-bit RCA has 64 stages of delay — too slow for modern CPUs

Carry Look-Ahead Adder (CLA):
- Pre-computes carries in parallel using Generate (G=A·B) and Propagate (P=A+B) signals
- All carries computed simultaneously — O(log N) delay instead of O(N)
- Modern CPUs use this (or carry-select, prefix adders)

Multiplexer (MUX) — data selector:
- 2:1 MUX: select signal S picks one of 2 inputs (A or B) to pass to output
- 4:1 MUX: 2 select bits pick one of 4 inputs
- F = S'·A + S·B (for 2:1)
- Used EVERYWHERE: choosing between ALU result and memory data, selecting register values, routing signals

Demultiplexer (DEMUX): opposite of MUX — routes one input to one of N outputs based on select.

Decoder: N inputs → 2^N outputs. Exactly one output is HIGH for each input combination.
- 2-to-4 decoder: 2 inputs → 4 outputs (one per minterm)
- Used in memory addressing: which RAM cell to read/write

Encoder: opposite of decoder. One of 2^N inputs → N-bit binary output.
Priority encoder: if multiple inputs high, outputs the highest-priority one.

Comparator: compares two N-bit numbers.
- Outputs: A>B, A=B, A<B
- A=B: all bits equal (use XNOR on each bit, AND all results)
- A>B: done bit by bit from MSB, first differing bit determines result

1# Build all combinational circuits from scratch
2
3# ── Half Adder ─────────────────────────────────────────
4def half_adder(A, B):
5    Sum   = A ^ B      # XOR
6    Carry = A & B      # AND
7    return Sum, Carry
8
9print("Half Adder:")
10for A in range(2):
11    for B in range(2):
12        S, C = half_adder(A, B)
13        print(f"  {A}+{B} = Sum={S} Carry={C}  ({A+B} in decimal)")
14
15# ── Full Adder ─────────────────────────────────────────
16def full_adder(A, B, Cin):
17    sum1, c1 = half_adder(A, B)
18    Sum, c2  = half_adder(sum1, Cin)
19    Cout     = c1 | c2
20    return Sum, Cout
21
22print("
23Full Adder (A + B + Cin):")
24for A, B, Cin in [(0,0,0),(0,1,1),(1,1,0),(1,1,1)]:
25    S, C = full_adder(A, B, Cin)
26    print(f"  {A}+{B}+{Cin}(cin) = Sum={S} Cout={C}")
27
28# ── N-bit Ripple Carry Adder ───────────────────────────
29def ripple_carry_adder(A_bits, B_bits):
30    """Add two N-bit numbers (lists of bits, LSB first)"""
31    assert len(A_bits) == len(B_bits)
32    result = []
33    carry = 0
34    for a, b in zip(A_bits, B_bits):
35        s, carry = full_adder(a, b, carry)
36        result.append(s)
37    result.append(carry)  # final carry out
38    return result
39
40def int_to_bits(n, width):
41    return [(n >> i) & 1 for i in range(width)]
42
43def bits_to_int(bits):
44    return sum(b << i for i, b in enumerate(bits))
45
46A, B = 13, 11   # 1101 + 1011
47width = 4
48A_bits = int_to_bits(A, width)
49B_bits = int_to_bits(B, width)
50result = ripple_carry_adder(A_bits, B_bits)
51print(f"
524-bit RCA: {A} + {B} = {bits_to_int(result)}")
53print(f"  A    = {''.join(str(b) for b in reversed(A_bits))}")
54print(f"  B    = {''.join(str(b) for b in reversed(B_bits))}")
55print(f"  Sum  = {''.join(str(b) for b in reversed(result))}")
56
57# ── Multiplexer ────────────────────────────────────────
58def mux_2to1(A, B, S):
59    return B if S else A
60
61def mux_4to1(inputs, S1, S0):
62    sel = (S1 << 1) | S0
63    return inputs[sel]
64
65print("
662:1 MUX:")
67for S in range(2):
68    print(f"  S={S}: output = {mux_2to1(0b1010, 0b1100, S):#06b}")
69
70# ── Decoder ────────────────────────────────────────────
71def decoder_2to4(A1, A0):
72    sel = (A1 << 1) | A0
73    return [1 if i == sel else 0 for i in range(4)]
74
75print("
762-to-4 Decoder:")
77for A1 in range(2):
78    for A0 in range(2):
79        out = decoder_2to4(A1, A0)
80        print(f"  A={A1}{A0} → Y={out}")
81
82# ── N-bit Comparator ───────────────────────────────────
83def comparator(A, B):
84    if A > B: return "A > B"
85    if A < B: return "A < B"
86    return "A = B"
87
88print("
89Comparator:")
90for A, B in [(5,3),(3,5),(4,4),(15,8)]:
91    print(f"  {A:4d} vs {B:4d} → {comparator(A,B)}")