Community › Week 3 · Building blocks
K-Maps: Simplify Boolean Logic by Drawing Boxes
A Karnaugh map (K-map) is a truth table redrawn as a grid whose rows and columns follow Gray code, so cells that touch differ in exactly one input. Circling groups of 1, 2, 4 or 8 neighbouring 1s removes the inputs that change inside each group, which gives the smallest sum-of-products expression for the circuit.
Where you'll use this
- University exams: 2, 3 and 4-variable K-maps with don't-cares come up every semester
- Hardware design: fewer terms means fewer gates, less area and less delay
- Verilog RTL: reading a synthesis report makes more sense once you have minimised logic by hand
- Interviews: "simplify F = Σm(...)" is a common written-round question
Key terms
- Minterm
- One row of the truth table where the output is 1, written as an AND of every input, plain or inverted.
- Gray code
- A counting order in which each step changes only one bit: 00, 01, 11, 10.
- Sum of products (SOP)
- An OR of AND terms, such as AB' + C. A K-map gives the shortest SOP form.
- Prime implicant
- A group of 1s on the map that cannot be made any bigger.
- Don't-care
- An input combination that never happens or whose output does not matter. It is marked X and may be grouped as a 1 or left out.
Questions people ask
Why are K-map columns ordered 00, 01, 11, 10?
That is Gray code order. Each step changes only one bit, so any two cells that touch, including across the left and right edges, differ in a single input. That one-input difference is what lets a pair of 1s drop a variable.
How big can a group be on a K-map?
A group is a rectangle of 1, 2, 4, 8 or 16 cells, always a power of two. Each doubling removes one more variable from the term, so a pair removes one, a group of four removes two and a group of eight removes three.
Do K-maps work for more than four variables?
Five and six-variable maps exist, drawn as two or four 4-variable maps side by side, but groups become hard to see. Beyond that, engineers use the Quine-McCluskey method or simply let a synthesis tool minimise the logic.
Last updated · Reviewed by the BitForBytes team
When it opens
Part 1, the interactive concept, opens Mon, 19 Oct, 7:30 pm IST. Part 2, the harder half with worked Level-Up answers, opens Thu, 22 Oct, 7 pm IST. Both are free and need no signup.
This week's challenge
Challenge #4: 4-to-1 Multiplexer: Pick a select value and watch one input's path light up, then write a 4:1 mux in Verilog. Opens Wed, 21 Oct, 7:30 pm IST.