Home Page Home Page
A Program for the Tabulation Method for Boolean Functions Simplification.

Feedback

Introduction:

There are two methods for simplification of Boolean functions:-

  1. The Map Method (Karnaugh Map).
  2. The Tabulation Method.

A screen shot of the LOGIC program :

Click to download the program


The map method is convenient as long as the number of variables does not exceed five or six, but when the number increases it becomes difficult to use this method. The tabulation method overcomes this difficulty, besides it is suitable for computer mechanisation. It was first formulated by Quine and later improved by McCluskey. It is also known as the Quine-McCluskey method.

The tabular method of simplification consits of two parts:
  1. Determination of Prime Implicants.
  2. Selection of Essential Prime Implicants.
The first part is covered in the software provided, the second part is not. Each minterm and its combined cells are included in the Minterm record, and linked lists techniques are used. Linked lists are the best way to manage unknown amount of data at run time instead of using a large array which is a waste of memory. The record used is:
Pminterm = ^Minterm;
Minterm = Record
  Number       : Word;    {This is to hold the decimal equivalent of the minterm}
  NumberOfOnes : Byte;    {This is to hold the no. of 1s in the field Number}
  Selected     : Boolean; {used as a tick when this term is selected}
  CellStr      : String;  { a string to hold all minterms that form a cell with this term }
  DashPlaceStr : String   {a string to hold the place of the dash }
  Next         : Pminterm { a pointer to the next record to form a linked list}
End;

The software procedure summarise as follows:
  1. The user enters the minterms in decimal equivalent.
  2. The program sorts minterms in the number of ones included in the binary equivalent (SortMinTerms).
  3. Any two minterms that differ from each other by only one variable are combined (done in FirstTabulation procedure), two minterms fit into this category if the number in the lower group is greater than that in the upper one, and the two numbers differ by a power of 2 e.g. ( 2d = 0010b and 10d = 1010b the difference is 8d which is a power of 2). Then the two numbers are copied to the second linked list ( First, Second, Vertex : Pminterm;). This procedure is carried for all the minterms. Matching groups are copied to second linked list while first one deleted.
  4. Then a second tabulation is carried in the SecondTabulation procedure, here each cell contained in the CellStr field of the Minterm record are compared together, a matching is found if the numbers in one cell are greater than the other one and they differs by a power of 2 e.g. (0,2 and 8,10 differs by 8 which is a power of two) . This procedure is carried for all the records in the second linked list and matching cells are copied to the first linked list, and any incomparable cells are copied to the Vertex linked list. Then the second linked list is deleted.
  5. The step 4 is repeated m - 1 time where m is the number of inputs, transferring cells between first and second linked lists.
  6. The last linked list and the vertex linked list prime implicants are printed in the ABC equivalent using the WMterm procedure.
My program architecture can be used to simplify any number of inputs, but practical limitations are in the Number field in the Minterm record which is a word i.e. 16 bits (16 inputs). Bearing in mind as well the simplified expression is contained in a string which is only 255 characters.

Some inputs and corresponding outputs to try on the program:

Boolean Expression Simplified Boolean Expression
F(A,B,C) = S(0,6,7)A'B'C' + AB
F(A,B,C) = S(0,4,6,7)B'C' + AB + AC'
F(A,B,C,D,E,F) = S(4,5,6,7,36,37,38,39)B'C'D
F(A,B,C,D,E,F,G,H) = S(16,17 up to 31,144,145 up to 159) B'C'D

The above results were checked using Electronics WorkBench Version 3.0E Logic Converter, Copyright (c) Interactive Image Technologies.

Reference :
Digital Design By M. Morris Mano
ISBN: 013212937X
Publisher: Prentice Hall
Pub. Date: January 1991
Edition: 2nd ed


The program files are:
  1. Borland Delphi 1.0
    Logic.zip that includes :
    Tabula.pas (unit)
    Tab.pas (unit)
    Logoc.pas (unit)
    Mainc.pas (unit)
    Logic.res (resource file)
    Logic.dpr (project file)
    Logoc.dfm (logo form)
    Mainc.dfm (main form)
    Logic.exe (executable program)

  2. Turbo Pascal 7.0 for DOS:
    Tab.pas (unit)
    Tabula.pas (unit)
    logic.pas (main program)