Lecture Notes: Boolean Algebra & Karnaugh Maps

1. Introduction to Karnaugh Maps

The Karnaugh Map (K-map) is a systematic method used to obtain the simplest Boolean Sum-of-Products (SOP) expression. It is a graphical technique based on a special arrangement of Venn Diagrams.

• Objective: To minimize the number of literals and "products" in a Boolean function.
• Advantage: Provides a visual aid that makes simplification easier compared to algebraic manipulation.
• Disadvantage: Generally limited to five or six variables due to increasing complexity.

Relationship with Venn Diagrams

• A K-map is essentially an abstract form of a Venn diagram arranged as a square matrix.
• Each square in the grid represents one minterm (a specific combination of inputs).
• Adjacency Rule: Adjacent squares always differ by exactly one literal. This allows the application of the theorem:
  

---

2. K-Map Structure and Variables

2-Variable K-Map

• Contains minterms.
• Arranged as a grid.

3-Variable K-Map

• Contains minterms.
• Wrap-around property: The map is continuous.
  • Leftmost column is adjacent to the rightmost column.
  • Example: () is adjacent to ().
• Each cell has 3 adjacent neighbors.

4-Variable K-Map

• Contains cells (variables ).
• Wrap-around property:
  • Horizontal: Left/Right columns wrap.
  • Vertical: Top/Bottom rows wrap.
• Each cell has 4 adjacent neighbors.
  • Example: Cell is a neighbor of and .

5-Variable K-Map

• Contains squares.
• Visualized as two 4-variable maps layered or side-by-side (representing the 5th variable changing from 0 to 1).
• Neighbors exist within the same 4-var map and in the corresponding position on the adjacent map.

3. Simplification Rules

Grouping Strategy

To get the simplest SOP expression, you must minimize the number of literals and product terms.

1. Group Size: Clusters must be a power of two ().
2. Grouping Goal: Group the largest possible number of minterms (1s) in a single cluster.
   • Larger clusters eliminate more variables.
   • 1 cell = literals (no simplification).
   • 2 cells = Eliminates 1 variable.
   • 4 cells = Eliminates 2 variables.
   • 8 cells = Eliminates 3 variables.
   • 16 cells = Eliminates 4 variables (Result is 1).
3. Overlap: Groups can overlap to maximize cluster size.

Terminology

• Implicant: A "covering" (product term) of one or more minterms.
• Prime Implicant (PI): A product term obtained by grouping the maximum possible number of adjacent minterms. It cannot be covered by a larger group.
• Essential Prime Implicant (EPI): A Prime Implicant that covers at least one minterm that is not covered by any other Prime Implicant. EPIs must be included in the final solution.

4. Algorithms for Simplification

Algorithm 1: Selecting Terms

1. Count the number of adjacent minterms for each '1' on the map.
2. Identify uncovered minterms with the least number of adjacent neighbors.
3. Create a Prime Implicant (PI) for that minterm. If multiple PIs are possible, choose the one covering the most minterms.
4. Repeat until all minterms are looped.

Algorithm 2: EPI Strategy

1. Identify and loop all Prime Implicants (PI) in the K-map.
2. Determine the Essential Prime Implicants (EPI) and include them in the expression.
3. Select the minimum subset of remaining PIs needed to cover any minterms not yet grouped by the EPIs.

5. Product of Sums (POS) Simplification

While SOP groups the 1s (minterms), POS simplification groups the 0s (maxterms).

1. Draw K-Map: Fill the map based on the function.
2. Cluster 0s: Group the 0s using the same power-of-two rules as SOP.
3. Result: The resulting expression represents .
4. Invert: Apply De Morgan's laws or simply write the complement to get in POS form.
   • Example: If grouping 0s gives , then .

Alternative Method:
Given , you can map the maxterms (missing minterms) directly and group them to find the simplified POS.

6. Don't Care Conditions

In digital logic, some input combinations never occur, or the output for a specific input does not matter. These are called Don't Care conditions, marked by X.

• Utility: Don't cares can be treated as either 1 or 0, depending on which choice yields a simpler expression.
• Strategy:
  • Treat 'X' as a 1 if it helps create a larger cluster (eliminating more literals).
  • Treat 'X' as a 0 if including it would force an extra group or smaller group.
• Example: In a BCD code executor, codes above 1001 (9) might be unused, making inputs 10-15 "Don't Cares".

Summary of Conversion

• Canonical Forms:
  • SOP (Sum of Products): Sum of minterms ( ).
  • POS (Product of Sums): Product of maxterms ( ).
• To convert non-standard SOP to K-Map:
  • Expand the expression to minterms algebraically, OR
  • Fill the K-map directly based on the literals present (e.g., if term is , place 1s in all cells where and ).