Show understanding of Karnaugh maps (K-map)

15.2 Boolean Algebra and Logic Circuits – Karnaugh Maps (K‑maps)

Learning Objective

Demonstrate a clear understanding of Karnaugh maps and use them to minimise Boolean expressions for both SOP and POS forms, producing efficient logic‑circuit designs (including half‑adders and full‑adders) as required by the Cambridge International AS & A Level Computer Science (9618) syllabus.

Syllabus Alignment – Quick‑Reference Map

Foundations – AS‑level Recap (Units 1‑8)

• Binary numbers & truth tables – every Boolean function can be described by a truth table of 0’s and 1’s.
• Logic gates – AND, OR, NOT, NAND, NOR, XOR, XNOR. Their symbols and truth tables are the building blocks for combinational circuits.
• Combinational vs sequential circuits – K‑maps apply only to combinational (memory‑less) functions.
• Why minimisation matters – fewer literals → fewer gates → lower cost, power, and propagation delay.

Link‑in to Algorithmic Design (Units 9‑12)

When Boolean functions are implemented in hardware description languages (e.g., VHDL, Verilog) or compiled into micro‑code, a minimal expression reduces the number of instructions the compiler must generate. This directly influences algorithmic efficiency and the overall software development life‑cycle.

Why Use Karnaugh Maps?

• Visual, systematic method for minimising Boolean functions without lengthy algebraic manipulation.
• Groups of 1’s (for SOP) or 0’s (for POS) correspond to product‑terms or sum‑terms.
• Reduces the number of literals and gates → simpler, cheaper, faster circuits.
• Handles “don’t‑care” (X) conditions efficiently, often allowing larger groups.

Basic Concepts

1. Cell layout – each cell represents a unique combination of variable states (binary code).
2. Adjacency – cells that differ in only one variable are adjacent; the map wraps around on all edges (toroidal adjacency).
3. Grouping rules – groups must contain 1, 2, 4, 8 … cells (powers of two) and be as large as possible; groups may wrap around edges.
4. Don’t‑care cells (X) – may be treated as 1 or 0 to enable larger groups, provided the required output is unchanged.

K‑map Size Selection

Step‑by‑Step Procedure (SOP)

1. Write the truth table for the function (include X for don’t‑care).
2. Select the appropriate K‑map size (see table above).
3. Transfer the output values into the K‑map, preserving Gray‑code order for rows and columns.
4. Identify the largest possible groups of 1’s. Use X cells if they enlarge a group.
5. For each group, write the product term:

   • Eliminate any variable that changes within the group.
   • Keep a variable in true form if it is 1 throughout the group; otherwise use its complement (A′).

6. Combine all product terms with logical OR ( + ) to obtain the minimal SOP.

Step‑by‑Step Procedure (POS)

Worked Example 1 – 4‑Variable SOP

Function: F(A,B,C,D) – truth table given below.

Step 1 – K‑map layout (AB = rows, CD = columns, Gray code order)

Step 2 – Form the largest groups of 1’s

• Group 1 – four 1’s (minterms 2, 3, 6, 7) → product term A′ C
• Group 2 – four 1’s (minterms 1, 5, 9, 13) → product term B′ D
• Group 3 – two 1’s (minterms 8, 10) → product term A D′

Step 3 – Minimal SOP

Worked Example 2 – Using Don’t‑Care Conditions

Assume the same function with don’t‑care conditions at minterms 3 and 12 (X). Including them may allow larger groups.

Updated K‑map (X shown in light grey)

New grouping

• Eight‑cell group (rows 00 & 01, columns 01 & 11) → product term B′
• Four‑cell group (row 10, columns 00 & 10) → product term A D′

Resulting minimal SOP

Using the don’t‑care cells reduced the expression from three product terms to two, saving one gate.

Worked Example 3 – POS Minimisation (3 Variables)

Function: G(A,B,C) = Π M(0,2,5,7) (i.e., G = 0 for minterms 0, 2, 5, 7).

Step 1 – Group the 0’s (including wrap‑around)

• Group A – four 0’s covering column C=0 → sum term (C + A′) (C is 0 throughout, A varies → use A′).
• Group B – two 0’s at minterms 2 and 6 → sum term (B + C′) (B is 0 throughout, C varies → use C′).

Minimal POS

Worked Example 4 – Half‑Adder Design Using K‑maps

The half‑adder adds two single‑bit binary numbers (A and B). Its two outputs are:

• Sum = A ⊕ B
• Carry = A · B

Sum (XOR) – SOP minimisation

2‑variable K‑map (A = rows, B = columns)

Two 1’s are diagonally opposite; they cannot be grouped together, so each forms a 1‑cell group:

• Cell (A=0, B=1) → product term A′ B
• Cell (A=1, B=0) → product term A B′

Minimal SOP for Sum

Carry – SOP minimisation (trivial)

Only minterm 3 (A=1, B=1) is a 1, giving the product term A B.

Minimal SOP for Carry

Resulting Half‑Adder Circuit

• Sum output: two‑input XOR gate (or the SOP expression above).
• Carry output: single AND gate.

Worked Example 5 – Full‑Adder Design (3 Variables) Using K‑maps

Inputs: A, B, Cin. Outputs: Sum, Cout.

Sum (A ⊕ B ⊕ Cin) – SOP

1. Construct the 3‑variable truth table (8 rows).
2. Place the 1’s (minterms 1, 2, 4, 7) on a 2 × 4 K‑map (AB = rows, C = columns).
3. Group as two 4‑cell groups:

   • Group 1 → A′ B Cin
   • Group 2 → A B′ Cin′

4. Combine → Sum = A′ B Cin + A B′ Cin′ + A B Cin′ + A′ B′ Cin, which simplifies to the well‑known XOR chain.

Cout (majority function) – SOP

• 1’s at minterms 3, 5, 6, 7.
• Group as a 4‑cell block (AB = 11) → product term A B.
• Group as a 2‑cell block (A = 1, Cin = 1) → product term A Cin.
• Group as a 2‑cell block (B = 1, Cin = 1) → product term B Cin.

Minimal SOP for Cout

Key Boolean Identities Used in Minimisation

• Complementarity