Training Digital Logic & Sequential Circuits — Boolean Algebra to Finite State Machines Boolean Minimisation & Combinational Logic Hazards
1 / 2

Boolean Minimisation & Combinational Logic Hazards

60 min Digital Logic & Sequential Circuits — Boolean Algebra to Finite State Machines

Boolean Minimisation & Combinational Logic Hazards

Boolean minimisation reduces the gate count and propagation delay of combinational circuits. Karnaugh maps provide a graphical approach up to 6 variables; Quine–McCluskey extends this algorithmically for synthesis tools. Equally important — and often overlooked — is hazard analysis: combinational circuits may produce spurious glitches that propagate to registers and corrupt state.

1. Boolean Algebra — Key Identities

The Boolean algebra axioms (Huntington's postulates) underpin all minimisation:

  • Idempotency: $A + A = A$, $A \cdot A = A$
  • Absorption: $A + AB = A$, $A(A+B) = A$
  • De Morgan: $\overline{A+B} = \bar{A}\cdot\bar{B}$, $\overline{A\cdot B} = \bar{A}+\bar{B}$
  • Consensus: $AB + \bar{A}C + BC = AB + \bar{A}C$

The consensus theorem is critical for static hazard elimination: the consensus term $BC$ can be added redundantly to bridge the gap between two prime implicants.

2. Karnaugh Map Minimisation

For a 4-variable function $f(A,B,C,D)$, the K-map is a $4\times 4$ grid with Gray-code ordering. Groups of $1, 2, 4, 8, 16$ cells are prime implicants. Minimum SOP (Sum of Products) uses the largest possible groups (prime implicants) with fewest essential prime implicants covering all minterms.

Example: $f = \sum m(0,1,2,3,4,5,10,11) = \overline{A}\cdot\overline{B} + \overline{A}C + B\overline{D}$... (work through K-map groupings systematically).

3. Static-0 and Static-1 Hazards

A static-1 hazard occurs when the output should remain 1 but glitches to 0 during an input transition. In SOP implementations, a hazard exists whenever two adjacent minterms are covered by different prime implicants — the output goes low briefly during the gate switching. Elimination: add a redundant prime implicant (consensus term) spanning the gap.

Example: $f = \overline{A}C + AB$ has a static-1 hazard at the transition $ABC: 011 \to 111$. Adding $BC$ eliminates it: $f = \overline{A}C + AB + BC$.

4. CMOS Gate Implementation

CMOS realises complementary logic with a pull-up network (PMOS, series = AND, parallel = OR) and a pull-down network (NMOS, dual of PMOS). For $Y = \overline{AB+C}$: PDN = ($A$ NMOS in series with $B$ NMOS) in parallel with $C$ NMOS; PUN = ($A$ PMOS in parallel with $B$ PMOS) in series with $C$ PMOS. Static power = 0; dynamic power $P = \alpha C_L V_{DD}^2 f$ where $\alpha$ is the activity factor.

Worked Example — Full Adder Minimisation

Full adder sum: $S = A \oplus B \oplus C_{in}$ — cannot be simplified beyond XOR chain. Carry: $C_{out} = AB + BC_{in} + AC_{in}$ — already in minimal SOP (3 prime implicants, each essential). Hazard check: transitions $ABC_{in}: 011\to 111$ covered by $BC_{in}$ and $AB$ — add consensus $AC_{in}$... but $AC_{in}$ is already present. No additional hazard terms needed. ✓

Digital Logic Simulator — Basic Gates & Full Adder
A AND B =0
A OR B =0
A XOR B =0
A NAND B =1
Full Adder Sum (A⊕B⊕C) =0
Full Adder Carry-out =0

Practice Problems

1. Minimise $f(A,B,C,D) = \sum m(0,2,4,5,6,7,8,10,13,15)$ using a K-map. List all prime implicants and identify the essential prime implicants.
2. Show that the function $f = \overline{A}B + A\overline{C}$ has a static-1 hazard at the transition $ABC: 010 \to 000$. Add the consensus term to eliminate it and verify.
3. Implement a 3-input majority function using CMOS gates. Draw the NMOS pull-down network and the complementary PMOS pull-up network. Compute the number of transistors and compare to a NAND-NAND realisation.
Sequential Logic — D Flip-Flops & Finite State Machines