Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (2024)

Contents

  • 1 History and nomenclature
  • 2 Usage in boolean logic
  • 3 Properties
  • 4 Size of map
  • 5 Example
    • 5.1 Truth table
    • 5.2 Map
    • 5.3 Toroidally connected
    • 5.4 Inverse
    • 5.5 Don't cares
  • 6 Race hazards
  • 7 2 variable maps
  • 8 Problems with Karnaugh maps
  • 9 See also
  • 10 External links
    • 10.1 Applications
  • 11 References
EE111 Edit/View
  • Electronic Engineering
    • EE Digital Electronics
      • Lecture, Number systems and logic states
      • Lecture, Digital Logic Gates
      • Lecture, Combinatorial Functions
      • Lecture, Karnaugh Map Reductions
      • Lecture, Arithmetic
      • Lecture, Flip-flops
    • Mid-term Exam
      • Lecture, Sequential Logic
      • Lecture, Memory Elements
      • Lecture, Registers and Counters
      • Lecture, Advanced Sequential Circuits
      • Lecture, Logic Simulation
      • Lecture, High Level Language Logic Modelling and Synthesis
    • Final Exam

The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool to facilitate management of Boolean algebraic expressions. A Karnaugh map is unique in that only one variable changes value between squares, in other words, the rows and columns are ordered according to the principles of Gray code.

History and nomenclature

[edit | edit source]

The Karnaugh map was invented in 1953 by Maurice Karnaugh, a telecommunications engineer at Bell Labs.

Usage in boolean logic

[edit | edit source]

Normally, extensive calculations are required to obtain the minimal expression of a Boolean function, but one can use a Karnaugh map instead.

Problem solving uses

  • Karnaugh maps make use of the human brain's excellent pattern-matching capability to decide which terms should be combined to get the simplest expression.
  • K-maps permit the rapid identification and elimination of potential race hazards, something that boolean equations alone cannot do.
  • A Karnaugh map is an excellent aid for simplification of up to six variables, but with more variables it becomes hard even for our brain to discern optimal patterns.
  • For problems involving more than six variables, solving the boolean expressions is more preferred than the Karnaugh map.

Karnaugh maps also help teach about Boolean functions and minimization.

Properties

[edit | edit source]

A Karnaugh map may have any number of variables, but usually works best when there are only a few - between 2 and 6 for example. Each variable contributes two possibilities to each possibility of every other variable in the system. Karnaugh maps are organized so that all the possibilities of the system are arranged in a grid form and between two adjacent boxes only one variable can change value. This is what allows it to reduce hazards.

When using a Karnaugh map to derive a minimized function, one "covers" the ones on the map by rectangular "coverings" that contain a number of boxes equal to a power of 2 (for example, 4 boxes in a line, 4 boxes in a square, 8 boxes in a rectangle, etc). All of the ones must be covered and a covering cannot have a zero in it. Once a person has covered the ones, a term of a sum of products is produced by finding the variables that do not change throughout the entire covering, and taking a 1 to mean that variable and a 0 as the complement of that variable. Doing this for every covering gives you a matching function.

One can also use zeros to derive a minimized function. The procedure is identical to the procedure for ones except that each term is a term in a product of sums - and a 1 means the complement of the variable while 0 means the variable non-complemented.

Each square in a Karnaugh map corresponds to a minterm (and maxterm). The picture to the right shows the location of each minterm on the map.

Size of map

[edit | edit source]

In a Karnaugh map with Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (3) variables, a Boolean term mentioning Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (4) of them will have a corresponding rectangle of area Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (5).Common sized maps are of 2 variables which is a 2x2 map; 3 variables which is a 2x4 map; and 4 variables which is a 4x4 map (shown below).

  • 2 variable map

  • 3 variable map

  • 4 variable map

Example

[edit | edit source]

Consider the following function of four variables (which, in binary, has a maximum number of combinations of 16):

Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (9)

The values inside Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (10) lists the minterms to map (i.e., which rows have output 1 in the truth table).

