Problem

To investigate the use of Karnaugh maps as a way to simplify complex digital circuits.

Prelab

Logic circuitry is needed to perform the following function: F(ABCD) = Σ(0,4,5,6,7,11,12,13,14,15) + Σd(2,3)

1. Write out the function as a SOP (sum-of -products) expression (do not simplify).

2. Make a table of all possible input combinations 0 - 15.

3. Record the expected output. Provide a blank column for the simulated result, and another for the simplified simulated result.

4. In logisim draw the schematic that represents the above non-simplified SOP function.

5. Simplify the minterm expression using a Karnaugh Map and taking advantage of the don’t-care conditions.

6. Draw the schematic that represents the simplified SOP obtained above.

7. Simulate both the given and simplified functions filling in the appropriate column in the table (Given, Simulated, Simplified)

Theory

Karnaugh maps or K-maps are a means of reducing the complexity of digital circuits, or logical expressions without losing functionality or otherwise altering the behavior or truthtable in question. Circuit designs often include some unintentional redundancy and K-maps can help us eliminate such instances when simplicity is the only design constraint. While redundancy may offer some error correction, or help prevent glitches and malfunctions from altering circuit behavior, the ICs used to design digital logic are expensive, and simpler designs will often take up less room in a device, use less power while running, and will run more quickly.

K-maps are easy and intuitive to use once you become familiar with the basic rules. The graphical nature of them allows you to see necessary vs redundant behavior by inspection. The example below shows the inputs on the axes (ABCD in this case), and the desired minterms  and don't-cares are drawn in the grid where appropriate as indicated by the grid. They are then highlighted in various colors. The patterns that we are looking for are groupings of 1, 2, or 4 minterms in line, or a box of 4 or 8 minterms. The minterms can wrap around edges, overlap other groupings, or be split across the sides the chart so long as they are "continuous". The only tricky part of the setup is the numbering of the rows and columns, where expressions are slightly out of the expected order: 00, 01, 11, 10. The reason for this ordering is related to "Gray Code" if you are curious to investigate further on your own.

To translate from the graphical depiction to the sum of products (or product of sums) expression you must find which of the inputs remain consistent in the grouping under investigation. The purple line of 4 minterms below, for example, is consistent in A, A=0 through the entire group. It is also consistent in B, B=0 through the entire group. It changes in C & D so these are not included in the expression. Since A=0 and B=0, the expression depicted by the purple group is A'B' where the apostrophes indicate "not".  Repeat this process for all of the shapes found. 

To ensure that you have found the simplest expression, follow these guidelines:

• Circle the largest possible groupings first, be sure to check for groups that wrap around edges.

• Include don't care terms when convenient.

• Overlapping groups are preferable when it would allow a larger group to be circled (see red/purple case below).

Procedure

1. Draw the schematic from Section 2 of the Prelab in Logisim for simulation.

2. Simulate all input combinations and make note of the output in the table of Section 4 of the Prelab.

3. Draw the schematic from Section 6 of the Prelab in Logisim for simulation. 

4. Simulate all input combinations and make note of the output in the table of Section 7 of the Prelab. 

5. Make sure you also test the don’t care input combinations. 

Conclusions

1. Compare the simulated results with the desired results for the two circuits, Did the circuit perform as designed?

2. Was the complexity of the circuits the same? What advantages would the simplified circuit provide in the real world?