Karnaugh Maps (Digital Logic Optimization)

David A. Snyder, P.E.

Course Outline

This 6 PDH course shows how to rearrange a truth table into a Karnaugh map and how to derive an optimum logical expression from the Karnaugh map.  It is important to optimize (reduce and simplify) the digital function in order to do away with extraneous, unnecessary logic components that add cost and complexity to the design without providing any benefit.  The concepts of minterms (sum of products) and maxterms (product of sums) will be explained and the use of both will be illustrated.  The concept of “don’t care” conditions will be discussed, and the effects of these conditions on the optimization of the logical functions will be clearly demonstrated.  Many illustrations and several examples are given to increase the reader’s understanding of the subject matter.

This course includes a multiple-choice quiz at the end, which is designed to enhance the understanding of the course materials.

Learning Objective

The following learning objectives are included in this course:

• Understand the concept of truth tables;
• Become acquainted with the concept of minterms;
• Become acquainted with the concept of maxterms;
• Understand the concept of checking the equality of two seemingly different logical functions by using a truth table;
• Observe that Boolean algebra can be used to prove the equality of two seemingly different logical functions;
• Understand how the optimization of a logical function can reduce the required number of gates or relay contacts and therefore reduce the cost of a project;
• Understand how to convert truth tables to Karnaugh maps;
• Use Karnaugh maps to determine a minterm expression for the logical function;
• Use Karnaugh maps to determine a minterm expression for the logical function;
• Understand the concept of logical adjacency between cells, rows, columns, and corners of Karnaugh maps of various sizes;
• Understand that 5-bit and 6-bit Karnaugh maps can be thought of as two or four 4-bit Karnaugh maps, respectively;
• Understand the concept of logical adjacency between different 4-bit portions of 5-bit and 6-bit Karnaugh maps;
• Understand the concept of Gray codes;
• Understand the difference between ‘regular’ Gray codes and the special type called reflected Gray codes;
• Understand the concept of “don’t care” conditions and how they can be used to further optimize the logical functions;
• Understand the concept of using the same “don’t care” condition as a 1 or a 0, as desired;
• Understand that a single Karnaugh map can produce two different functions that are equally optimized, though logically unequivalent; and
• Perform optimization of any binary function with as many as six input variables by using Karnaugh maps.

Intended Audience

Anyone who is involved in the design of relay logic (such as control panels) or gate logic (such as electronic circuit boards) will benefit from this course.

Benefit for Attendee

Upon successful completion of the course, the reader will have a thorough understanding of the use of Karnaugh maps to determine an optimum logical expression of a given digital (binary) function.  This function could be described by a truth table or as a binary equation, in the form of minterms (sum of products) like x + x’y + yz’, or in the form of maxterms (product of sums) like (x+y)(x’+z)(x+y’+z’).

Course Introduction

A truth table is one means of defining the output requirements of a digital (binary) function, based on all of the possible input conditions.  The truth table assigns a value of 1 (true or on) or 0 (false or off) to the output of each unique combination of input variables.  A Karnaugh map rearranges the information presented in the truth table such that cells with a value of 1 can be grouped together if they are logically adjacent to each other.  This grouping will reveal which of the input variables can be ignored, since they aren’t required to implement the digital function.  This technique works the same way when grouping together cells that have a value of 0.  When the optimized function has been extracted from the Karnaugh map, it can be used to design gate logic or relay logic that uses fewer components than would have been required if only the truth table were used to design the logic.  Several examples of the results of optimization are presented in this course, as well as the concept of “don’t care” conditions and the resulting further optimization that can be realized.

Course Content

The course content is in the following PDF file:

Karnaugh Maps (Digital Logic Optimization)

Please click on the above underlined hypertext to view, download or print the document for your study. Because of the file size, we recommend that you first save the file to your computer by right-clicking the mouse and choosing "Save Target As ...", and then open the file in Adobe Acrobat Reader from your computer.

Course Summary

Digital (binary) logic is being designed every day in the form of relay logic (in control panels, switchgear, and automobiles) and gate logic (integrated circuits on circuit boards, in computers, in televisions, and also in automobiles.).  The concepts presented in this course are used to optimize the design of that logic by reducing the required number of components (relay contacts or integrated circuit chips), as well as reducing the amount of interconnecting wiring.  This optimization reduces the cost, size, and complexity of projects and products.

Quiz

Once you finish studying the above course content, you need to take a quiz to obtain the PDH credits.

DISCLAIMER: The materials contained in the online course are not intended as a representation or warranty on the part of PDH Center or any other person/organization named herein. The materials are for general information only. They are not a substitute for competent professional advice. Application of this information to a specific project should be reviewed by a registered architect and/or professional engineer/surveyor. Anyone making use of the information set forth herein does so at their own risk and assumes any and all resulting liability arising therefrom.