Truth table

[edit | edit source]

Using the defined minterms, the truth table can be created:

#Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (11)Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (12)Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (13)Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (14)Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (15)
000000
100010
200100
300110
401000
501010
601101
701110
810001
910011
1010101
1110111
1211001
1311011
1411101
1511110

Map

[edit | edit source]

The input variables can be combined in 16 different ways, so our Karnaugh map has to have 16 positions. The most convenient way to arrange this is in a 4x4 grid.

The binary digits in the map represent the function's output for any given combination of inputs. We write 0 in the upper leftmost corner of the map because Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (17) when Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (18), Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (19), Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (20), Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (21). Similarly we mark the bottom right corner as 1 because Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (22), Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (23), Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (24), Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (25) gives Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (26). Note that the values are ordered in a Gray code, so that precisely one variable flips between any pair of adjacent cells.

After the Karnaugh map has been constructed our next task is to find the minimal terms to use in the final expression. These terms are found by encircling groups of 1's in the map. The encirclings must be rectangular and must have an area that is a power of two (i.e. 1, 2, 4, 8, …). The rectangles should be as large as possible without containing any 0's. The optimal encirclings in this map are marked by the green, red and blue lines.

For each of these encirclings we find those variables that have the same state in each of the fields in the encircling. For the first encircling (the red one) we find that:

  • The variable Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (27) maintains the same state (1) in the whole encircling, therefore it should be included in the term for the red encircling.
  • Variable Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (28) does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
  • Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (29) does not change: it is always 0.
  • Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (30) changes.

Thus the first term in the Boolean expression is Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (31).

For the green encircling we see that Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (32) and Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (33) maintain the same state, but Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (34) and Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (35) change. Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (36) is 0 and has to be negated before it can be included. Thus the second term is Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (37).

In the same way, the blue rectangle gives the term Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (38) and so the whole expression is: Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (39).

Toroidally connected

[edit | edit source]

The grid is toroidally connected, which means that the rectangles can wrap around edges, so Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (40) is a valid term, although not part of the minimal set — this covers minterms 8, 10, 12, & 14.

Perhaps the hardest-to-visualize wrap-around term is Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (41) which covers the four corners — this covers minterms 0, 2, 8, 10.

Inverse

[edit | edit source]

The inverse of a function is solved in the same way by encircling the 0's instead.

The three terms to cover the inverse are all shown with grey boxes with different colored borders:

  • brown — Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (42)
  • gold — Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (43)
  • blue — Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (44)

This yields the inverse:

Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (45)

Through the use of De Morgan's laws, the product of sums can be determined:

Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (46)
Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (47)

Don't cares

[edit | edit source]

