Better to know some... than all
|
||||||
|
Minimisation of Boolean FunctionsWhat is minimisation?In mathematics expressions are simplified for a number of reasons, for instance simpler expression are easier to understand and easier to write down, they are also less prone to error in interpretation but, most importantly, simplified expressions are usually more efficient and effective when implemented in practice. A Boolean expression is composed of variables and terms. The simplification of Boolean expressions can lead to more effective computer programs, algorithms and circuits. Before continuing with this section, you should make sure you are familiar with the following topics: * Boolean Algebra * Basic Gates and Functions * Forms and Definitions of Boolean Expressions Minimisation can be achieved by a number of methods, four well known methods are: 1)Algebraic Manipulation of Boolean Expressions 2)Karnaugh Maps 3)Tabular Method of Minimisation 4)Tree reduction Algebraic Manipulation of Boolean ExpressionsThis is an approach where you can transform one boolean expression into an equivalent expression by applying Boolean Theorems. Minimising terms and expressions can be important because electrical circuits consist of individual components that are implemented for each term or literal for a given expression. This allows designers to make use of fewer components, thus reducing the cost of a particular system. It should be noted that there are no fixed rules that can be used to minimise a given expression. It is left to an individuals ability to apply Boolean Theorems in order to minimise a function.  Numerical Assignment of Karnaugh Map CellsEach cell of a Karnaugh map has a unqiue binary value. With reference to the Forms and Definitions of Boolean Expressions it is obvious that each value can be converted to the equivalent decimal value. This can be useful when entering functions expressed in numerical form, in the map.  So far we can see that applying Boolean algebra can be awkward in order to simplify expressions. Apart from being laborious (and requiring the remembering all the laws) the method can lead to solutions which, though they appear minimal, are not. The Karnaugh map provides a simple and straight-forward method of minimising boolean expressions. With the Karnaugh map Boolean expressions having up to four and even six variables can be simplified. Karnaugh MapA Karnaugh map provides a pictorial method of grouping together expressions with common factors and therefore eliminating unwanted variables. The Karnaugh map can also be described as a special arrangement of a truth table. The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem.  The values inside the squares are copied from the output column of the truth table, therefore there is one square in the map for every row in the truth table. Around the edge of the Karnaugh map are the values of the two input variable. A is along the top and B is down the left hand side. The diagram below explains this:  The values around the edge of the map can be thought of as coordinates. So as an example, the square on the top right hand corner of the map in the above diagram has coordinates A=1 and B=0. This square corresponds to the row in the truth table where A=1 and B=0 and F=1. Note that the value in the F column represents a particular function to which the Karnaugh map corresponds. Example:  By using the rules of simplification and ringing of adjacent cells in order to make as many variables redundant, the minimized result obtained is B.  By using the rules of simplification and ringing of adjacent cells in order to make as many variables redundant, the minimised result obtained is B + AC--- Tabular Method of MinimisationIn order to understand the tabular method of minimisation, it is best you understand the numerical assignment of Karnaugh map cells and the incompletely specified functions also known as the can't happen conditions. This is because the tabular method is based on these principles. The tabular method which is also known as the Quine-McCluskey method is particularly useful when minimising functions having a large number of variables, e.g. The six-variable functions. Computer programs have been developed employing this algorithm. The method reduces a function in standard sum of products form to a set of prime implicants from which as many variables are eliminated as possible. These prime implicants are then examined to see if some are redundant. The tabular method makes repeated use of the law A +Â = 1. Note that Binary notation is used for the function, although decimal notation is also used for the functions. As usual a variable in true form is denoted by 1, in inverted form by 0, and the abscence of a variable by a dash ( - ). Rules of Tabular MethodConsider a function of three variables f(A, B, C):  Consider the function:  Listing the two minterms shows they can be combined  Now consider the following:  Note that these variables cannot be combined  This is because the FIRST RULE of the Tabular method for two terms to combine, and thus eliminate one variable, is that they must differ in only one digit position. Bear in mind that when two terms are combined, one of the combined terms has one digit more at logic 1 than the other combined term. This indicates that the number of 1's in a term is significant and is referred to as its index. For example: f(A, B, C, D) 0000...................Index 0 0010, 1000.............Index 1 1010, 0011, 1001.......Index 2 1110, 1011.............Index 3 1111...................Index 4 The necessary condition for combining two terms is that the indices of the two terms must differ by one logic variable which must also be the same. Example:  |
|||||