Karnaugh Maps
Karnaugh Maps
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
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
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:
1.
The input values combinations at two adjacent rows or columns must
differ in exactly one bit.
2.
The map is cyclic: the first and last rows are considered to be
adjacent, and the first and last columns are also adjacent.
3.
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.
Categories:
Digital Electronics
0 comments:
Post a Comment