28-05-2013, 12:51 PM
Simplification of Boolean Functions
Simplification of Boolean.docx (Size: 234.39 KB / Downloads: 15)
Introduction
You already know one method for simplifying Boolean expressions: Boolean algebra.
There are two serious limitations to using Boolean algebra though:
• There is no algorithm you can follow that is guaranteed to lead to the simplest form of the expression
• Given any intermediate result there is no way to tell if it is in fact the simplest form of the expression
In this lecture you will learn an algorithmic procedure for finding the simplest two level form of a Boolean expression.
This method doesn't give you the simplest form in any number of levels. However, the simplest two level form is usually what we want because as you add more levels the expression may get smaller but the propagational delay will also increase. Propagational delay determines the speed of the circuit.
Two Level Form of a Boolean Expression
The two level form of an expression refers to the number of subexpressions in the Boolean equation or the number of gates in the longest path through the gate implementation of the expression. Inverter gates don't count as a separate level.
K-Maps
A K-map shows the value of a function for every combination of input values just like a truth table, but a K-map spatially arranges the values so it is easy to find common terms that can be factored out. The image below shows the form of a 2,3 and 4 variable K-map.
Don't Cares
Sometimes the output of a function for a specific input value is "don't care". For example, the output of a BCD increment by one circuit given the input 1010 would be XX, or don't care because the input (1010)2 = (10)10 would never be seen. Don't cares act like joker in a deck of playing cards--we can make them whatever we want. When you are simplifying a function using a K-map these don't care values help you to form larger groups of 1's which give you smaller prime implicants.