Chapter 3: Simplification of Boolean Functions
Introduction
We know from the previous chapter that any Boolean function can be expressed in canonical form using minterms or maxterms. However, these canonical expressions are often not optimal for implementation. A simplified Boolean expression uses fewer gates and less power, making circuit design more economical and practical. In this chapter, we explore systematic methods for simplification, with the Karnaugh map being the most widely used tool for up to 5 or 6 variables.
1. Algebraic Simplification Review
Boolean Algebra Approach
As we saw, using Boolean algebra laws (absorption, De Morgan's, consensus, etc.), we can manually simplify expressions. However, this approach has limitations: there's no guarantee we'll find the optimal solution, and the process is error-prone for larger expressions. Algebraic simplification works best for smaller expressions or when patterns are obvious.
2. Karnaugh Maps (K-maps)
What is a Karnaugh Map?
The Karnaugh map is a graphical method for simplifying Boolean functions. It's essentially a reorganization of the truth table into a grid where adjacent cells differ by only one variable. This adjacency relationship makes it easy to spot terms that can be combined using the Boolean identity A + A' = 1.
2-Variable K-Map
For two variables (A, B), we create a 2×2 grid. Each cell represents one minterm. The rows represent values of A (0 or 1), columns represent values of B (0 or 1). Adjacency includes both horizontal and vertical neighbors, and the map wraps around (leftmost adjacent to rightmost, top adjacent to bottom).
3-Variable K-Map
For three variables (A, B, C), we create a 2×4 or 4×2 grid (8 cells total). The key insight: we arrange the variables so that adjacent cells differ by only one variable. A common arrangement uses A on the left, BC across the top (in order 00, 01, 11, 10—Gray code order, not binary order!). This ensures that 01 and 11 are adjacent (differing only in C), and 11 and 10 are adjacent (differing only in B).
4-Variable K-Map
For four variables (A, B, C, D), we create a 4×4 grid (16 cells). We place AB down the left side and CD across the top, again in Gray code order (00, 01, 11, 10) to ensure single-variable differences between adjacent cells. This layout becomes crucial for finding valid groupings.
3. Grouping Terms in K-Maps
The Grouping Process
After placing 1s in cells corresponding to minterms where the function outputs 1, we group adjacent cells into rectangles. Valid group sizes are powers of 2: 1 (single cell), 2, 4, 8, 16, etc. Each group represents a simplified term. Larger groups result in simpler terms (fewer variables), so we want the largest possible groups.
Guidelines for Optimal Grouping
Make groups as large as possible. Overlapping is allowed—a 1 can be part of multiple groups. Cover all 1s with the minimum number of groups. Use larger groups when available, as they eliminate more variables. Essential prime implicants (groups not covered by any other group) must be included in the final expression.
Practical Example
Suppose we have a 3-variable function with 1s at positions 1, 3, 5, 7 (odd numbers). In K-map form, these would be arranged so that some are adjacent. If positions 1 and 5 are adjacent (differing only in A), and 3 and 7 are adjacent, we can group them. The result simplifies to just one term (in this case, the single variable C if C=1 is common to all 1s).
4. NAND and NOR Gate Realization
Why NAND and NOR?
NAND and NOR are universal gates—any Boolean function can be implemented using only NAND gates or only NOR gates. In many technologies (like CMOS), NAND and NOR are as easy or easier to implement than AND and OR. Learning to convert between AND-OR expressions and NAND-NAND or NOR-NOR expressions is essential for practical circuit design.
AND-OR to NAND-NAND Conversion
The key insight: two consecutive inversions (NAND followed by NAND) can replace AND followed by OR. If you have a sum of products (SOP) expression, you can implement it using NAND gates: create NAND gates for each product term, then feed their outputs into another NAND gate. This is equivalent to AND-OR, but uses only NAND gates.
OR-AND to NOR-NOR Conversion
Similarly, for product of sums (POS) expressions, you can implement using only NOR gates. Create NOR gates for each sum term, then feed outputs into another NOR gate. This is equivalent to OR-AND.
Implementation Benefits
Using NAND or NOR exclusively simplifies chip design, as you only need one gate type. It also often reduces the total number of gates because NAND and NOR are typically more efficient to implement in the underlying technology.
5. Advanced K-Map Techniques
Don't Care Conditions
Sometimes certain input combinations never occur in practice, or their output value doesn't matter. These are marked as "don't care" (X or d) in the truth table. In K-maps, you can treat don't cares as either 0 or 1, choosing whichever helps form larger groups. This flexibility often leads to simpler final expressions.
Handling 5 and 6 Variable Functions
K-maps become unwieldy with more than 4-5 variables. For 5 variables, you can use two 4-variable maps (one for each value of the fifth variable). For 6 variables, you need four 4-variable maps. At this point, computer-aided design tools like Quine-McCluskey algorithm become more practical.
6. Quine-McCluskey Method (Brief Overview)
When K-Maps Aren't Practical
For functions with 6 or more variables, manual K-map simplification becomes impractical. The Quine-McCluskey algorithm is a tabular method that can be programmed for computer implementation.
Basic Idea
The method systematically compares minterms, combining those that differ in only one variable position. It continues iteratively until no more combinations are possible, identifying all prime implicants. Then, a prime implicant chart determines the minimum set needed to cover all minterms.
7. Practical Implementation Considerations
Trade-offs in Optimization
Sometimes the absolute minimum gate count isn't the best solution. You might prefer a structure that's easier to layout on a chip, or one that has better timing characteristics. Fan-in (number of inputs to a gate) and fan-out (number of loads on a gate output) affect circuit performance.
Multiple Output Functions
Real circuits often have multiple outputs. When simplifying, look for common terms that can be shared among outputs—this reduces total gates compared to optimizing each output independently.
Conclusion
Simplification transforms abstract Boolean functions into practical, efficient circuits. Karnaugh maps provide an elegant visual method for 4 or fewer variables, and their systematic approach makes them ideal learning tools. NAND and NOR gate realizations connect theory to real-world implementation. Understanding these techniques—and knowing when to use each—is essential for any digital logic designer. For larger problems, computerized tools take over, but the underlying concepts remain the same.