Karnaugh Maps (OCR A Level Computer Science)

Karnaugh Maps

What is a Karnaugh Map?

• This is a tool that is used for simplifying Boolean algebra expressions

• It offers a visual method of grouping together expressions with common factors

• The format of the map makes it easy to identify and eliminate redundant terms

• They are used in digital logic design, such as simplifying the logic of digital circuits

Steps:

1. Create the Map: Each cell in the grid corresponds to a term in the Boolean expression. Fill cells with 1s and 0s corresponding to the output of that term

2. Grouping: Group the 1s in the grid. Each group must be a rectangle and the size of the group must be a power of 2. A cell can be part of multiple groups

3. Simplifying: Write down a simplified Boolean expression for each group. The simplified expression for a group consists of the variables that remain constant in all terms in the group

4. Final Expression: Combine the simplified expressions from each group using OR operations to get the final simplified Boolean expression

Creating Karnaugh Maps

• A Karnaugh Map (KMap) can be used to simplify a Boolean expression with 2 inputs

• Here is an example for the expression A V B (A OR B)

Step 1

• Add each variable starting with A at the top and B down the side

• Add each possible state for A and B

Step 2

• Take each expression in turn separated by the V (OR)

• First look at A on it's own

• Find all cells where A is 1

• Add 1 to the cell

Step 3

• Repeat for B

Step 4

• This is now a completed KMap for the expression A V B (A OR B)

Simplifying Expressions Using Karnaugh Maps

Simplify ¬A^¬B^C v ¬A^B^¬C v A^¬B^C v A^B using a KMap.

In this example there will be 3 variables A,B and C so the empty KMap will look like this:

Step 1:

Split this long term at each OR giving 4 smaller expressions (subterms) to add to the table:

• ¬A^¬B^C

• ¬A^B^¬C

• A^¬B^C

• A^B

Step 2: 

• Take the first subterm ¬A^¬B^C

• Put a 1 in the map for every cell where this term would be TRUE (1)

• So if A and B were 0 and C was 1 this subterm would be 1

• So put a 1 in every cell in the KMap where A is 0, B is 0 and C is 1

Step 3:

• The next subterm is ¬A^B^¬C

• Put a 1 in the KMap where A is 0, B is 1 and C is 0

Step 4:

• The next subterm is A^¬B^C

• Put a 1 in the KMap where A is 1, B is 0 and C is 1

Step 5:

• The final subterm is A^B

• Put a 1 in the KMap where A is 1 and B is 1 (2 cells this time)

Making the groups

• Once you have written the 1s and 0s into your KMap, you can then use this to simply the expression

• In order to do this, you need to identify the groups

• This is the key to using the Karnaugh map to derive the simplified expression

• The aim of making the groups is to

  • Make rectangular groups 

  • Make groups that are as large as possible

  • Make groups that contain either 8,4,2 or 1 ones

  • Groups can overlap (i.e. some ones can be in multiple groups)

  • The Karnaugh map ‘grid’ wraps round in all directions so the groups can wrap round

Example grouping

Group 1:

So this would be one group.

This group would represent A since within this group both C and B change (have zeros and ones) whereas for A all the cells are one.

Group 2:

This would be another group (note the wrapping around).

This group would represent ¬B since within this group both A and C change (have zeros and ones) whereas for B all the cells are zero

Final simplified expression

• To get the final simplified expression we OR the terms representing the two groups together.

• So the simplified expression is A v ¬B