Karnaugh map (k map)

K-map and its types. Rules for simplifying K-map

1. Karnaugh map (k-map) Name : Adeen Ali Bsit 3 rd semester

2. K-map inventor: Maurice Karnaugh ( October 4, 1924 (age 96 years) )   introduced Karnaugh map in 1953. The  Karnaugh map  ( KM  or  K-map ) is a method of simplifying  Boolean algebra  expressions . A Karnaugh map (K-map) is a pictorial method used to minimize  Boolean  expressions without having to use Boolean algebra theorems and equation manipulations. A K-map can be thought of as a special version of a  truth table  .

3. Karnaugh map: Karnaugh map is an array of cells in which each cell represents a binary value of input variables . The cells are managed in a way so that simplification of a given expression is simply a matter of properly grouping the cells . Karnaugh maps can be used for expression with two, three, four and five variables.

4. Steps to solve expression using K-map: Select K-map according to the number of variables. Identify minters or midterms as given in problem. For SOP put 1’s in blocks of K-map respective to the minters (0’s elsewhere). For POS put 0’s in blocks of K-map respective to the midterms(1’s elsewhere). Make rectangular groups containing total terms in power of two like 2,4,8 ..(except 1 ) and try to cover as many elements as you can in one group. From the groups made in step 5 find the product terms and sum them up for SOP form .

5. No. cell in k-map: The number of cells in K-MAP is equal to the total number of possible input variable combinations as is the number of row in a truth table. For two variable, the number of cell are 2 2 =4. For three variable, the number of cell are 2 3 =8. For four variables, the number of cell are 2 4 = 16. For five variables, the number of cells are 2 5 =32.

6. 2 variable Karnaugh map: A two variable has four minters, hence it has 4 squares one for each term, as shown below,

7. 3 variable karnaugh map: The 3-variable karnaugh map is an array of eight cells. In this case A, B and C are used for the variables although other letters could be used . Binary values of A is along the left side and the value of B and C is across the top . The value of a given cell is the binary values of A at the left in the same row combined with the value of B and C at the top in the same column.

8. 3 variable K-map For example: the cell in the upper left corner has a binary value of 000 and the cell in the lower right corner has a binary value of 110.

9. 4 variable Karnaugh map: The 4-variable karnaugh map is an array of sixteen cells. Binary values of A and B are along the left side and the values of C and D are across the top . The value of a given cell is the binary value of A and B at the left in the same row combined with the binary values of C and D at the top of the same column.

10. 4 variable karnaugh map:

11. 5 variable karnaugh map: A 5 variable K-Map is having 2 5 cells = 32 cells arranged in 4 rows and 8 columns or 8 rows and 4 columns .

12. 5 variable karnaugh map: There are 32 minters (squares) for a Boolean function with 5 variable. It consist of 2- four variables. Variable distinguishes between the two map, the left hand four variable map represent 16 square where, A=0. And the other four represent the square A=1.

13. Grouping of cells for simplification: Adjacent cells which have 1’s or 0’s can be grouped together in 2’s power. e.g.; 2 1 =2 adjacent cell can be grouped (pair). 2 2 =4 adjacent cell can be grouped (quad). 2 3 =8 adjacent cell can be grouped (octal). 2 4 =16 adjacent cell can be grouped (hex).

14. Rules for grouping in k-map: T h e karnaugh map uses the following rules for the simplification of expressions by grouping together adjacent cells containing  ones : Groups may not include any cell containing a zero. Groups may be horizontal or vertical, but not diagonal .

15. Groups must contain 1, 2, 4, 8, or in general 2 n  cells. That is if n = 1, a group will contain two 1's since 2 1  = 2. If n = 2, a group will contain four 1's since 2 2  = 4 . Each group should be as large as possible.

16. Groups may overlap. Groups may wrap around the table. The leftmost cell in a row may be grouped with the rightmost cell and the top cell in a column may be grouped with the bottom cell.

17. There should be as few groups as possible, as long as this does not contradict any of the previous rules. THE END