Combinational Logic Circuits
Adders - The Building Block of Arithmetic
What Makes a Circuit "Combinational"? — A combinational circuit has no memory - the output at any moment depends only on the current inputs, not on past history. There are no flip-flops or feedback loops. Examples: adders, multiplexers, decoders, encoders. Contrast with sequential circuits which have state.
Adders - The Building Block of Arithmetic
Half Adder
Equations:
| A | B | Sum S | Carry C |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Limitation:
Full Adder
S = A ⊕ B ⊕ Cin
Cout = AB + BCin + ACin
| A | B | Cin | Sum | Cout |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
4-Bit Ripple Carry Adder — Chain 4 full adders: the Cout of each stage feeds the Cin of the next. Cin of FA0 = 0 (no initial carry). Problem: Carry must "ripple" through all stages - delay increases linearly with bit-width. A 32-bit ripple adder has 32× the delay of 1 full adder. Solution: Carry Lookahead Adder (CLA) - precomputes carries in parallel. Used in modern CPUs.
Multiplexer (MUX) - Data Selector
A MUX selects one of several input lines and routes it to the output, based on select signals. A 2n:1 MUX has n select lines and 2n data inputs.
2:1 MUX
1 select line (S), 2 data inputs (I0, I1). Y = S'·I0 + S·I1
When S=0 → Y=I0 | When S=1 → Y=I1
Think of it as a programmable switch: S controls which wire gets through.
4:1 MUX
2 select lines (S1, S0), 4 data inputs (I0–I3). Y = S1'S0'·I0 + S1'S0·I1 + S1S0'·I2 + S1S0·I3
S1S0=00→I0, 01→I1, 10→I2, 11→I3
Key application: Any 3-variable Boolean function can be implemented with a 4:1 MUX (2 select + 1 data variable).
MUX as a Universal Logic Element — A 2n:1 MUX can implement any Boolean function of (n+1) variables. Connect (n) variables to select lines; wire the data inputs with constants (0,1) or the (n+1)th variable to realize the truth table directly. This is why FPGAs use LUTs (Look-Up Tables) - essentially large MUXes.
Decoder - 1-of-N Selector
A decoder takes an n-bit binary input and activates exactly one of 2n output lines. A 3:8 decoder has 3 inputs and 8 outputs - only one output is HIGH at any time.
| A | B | Y0 | Y1 | Y2 | Y3 |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Y0 = A'B', Y1 = A'B, Y2 = AB', Y3 = AB - each output is a minterm. Decoders can implement any Boolean function by OR-ing selected outputs.
Encoder & Priority Encoder
Encoder (4:2)
Opposite of decoder. Takes 4 inputs (exactly one HIGH at a time) and outputs a 2-bit binary code. A0 = I1 + I3 | A1 = I2 + I3
Problem: Standard encoders break if more than one input is active simultaneously.
Priority Encoder
Handles multiple active inputs by encoding the highest-priority (usually highest-numbered) active input. Also has a Valid (V) output - goes HIGH when any input is active.
Used in interrupt controllers: CPU must know which device needs attention when multiple devices request simultaneously.
Comparator
Compares two n-bit numbers A and B. Outputs three signals: A>B, A=B, A<B. A 1-bit comparator: A=B when XNOR(A,B)=1. For multi-bit: compare MSBs first; if equal, compare next bits down.
Parity Generator / Checker
XOR all bits together to generate a parity bit. Even parity: parity bit makes total 1s count even. Odd parity: makes count odd. At receiver, XOR all bits including parity - result should be 0 (even) or 1 (odd). Any single-bit error flips this check. XOR chains implement parity naturally.