Combinational Circuits

Combinational vs Sequential Circuits

Combinational: output depends ONLY on current inputs (no memory)
  Examples: adder, multiplexer, decoder, encoder

Sequential: output depends on current inputs AND past state (has memory)
  Examples: flip-flops, counters, shift registers

---

Adders — The Math of Computers

Half Adder (2 inputs)

Analogy: Adding two single bits: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (carry!)

Inputs: A, B
Sum   = A ⊕ B  (XOR)
Carry = A · B  (AND)

Truth table:
A  B | Sum  Carry
0  0 |  0    0
0  1 |  1    0
1  0 |  1    0
1  1 |  0    1   ← 1+1 = 10 in binary (sum=0, carry=1)

Full Adder (3 inputs)

Inputs: A, B, Cin (carry in from previous stage)
Sum  = A ⊕ B ⊕ Cin
Cout = AB + BCin + ACin = AB + Cin(A ⊕ B)

Implementation: two half adders + one OR gate

Ripple Carry Adder

Analogy: Like adding numbers on paper — you carry from rightmost column to the next, one at a time.

4-bit adder: chain 4 full adders

FA₀  →  FA₁  →  FA₂  →  FA₃
Cin₀    Cin₁    Cin₂    Cin₃
(=0)   (=Cout₀) (=Cout₁) (=Cout₂)

Problem: carry must ripple from bit 0 to bit n-1 — delay grows linearly with n

Carry Lookahead Adder (CLA)

Instead of waiting for carry to ripple, COMPUTE all carries simultaneously!

Generate:  Gᵢ = Aᵢ · Bᵢ  (this bit GENERATES a carry regardless of Cin)
Propagate: Pᵢ = Aᵢ ⊕ Bᵢ  (this bit PROPAGATES an incoming carry)

Carry equations (all computable in parallel):
C₁ = G₀ + P₀·C₀
C₂ = G₁ + P₁·G₀ + P₁·P₀·C₀
C₃ = G₂ + P₂·G₁ + P₂·P₁·G₀ + P₂·P₁·P₀·C₀

All these are computable simultaneously → O(1) delay (for fixed-width adder)!
Tradeoff: more gates, more complex wiring

---

Multiplexer (MUX) — The Data Selector

Analogy: A railway switch that directs a train onto one of several tracks based on a control signal.

2:1 MUX: 2 data inputs (I₀, I₁), 1 select line (S), 1 output (Y)
  Y = S'·I₀ + S·I₁
  S=0 → Y = I₀
  S=1 → Y = I₁

4:1 MUX: 4 data inputs, 2 select lines (S₁,S₀)
  Y = S₁'S₀'·I₀ + S₁'S₀·I₁ + S₁S₀'·I₂ + S₁S₀·I₃

Implementing any Boolean function with a MUX:

Method 1: 2^n : 1 MUX (n = number of variables)
  Connect minterms to data inputs: I_k = 1 if k ∈ minterm list, else 0
  Connect variables to select lines

Method 2: 2^(n-1) : 1 MUX (one variable as select, rest as data)
  Shannon expansion: f(A,B,C) = A'·f(0,B,C) + A·f(1,B,C)
  Use A as select; compute f(0,B,C) and f(1,B,C) as data inputs

Example: implement f = A'B'C + AB'C' + ABC using 4:1 MUX with A,B as selects
  f(A=0,B=0) = C       → I₀ = C
  f(A=0,B=1) = 0       → I₁ = 0
  f(A=1,B=0) = C'      → I₂ = C'
  f(A=1,B=1) = 1       → I₃ = 1

---

Decoder — The "Exactly One" Circuit

Analogy: Like a hotel where exactly one room light turns on based on the room number you input.

n-to-2^n decoder: n input bits → 2^n output lines
  Exactly ONE output = 1; which one depends on the input binary value

3-to-8 decoder example:
  Input A₂A₁A₀ = 101 (=5 in decimal) → output Y₅ = 1, all others = 0

Implementing functions with a decoder:
  f = Σm(0,3,5) → connect a 3-to-8 decoder's outputs 0, 3, 5 through an OR gate
  This works because decoder generates ALL minterms simultaneously!

---

Encoder

Encoder: 2^n inputs → n outputs
  Input i is high → outputs encode binary number i
  Opposite of decoder

Priority encoder: if MULTIPLE inputs are high, output binary code of the
  HIGHEST PRIORITY (usually highest-numbered) active input
  Also outputs a valid bit (V=1 if any input active)

---

Universal Gates — NAND and NOR

Any Boolean function can be implemented using only NAND gates (or only NOR gates).

Using only NAND:
  NOT A  = A NAND A     (A · A = A, so (A NAND A) = A')
  A AND B = (A NAND B) NAND (A NAND B)
  A OR B  = (A NAND A) NAND (B NAND B)  = A' NAND B' = (A·B)'' = A+B

Using only NOR:
  NOT A  = A NOR A
  A OR B = (A NOR B) NOR (A NOR B)
  A AND B = (A NOR A) NOR (B NOR B)

Why important in practice: NAND and NOR gates are cheaper and faster to fabricate in CMOS. Entire CPUs are built from NAND gates!

---

Quick Check

Q1. Full adder: A=1, B=1, Cin=1. What are Sum and Cout?

Sum  = 1 ⊕ 1 ⊕ 1 = 0 ⊕ 1 = 1
Cout = 1·1 + 1·1 + 1·1 = 1 + 1 + 1 = 1
Output: Sum=1, Cout=1 (binary: 1+1+1 = 11₂ = decimal 3)

Q2. What is the minimum size MUX to implement a 3-variable function? Answer: 4:1 MUX (2^(3-1) = 4). Use 2 variables as select lines and compute the 4 sub-functions of the third variable as data inputs.

Q3. How do you implement f = A' + BC using only NAND gates?

f = A' + BC = (A'' · (BC)'')' = NAND of [NAND(A,A)] and [NAND(B,C)] inverted
Actually: A' + BC = ((A)(BC)')' ← NAND with De Morgan:
(A'·(BC)')' = A'' + BC = A + (BC)... hmm.
Better: A' + BC, use De Morgan: = (A · (BC)')' = NAND(A, NAND(B,C))