Karnaugh Map

29 April 2020 Off By Sdbamie

5) Karnaugh map

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

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

Usage in boolean logic

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

properties

A mapping of minterms on a Karnaugh map. The arrows indicate which squares can be thought of as “switched” (rather than being in a normal sequential order).  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). Once a person has covered the ones, that person can produce a term of a sum of products 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 compliment of the variable, while 0 means the variable non-complimented.
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.

Example

Consider the following function:
f(A,B,C,D) = E(4,8,9,10,11,12,14,15)
The values inside E tell us which rows have output 1.
This function has this truth table:
# A B C D f(A,B,C,D)
0 0 0 0 0 0
1 0 0 0 1 0
2 0 0 1 0 0
3 0 0 1 1 0
4 0 1 0 0 1
5 0 1 0 1 0
6 0 1 1 0 0
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 1
13 1 1 0 1 0
14 1 1 1 0 1
15 1 1 1 1 1
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 4×4 grid.

kmap
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 f = 0 when A = 0, B = 0, C = 1, D = 0. 

Similarly we mark the bottom right corner as 1 because A = 1, B = 0, C = 0, D = 0 gives f = 1. 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 positive power of two (i.e. 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 A maintains the same state (1) in the whole encircling, therefore it should be included in the term for the red encircling.
  • Variable B does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
  • C does not change: it is always 1.
  • D changes.

Thus the first term in the Boolean expression is AC.
For the green encircling we see that A and B maintain the same state, but C and D change.
B is 0 and has to be negated before it can be included. Thus the second term is AB’.
In the same way, the blue rectangle gives the term BC’D’ and so the whole expression is: AC + AB′+ BC′D′.
The grid is toroidally connected, which means that the rectangles can wrap around edges, so ABD′ is a valid term, although not part of the minimal set.
The inverse of a function is solved in the same way by encircling the 0’s instead.
In a Karnaugh map with n variables, a Boolean term mentioning k of them will have a corresponding rectangle of area 2n-k.
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 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.

Race hazards

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 and D are both 0, A is a 1, and B changes from a 0 to a 1 (moving from the green state to the blue 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 if D was 0 and A and B were both 1, with C changing from 0 to 1. In this case the glitch wraps around from the bottom of the map to the top of the map.

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 +AD’ would eliminate the potential race hazard, bridging between the green and blue output states or blue and red output states.
The term is redundant in terms of the static logic of the system, but such redundant terms are often needed to assure race-free dynamic performance.

When not to use K-maps

The diagram becomes cluttered and hard to interpret if there are more than four variables on an axis. This argues against the use of Karnaugh maps for expressions with more than six variables. For such expressions, the Quine-McCluskey algorithm, also called the method of prime implicants, should be used.
This algorithm generally finds most of the optimal solutions quickly and easily, but selecting the final prime implicants (after the essential ones are chosen) may still require a brute force approach to get the optimal combination (though this is generally far simpler than trying to brute force the entire problem).

कर्णघ मानचित्र, जिसे विच आरेख (लघु के लिए के-मानचित्र या केवी-मानचित्र) के रूप में भी जाना जाता है, बूलियन बीजीय अभिव्यक्तियों के प्रबंधन की सुविधा के लिए एक उपकरण है। एक करनौघ मानचित्र अद्वितीय है कि वर्गों के बीच केवल एक परिवर्तनशील मूल्य है, दूसरे शब्दों में, ग्रे कोड के सिद्धांतों के अनुसार पंक्तियों और स्तंभों का आदेश दिया गया है।

इतिहास और नामकरण

बेल लैब्स के दूरसंचार इंजीनियर मौरिस कर्णघ द्वारा 1953 में कर्णघट मानचित्र का आविष्कार किया गया था।

बूलियन लॉजिक में उपयोग

आमतौर पर, बूलियन फ़ंक्शन की न्यूनतम अभिव्यक्ति प्राप्त करने के लिए व्यापक गणनाओं की आवश्यकता होती है, लेकिन कोई इसके बजाय एक करनौघ मानचित्र का उपयोग कर सकता है।

समस्या समाधान का उपयोग करता है

  • कर्णघू मानचित्र मानव मस्तिष्क की उत्कृष्ट पैटर्न-मिलान क्षमता का उपयोग यह तय करने के लिए करते हैं कि सबसे सरल अभिव्यक्ति प्राप्त करने के लिए किन शर्तों को जोड़ा जाना चाहिए।
  • के-मैप्स तेजी से पहचान और संभावित दौड़ खतरों को खत्म करने की अनुमति देते हैं, कुछ ऐसा जो बूलियन समीकरण अकेले नहीं कर सकता है।
  • एक करनौघ मानचित्र छह चर तक सरलीकरण के लिए एक उत्कृष्ट सहायता है, लेकिन अधिक चर के साथ यह हमारे मस्तिष्क के लिए भी इष्टतम पैटर्न को समझना कठिन हो जाता है।
  • छह से अधिक चरों को शामिल करने वाली समस्याओं के लिए, बूलियन अभिव्यक्तियों को हल करना कर्णघट मानचित्र की तुलना में अधिक पसंदीदा है।

कर्णघ मानचित्र बुलियन कार्यों और न्यूनीकरण के बारे में सिखाने में भी मदद करता है।

गुण

गुण

कर्णघट मानचित्र पर लघुशंकाओं का मानचित्रण। तीर इंगित करते हैं कि किन वर्गों को “स्विच किया गया” (सामान्य अनुक्रमिक क्रम में होने के बजाय) माना जा सकता है। एक करनौघ मानचित्र में किसी भी प्रकार के चर हो सकते हैं, लेकिन आमतौर पर सबसे अच्छा काम करता है जब उदाहरण के लिए केवल 2 और 6 के बीच कुछ ही होते हैं। प्रत्येक चर प्रणाली में हर दूसरे चर की प्रत्येक संभावना के लिए दो संभावनाओं का योगदान देता है। कर्णघट मानचित्रों को व्यवस्थित किया जाता है ताकि सिस्टम की सभी संभावनाओं को एक ग्रिड रूप में व्यवस्थित किया जा सके, और दो आसन्न बक्से के बीच, केवल एक चर मान बदल सकता है। यही वह है जो इसे खतरों को कम करने की अनुमति देता है।
कम से कम फ़ंक्शन प्राप्त करने के लिए एक करनौघ मानचित्र का उपयोग करते समय, एक “कवर” जो कि आयताकार “कवरिंग” द्वारा मानचित्र पर होता है, जिसमें 2 की शक्ति के बराबर कई बॉक्स होते हैं (उदाहरण के लिए, एक पंक्ति में 4 बॉक्स, 4 बक्से एक वर्ग, एक आयत में 8 बक्से, आदि)। एक बार एक व्यक्ति को कवर करने के बाद, वह व्यक्ति उन उत्पादों की एक राशि का उत्पादन कर सकता है, जो उन चर को खोजते हैं जो पूरे कवरिंग में नहीं बदलते हैं, और उस चर का 1 मतलब निकालने के लिए और उस चर के पूरक के रूप में एक 0। । हर कवर के लिए ऐसा करने से आपको मैचिंग फंक्शन मिलता है।
एक भी शून्य का उपयोग एक कम से कम समारोह प्राप्त कर सकते हैं। प्रक्रिया लोगों के लिए प्रक्रिया के समान है, सिवाय इसके कि प्रत्येक पद रकम के उत्पाद में एक शब्द है – और 1 का मतलब चर की प्रशंसा है, जबकि 0 का मतलब चर की सराहना नहीं है।
कर्णघू मानचित्र में प्रत्येक वर्ग एक छोटा (और अधिकतम) से मेल खाता है। दाईं ओर की तस्वीर नक्शे पर प्रत्येक माइनर का स्थान दिखाती है।

उदाहरण

निम्नलिखित फ़ंक्शन पर विचार करें:
f (A, B, C, D) = E (4,8,9,10,11,12,14,15)
E के अंदर के मान हमें बताते हैं कि किन पंक्तियों का आउटपुट 1 है।
इस फ़ंक्शन में यह है सत्य सारणी:
# ABCD f (A, B, C, D)
0 0 0 0 0 0
1 1 0 0 0 1
2 0 0 1 0 0 0
3 3 0 0 1 1 0
4 1 1 0 0 1
5 5 1 1 0 1 1 0
6 0 1 1 0 0
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 1
13 1 1 0 1 0
14 1 1 1 0 1
15 1 1 1 1 1
इनपुट चर को 16 अलग-अलग तरीकों से जोड़ा जा सकता है, इसलिए हमारे कर्णघू मानचित्र में 16 स्थान हैं। इसे व्यवस्थित करने का सबसे सुविधाजनक तरीका 4 × 4 ग्रिड है।

kmap
मानचित्र में बाइनरी अंक इनपुट के किसी भी संयोजन के लिए फ़ंक्शन के आउटपुट का प्रतिनिधित्व करते हैं। हम मानचित्र के ऊपरी बाएँ कोने में 0 लिखते हैं क्योंकि f = 0 जब A = 0, B = 0, C = 1, D = 0 होता है। 

इसी तरह हम नीचे दाएं कोने को 1 के रूप में चिह्नित करते हैं क्योंकि A = 1, B = 0, C = 0, D = 0 देता है f = 1. ध्यान दें कि मान एक ग्रे कोड में दिए गए हैं, ताकि किसी भी जोड़ी के बीच ठीक एक चर निकल जाए आसन्न कोशिकाओं के।
कर्णघट मानचित्र के निर्माण के बाद हमारा अगला कार्य अंतिम अभिव्यक्ति में उपयोग करने के लिए न्यूनतम शर्तों को खोजना है। ये शब्द मानचित्र में 1 के समूहों को घेरते हुए पाए जाते हैं। घेरा आयताकार होना चाहिए और एक ऐसा क्षेत्र होना चाहिए जो दो की एक सकारात्मक शक्ति हो (यानी 2, 4, 8,…)। आयतों को किसी भी 0 के बिना जितना संभव हो उतना बड़ा होना चाहिए। इस नक्शे में इष्टतम घेर हरे, लाल और नीले रंग की रेखाओं द्वारा चिह्नित हैं।

इन परिवृत्तियों में से प्रत्येक के लिए हम उन चरों को खोजते हैं जो घेरे में प्रत्येक क्षेत्र में एक ही अवस्था रखते हैं। पहले घेरने के लिए (लाल वाला) हम पाते हैं कि:

  • चर A पूरी स्थिति में एक ही स्थिति (1) को बनाए रखता है, इसलिए इसे लाल घेरने के लिए शब्द में शामिल किया जाना चाहिए।
  • परिवर्तनीय बी एक ही स्थिति को बनाए नहीं रखता है (यह 1 से 0 तक बदलता है), और इसलिए इसे बाहर रखा जाना चाहिए।
  • C नहीं बदलता है: यह हमेशा 1 होता है।
  • D बदलता है।

इस प्रकार बूलियन अभिव्यक्ति में पहला शब्द एसी है।
हरे घेरे के लिए हम देखते हैं कि A और B एक ही अवस्था बनाए रखते हैं, लेकिन C और D बदल जाते हैं।
बी 0 है और इसे शामिल किए जाने से पहले इसे नकार दिया जाना चाहिए। इस प्रकार दूसरा शब्द है एबी ‘।
उसी तरह, नीला आयत शब्द BC’D ‘देता है और इसलिए पूरी अभिव्यक्ति है: AC + AB the + BC′D the।
ग्रिड toroidally कनेक्टेड है, जिसका अर्थ है कि आयताकार किनारों के चारों ओर लपेट सकते हैं, इसलिए ABD ′ एक वैध शब्द है, हालांकि न्यूनतम सेट का हिस्सा नहीं है।
किसी फ़ंक्शन का उलटा उसी तरीके से हल किया जाता है जो 0 के बजाय घेरता है।
N चरों के साथ एक करनौघ मानचित्र में, उनमें से कश्मीर का उल्लेख करने वाले बूलियन शब्द का क्षेत्रफल 2n-k होगा।
कर्णघू मानचित्र ऐसे कार्यों की आसान न्यूनतम अनुमति भी देता है जिनकी सत्य सारणी में “परवाह न करें” स्थितियां शामिल हैं (यह उन इनपुटों का सेट है जिनके लिए डिजाइनर को ध्यान नहीं है कि आउटपुट क्या है) क्योंकि “परवाह न करें” शर्तों को शामिल किया जा सकता है। एक अंगूठी इसे बड़ा बनाने के लिए लेकिन इसे रिंग करने की आवश्यकता नहीं है। उन्हें आमतौर पर संख्या के स्थान पर एक हाइफ़न / डैश के साथ मानचित्र पर दर्शाया जाता है। मान एक “0,” “1” या हाइफ़न / डैश / X हो सकता है, जो इस आधार पर होता है कि कोई KM को सरल बनाने के लिए “0” या “1” का उपयोग कर सकता है। यदि “परवाह नहीं” आप KM को सरल बनाने में मदद नहीं करते हैं, तो हाइफ़न / डैश / X का उपयोग करें।

दौड़ खतरों

करनूघ मानचित्र दौड़ के खतरों का पता लगाने और उन्हें समाप्त करने के लिए उपयोगी हैं। वे एक करनौघ मानचित्र का उपयोग करना बहुत आसान हैं, क्योंकि आस-पास के किसी भी जोड़े के बीच चलते समय एक दौड़ की स्थिति मौजूद हो सकती है, लेकिन असंतुष्ट, क्षेत्रों को नक्शे पर चक्कर लगाया जाता है।

  • उपरोक्त उदाहरण में, एक संभावित दौड़ की स्थिति तब मौजूद होती है जब C और D दोनों 0, A 1 होते हैं, और B 0 से 1 में बदल जाते हैं (हरे रंग की अवस्था से नीले रंग की अवस्था में चले जाते हैं)। इस मामले के लिए, आउटपुट को 1 पर अपरिवर्तित रहने के लिए परिभाषित किया गया है, लेकिन क्योंकि यह संक्रमण समीकरण में किसी विशिष्ट शब्द से ढंका नहीं है, एक गड़बड़ के लिए एक संभावित (आउटपुट का क्षणिक संक्रमण 0) मौजूद है।
  • स्पॉट करने के लिए एक कठिन संभव गड़बड़ यह है कि यदि डी 0 और ए और बी दोनों 1 थे, सी 0 से 1 तक बदल रहा है। इस मामले में यह गड़बड़ मानचित्र के नीचे से नक्शे के शीर्ष तक चारों ओर घूमती है।

चाहे ये ग्लिच होते हैं, कार्यान्वयन की भौतिक प्रकृति पर निर्भर करता है, और क्या हमें इसके बारे में चिंता करने की आवश्यकता है यह आवेदन पर निर्भर करता है।
इस मामले में, + AD ‘का एक अतिरिक्त शब्द हरे और नीले आउटपुट राज्यों या नीले और लाल आउटपुट राज्यों के बीच ब्रिजिंग संभावित संभावित खतरे को समाप्त करेगा।
यह शब्द प्रणाली के स्थिर तर्क के संदर्भ में निरर्थक है, लेकिन इस तरह के अनावश्यक शब्दों को अक्सर दौड़-मुक्त गतिशील प्रदर्शन को आश्वस्त करने की आवश्यकता होती है।

जब K- नक्शे का उपयोग नहीं करना है

आरेख पर चार से अधिक चर होने पर आरेख अव्यवस्थित और कठिन हो जाता है। यह छह से अधिक चरों के साथ अभिव्यक्तियों के लिए कर्णघ मानचित्र के उपयोग के खिलाफ तर्क देता है। ऐसे भावों के लिए, Quine-McCluskey एल्गोरिथम, जिसे प्राइम इम्प्लिकेंट्स की विधि भी कहा जाता है, का उपयोग किया जाना चाहिए।
यह एल्गोरिथ्म आमतौर पर अधिकांश इष्टतम समाधानों को जल्दी और आसानी से ढूंढता है, लेकिन अंतिम प्राइम इम्प्लिकेंट्स (आवश्यक लोगों को चुने जाने के बाद) का चयन करने के लिए अभी भी इष्टतम संयोजन प्राप्त करने के लिए एक ब्रूट फोर्स दृष्टिकोण की आवश्यकता हो सकती है (हालांकि यह आमतौर पर ब्रूट की कोशिश करने की तुलना में बहुत सरल है। पूरी समस्या को बल दे)।

Ones’ complement
Computing and Informatics

Ones’ complement

8) Ones' complement Alternatively, a system known as ones' complement can be used to represent negative numbers. The ones' complement...
Read More
Adders (electronics)
Computing and Informatics

Adders (electronics)

7) Adders (electronics) In electronics, an adder is a device which will perform the addition, S, of two numbers. In...
Read More
Computing and Informatics

Logic Gate

6) Logic Gate A logic gate performs a logical operation on one or more logic inputs and produces a single...
Read More
Computing and Informatics

Karnaugh Map

5) Karnaugh map The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool...
Read More
Computing and Informatics

Internet protocol suite

4) Internet protocol suite The Internet protocol suite is the set of communications protocols that implement the protocol stack on...
Read More
Computing and Informatics

Network Topology

3) Network Topology In networking, the term "topology" refers to the layout of connected devices on a network. This article...
Read More
Computing and Informatics

What About MAN, SAN, PAN, DAN, and CAN?

2) What About MAN, SAN, PAN, DAN, and CAN? Future articles will describe the many other types of area networks...
Read More
Computing and Informatics

Local Area Networks

1) Local Area Networks  Local Area NetworksFor historical reasons, the industry refers to nearly every type of network as an...
Read More