Summary Of Karnaugh Map Methodology

The Karnaugh Map method, also called the K map, is one of two methods taught in digital computer and electronic fundamentals undergraduate courses, which are commonly used to attain “product terms with irredundant literals”. K maps typically have 16 squares used for four variables of Boolean functions, where 1 is written if the Boolean function is 1, and thus creates a diagram called the K map. However, this approach is not effective for multiple variables, since it is impractical analyzing numerous four-variable maps simultaneously in order to spawn prime implicants. Based on the findings of other authors who have previously studied this problem, such as Roy and Bhunia’s study, “Minimization Method for Multiple Input to Two Input Variables, ” and Holder’s report in “A Modified Karnaugh Map Technique, ” V. C (2005; 2014).

Prasad describes the Karnaugh map method in more generalized terms: the Boolean function is displayed as a tree of K maps that are individually generated and examined, and necessary variables are added throughout the navigation from leaf nodes to the root. For general reference, “a literal is an appearance of a Boolean variable in complemented or uncomplemented form but not both” and a minterm “is a product (AND) term in which every variable appears as a literal”. Therefore, implicants, which are “product term(s) of some or all variables of ƒ, ” are prime if there are no redundant literals, which is true if there is no change to the value of ƒ whenever a variable is omitted. Optional combinations of ƒ, referred to as don’t cares, are represented as 1 and prime implicants are eliminated if it only covers don’t cares.

To shorten the K map method, prime implicants are not selected within a minimal set. Prasad uses to the representative equation of S = {P1, P2, …. , Pp} as a set of prime implicants of ƒ (where F (x1, x2, …, xn) is the SOP of all prime implicants of S) to reiterate the above terms, and determines that in this case m is a minterm of ƒ-i, ƒi, and ƒi’, therefore it is a ‘K-don’t care’ and its value denoted as Ki. Prasad goes on to discuss limitations and falsehoods of this representation before examining how to obtain the prime implicants of ƒ by finding the prime implicants of ƒ-i, ƒi, and ƒi’. Perhaps the most important figure representative of this process, which involves the levels of the K map tree as bilinear depictions that are illustrative of computer science applications. This tree taken together with the entries of a square K map is called the generalized Karnaugh map.

Algorithm I

Generalized Karnaugh map method begins with a 6-step process to obtain all prime implicants:

• Level 0 of the tree and placement of variables,
• Determining the minterms of g,
• Evaluation of gj,
• G siblings,
• Formation of the four-variable K map of g,
• Reconfiguration of g siblings.

Prasad explains and analyzes the contents of Table 1, which is a representation of the above algorithm, in 11 parts, paying particular attention to the relationship of determining parent and child nodes of each tree level. From there, four theorems are broken down and explained in a series of steps: Theorem 2. 1 proves the conditions of “(i) if P is a prime implicant of the K map and (ii) all minterms of P do not have K-don’t care value of the same variable”. Theorem 2. 2 observes that all prime implicants of g can be attained via the algorithm if gj, gj’, and g-j are its known children. Theorem 2. 3 is simply that “the algorithm generates all prime implicants of ƒ”. And, finally, Theorem 2. 4 observes that the algorithm will only generate prime implicants of ƒ once. There are 6 important remarks about these Theorems and K map, the most important being that there is a maximum of 3n-4 K maps at the leaf nodes, but if these trees are traversed in depth from the beginning, then they do not need to be made all at the same time and can instead be managed one K map at a time. This is similar to the algorithm presented in Markovic, Nikolic, and Oklobzija’s study, “A General Method in Synthesis of Pass-Transistor Circuits” (2001).

Lemma 3. 1 is the simplified method for finding generate "some but not all prime implicants" from the generalized K map method. Lemma 3. 1 states that "Every minterm of ƒ appears as 1 in one K map only in the generalized K map method”. In this case, prime implicants with K-don’t care values can be ignored, and therefore can cover all minterms of ƒ when K map prime implants cover at least one 1, so because of Theorem 2. 1 it is not necessary to extricate between K-don't care values. A simplification process begins: Using Tables 1 and 2 as a reference, replace K-don't care values in Table 1 with K, consequently simplifying Table 2, and creates this so-called revised method in which Table 2 can be used in place of Table 1. This revised method also ensures that “A node is grown further only if it has at least one minterm value of 1” and that K map generated prime implicants covers at least one 1 and one new 1 is formed within a new group.

Example 3. 1 takes the Boolean function of Example 2. 1 and uses the revised method to prove this lemma. In conclusion, the K map method it limited by functions of multiple variables, but this limitation is lifted by using the tree of K maps, which “is a natural generational of the existing map method”.