Karnaugh maps also allow easy minimizations of functions whose truth tables include "don't care" conditions (that is sets of inputs for which the designer doesn't care what the output is) because "don't care" conditions can be included in a ring to make it larger but do not have to be ringed. They are usually indicated on the map with a hyphen/dash/X in place of the number. The value can be a "0," "1," or the hyphen/dash/X depending on if one can use the "0" or "1" to simplify the KM more. If the "don't cares" don't help you simplify the KM more, then use the hyphen/dash/X.

The example to the right is the same above example but with minterm 15 dropped and replaced as a don't care.This allows the red term to expand all the way down and, thus, removes the green term completely.This does impact the blue inverse term and must be restricted by Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (49).

This yields the new minimum equation:

Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (50)

Note that the first term is just Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (51) not Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (52).In this case, the don't care has dropped a term (the green); simplified another (the red); and removed the race hazard (the yellow as shown in a following section).

Race hazards

[edit | edit source]

Karnaugh maps are useful for detecting and eliminating race hazards. They are very easy to spot using a Karnaugh map, because a race condition may exist when moving between any pair of adjacent, but disjointed, regions circled on the map.

  • In the above example, a potential race condition exists when C is 1 and D is 0, A is 1, and B changes from 1 to 0 (moving from the blue state to the green state). For this case, the output is defined to remain unchanged at 1, but because this transition is not covered by a specific term in the equation, a potential for a glitch (a momentary transition of the output to 0) exists.
  • A harder possible glitch to spot is when D is 0 and A and B are both 1, with C changing from 1 to 0 (moving from the blue state to the red state). In this case the glitch wraps around from the top of the map to the bottom.

Whether these glitches do occur depends on the physical nature of the implementation, and whether we need to worry about it depends on the application.

In this case, an additional term of Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (55) would eliminate the potential race hazard, bridging between the green and blue output states or blue and red output states: this is shown as the yellow region.

The term is redundant in terms of the static logic of the system, but such redundant, or consensus terms, are often needed to assure race-free dynamic performance.

2 variable maps

[edit | edit source]

The following are all the possible 2 variable, 2x2 Karnaugh maps.Listed with each is the minterms as a function of Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (56) and the race hazard free (see previous section) minimum equation.

  • E(); K=0

  • E(1); K=A'B'

  • E(2); K=AB'

  • E(3); K=A'B

  • E(4); K=AB

  • E(1,2); K=B'

  • E(1,3); K=A'

  • E(1,4); K=A'B' + AB

  • E(2,3); K=AB' + A'B

  • E(2,4); K=A

  • E(3,4); K=B

  • E(1,2,3); K=A' + B'

  • E(1,2,4); K=A + B'

  • E(1,3,4); K=A' + B

  • E(2,3,4); K=A + B

  • E(1,2,3,4); K=1

Problems with Karnaugh maps

[edit | edit source]

Karnaugh maps generally become more cluttered and hard to interpret when adding more variables. A general rule is that Karnaugh maps work well for up to four variables, and shouldn't be used at all for more than six variables. For expressions with larger numbers of variables, the Quine-McCluskey algorithm can be used. Nowadays in general the minimization process is carried out by computer, for which the Espresso heuristic logic minimizer has become the standard minimization program.

See also

[edit | edit source]

  • List of Boolean algebra topics
  • Venn diagram
  • Quine-McCluskey algorithm
  • Espresso heuristic logic minimizer
  • Karnaugh maps (above) should not be confused with Carnot cycle graphs for heat engines.

External links

[edit | edit source]

Applications

[edit | edit source]

References

[edit | edit source]

  • Karnaugh, Maurice (November 1953). "The Map Method for Synthesis of Combinational Logic Circuits". Transactions of American Institute of Electrical Engineers part I 72 (9): 593-599.
  • Katz, Randy (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company. pp.70-85. doi:10.1016/0026-2692(95)90052-7. ISBN0-8053-2703-7.
EE111 Edit/View

* Electronic Engineering * EE Digital Electronics * Lecture, Number systems and logic states * Lecture, Digital Logic Gates * Lecture, Combinatorial Functions * Lecture, Karnaugh Map Reductions * Lecture, Arithmetic * Lecture, Flip-flops * Mid-term Exam * Lecture, Sequential Logic * Lecture, Memory Elements * Lecture, Registers and Counters * Lecture, Advanced Sequential Circuits * Lecture, Logic Simulation * Lecture, High Level Language Logic Modelling and Synthesis * Final Exam

Resource type: this resource contains a lecture or lecture notes.
Digital Electronics/Lecture Karnaugh Map Reductions - Wikiversity (2024)
Top Articles
Latest Posts
Article information

Author: Dean Jakubowski Ret

Last Updated:

Views: 5924

Rating: 5 / 5 (70 voted)

Reviews: 85% of readers found this page helpful

Author information

Name: Dean Jakubowski Ret

Birthday: 1996-05-10

Address: Apt. 425 4346 Santiago Islands, Shariside, AK 38830-1874

Phone: +96313309894162

Job: Legacy Sales Designer

Hobby: Baseball, Wood carving, Candle making, Jigsaw puzzles, Lacemaking, Parkour, Drawing

Introduction: My name is Dean Jakubowski Ret, I am a enthusiastic, friendly, homely, handsome, zealous, brainy, elegant person who loves writing and wants to share my knowledge and understanding with you.