Logic minimisation with Karnaugh maps

Karnaugh-map minimisation in SOP and POS form with prime and essential prime implicants, don't-cares, cyclic maps and hazards.

Drafted with Aria, reviewed by the AiCanCode.org team. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Every gate you remove from a logic circuit saves cost, power, board area and propagation delay. Karnaugh maps let you find the minimum two-level (AND-OR or OR-AND) circuit for functions of up to four or five variables by eye, and they show where don't-care input combinations, such as unused BCD codes, can be exploited.

Key ideas

What a K-map is. A K-map is a truth table redrawn as a grid in which every cell is one minterm and neighbouring cells differ in exactly one variable. Rows and columns are labelled in Gray-code order (00, 01, 11, 10), so the map wraps around: the left edge is adjacent to the right edge, the top to the bottom, and in a 4-variable map the four corners are mutually adjacent.

Cell numbering (4 variables, A B as rows, C D as columns). Row order 00, 01, 11, 10 and column order 00, 01, 11, 10 give the cell layout

  • row AB = 00: m0, m1, m3, m2
  • row AB = 01: m4, m5, m7, m6
  • row AB = 11: m12, m13, m15, m14
  • row AB = 10: m8, m9, m11, m10

Grouping rules (SOP).

  • Group only 1s (and, optionally, don't-cares X) in rectangles of 1, 2, 4, 8 or 16 cells, i.e. 2ᵏ cells.
  • A group of 2ᵏ cells in an n-variable map eliminates k variables and leaves a product of n − k literals.
  • Make every group as large as possible; such a group is a prime implicant (PI).
  • A PI that alone covers some 1 is an essential prime implicant (EPI); every EPI must appear in the answer.
  • After the EPIs, cover the remaining 1s with as few, as large PIs as possible. Don't-cares are used only if they enlarge a group; they never need to be covered.

POS form. Group the 0s instead. Each group gives a sum term in which a variable that is 0 throughout the group appears uncomplemented and one that is 1 appears complemented. Equivalently, find the minimal SOP of F' and apply De Morgan.

Cyclic maps and non-uniqueness. Some functions have no EPIs and two equally minimal answers (for example Σm(0, 1, 2, 5, 6, 7) in three variables). Either answer is correct; GATE questions on this usually ask for the number of literals or the number of PIs, which is the same for both.

Limits. K-maps are practical up to 4 variables and workable for 5 or 6 (two or four 4-variable maps stacked). Beyond that, use the tabular Quine–McCluskey method or software (Espresso). K-maps minimise two-level logic only; multilevel factoring or XOR forms (for parity) can be smaller still, and XOR functions give checkerboard maps that do not simplify at all.

Hazards. A static-1 hazard can occur when two adjacent 1-cells are covered by different groups that do not overlap; adding the redundant consensus group removes it. This is one place where the minimal circuit is deliberately not used.

Formulas

Number of cells = 2ⁿ

  • n: number of input variables.

Literals in a group term = n − k for a group of 2ᵏ cells

  • k: number of variables eliminated.

Number of minterms in a term with p literals = 2^(n − p)

F (POS) = [minimal SOP of F′]′ (De Morgan)

A·B + A′·C = A·B + A′·C + B·C (consensus term BC removes the static hazard)

Worked examples

Example 1 (standard). Simplify F(A, B, C) = Σm(0, 1, 2, 5, 6, 7).

  1. Three-variable map: rows A = 0, 1; columns BC = 00, 01, 11, 10. Row A = 0 holds m0, m1, m3, m2 = 1, 1, 0, 1. Row A = 1 holds m4, m5, m7, m6 = 0, 1, 1, 1.
  2. No 1 can be put into a group of four, and every 1 has two neighbouring 1s, so no prime implicant is essential: the map is cyclic.
  3. The six pairs (prime implicants) are A′B′ (m0, m1), A′C′ (m0, m2), B′C (m1, m5), BC′ (m2, m6), AC (m5, m7), AB (m6, m7).
  4. Three pairs suffice: A′B′ + BC′ + AC, or alternatively A′C′ + B′C + AB.

Answer: F = A′B′ + BC′ + AC (or A′C′ + B′C + AB): 3 terms, 6 literals

Example 2 (GATE level). F(A, B, C, D) = Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15). Find the minimal SOP and minimal POS.

  1. Place 1s at 2, 3, 7, 9, 11, 13 and X at 1, 10, 15.
  2. Group 9, 11, 13, 15 (rows AB = 11, 10; columns CD = 01, 11): A and D are constant at 1 → AD.
  3. Group 2, 3, 10, 11 (rows AB = 00, 10; columns CD = 11, 10): B = 0, C = 1 → B′C.
  4. Minterm 7 remains. Group 3, 7, 11, 15 (column CD = 11) → CD.
  5. SOP: F = AD + B′C + CD (3 terms, 6 literals).
  6. For POS, the 0s are 0, 4, 5, 6, 8, 12, 14. Group the 0s, now free to use don't-cares 1 and 10 as 0s: A′C′ (0, 1, 4, 5), AD′ (8, 10, 12, 14) and BD′ (4, 6, 12, 14), so F′ = A′C′ + AD′ + BD′.
  7. De Morgan: F = (A + C)(A′ + D)(B′ + D).
  8. Check row m9 (A = 1, B = 0, C = 0, D = 1): SOP gives AD = 1; POS gives (1)(1)(1) = 1. Both agree. (The SOP and POS answers may differ on the don't-care rows, here m10, because each minimisation chooses its own values for X; both are correct.)

Answer: F = AD + B′C + CD = (A + C)(A′ + D)(B′ + D)

Example 3 (quick). F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15). The four corners (0, 2, 8, 10) give B′D′; the centre block (5, 7, 13, 15) gives BD.

