Talk:Karnaugh map

From Wikipedia, the free encyclopedia

Mathematics Portal

This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.

Mathematics rating:

B Class

Mid Priority

Field: Applied mathematics

One of the 500 most frequently viewed mathematics articles.

Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments.
Please add to or update the comments to suggest improvements to the article.
--Cronholm¹⁴⁴ 21:26, 15 June 2007 (UTC)

1 Veitch Diagram
2 Grey code
3 wrap around
4 rectangular circling
5 Pronunciation
6 Second diagram
7 Minterms
8 circling xor or xnor terms
9 Image changes
10 Map Entered Variables
11 Definition of Karnaugh Map
12 Don't cares
13 Race hazards
14 map
15 More than 4 variables
16 Link-to's
17 Circuit Design Image
18 axion law?
19 Karnaugh map example

[edit] Veitch Diagram

Although there is now a reference to the Veitch diagram, this is a little misleading. The Karnaugh Map is a special case of a Veitch Diagram. Although the original form of the Veitch diagram doesn't enjoy any sort of uses now.

This also conflicts with the idea that the Karnaugh map was 'invented' in 1950 - it is more properly an extension of existing work. Anyone have any thoughts on how to resolve this? NVeitch

Hm the C,D-row is upside-down. It should go as (0,0)-(0,1)-(1,1)-(1,0). --BL

[edit] Grey code

Perhaps we should mention that the rows and columns are ordered according to a grey code, or otherwise explain the importance of having precisely one input value flip between adjacent boxes. Bovlb 00:37, 2004 Mar 11 (UTC)

Done. Fresheneesz

[edit] wrap around

Should there be mentionted that a K-diagram is wrapped around?

So the top left and top right connect and the same goes for bottom left and bottom right.

Kind regards

I second this. Fresheneesz 08:50, 8 March 2006 (UTC)

[edit] rectangular circling

Should there be a mention that the cells need to be cirlced in a rectangular shape?

Done (not by me tho) Fresheneesz 08:52, 8 March 2006 (UTC)

Not wishing to be pedantic, but is this strictly true? When doing them by hand any rough shape that groups the right things will do - mine usually come out ellipsoid. The shape of the "circling" is not relevant to the use of the K-map, it's the grouping that matters.Graham 11:32, 8 March 2006 (UTC)

Well, not only would that be confusing, but what we mean when we say that is that the circled numbers must trace a rectangular shape. Fresheneesz 19:39, 23 March 2006 (UTC)

[edit] Pronunciation

What is the correct pronunciation of Karnaugh's name? Stern 00:00, 1 Dec 2004 (UTC)

Same as Carnot, or CAR-NO. Graham 00:08, 1 Dec 2004 (UTC)

[edit] Second diagram

What's the purpose of the second diagram? I don't understand it, it appears to duplicate the first with a less clear labelling, and the text doesn't refer to it. I think it should go. Graham 00:29, 21 Dec 2004 (UTC)

It is an alternative syntax, the one we were taught at the university. I actually find it much more clear than the first one: in this one you can see directly where A, B, C and D are ON and where they are OFF just by looking at the line/row. It should actually be rotated 90 degrees so that it could be drawn more directly from the truth table of the function (and so should the already existing map). I'll create an improved version and add a description of it to the article soon. --ZeroOne 17:57, 21 Dec 2004 (UTC)

OK, you can see the improved version here. Refresh the image if it doesn't differ from the one you saw - it is updated:

The little numbers at the corner of each square are the row numbers of the truth table of the function. It is otherwise from 0 to 15, left to right, up to down but the two last columns and two last rows are flipped. There's nothing strange in that, the existing map has the same feature, too. The area "A{", two last rows, is where A is 1. The area "}B", two middle rows, is where B is 1. The area "C{", two last columns, is where C is 1 and the area "D{", two middle columns, is where D is 1. What do you think now? --ZeroOne 18:41, 21 Dec 2004 (UTC)

Weeellll.... to be honest I've been using Karnaugh maps for years and have never seen this form. I'm trying to figure out exactly what it is portraying just by looking at it, and I'm afraid I still don't get it. Maybe I'm just too used to the "old" form. Seems to me the need for the row numbers to be put in each square to help make sense of it mean it might not be as effective as the "old" type - with that one, I can see at a glance what the terms need to be and can simply write them down without any interpretation - but again I'm willing to put that down to familiarity. The flipping of the columns you mention is indeed a feature of the normal map - that's because the bit ordering needs to follow a gray code - something that the article fails to mention, but probably should. Maybe the explanatory text you plan to write will help the lightbulb go on, but the diagram on its own doesn't work for me - but maybe others here will have more to say about it? Graham 22:39, 21 Dec 2004 (UTC)

