Karnaugh Map

 

In combinatorial logic minimization, a device known as a Karnaugh map is frequently used. It is similar to a truth table, but the various variables are represented along two axes and are arranged in such a way that only one input bit changes in going from one square to an adjacent square. It is also known as a Veitch diagram, K-map, or KV-map.

The Karnaugh map may be used to quickly eliminate redundant operations in a Boolean function. The easiest to read Karnaugh maps are those drawn for a function in the form of a complete product or "sum of products," where the latter name also implies the use of  and  for the AND and OR operators. In a typical truth table for such a function, the inputs are enumerated using 0 for false and 1 for true, and ordered as a counting sequence when read as positive binary integers. A truth table for a function of four variables is illustrated below.

0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	0
1	1	1	1	0

For those rows in the table where the function value is 1 (True), a logical expression called a minterm is shown. The minterms use the overbar notation to mean NOT. When all seven minterms are accumulated,

(1)

the function is realized. This realization is not optimal, and a Karnaugh map can be used to reduce it.

A Karnaugh map for the function is shown above. It is a two dimensional layout of the truth table. Each dimension spans an adjacent, though not necessarily so, pair of variables. Instead of a counting sequence, the variables' sequence is in Gray code, so that between each pair of adjacent cells (in rows or columns) only a single variable changes state.

On the map, neighboring cells where the function value is 1 are grouped together with loops. Each loop represents minterms which can be reduced. Those variables which change within a loop can be eliminated. The validity of this, using the uppermost expression as an example, can be shown algebraically.

			(2)
			(3)
			(4)

Loops can also be drawn wrapping around rows and/or columns, because the Karnaugh map (up to four variables) is really the surface of a torus.

Karnaugh maps such as in the above example can be similarly drawn for two (degenerate) or three variables. They can be employed for more than four variables (e.g., five variables by overlaying two four-variable maps), but visualization becomes a much greater chore than algebra.

There are other logic design and minimization methods based on the Karnaugh map, such as for using NAND operators instead of AND and OR.

---

REFERENCES

Booth, T. Digital Networks and Computer Systems. New York: Wiley, pp. 64 and 125-136, 1971.

Muroga, S. Logic Design and Switching Theory. New York: Wiley, pp. 87-90 and 281-297, 1979.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الدينية يُطلق دورة فقهية دينية لملاكات مستشفى الكفيل

شعبة فاطمة بنت أسد للدراسات القرآنية تعلن نتائج مسابقة (ميثاق الرسول)

شعبة الخطابة الحسينية النسوية تنظّم مسابقة فرقية لطالبات برنامج ثمار العطاء

قسم العلاقات ينظم ورشة عن فن الإقناع والتواصل الفعّال للطلبة المنسقين

المزيد

الآخبار الصحية

تغيير بسيط في نمط التفكير قد يحدث فرقا كبيرا لصحة الدماغ ؟

لماذا ينعشنا المشروب الساخن في الطقس الحار؟

علماء يكتشفون فئة دم فريدة من نوعها في العالم !

لماذا ينصح الأطباء بزيت الزيتون يوميا؟

المزيد

الآخبار التكنلوجية

حساس الإطارات.. ما هو وعلامات تلفه وكيفية صيانته؟

ما معنى أودي Quattro؟ سر الأداء والتميز الهندسي ؟!

فصل الشاحن أم الهاتف أولا؟.. عادات بسيطة تطيل عمر البطارية

تعود للقرن الرابع قبل الميلاد.. اكتشاف بقايا "إيمت" المصرية

المزيد

مواضيع ذات صلة

Lemma

Proof

Zeno,s Paradoxes

Unexpected Hanging Paradox

Strange Loop

Sorites Paradox

Simpson,s Paradox

Russell,s Antinomy

Paradox

Newcomb,s Paradox

Missing Dollar Paradox

Line Point Picking