Answer: F = B′D′ + BD (the XNOR of B and D)

Common mistakes

  • Numbering cells in binary order (00, 01, 10, 11) instead of Gray order, which breaks adjacency.
  • Forgetting the wrap-around and corner adjacencies.
  • Making groups of 3, 6 or other non-powers of two, or L-shaped groups.
  • Covering every don't-care, or ignoring don't-cares that would enlarge a group.
  • Writing POS terms with the wrong polarity: in POS a variable that is 0 over the group appears uncomplemented.
  • Adding a non-essential PI that is already fully covered by others.

For GATE IN

Typical questions give a function in Σm form (often with don't-cares) and ask for the minimal expression, the number of prime implicants or essential prime implicants, or the number of literals; others ask whether two expressions are equivalent or which form a given gate circuit implements. Practise drawing 4-variable maps quickly with correct cell numbers and checking your answer against two or three rows of the truth table.

Quick check

  1. Simplify F(A, B, C) = Σm(1, 3, 5, 7).
  2. How many literals does a group of 4 cells in a 4-variable map leave?
  3. Which cells are adjacent to m0 in a 4-variable map?
  4. Simplify F(A, B, C, D) = Σm(0, 2, 8, 10).

Answers: 1. C 2. 2 3. m1, m2, m4, m8 4. B′D′

Interview questions

All Digital Electronics and Microcontrollers interview questions

Try answering each one aloud before you open it.

  1. 1.What is a Karnaugh map and why is it used in digital electronics?Concept

    A Karnaugh map, or K-map, is a graphical tool used to simplify Boolean algebra expressions. It helps in minimizing logic functions by organizing truth table values into a visual format that makes it easier to identify patterns and eliminate redundant terms. This simplification is crucial in digital electronics to reduce the complexity of digital circuits, which can lead to cost savings and improved performance.

  2. 2.Explain the process of grouping in a Karnaugh map.Concept

    Grouping in a Karnaugh map involves combining adjacent cells that contain the value '1' (for SOP) or '0' (for POS) into groups of 1, 2, 4, 8, etc. These groups must be rectangular and can wrap around the edges of the map. The goal is to create the largest possible groups to simplify the Boolean expression. Each group corresponds to a simplified product term in the case of SOP or a sum term in the case of POS.

  3. 3.How does a Karnaugh map differ from a truth table?Concept

    A truth table lists all possible combinations of inputs and their corresponding outputs, providing a complete representation of a logic function. In contrast, a Karnaugh map is a visual representation that organizes these outputs in a way that highlights opportunities for simplification. While a truth table is useful for understanding the function, a K-map is specifically designed to aid in minimizing the logic expression.

  4. 4.Why is logic minimization important in digital circuit design?Application

    Logic minimization is important because it reduces the number of gates and connections required in a digital circuit. This leads to lower power consumption, reduced physical space, and potentially lower costs. Additionally, simpler circuits are generally more reliable and easier to troubleshoot and maintain.

  5. 5.What happens if you incorrectly group cells in a Karnaugh map?Application

    Incorrectly grouping cells in a Karnaugh map can lead to an incorrect simplified Boolean expression. This may result in a digital circuit that does not perform the intended logic function, leading to errors in the system's operation. It is crucial to follow the rules of grouping to ensure the accuracy of the simplification.

  6. 6.How can Karnaugh maps be used to simplify a logic function with don't-care conditions?Application

    Don't-care conditions in a Karnaugh map are represented by 'X' and can be used flexibly to form larger groups. These conditions can be treated as either '1' or '0' to help create the largest possible groups, leading to a more simplified expression. This flexibility allows for further reduction in the complexity of the logic function.

  7. 7.What is the significance of wrapping around the edges in a Karnaugh map?Application

    Wrapping around the edges in a Karnaugh map allows for the creation of larger groups by considering the map as a toroidal structure. This means that the cells on the edges are adjacent to each other, enabling the formation of groups that span across the boundaries. This technique is essential for achieving the most simplified expression possible.

  8. 8.Given a 3-variable Karnaugh map with the minterms 1, 3, 5 and 7, simplify the logic expression.Numerical

    Minterms 1, 3, 5 and 7 are exactly the rows where the least significant variable C = 1 (001, 011, 101, 111). On the map they form one group of four, which eliminates A and B, so F = C. A single wire, no gates at all.

  9. 9.Simplify F(A, B, C, D) = Σm(0, 1, 2, 5, 6, 7, 8, 9, 10, 14) using a Karnaugh map.Numerical

    Group 0, 1, 8, 9 (B = 0, C = 0) to get B′C′, and 2, 6, 10, 14 (C = 1, D = 0) to get CD′. Minterms 5 and 7 remain; the largest group containing them is 5, 7 (A = 0, B = 1, D = 1), giving A′BD. So F = B′C′ + CD′ + A′BD: three terms and seven literals, which a truth-table check confirms.

  10. 10.What are the limitations of using Karnaugh maps for logic minimization?Application

    K-maps are practical only up to about four variables and become error-prone at five or six, where stacked maps are needed. They give minimal two-level (SOP or POS) logic only, so they miss smaller multilevel or XOR-based forms. They are a manual method; for many variables or for automated design, the Quine-McCluskey tabular method or heuristic tools such as Espresso are used instead.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?

PreviousNumber systems, codes and Boolean algebraNext Logic families: TTL and CMOS characteristics