Truth Table to Equations

After you have generated the truth table to describe the desired functionality of your circuit, you will need to convert this to a set of equations. One approach to reducing your equations is using Karnaugh maps, or K-maps for short. This is a graphical reduction technique that will result in the same reductions as Boolean algebra for up to 4 variables. This technique is not generally useful for more than 4 variables (although it can be done with significant effort).

Assume that we want to implement the following truth table

D C B A	Y
0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1	1 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0

We start by drawing a blank K-map.

The digits across the top represent DC and the column down the left side represent BA. We populate the K-map with the 1s from the truth table (there is an alternative method where you use the 0s instead). The first 1 that appears is when the input is 0000.

We then populate the next 1 from the truth table which corresponds to the input 0001

Repeat until the entire function has been entered into the table

Now, we need to decide on the groups. A group must contain a power of 2 1s and must be arranged in a square or rectangle (1x1, 1x2, 1x4, 2x2, etc). Circle the largest groups possible overlapping when possible to make the group larger.

Repeat until all 1s are covered by at least one group.

Next, we need to read these groups out since they represent the minimal sum-of-products. To do this, look at each group for each input variable (D, C, B, A). If the group is completely in or completely out of the region covered by the input variable, then that letter appears in the minterm or is complimented in the minterm. Looking at the largest group (2x2) we see the following

This is completely outside the D region indicating that D' is part of this term. Below we see that we cross the boundary of the C region so we do not use this variable.

This is completely outside the B region.

Again we see that we cross the boundary of the A region so we do not use this variable either. The resulting minimized minterm for this group is D'B'.

Repeating the procedure for the next group we get D'CA. Therefore, the resulting equation is Y = D'B' + D'CA.

If you would like to use these power point graphics for your reports, you may copy them here.