Electronics Lessons: Reducing logical expressions using Karnaguh maps.

Up to now I've talked about systems that have only a couple of inputs.

In this tutorial I'm going to look at designing a system that has two inputs, or three inputs, or four inputs.

Karnaugh maps
Karnaugh maps are a design tool used for reducing binary expressions. the idea of a kanaugh maps is to look at the inputs to a system and the outputs of a system and write them down in such a way that they can be grouped together.

First we'll consider a very simple system.
We've got two inputs, (A and B)
We look at the system and we say.
when I apply logic 0 to input A, and logic 0 to input B the output Q is 0
when I apply logic 0 to input A, and logic 1 to input B the output Q is 0
when I apply logic 1 to input A, and logic 0 to input B the output Q is 0
when I apply logic 1 to input A, and logic 1 to input B the output Q is 1

so we draw a table that is two columns wide, and 2 rows deep.
the columns are representing input A, whilst the rows represent input B.
in the table there are four spaces, these correspond to the output state.

We then Circle the input such that we group in blocks of 1, or 2 or 4 (in squares or rectangles.)

Here we've circles a block of 1.
This tells us the output is high for conditions of A . B, we've reduced the four statements into a single statement.


A different system may have the outputs
when I apply logic 0 to input A, and logic 0 to input B the output Q is 0
when I apply logic 0 to input A, and logic 1 to input B the output Q is 1
when I apply logic 1 to input A, and logic 0 to input B the output Q is 1
when I apply logic 1 to input A, and logic 1 to input B the output Q is 1

You see when we start making circles on the map this time there is two blocks of 2.

so our out put is high for conditions of A High, or conditions of B High.

We've reduced the map to A + B


2 input systems are a bit simple, and possibly faster to see worked out in your head faster than writing a map out.
however, as a system gets more complex adding more inputs they boolean algebra involved also gets more complex, and this is where karnaugh maps start to be really useful.


 Three Input Karnaugh Maps
Assume that we're dealing with a three input system where we have outputs for the following conditions.
(/a . /b . /c) + (/a . b . /c) + (/a . b . c) + (a . /b . c)
Now to draw this karnaugh map we use four columns along the top to show states of A nd B, with two rows to show what state C is.

But each column can only differ by one single value.
this means that you can change either input A OR in put A as you move across the columns, but not both at once.
so you can't go 00, 01 10, 11 the step from 01 to 10 changes A and B at the same time
so your column headers must go 00 01 11 10

You see in this Map there are two groups of two, and a single logic high on it's own.

This means that we can reduce the statement
(/a . /b . /c) + (/a . b . /c) + (/a . b . c) + (a . /b . c)
to
(/a . /c) + (/a . b) + (a . /b .c)


Four input Karnaugh maps
For a four input karnaugh map we must use inputs a, b, c and d this means we need four rows as well as four columns, though again each time the column must not differ by more than one value at a time.

In this example we'll use the logic statement.
Q1 = /a./b./c./d + /a./b.c./d + /a./b.c.d + /a.b./c./d + /a.b.c./d + /a.b.c.d + a./b./c./d + a./b./c.d + a./b.c./d + a./b.c.d + a.b./c./d + a.b.c./d + a.b.c.d

To fill in the karnaugh map we read through the statement filling in the corresponding box on the map where the statements match.

there are 13 parts of the statement;


1 /a./b./c./d +
2 /a./b.c./d +
3 /a./b.c.d +
4 /a.b./c./d +
5 /a.b.c./d +
6 /a.b.c.d +
7 a./b./c./d +
8 a./b./c.d
 9 a./b.c./d +
10 a./b.c.d +
11 a.b./c./d +
12 a.b.c./d +
13 a.b.c.d

so the map is filled in like so:

now we replace with ones and zeros...



And we start grouping blocks of logic highs together. - grouping squares and rectangles of 1, 2, 4, 8, or 16 (obviously if we could group a block of 16 that's mean that the output was high no matter what.

We start by grouping the block of 8 at the bottom.

The common value here is C
we can see that when C is high the output of the system is high no matter what else happens in the system.

Now it looks like we have two groups of four left, (which would make the final statement, C . (/C . /D) + (A . /B)

But karnaugh maps can wrap around on themselves.
We make our loops to group logic highs where the inputs are only 1 value changed.
the first and fourth row only have 1 value changed (the value of C) so we create a loop that goes off the bottom of the table and comes back to the top.

So our logic statement is now C OR /D

Now we look at the final block of grouped values, which is the column at the end.

The consistent values here are A . /B, C and D can be anything.

The complete map looks like this:

Leaving our complete logic statement as
Red loop conditions OR Green Loop conditions OR Blue loop conditions
C + /D + (A . /B)


Q1 = /a./b./c./d + /a./b.c./d + /a./b.c.d + /a.b./c./d + /a.b.c./d + /a.b.c.d + a./b./c./d + a./b./c.d + a./b.c./d + a./b.c.d + a.b./c./d + a.b.c./d + a.b.c.d
or Q1 = C + /D + (A . /B)

Which I'm sure you'll agree is a pretty fantastic reduction, from 13 conditions down to just 3.