Karnaugh Map

A Karnaugh map (or Karnaugh map) is a graphical tool used in Boolean algebra to simplify logical expressions, called Boolean functions.

It allows you to go from a canonical form (sum of products or product of sums) to a simpler equivalent expression by visually grouping adjacent cells.

The goal is to reduce the number of variables in each term, and therefore decrease the number of logic gates needed to implement a digital circuit, thus optimizing its complexity, reliability, and cost.

Determine the number of variables: a Karnaugh map has $ 2^n $ cells for $ n $ Boolean variables.

Organize the rows and columns: label the rows and columns with the binary combinations of the variables, arranged in Gray's order (only one bit changes between two adjacent cells). This ordering ensures that two neighboring cells differ by only one variable, an essential condition for simplification.

Fill the cells by placing the $ 1 $ and $ 0 $ values in each corresponding cell.

— Number of variables: Karnaugh maps are particularly well-suited for up to 4 variables (16 cells). With 5 or 6 variables, the method remains possible but quickly becomes difficult to read and use correctly. Beyond that, algorithmic methods like Quine-McCluskey or software tools are preferable.

— Subjectivity of groupings: Several valid groupings may exist for the same function, leading to different but logically equivalent expressions.

The Karnaugh map was developed in 1953 by Maurice Karnaugh, an American engineer working at Bell Labs.

It is based on Veitch diagrams, introduced in 1952, but improves upon them by systematically using Gray's order.

This innovation makes adjacencies more visible and greatly simplifies the grouping of terms, which has contributed to its widespread adoption in digital electronics and computer science.