Digital Circuits/Karnaugh Maps
This page talks about Karnaugh maps, which are fundamental tools for analyzing and optimizing digital circuits.
Karnaugh Maps[edit | edit source]
A Karnaugh map (K-map for short) is a useful tool used in the simplification of combinational boolean equations and the creation of sequential logic circuits. Karnaugh maps were created by Maurice Karnaugh in 1953. The size of a Karnaugh map can be very large, however a size of four columns by four rows is easier to understand than any larger maps.
The philosophy behind these drawings is that differences of only one bit for the logic of a boolean equation are adjacent to each other. This is just an organizational method for a boolean logic truth table, but it can give you the ability to help simplify logical equations. This has proven to be especially useful for digital circuit designers, as it can suggest components which can be eliminated or a way to simplify circuit designs. This reduces both the cost and complexity of these designs, and even an automated method for developing these circuits assuming that you can come up with a logical truth table in the first place.
What is going to be demonstrated here is how to manually evaluate Karnaugh Maps. For very complex circuit designs that involve dozens or even hundreds of variables, there is software available that automates this process.
Structure and Creation[edit | edit source]
The structure of a Karnaugh map is grid shaped. The two most typical sizes used for instruction or for small projects is the three variable (a 2x4 grid or 4x2 depending on the user) and the four variable map (4x4 grid).
K-maps can only be created if a truth table is present; it works differently for sequential logic, which will be discussed later. A finished K-map can make a truth table, or a boolean equation vice versa. Once a truth table is acquired, a Karnaugh map can be created. The top left corner(or sometimes just the top and the left) of a K-map shows the variables used for that side.The picture of the K-map example shows the variables associated to that side. The top is A and B and the numbers below them is the state A and B are for that column (i.e. The column 10 is when A is true(high) and B is false(low)). From the truth table we put its output in the corresponding squares (i.e. If on the truth table when ABCD is 1011 and the output was 1, then on the four variable map, a 1 would go in the fourth column, second row). The following example shows how to translate a truth table to a K-map and then turn the K-map into a boolean equation.
Order of input values[edit | edit source]
On a K-map, the order in which the input values combinations are placed is of utmost importance. By looking at the example image above, it can be noticed that it doesn't use the normal, or numeric, ordering of values (00, 01, 10, 11), but instead uses (00, 01, 11, 10). Although there are usually many orderings that can be used, not all possible orderings are usable for a K-map. A formal description for valid K-map orderings would be defined by the following rules:
- The input values combinations at two adjacent rows or columns must differ in exactly one bit.
- The map is cyclic: the first and last rows are considered to be adjacent, and the first and last columns are also adjacent.
- Each possible combination of bits must appear exactly once in the map.
For two-variable maps, fulfilling this rules is trivial: one of the variables is assigned to rows, the other one to columns, and a 2x2 map can be drawn where both possible sequences (0,1 and 1,0) are valid. It's valid even to use (0,1) for one variable and (1,0) for the other. On three or four variables, either the columns or rows (or both, for 4 variables) need to hold two variables. The sequence used in the examples above (00, 01, 11, 10) works well, and is the most used; an alternative to this could be (00, 10, 11, 01). If a K-map is ever needed for a 5 or even more inputs circuit, then longer sequences need to be made up that fulfill the rules above. For three variables (8 combinations), the (000, 001, 011, 010, 110, 111, 101, 100) sequence is often used. This is enough for maps of up to 6 inputs, or 64 combinations; bigger circuits are very rarely mapped by hand, most often using specialized software to build the map and even to retrieve information from it; but, if the need arises, an appropriate combinations sequence can be made by constructing an n-bit Gray Code.
As could be noticed from later sections, optimization of circuits through K-maps relies completely in the above rules or properties of such maps, so using wrong combination sequences may lead to circuits that are not optimal, or even to circuits that do not produce the expected output.