You don't need those row numbers, you learn them quickly and can always deduce them again should you forget them. Actually the map I'm showing is no different from your map: it just emphasizes the ones better. That is, the rows and columns where a certain variable is 1 are "grouped" with the {'s. The squares which do not belong to a given group belong to the negation (where the variable is 0) of that group. I found a nice picture from the teaching material of my university: [1]. It combines both of the maps in the same picture (because they actually are the same map). Maybe *that* will explain it to you too? :) To add, to me the current map looks almost like if it had 8 rows and 8 columns. The amount of variables shown is too big to handle effectively. --ZeroOne 23:22, 21 Dec 2004 (UTC)

Ah, OK, I get it now. The image on your uni site adds the crucial "lightbulb" detail for me - the AB/CD labelling in the top corner. That said I'm not really convinced that this method is really any better than the normal one - perhaps I was expecting the advantage to be much greater than what is really just a small change to the way the columns and rows are labelled. I'd like to hear some other opinions on this though. By the way, the appearance of 8 columns rather than 4 is not something I'd really found before, since it's clear to me that it is PAIRS of variables that are being considered by each column. Graham 23:47, 21 Dec 2004 (UTC)p

[edit] Minterms

Image:Karnaugh_map_showing_minterms.png

I made the above picture to specify how to find minterms from a karnaugh map. I didn't put this on the main page, because I'm not sure if this is univerasal. Comments please. Fresheneesz 04:57, 6 March 2006 (UTC)

I have made an SVG image Image:K-map minterms.svg. Cburnett 06:06, 22 December 2006 (UTC)

[edit] circling xor or xnor terms

This article should mention the possibility and how-to of finding xor terms when minimizing. Fresheneesz 01:56, 19 October 2006 (UTC)

A karnaugh map doesn't attempt to get the minimum form, it attempts to get the minimum form for a two stage implementation using a particular gate in each stage. Yes there may be tricks that allow one to occasionally spot that there is another way that might save a bit when working in discrete logic but they aren't the main purpose of the maps. Plugwash 16:04, 20 October 2006 (UTC)

Are you talking about Reed-Muller logic ? --68.0.120.35 14:58, 7 December 2006 (UTC)

[edit] Image changes

I created a few SVG images for this article and, in the process, discovered the listed minterms were not reflected correctly in the images. Please, give the example a thorough review if you have a chance. I did confirm what I could with [2]. Cburnett 08:08, 22 December 2006 (UTC)

Under Race hazards, first bullet point - shouldn't that read when C is 1, D is 0 and not "when C and D are both 0"? I could be wrong - it's only been 30 years since I have looked at these. Great graphic by the way.--Larry In Cincinnati 03:31, 7 January 2007 (UTC)

Correct and I've fixed it. Thanks for the complements on the graphics. :) Cburnett 04:01, 7 January 2007 (UTC)

[edit] Map Entered Variables

Should these be mentioned?

[edit] Definition of Karnaugh Map

What is a Karnaugh map? Neither in your article, nor in the general literature on the subject, will you find a definition (with one exception). Given a function $f:\{0,1\}^n \mapsto \{0,1\}$ , we call its $2 n$ 'arguments' $(x_1,\dots,x_n)$ — each an element of ${0,1} n$ — an input combination or input event. We can now define:

A Karnaugh map for n input variables $x_1,\dots,x_n$ is a Venn diagram whose universe consists of all $2 n$ input events $(x_1,\dots,x_n)$ . The sets defined and pictured on the universe are n non-disjoint sets $\mathcal{X}_1,\dots,\mathcal{X}_n$ , any such set $\mathcal{X}_i$ containing all input events whose i-th input variable $x i$ is 1, i.e., $(x_1,\dots,x_i,\dots,x_n)\in \mathcal{X}_i\Leftrightarrow x_i=1$ .

Karnaugh maps and their usage are covered quite extensively in chapters 6, 7 and 21 (Reduced K-maps) of

Shimon P. Vingron:'Switching Theory. Insight through Predicate Logic' Springer-Verlag, 2004, ISBN 3-540-40343-4.

I have not put this, and other aspects touched on in the above reference, in the main article so as not to intrude on your work: I leave it to you whether you want to make use of the above comment.

S.P.Vingron, 81.217.16.172 14:16, 28 August 2007 (UTC)

[edit] Don't cares

Why must the blue inverse term be restricted by $\overline{A}$ ? If we really don't care about the m15 case, it can be treated as 1 for the non-inverse case and 0 for the inverse case; while this makes the non-inverse and inverse cases non-equivalent for all inputs, they are still equivalent for all inputs that we care about.

However, it doesn't really matter, since treating the don't-care as 1 allows the inverse function to be simplified to $F = \left(A + B\right)\left(A + C\right)\left(A + \overline{D}\right)$ . I can't take credit for this second bit though, an applet gave it to me when I was checking the first paragraph. Anomie 17:07, 14 October 2007 (UTC)

[edit] Race hazards

Shouldn't the $\left(A + \overline{D}\right)$ term be added to the inverse case to remove a hazard when moving from m7 to either m3 or m5? Anomie 17:07, 14 October 2007 (UTC)

[edit] map

For the green encircling, besides A and B, C also maintains the same state of 1. So, shouldn't the second term be $A\overline{B}C$ and not $A\overline{B}$ ?

Sepia tone 04:40, 25 October 2007 (UTC)

I don't know which image you're looking at, but I can't find one where a green encircling has C remaining unchanged. In Image:K-map 6,8,9,10,11,12,13,14.svg, for example, the green circles all four minterms in the rightmost ( $A\overline{B}$ ) column, overlapping with the right half of the red group. Anomie 11:20, 25 October 2007 (UTC)

You are right. My bad. Sepia tone (talk) 02:53, 30 November 2007 (UTC)

[edit] More than 4 variables

Can we have examples for 5 and 6 variables?

For 5 variables A,B,C,D,E: We can make a 4 variable frame A,B,C,D, then fill in each entry with 1,0,x(don't care),E,e(Ebar). Then but in the circles, noting that E is not 0 and is not 1.

Truth table

Map

  |0110|C
  |0011|D
--|----|
00|EEEE|
10|0110|
11|1010|
01|EEEE|
--|----|
AB|

Out=aE+AbC+aCD+ABcd

No, usually you would use Boolean Algebra when simplifying five, six, or more variable circuits. It's certainly possible, but do you really want to have thirty-two squares to fill out? ChyranandChloe (talk) 02:29, 14 June 2008 (UTC)

[edit] Link-to's

Shouldn't entries such as K-Map link to this page? Thanks

129.7.108.128 (talk) 18:28, 6 February 2008 (UTC)

K-map does, K-Map doesn't because "map" isn't capitalized. But if you put "K-Map" in the search box then you hit this article just fine. Cburnett (talk) 19:03, 6 February 2008 (UTC)

[edit] Circuit Design Image

I think it would helpful if we could include a unsimplified digital electronic circuit design and a simplified circuit design in addition to the boolean algebra - it makes it difficult to apply if you don't have the circuit to refer to. ChyranandChloe (talk) 00:01, 30 May 2008 (UTC)

[edit] axion law?

What the heck is the "axion law"? This term is used at least twice in this article, and links to the boolean logic page, in which the word "axion" never appears. linas (talk) 21:34, 4 June 2008 (UTC)

It is "axiom laws" (an axion is a hypothetical elementary partial - in physics). An Axiom is a postulate, a assumption that is accepted and known to be true. The way that is is used in the article (and in boolean algebra) is that we automatically accept that if you have A and NOT A they cancel each other out; it's like adding

- 1

and

1

, you get

0

. They go to a lot of trouble explaining it in the Boolean algebra page:

"...Two Boolean laws having no numeric counterpart are the laws characterizing logical negation, namely x∧¬x = 0..."

∧ = AND; ¬ = NOT by the way. The edit fixes are made, thanks. ChyranandChloe (talk) 01:55, 6 June 2008 (UTC)

[edit] Karnaugh map example

In the example diagram it is not obvious that the brown section is the overlapping of the red and green sections. This got me confused for quite a while! I suggest that using eg striped red and green for the overlapping section, or make the outlines easier to see.--Czar Kirk (talk) 04:30, 13 June 2008 (UTC)

I suggest we stop coloring our K-maps or at least the inverses. I'll make an effort to redo them, but I'm still learning how to use Inkscape. ChyranandChloe (talk) 02:29, 14 June 2008 (UTC)

Yeah, the current colouring scheme is illegible. I'd suggest using multiple maps to avoid the tangle. Dcoetzee 02:34, 14 June 2008 (UTC)