New Document
Electronics
Electronics Catlog
DIC Catlog

Number System
Conversions Between Number System
Arithematic Operations
1's & 2's Complement
Gray Codes
Arithmetic Circuits
Logical Gates and Truth Table Funtions
Boolean Expressions
Boolean Algebra
Karnaugh Map
Multiplexer
DeMultiplexer
Encoder & Decoder
TTL Circuits
Multivibrators
555 Timer
Flip Flops
RS Flip - Flop
JK Flip - Flop
D Flip - Flop
Shift Register
Schmitt Trigger
Asynchronous Counters
Synchronous Counters
Digital - Analog Conversion
Data Flow
ROM
Memory Drives
Electronics Equation
Resistor Color Codes

Minimisation of Boolean Functions


What 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 Expressions


    This 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.

Algebraic Manipulation

Numerical Assignment of Karnaugh Map Cells


    Each 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.

Karnaugh Map Ex03

    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 Map


    A 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.

Karnaugh Map Ex04

    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:

Karnaugh Map Ex05

    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:

Karnaugh Map Ex01

    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.

Karnaugh Map Ex02

    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 Minimisation


    In 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 Method


Consider a function of three variables f(A, B, C):

Tabular Method Ex02

Consider the function:

Tabular Method Ex03

Listing the two minterms shows they can be combined

Tabular Method Ex04

Now consider the following:

Tabular Method Ex05

Note that these variables cannot be combined

Tabular Method Ex06

    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:

Tabular Method Ex01