Solved Problem - Karnaugh Maps

Question

A circuit with inputs A, B, C and D is to be designed such that its output Y is given according to the following truth table.

A	B	C	D	Y		A	B	C	D	Y
0	0	0	0	0		1	0	0	0	0
0	0	0	1	1		1	0	0	1	1
0	0	1	0	1		1	0	1	0	1
0	0	1	1	1		1	0	1	1	1
0	1	0	0	1		1	1	0	0	0
0	1	0	1	1		1	1	0	1	1
0	1	1	0	0		1	1	1	0	0
0	1	1	1	0		1	1	1	1	0

 

state the simplified minterm expression for this circuit

Answer

The first step is to develop the first canconical expression (minterm form) for the truth table, this is given by

 

Next draw a correctly-labelled 4-input Karnaugh map and populate it with 1s corresponding to the individual minterms in the above expression. This gives

 

 

At this stage it is necessary to loop all of the 1s in the K-map. Remember that in order to simplify the Boolean expression as much as possible it is necessary to draw the largest loops possible. It is also necessary to include each 1 in the K-map in at least one loop. A summary of Karnaugh map looping rules is available in the lecture summary.

 

The looped Karnaugh map looks like

 

The red loop is a loop of 4 i.e. 2² and therefore allows two variables to be eliminated. The loop contains both A and B and their complements and so the resulting minterm is NOT C AND D.
The green loop is a loop of 2 and so one variable can be eliminated leaving 3 variables in the minterm. The K-map shows that this loop is independent of D and so the minterm is given by NOT A AND B AND NOT C.
The purple loop is again a loop of 4. It contains A, NOT A, D and NOT D and so these two variables can be eliminated. The corresponding minterm is NOT B AND C.
The blue loop is totally redundant as all of the 1s in the blue loop are also contained in another loop. Therefore there is no minterm from the blue loop in the simplified minterm form.

Finally the simplified minterm expression is derived by writing one term per loop and OR-ing the final terms together to give