EE 110 Lab Experiment #6 Fall 2009
NAME: ______
EXPERIMENT 6: Practice Karnaugh Maps using the Java Applet
The purpose of this laboratory is to gain experience and skill with Karnaugh map problems of up to four variables. Students will work individually as much as possible. Due to the limited number of computers in the lab, some students may need to work in pairs on the computer exercises.
Background:
The Karnaugh map is a very powerful graphical method of simplifying Boolean expressions of up to six variables. It relies on our human ability to recognize graphical patterns and so eliminates some tedium.
Some general guidelines for K-map problems:
§ Draw and label a grid appropriate for variables specified in the problem. Be sure to use the correct ordering so that the positions of any two neighboring cells differ by exactly one bit.
§ Transcribe the truth table entries into the appropriate places in the K-map grid. Watch out for the strange ordering!
§ Every cell has neighbors vertically and horizontally (but not diagonally!!), with wrap-around included.
§ Neighboring cells that have the same contents (1 for SOP, 0 for POS) might be grouped together. The larger the group, the better the reduction in the final Boolean expression.
§ Allowed groupings must be an exact power of 2 in size and an exact power of 2 in each direction. For example, allowed groupings can be 1x1, 2x4, 1x4, 2x2, etc.
§ For SOP problems, the goal is to group the ones. For POS problems, group the zeroes.
§ For minimization, the goal is to choose the smallest number of groupings that cover the ones (for SOP) or zeroes (for POS). By “cover”, we mean that every one (or zero) must be included in at least one group. No orphans are allowed.
§ For minimization, avoid choosing redundant groups. Each group should add at least one new cell to the covered set. If a group does not add any new cells, then it’s redundant.
§ Once the minimum set of covering groups is chosen, write the expression for each group (term) to build the final Boolean expression.
We have developed a Java applet that we call the K-Mapplet. Its purpose is to allow you to practice Karnaugh map problems on the computer, with the goal of building your skill quickly. To run this applet, you will need a recent version (at least version 6.0) of the Microsoft Internet Explorer browser, or FireFox (verified for version 3.0.1), or Safari (verified for version 3.2.1). The lab computers have both Internet Explorer and FireFox browsers available.
You can access the applet at the following website: : http://www.cefns.nau.edu/~pam7/Applets/College/KMapplet.html
Incidentally, you are encouraged to practice with the applet outside of class and lab. You can access it from anywhere on the internet, provided you login with your dana ID.
Note that this is beta test software. If you discover any errors or problems with the software, please report them to the TA or professor and write them in the space provided at the end of this report.
Pre-Lab:
Please do the following problems. Do not use the computer. (You can’t give the computer a specific problem anyway.) Show your work on the next page and the blank page following it. If you need to, feel free to draw a truth table. The K-Map Java Applet is described beginning on page 4.
- Draw and use a K-map to produce a minimized SOP expression for:
f(a,b,c) = Sm(0,2,5,6,7)
- Draw and use a K-map to produce a minimized POS expression for the function in part (a). Draw a fresh map – don’t draw more groups onto your part (a) diagram.
- Draw and use a K-map to produce a minimized SOP expression for:
f(w,x,y,z) = Sm(0,2,6,7,8,10,11,15)
- Draw and use a K-map to produce a minimized POS expression for the function in part (c). Draw a fresh map – don’t draw more groups onto your part (c) diagram.
Pre-Lab Work (cont.):
K-Map Java Applet:
Procedure:
1) Login to one of the lab computers. You may need to work with a partner. Please, no more than two students to a group.
2) Start the browser and go to the URL for the K-Map Applet on page 1.
3) After a short delay, you should see the applet window appear, with a “Select Level” dialog box containing a long list of options. Choose the “3 Variable” option, with “KMAP Translation” selected (as default) from the list at the right. Click the “OK” button. You should now see a truth table on the left and a K-map grid in the middle. Your task is to change the grid entries to match the function listed in the truth table. Use the left mouse button to click on cells you wish to change. When you’re satisfied that everything is correct, click “Check Work” at the bottom. If your answer is correct, go on to another problem of the same kind. If you made a mistake, try the same problem again. Ask questions if you don’t understand something.
Note: You need to start with at least one problem at the KMAP Translation level. If you start with “SOP Minimized” or “POS Minimized”, there is a bug in the applet which may prevent the applet from displaying correctly. SOP or POS Minimized will work correctly after the 1st try.
You should know that a score is awarded by the computer for each answer. Correct answers give you a boost according to the difficulty of the problem. Incorrect answers cause your score to drop. If you miss a problem, you’ll get penalized less for trying it again than for skipping to a different problem. The score does not determine your grade! It’s merely a rough indicator of how far you’ve gone.
4) After you have done at least three consecutive problems successfully, select a “4 Variable” problem from the list. Practice these until you can do at least three consecutively without mistakes. Don’t race! It’s best to take it slow and carefully at first. You’ll develop some speed as you gain more practice. When you’ve succeeded, go on to step 5.
5) Now select “3 Variable SOP Minimized” from the Select Level list. First, transcribe the truth table entries into the grid. Next, change from Translation Mode to Grouping Mode by clicking the button on the right. This now locks the contents of your map and allows you to define groups of cells.
There are two ways to group cells: control-drag or control-click. In both cases, you need to press and hold down the CONTROL (Ctrl) key until your group is fully specified. Releasing the control key tells the computer to draw a boundary around the group you’ve defined. To control-drag a group of cells, the arrangement must be rectangular without wrap-around. Hence, you can’t use control-drag to define a wrap-around group. Instead, use control-click by holding down the control key as you click individual cells with the left mouse button. Each selected cell should highlight. When your group is complete, release the control key. The computer should now draw a boundary around the group.
For this type of exercise, your goal is to define the fewest groups that completely cover the ones in your grid. When you’re done, check your work. Try the same problem again if you made a mistake. Once it’s correct, go on to another problem of the same kind. When you are able to do at least three of these problems consecutively without mistakes, go on to step 6.
6) Select “4 Variable SOP Minimized” from the Select Level list. Practice until you can correctly do at least 3 consecutively. Once again, it pays to be methodical and not rush. Develop accuracy first. You can work on speed later.
7) Now try “3 Variable POS Minimized” problems. Your goal now is to define groups that cover the zeroes. Make sure you can do at least 3 in a row correctly before moving on.
8) Now do “4 Variable POS Minimized” problems. Again, be sure you can do at least 3 in a row correctly before proceeding.
9) Now we’re going to do the same exercises again, but this time you’ll need to enter the Boolean equations. To start, choose “3 Variable SOP Minimized with Equation”. As before, transcribe into the grid and define the minimal set of groupings to cover the ones. Now you’ll need to enter your Boolean expression in the text box at the bottom of the screen. A few rules apply:
- Variable names can be upper or lower case. The computer converts for you.
- Parentheses can be used as needed. For SOP expressions, you will generally not need parentheses. For POS expressions, you’ll need to use them.
- Spaces are irrelevant since the computer removes them during expression parsing.
- To complement a variable, use the apostrophe as a leading character just before the variable name. For example, a’bc means “a AND (not b) AND c”.
- Use the plus sign for OR operations. Example: abc + ‘bd means “ (a AND b AND c) OR (not b AND d) “
- Be careful and methodical. You’ll make fewer mistakes.
Make sure you can do at least 3 correctly in a row before going on.
10) Practice “3 Variable POS Minimized with Equation” until you can do at least 3 in a row correctly. Note that you’re grouping the zeroes now. Your Boolean expression is a product-of-sums expression, so be careful.
11) If you have time, practice “4 Variable SOP Minimized with Equation” and “4 Variable POS Minimized with Equation” problems. If not, move to section 12.
12) At the bottom of the applet window, click “View Scores”. You should now see a screen that describes what you’ve practiced. Each type of problem shows the number of attempts and the score you achieved with that problem. Please use that information to complete the following table:
Type of problem / Number of Attempts / Points3 Variable
4 Variable
3 Variable SOP Minimized
3 Variable POS Minimized
4 Variable SOP Minimized
4 Variable POS Minimized
3 Variable SOP Minimized with Eq
3 Variable POS Minimized with Eq
4 Variable SOP Minimized with Eq
4 Variable POS Minimized with Eq
Total points: ______
14) Describe your results.
a. What did you find good or useful about the applet?
b. What suggestions do you have for improvements to the applet?
c. Describe any errors or bugs you encountered with the software. Draw pictures if needed.
5-1