Simplification of Boolean Algebra (If Only...)
Some of these algebraic expressions are starting to get quite complicated, but fear not there are tools we can use to simplify them by the boolean equivalent of factorisation.
The aim of simplification is to cut the number of physical logic gates needed to construct a circuit, and in turn reduce the cost of manufacturing the circuit. To simplify an equation, first all the terms are expanded - and then reduced in the most economical way possible.
An equation is said to be n-variable when its truth table contains n variables, a term which contains all n terms is said to be a monovalent term, whereas a term with less than n terms is said to be polyvalent.
Polyvalent minterms can be expanded by multiplying each term by the missing variable(s) and their compliment(s). Duplicate terms can then be removed. A full example can be viewed here.
The next step of simplification is to combine similar terms, this can only be done where the terms have exactly the same variables, and a maximum of one difference in compliments. Similar terms are then combined, which means the term with a difference is dropped. This is shown in an example here.
Karnaugh Maps
A slightly different method of simplification is to use a Karnaugh Map. This is a method of mapping the output of a function onto a truth table, and then onto a Karnaugh map in order to find the best way of simplifying the function.
This is achieved by first calculating a truth table for the expression, then all the true results are plotted onto the Karnaugh Map. Once this has been done, adjacent "1"'s on in the map can be grouped in factors of 2. In each group only the terms which are common to all the tiles in the group are part of the final expression, expressed as minterms. A worked example is available here.
Where the result in the truth table is irrelevant to the problem in hand (for example, if only 6 different results are valid but since three variables are being used 8 are possible) the two irrelevant results are marked as "Don't Care" values (Φ), since it is not important what the output of our circuit is when these inputs occur. Don't Care figures are also shown on the Karnaugh map as we can choose to include them in our groupings or not - it is only prudent to include them if it helps simplify the final expression more.
References:
- Janet Lavery - Durham University Computer Systems, Machine Architecture Lecture 3, 2007
- Janet Lavery - Durham University Computer Systems, Machine Architecture Lecture 4, 2007
- http://www.generalnumbers.com/karnaugh_application1.html Karnaugh Map Worked Example