K-Map

         Alright ladies and gents, today we’ll be learning about the Karnaugh Map otherwise known as the K-Map. The K-Map is an alternative method for simplifying a Boolean expression. It is suitable for inputs of 2 to 4 variables. This method is much simpler compared to using the Boolean algebra. There are 4 steps involved when making a karnaugh map which are:

1. By referring to the truth table, fill in all of the 1’s from the minterms in the truth table.

2. Group the 1’s following a simple set of rules. (We’ll get more in depth about those rules later).

3. List the groups, analyze it and simptuylify.

4. The simplified expressions are add together (*ORed).                  * Read as OR in past-tense form.

Let’s do some examples to help you get a clearer picture on what I’m rambling on about.

Example 1:  

Let’s say we are given 2 variables. Find the simplified Boolean expression.

Step 1: Make a truth table and a K-Map.

A	B	F	Minterms
0	0	0	A’B’
0	1	1	A’B
1	0	1	AB’
1	1	1	AB

B A	B’ (0)	B (1)
A’ (0)	O	1
A (1)	1	1

                                                                                               

* In the Karnaugh Map, each cells is filled with values that corresponds with the “F” column.

Step 2: Group the 1’s in the K-Map using a set of rules stated below.

• Each groups can consists of only 1’s.
• Only adjacent cells are allowed to be grouped.
• The group must be as large as possible meaning that it can have 2, 4, 8 or 16 of 1’s in it.
• The least number of grouhgvps formed the better.
• All 1’s must belong to a group even if it’s a group of one.
• Wrap around is allowed.
• Overlapping groups are allowed.

B     A	B’	B
A’	o	1
A	1	1

- The first group is B as variable B is the only

   variable that remains constant

B     A	B’	B
A’	o	1
A	1	1

    - The second group is A since A is the only variable that 

       remains constant.

Step 3: Skipping this step as we havjnkle already found the simplest Boolean expression.

Step 4:  Add together the groups.

                Answer = B + A or A + B

Example 2: Given 3 variables. Find the simplified Boolean expression.

Step 1:  Build a truth table and a K-Map.

A	B	C	F	Minterms
0	0	0	1	A’B’C’
0	0	1	1	A’B’C
0	1	0	1	A’BC’
0	1	1	1	A’BC
1	0	0	0	AB’C’
1	0	1	0	AB’C
1	1	0	1	ABC’
1	1	1	1	ABC

                             

BC A	B’C’	B’C	BC	BC’
A’	1	1	1	1
A	0	0	1	1

Step 2: Group the 1’s.

BC A	B’C’	B’C	BC	BC’
A’	1	1	1	1
A	0	0	1	1

                  - A’B’C’         - A’B’C

                 - A’BC            -A’BC’

BC A	B’C’	B’C	BC	BC’
A’	1	1	1	1
A	0	0	1	1

                 - A’BC            - A’BC’

                 - ABC             - ABC’

Step 3: Analyze.

For same letters in a column they will be brought down. For different letters in a column they will cancel each other out.

   Group 1:                                                                           Group 2:

   A’ B’ C’                                                                               - A’   B   C                                                                            

   A’ B’ C                                                                                - A    B    C           

   A’ B  C                                                                                 - A     B    C’                         

   A’ B  C’                                                                                - A’   B     C’   

   A’                                                                                                   B

                                                                                                               

Step 4: Add the groups together.

            

           Answer = A’ + B or B + A’

Below are some links that i found to be very helpful when learning about K-Maps:

http://www.wisc-online.com/Objects/ViewObject.aspx?ID=DIG5103

http://www.youtube.com/watch?v=-iF112AJGfc

http://www.laynetworks.com/Karnaugh%20Maps.htm

---

Thanks for reading, please leave your comment here.

---