Karnaugh - map or K-map
The Karnaugh map, also known as the K-map, is a method to simplify boolean algebra expressions.
It is a tabular representation of logic expression.
It reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability.
Karnaugh maps are used to simplify real-world logic requirements so that they can be implemented using a minimum number of physical logic gates.
K-map can be done in two different ways which is discussed below
It is a tabular representation of logic expression.
It reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability.
Karnaugh maps are used to simplify real-world logic requirements so that they can be implemented using a minimum number of physical logic gates.
K-map can be done in two different ways which is discussed below
Sum of Products (SOP) Form
It is in the form of sum of three terms AB, AC, BC with each individual term is a product of two variables. Say A.B or A.C etc. Therefore such expressions are known as expression in SOP form. The sum and products in SOP form are not the actual additions or multiplications. In fact they are the OR and AND functions. In SOP form, 0 represents a bar and 1 represents an unbar.
Given below is an example of SOP.
Given below is an example of SOP.
Product of Sums (POS) Form
It is in the form of product of three terms (A+B), (B+C), or (A+C) with each term is in the form of a sum of two variables. Such expressions are said to be in the product of sums (POS) form. In POS form, 0 represents an unbar and 1 represents a bar.
Given below is an example of POS.
Given below is an example of POS.
Min term expression
A minterm is a product of all variables taken either in their direct or complemented form. Any Boolean function can be expressed as a sum of its 1-minterms and the inverse of the function can be expressed as a sum of its 0-minterms. Hence,
F (list of variables) = ∑ (list of 1-minterm indices)
and
F’ (list of variables) = ∑ (list of 0-minterm indices)
F (list of variables) = ∑ (list of 1-minterm indices)
and
F’ (list of variables) = ∑ (list of 0-minterm indices)
ExampleLet, F(x, y, z) = x’ y’ z’ + x y’ z + x y z’ + x y z
Or, F(x, y, z) = m0 + m5 + m6 + m7
Hence,
F(x, y, z) = ∑ (0, 5, 6, 7)
Now we will find the complement of F(x, y, z)
F’ (x, y, z) = x’ y z + x’ y’ z + x’ y z’ + x y’ z’
Or, F’(x, y, z) = m3 + m1 + m2 + m4
Hence,
F’(x, y, z) = ∑ (3, 1, 2, 4) = ∑ (1, 2, 3, 4)
Or, F(x, y, z) = m0 + m5 + m6 + m7
Hence,
F(x, y, z) = ∑ (0, 5, 6, 7)
Now we will find the complement of F(x, y, z)
F’ (x, y, z) = x’ y z + x’ y’ z + x’ y z’ + x y’ z’
Or, F’(x, y, z) = m3 + m1 + m2 + m4
Hence,
F’(x, y, z) = ∑ (3, 1, 2, 4) = ∑ (1, 2, 3, 4)
Max term expression
A maxterm is addition of all variables taken either in their direct or complemented form. Any Boolean function can be expressed as a product of its 0-maxterms and the inverse of the function can be expressed as a product of its 1-maxterms. Hence,
F (list of variables) = π (list of 0-maxterm indices)
and
F’(list of variables) = π (list of 1-maxterm indices).
F (list of variables) = π (list of 0-maxterm indices)
and
F’(list of variables) = π (list of 1-maxterm indices).
ExampleLet, F(x, y, z) = (x+y+z) • (x+y+z’) • (x+y’+z) • (x’+y+z)
Or, F(x, y, z) = M0 • M1 • M2 • M4
Hence,
F (x, y, z) = π(0, 1, 2, 4)
F’'(x, y, z) = (x+y’+z’) • (x’+y+z’) • (x’+y’+z) • (x’+y’+z’)
Or, F(x, y, z) = M3 • M5 • M6 • M7
Hence,
F ' (x, y, z) = π(3, 5, 6, 7)
Or, F(x, y, z) = M0 • M1 • M2 • M4
Hence,
F (x, y, z) = π(0, 1, 2, 4)
F’'(x, y, z) = (x+y’+z’) • (x’+y+z’) • (x’+y’+z) • (x’+y’+z’)
Or, F(x, y, z) = M3 • M5 • M6 • M7
Hence,
F ' (x, y, z) = π(3, 5, 6, 7)
Simplification Using K- map
K-map uses some rules for the simplification of Boolean expressions by combining together adjacent cells into single term. The rules are described below −
3-variable k-map using sop form
Minimize the following Boolean expression using K-map −
F (A, B, C) = A’BC + A’BC’ + AB’C’+ AB’C
Solution
Each term is put into k-map and we get the following −
F (A, B, C) = A’BC + A’BC’ + AB’C’+ AB’C
Solution
Each term is put into k-map and we get the following −
4-variable k-map using sop form
Both results above have four product terms of three Boolean variable each. Both are equally valid minimal cost solutions. The difference in the final solution is due to how the cells are grouped as shown above. A minimal cost solution is a valid logic design with the minimum number of gates with the minimum number of inputs.
3-variable k-map using pos form
The procedure for placing a max term in the K-map is:
- Identify the Sum term to be mapped.
- Write corresponding binary numeric value.
- Form the complement
- Use the complement as an address to place a 0 in the K-map
- Repeat for other max terms (Sum terms within Product-of-Sums expression).
Max term A’+B’+C’ is shown above. Numeric 000 corresponds to A’+B’+C’. The complement is 111. Place a 0 for max term (A’+B’+C’) in this cell (1,1,1) of the K-map as shown above.
A Boolean Product-Of-Sums expression or map may have multiple max terms as shown above. Max term (A+B+C) yields numeric 111 which complements to 000, placing a 0 in cell (0,0,0).Max term (A+B+C’)yields numeric 110 which complements to 001, placing a 0 in cell (0,0,1).
4-variable k-map using pos form
- Minimize the following Boolean expression using K-map –
Don’t Care Cells in the Karnaugh Map
A 3-variable truth table or Karnaugh map had 2n = 23 or 8-entries, a full table or map. It is not always necessary to fill in the complete truth table for some real-world problems. We may have a choice to not fill in the complete table.
For example, when dealing with BCD (Binary Coded Decimal) numbers encoded as four bits, we may not care about any codes above the BCD range of (0, 1, 2…9). The 4-bit binary codes for the hexadecimal numbers (Ah, Bh, Ch, Eh, Fh) are not valid BCD codes. Thus, we do not have to fill in those codes at the end of a truth table, or K-map, if we do not care to. We would not normally care to fill in those codes because those codes (1010, 1011, 1100, 1101, 1110, 1111) will never exist as long as we are dealing only with BCD encoded numbers. These six invalid codes are don’t cares as far as we are concerned. That is, we do not care what output our logic circuit produces for these don’t cares.
Don’t cares in a Karnaugh map, or truth table, may be either 1s or 0s, as long as we don’t care what the output is for an input condition we never expect to see. We plot these cells with an asterisk, *, among the normal 1s and 0s. When forming groups of cells, treat the don’t care cell as either a 1 or a 0, or ignore the don’t cares. This is helpful if it allows us to form a larger group than would otherwise be possible without the don’t cares. There is no requirement to group all or any of the don’t cares. Only use them in a group if it simplifies the logic.
For example, when dealing with BCD (Binary Coded Decimal) numbers encoded as four bits, we may not care about any codes above the BCD range of (0, 1, 2…9). The 4-bit binary codes for the hexadecimal numbers (Ah, Bh, Ch, Eh, Fh) are not valid BCD codes. Thus, we do not have to fill in those codes at the end of a truth table, or K-map, if we do not care to. We would not normally care to fill in those codes because those codes (1010, 1011, 1100, 1101, 1110, 1111) will never exist as long as we are dealing only with BCD encoded numbers. These six invalid codes are don’t cares as far as we are concerned. That is, we do not care what output our logic circuit produces for these don’t cares.
Don’t cares in a Karnaugh map, or truth table, may be either 1s or 0s, as long as we don’t care what the output is for an input condition we never expect to see. We plot these cells with an asterisk, *, among the normal 1s and 0s. When forming groups of cells, treat the don’t care cell as either a 1 or a 0, or ignore the don’t cares. This is helpful if it allows us to form a larger group than would otherwise be possible without the don’t cares. There is no requirement to group all or any of the don’t cares. Only use them in a group if it simplifies the logic.