Karnaugh Map Definition PDF

IT2014 Karnaugh Map Definition What is a Karnaugh Map? A Karnaugh Map, also known as the Veitch diagram or the K-map, was first proposed by Edward Veitch and modified by Maurice Ka...

IT2014 Karnaugh Map Definition What is a Karnaugh Map? A Karnaugh Map, also known as the Veitch diagram or the K-map, was first proposed by Edward Veitch and modified by Maurice Karnaugh (a telecommunications engineer at Bell Labs) while designing digital logic-based telephone switching circuits in 1953. It is an arrangement of boxes or squares called cells, where each cell corresponds to one line of a truth table (shown below). Also, it represents a different combination of the variables (either in minterm or maxterm) of a Boolean function. Inputs Output B Inputs Output B A B F A B F 0 0 A 0 1 0 0 A 0 1 0 1 0 0 1 0 1 0 1 0 1 1 1 1 1 1 Inputs Output B Inputs Output A B F A B F B 0 0 A 0 1 0 0 A 0 1 0 1 0 0 1 1 0 1 0 0 1 1 1 1 1 1 The binary value (either in 0s or 1s) for each box is the binary value of the output terms in the corresponding table row, while the input variables are the cells’ coordinates. Below is an example of a truth table of the X-OR gate (taken from Logic Gates discussion) and its corresponding Karnaugh map. Row Number A B 𝑭𝑭 = 𝑨𝑨 ⊕ 𝑩𝑩 X - coordinate Literal 0 0 0 0 B 𝐵𝐵 B 1 0 1 1 A 0 1 Binary Values 2 1 0 1 Row # 0 Row # 1 𝐴𝐴̅ 0 3 1 1 0 0 1 Function Values Y - coordinate Row # 2 Row # 3 A 1 1 0 The values inside the squares are copied from the output column of the truth table. Therefore, there is one (1) square in the map for every row in the truth table. Around the edge of the Karnaugh map are the values of the two (2) input variables. B is along the top, and A is placed in the left side of the K-map. In contrast to a truth table, in which the input values typically follow a standard binary sequence (00, 01, 10, 11), the Karnaugh map's input values are ordered as 00, 01, 11, and 10 such that one bit changes from one cell to the next. This ordering is known as a Gray code. Note: Gray code will be discussed further on the Code Conversion topic. The two (2) adjacent cells in the map are arranged in a way that one variable changes every time it crosses the horizontal or vertical cell boundaries so that any adjacent cells that are grouped together can eliminate any terms that form the Postulate 6a, which is 𝐴𝐴 𝐴𝐴̅ = 0. 03 Handout 1 *Property of STI  [email protected] Page 1 of 7  IT2014 With regards to the grouping together of adjacent cells containing both ones (for SOP) or zeros (for POS), the Karnaugh map uses the following rules for the simplification of expressions: Groups should NOT include cells with different values, as shown below: B 𝐵𝐵 B B 𝐵𝐵 B B 𝐵𝐵 B B 𝐵𝐵 B A 0 1 A 0 1 A 0 1 A 0 1 𝐴𝐴̅ 0 0 𝐴𝐴̅ 0 𝐴𝐴̅ 0 1 𝐴𝐴̅ 0 A 1 1 A 1 0 1 A 1 1 A 1 1 1 B 𝐵𝐵 B B 𝐵𝐵 B B 𝐵𝐵 B B 𝐵𝐵 B A 0 1 A 0 1 A 0 1 A 0 1 𝐴𝐴̅ 0 1 𝐴𝐴̅ 0 1 1 𝐴𝐴̅ 0 0 𝐴𝐴̅ 0 A 1 1 A 1 A 1 0 A 1 0 0 B 𝐵𝐵 B B 𝐵𝐵 B A 0 1 A 0 1 𝐴𝐴̅ 0 0 𝐴𝐴̅ 0 0 0 A 1 0 A 1 Groups can be in horizontal or vertical directions, but NOT diagonal. B 𝐵𝐵 B B 𝐵𝐵 B B 𝐵𝐵 B B 𝐵𝐵 B A 0 1 A 0 1 A 0 1 A 0 1 𝐴𝐴̅ 0 1 ̅ 𝐴𝐴 0 1 ̅ 𝐴𝐴 0 1 𝐴𝐴̅ 0 1 1 A 1 1 A 1 1 1 A 1 1 A 1 1 Groups should contain 2𝑛𝑛 cells. This implies that if 𝑛𝑛 = 1, a group will contain two 1's since 21 = 2 (as shown below). If 𝑛𝑛 = 2, a group will contain four 1's since 22 = 4. BC 𝐵𝐵 C BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ Group of 2 Group of 3 A 0 1 A 00 01 11 10 𝐴𝐴̅ 0 1 1 𝐴𝐴̅ 0 1 1 1 A 1 A 1 BC 𝐵𝐵 C BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ Group of 4 Group of 5 A 0 1 A 00 01 11 10 𝐴𝐴̅ 0 1 1 𝐴𝐴̅ 0 1 1 1 1 A 1 1 1 A 1 1 Groups may overlap, and each group should be as large as possible. The larger the number of 1’s or 0’s grouped together, the simpler is the product term or the sum term that the group represents. BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ Groups not BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ Groups A 00 01 11 10 overlapping A 00 01 11 10 overlapping 𝐴𝐴̅ 0 1 1 1 1 𝐴𝐴̅ 0 1 1 1 1 A 1 1 1 A 1 1 1 Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell, and the topmost cell in a column may be grouped with the bottommost cell. Cells occupying the four corners of the map are also included. 03 Handout 1 *Property of STI  [email protected] Page 2 of 7  IT2014 CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ A 00 01 11 10 AB 00 01 11 10 𝐴𝐴̅ 0 1 1 𝐴𝐴̅𝐵𝐵 00 1 1 1 1 A 1 1 1 𝐴𝐴̅𝐵𝐵 01 AB 11 𝐴𝐴𝐵𝐵 10 1 1 1 1 CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 AB 00 01 11 10 𝐴𝐴̅𝐵𝐵 00 1 1 𝐴𝐴̅𝐵𝐵 01 AB 11 𝐴𝐴𝐵𝐵 10 1 1 Two and Three-Variable Maps Two-Variable Map. The number of cells in a Karnaugh map is equal to 2𝑛𝑛 , where n is the total number of possible input variable combinations. Thus, for the case of 2 variables, we form a map consisting of 22 = 4 (2-by-2 matrix), as shown below, where B is along the top, and A is down the left-hand side. For Minterm (m): For Maxterm (M): B 𝐵𝐵 B B 𝐵𝐵 B B B 𝐵𝐵 B B 𝐵𝐵 A 0 1 A 0 1 A 0 1 A 0 1 Row Row Row # 0 Row # 1 Row Row Row # 0 Row # 1 𝐴𝐴̅ 0 A 0 𝐴𝐴̅ 0 #0 #1 𝐴𝐴̅𝐵𝐵 𝐴𝐴̅𝐵𝐵 A 0 #0 #1 𝐴𝐴 + 𝐵𝐵 𝐴𝐴 + 𝐵𝐵 00 01 Row # 2 Row # 3 0+0 0+1 Row # 2 Row # 3 A 1 𝐴𝐴̅ 1 Row Row 𝐴𝐴𝐵𝐵 𝐴𝐴𝐴𝐴 Row Row 𝐴𝐴̅ + 𝐵𝐵 𝐴𝐴̅ + 𝐵𝐵 A 1 #2 #3 𝐴𝐴̅ 1 #2 #3 10 11 1+0 1+1 Simplification rules for two-variable K-map Rules Example Sample Problem 1: Identify the function which generates the K-map shown: B 𝐵𝐵 B B 𝐵𝐵 B A 0 1 One (1) square – 2 literals A 0 1 𝐴𝐴̅ 0 1 A 0 A 1 𝐴𝐴̅ 1 0 𝑭𝑭 = + 𝑩𝑩 𝑨𝑨 𝑩𝑩 𝑭𝑭 = 𝑨𝑨 Sample Problem 2: Simplify the Boolean functions 𝐹𝐹 = 𝐴𝐴𝐵𝐵 + 𝐴𝐴𝐴𝐴 and 𝐹𝐹 = (𝐴𝐴 + 𝐵𝐵)(𝐴𝐴̅ + 𝐵𝐵) Solution: + 𝑨𝑨𝑨𝑨: For 𝑭𝑭 = 𝑨𝑨𝑩𝑩 For 𝑭𝑭 = (𝑨𝑨 + 𝑩𝑩)(𝑨𝑨’ + 𝑩𝑩): Two (2) adjacent squares – 1 B 𝐵𝐵 B B B 𝐵𝐵 literal A 0 1 0 1 A 𝐴𝐴̅ 0 0 A 0 A 1 1 1 0 𝐴𝐴̅ 1 𝑭𝑭 = 𝑨𝑨 𝑭𝑭 = 𝑩𝑩 Four (4) adjacent squares – logic Sample Problem 3: Identify the function which generates the K-map 1 (SOP); logic 0 (POS) shown: 03 Handout 1 *Property of STI  [email protected] Page 3 of 7  IT2014 B 𝐵𝐵 B B B 𝐵𝐵 A 0 1 A 0 1 𝐴𝐴̅ 0 1 1 A 0 0 0 A 1 1 1 𝐴𝐴̅ 1 0 0 𝑭𝑭 = 𝟏𝟏 𝑭𝑭 = 𝟎𝟎 Three-Variable Map. In the case of 3 variables, we form a map consisting of 23 = 8 cells (2-by-4 or 4-by-2 matrix), as shown below. 2-by-4 matrix (Minterm (m)) 2-by-4 matrix (Minterm (m)) BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ A 00 01 11 10 A 00 01 11 10 Row # 0 Row # 1 Row # 3 Row # 2 Row # 0 Row # 1 Row # 3 Row # 2 𝐴𝐴̅ 0 𝐴𝐴̅ 0 000 001 011 010 𝐴𝐴̅𝐵𝐵 𝐶𝐶̅ 𝐴𝐴̅𝐵𝐵 𝐶𝐶 𝐴𝐴̅𝐵𝐵𝐵𝐵 𝐴𝐴̅𝐵𝐵 𝐶𝐶̅ Row # 4 Row # 5 Row # 7 Row # 6 Row # 4 Row # 5 Row # 7 Row # 6 A 1 A 1 100 101 111 110 𝐴𝐴𝐵𝐵 𝐶𝐶̅ 𝐴𝐴𝐵𝐵 𝐶𝐶 𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐶𝐶̅ Note: The same table is applied for maxterm (M), except that the literals are in product of sum (POS) form – all literals in “1’s” are complemented while all literals in “0’s” are not complemented. Simplification rules for three-variable K-map Rules Example Sample Problem 1: Identify the function which generates the K- map shown: BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ One (1) square – 3 literals A 00 01 11 10 𝐴𝐴̅ 0 1 A 1 𝑩𝑩𝑩𝑩 𝑭𝑭 = 𝑨𝑨 Sample Problem 2: Simplify the Boolean function 𝐹𝐹 = 𝐴𝐴𝐴𝐴’𝐶𝐶 + 𝐴𝐴𝐴𝐴𝐴𝐴 + 𝐴𝐴𝐴𝐴𝐴𝐴’ Solution: For 𝑭𝑭 = 𝑨𝑨𝑩𝑩 𝑪𝑪 + 𝑨𝑨𝑨𝑨𝑨𝑨 + 𝑨𝑨𝑨𝑨𝑪𝑪 BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ A 00 01 11 10 𝐴𝐴̅ 0 Two (2) adjacent squares – 2 literals A 1 1 1 1 𝑭𝑭 = 𝑨𝑨𝑨𝑨 + 𝑨𝑨𝑨𝑨; Note: 2 literals per array Simplifying further: Postulate 5a (Distributive): (𝐴𝐴 𝐵𝐵) + (𝐴𝐴 𝐶𝐶) = 𝐴𝐴 (𝐵𝐵 + 𝐶𝐶) = 𝑭𝑭 = 𝑨𝑨(𝑪𝑪 + 𝑩𝑩) Sample Problem 3: Simplify the Boolean function Four (4) adjacent squares – 1 literal 𝐹𝐹 = (𝐴𝐴 + 𝐵𝐵 + 𝐶𝐶̅ )(𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶)(𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶̅ ) 03 Handout 1 *Property of STI  [email protected] Page 4 of 7  IT2014 Solution: )(𝑨𝑨 For 𝑭𝑭 = (𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪 + 𝑩𝑩 + 𝑪𝑪 )(𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪’)(𝑨𝑨 + 𝑩𝑩 + 𝑪𝑪’) BC 𝐵𝐵 + 𝐶𝐶 𝐵𝐵 + 𝐶𝐶̅ 𝐵𝐵 + 𝐶𝐶̅ 𝐵𝐵 + 𝐶𝐶 A 00 01 11 10 A 0 0 0 𝐴𝐴̅ 1 0 0 𝑭𝑭 = 𝑪𝑪 Sample Problem 4: Identify the function which generates the K- map shown: BC 𝐵𝐵 𝐶𝐶̅ 𝐵𝐵 𝐶𝐶 BC 𝐵𝐵𝐶𝐶̅ Eight (8) adjacent squares – logic 1 A 00 01 11 10 (SOP); logic 0 (POS) ̅ 𝐴𝐴 0 1 1 1 1 A 1 1 1 1 1 𝑭𝑭 = 𝟏𝟏 Four-Variable Map In the case of 4 variables, we form a map consisting of 24 = 16 cells (4-by-4 matrix), as shown below. For Minterm (m): For Minterm (m): CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 AB 00 01 11 10 AB 00 01 11 10 Row # Row # Row # Row # Row # Row # Row # Row # 𝐴𝐴̅𝐵𝐵 00 0 1 3 2 𝐴𝐴̅𝐵𝐵 00 0 1 3 2 0000 0001 0011 0010 𝐴𝐴̅𝐵𝐵 𝐶𝐶̅ 𝐷𝐷 𝐴𝐴̅𝐵𝐵 𝐶𝐶̅ 𝐷𝐷 𝐴𝐴̅𝐵𝐵 𝐶𝐶𝐶𝐶 𝐴𝐴̅𝐵𝐵 𝐶𝐶𝐷𝐷 Row # Row # Row # Row # Row # Row # Row # Row # 𝐴𝐴̅𝐵𝐵 01 4 5 7 6 𝐴𝐴̅𝐵𝐵 01 4 5 7 6 0100 0101 0111 0110 𝐴𝐴𝐵𝐵 𝐶𝐶̅ 𝐷𝐷 ̅ 𝐴𝐴𝐵𝐵 𝐶𝐶̅ 𝐷𝐷 ̅ ̅ 𝐴𝐴𝐵𝐵𝐵𝐵𝐵𝐵 ̅ 𝐴𝐴𝐵𝐵𝐵𝐵𝐷𝐷 Row # Row # Row # Row # Row # Row # Row # Row # AB 11 12 13 15 14 AB 11 12 13 15 14 1100 1101 1111 1110 𝐴𝐴𝐴𝐴𝐶𝐶̅ 𝐷𝐷 𝐴𝐴𝐴𝐴𝐶𝐶̅ 𝐷𝐷 𝐴𝐴𝐴𝐴𝐴𝐴𝐴𝐴 𝐴𝐴𝐴𝐴𝐴𝐴𝐷𝐷 Row # Row # Row # Row # Row # Row # Row # Row # 𝐴𝐴𝐵𝐵 10 8 9 11 10 𝐴𝐴𝐵𝐵 10 8 9 11 10 1000 1001 1011 1010 𝐴𝐴𝐵𝐵 𝐶𝐶̅ 𝐷𝐷 𝐴𝐴𝐵𝐵 𝐶𝐶̅ 𝐷𝐷 𝐴𝐴𝐵𝐵 𝐶𝐶𝐶𝐶 𝐴𝐴𝐵𝐵 𝐶𝐶𝐷𝐷 Note: The same table is applied for maxterm (M), except that the literals are in product of sum (POS) form – all literals in “1’s” are complemented while all literals in “0’s” are not complemented. Simplification rules for four- variable K-map Rules Example Sample Problem 1: Identify the function which generates the K- map shown: CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 AB 00 01 11 10 One (1) square – 4 literals 𝐴𝐴̅𝐵𝐵 00 𝐴𝐴̅𝐵𝐵 01 1 AB 11 𝐴𝐴𝐵𝐵 10 𝑩𝑩𝑩𝑩𝑫𝑫 𝑭𝑭 = 𝑨𝑨 Two (2) adjacent squares – 3 literals Sample Problem 2: Simplify the Boolean functions 03 Handout 1 *Property of STI  [email protected] Page 5 of 7  IT2014 𝐹𝐹 = (𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶 + 𝐷𝐷)( 𝐴𝐴̅ + 𝐵𝐵 + 𝐶𝐶̅ + 𝐷𝐷) CD 𝐶𝐶 + 𝐷𝐷 𝐶𝐶 + 𝐷𝐷 𝐶𝐶̅ + 𝐷𝐷 C’+D AB 0+0 0+1 1+1 1+0 𝐴𝐴 + 𝐵𝐵 0 + 0 𝐴𝐴 + 𝐵𝐵 0 + 1 𝐴𝐴̅ + 𝐵𝐵 1 + 1 0 0 ̅ 𝐴𝐴 + 𝐵𝐵 1 + 0 𝑭𝑭 = 𝑨𝑨 + 𝑩𝑩 + 𝑫𝑫 Sample Problem 3: Identify the function which generates the K- map shown: CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 AB 00 01 11 10 Four (4) squares – 2 literals 𝐴𝐴̅𝐵𝐵 00 1 𝐴𝐴̅𝐵𝐵 01 1 AB 11 1 𝐴𝐴𝐵𝐵 10 1 𝑭𝑭 = 𝑪𝑪𝑪𝑪 Sample Problem 4: Identify the function which generates the K- map shown: CD 𝐶𝐶 + 𝐷𝐷 𝐶𝐶 + 𝐷𝐷 𝐶𝐶̅ + 𝐷𝐷 𝐶𝐶̅ + 𝐷𝐷 AB 0+0 0+1 1+1 1+0 Eight (8) squares – 1 literal 𝐴𝐴 + 𝐵𝐵 0 + 0 0 0 𝐴𝐴 + 𝐵𝐵 0 + 1 0 0 ̅ 𝐴𝐴 + 𝐵𝐵 1 + 1 0 0 𝐴𝐴̅ + 𝐵𝐵 1 + 0 0 0 𝑭𝑭 = 𝑫𝑫 Sample Problem 5: Identify the function which generates the K- map shown: CD 𝐶𝐶̅ 𝐷𝐷 𝐶𝐶̅ 𝐷𝐷 CD 𝐶𝐶𝐷𝐷 AB 00 01 11 10 Sixteen (16) squares – logic 1 (SOP); logic 0 𝐴𝐴̅𝐵𝐵 00 1 1 1 1 (POS) 𝐴𝐴̅𝐵𝐵 01 1 1 1 1 AB 11 1 1 1 1 𝐴𝐴𝐵𝐵 10 1 1 1 1 𝑭𝑭 = 𝟏𝟏 Don’t Care Conditions Sometimes, a situation arises in which some input variable combinations are not allowed. These unallowed states are treated as the “don’t care” condition. The “don’t care” condition (which is often represented with an “X” in a K-map) can either be 0 or 1. It does not affect the result of the expression, since it is assumed that the combinations of the inputs leading to this condition will never occur. With don’t care conditions, further simplification of the K-map is often guaranteed. Note: Don’t care conditions are further covered in the Code Conversion topic. 03 Handout 1 *Property of STI  [email protected] Page 6 of 7  IT2014 Solution: CD 𝐶𝐶 + 𝐷𝐷 𝐶𝐶 + 𝐷𝐷 𝐶𝐶̅ + 𝐷𝐷 𝐶𝐶̅ + 𝐷𝐷 AB 0+0 0+1 1+1 1+0 0 1 3 2 Sample Problem: Simplify the Boolean function 𝐴𝐴 + 𝐵𝐵 0+0 X X 𝐹𝐹 (𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷) = 𝛱𝛱𝑀𝑀(6,7,10,11,12,14,15) with 4 5 7 6 the don’t care conditions described by the 𝐴𝐴 + 𝐵𝐵 0+1 0 0 function: 𝑑𝑑(𝐴𝐴, 𝐵𝐵, 𝐶𝐶, 𝐷𝐷) = 𝛱𝛱𝑀𝑀 (0,3,13). 12 13 15 14 𝐴𝐴̅ + 𝐵𝐵 1+1 X 0 0 0 8 9 11 10 𝐴𝐴̅ + 𝐵𝐵 1+0 0 0 + 𝑩𝑩 𝑭𝑭 = (𝑨𝑨 )(𝑩𝑩 + 𝑪𝑪 )(𝑨𝑨 + 𝑪𝑪 ) References: Karim, M., & Chen, X. (2017). Digital design: Basic concepts and principles. Boca Raton, FL: CRC Press/Taylor & Francis. LaMeres, B. (2019). Introduction to logic circuits & logic design with VHDL (1st ed.). Springer International. Ndjountche, T. (2016). Digital electronics 2: Sequential and arithmetic logic circuits. John Wiley & Sons. 03 Handout 1 *Property of STI  [email protected] Page 7 of 7