Karnaugh Maps

Class: CSCE-312

Notes:

What is a Karnaugh Map?

• Special form of a truth table which enables easier pattern recognition
• Pictorial method of simplifying Boolean expressions
• Good for circuit designs with up to 4 variables

Grouping Rules for K-maps

• A group must only contain 1s, no 0s
• A group can only be horizontal or vertical, not diagonal
• A group must contain 2ⁿ 1s (1,2,4,8, etc.)
• Each group should be as large as possible
• Groups may overlap
• Groups may wrap around a table
• Every 1 must be in at least one group
• There should be as few groups as possible

K-map Examples

The Majority function

• Each row of the table represents a single combination of the inputs b and c
• Each column of the table represents either 0 or 1 for the input a
  • So if b = 1, c = 1 and a = 1, the value that appears in the table aligned to this column and row is 1. This will be the value of the function.

• This is the function for the Majority function!
  • bc + ab + ac
• Things that are adjacent to each other in the K-map, are logically also adjacent to each other logically in a natural way
• Will you always group the 1s?
  • Yes
  • Groups might also be larger, you circle the larger group first.
  • Then you go on and get smaller and smaller groups

The Prime function

• List of first few numbers
  • 0:000
  • 1:001
  • 2:010
  • 3:011
  • 4:100
  • ...
• It turns out 1 is considered to be NOT a prime

• This nice K-map, with some opportunities to circle in things

• Gives you bc
  • a changes, but both b and c are true here

• a with a line on top of it is the complement of a
  • Also written as not a
  • Used basically when a has value 0
    • In this example b has two adjacent 1s when a is 0

The Parity function

• Same process as for the other functions

• Look at the table, there are no adjacent 1s!

• Still can be written as a function

Chained OR function

• In this table we have a lot to circle

• You can even circle the entire column

Prime function with 4-bit numbers

• A 4-variable truth table requires a bigger K-map

• Lets start circling

• not a not b c

• not a not b c + not a b d

• Tours = Shape of a donut
• not a not b c + not a b d + b not c d

• not a not b c + not a b d + b not c d + not b c d
• Not how these circles are connected from the outside
  • This is when b is 0, c is 1, and d is 1
  • a changes so it is not included