Boolean functions' minimisation software based on the Quine-McCluskey method

Table of contents

0. Abstract
1. The Quine-McCluskey minimisation algorithm
1.1 Introduction of the algorithm
1.2 Basic rules
1.3 Methodology
2. Minimisation software
2.1 Basic routines
2.1.1 The Q0FINDSIMILARITY routine
2.1.2 The Q1FINDDIFFERENCE routine
2.1.3 The Q2COPYMTRXTOMTRX routine
2.1.4 The Q3LIMITSRCMATRIX routine
2.1.5 The Q4MAKEMINTMATRIX routine
2.1.6 The Q5COMBINEIMPLICS routine
2.1.7 The Q6FINDEPRIMPLICS routine
2.2 Kernel routine
2.2.1 The QUINEMCCLUSKEY routine
2.3 Main programme
2.3.1 Minimisation examples
2.3.1.1 Minimisation example 1
2.3.1.2 Minimisation example 2
2.3.1.3 Minimisation example 3
2.3.1.4 Minimisation example 4
3. References

0. Abstract

In mathematics, expressions are simplified for a number of reasons. Simpler expressions are easier to understand and easier to write down and are also less prone to error in interpretation. Most importantly, simplified expressions are usually more efficient and effective when implemented in practice.

A Boolean expression is composed of variables and terms :

• A variable is a quantity which changes by taking on the value of any constant in the algebraic system. At any one time the variable has a particular value of constant. There are only two values of constants in the system - therefore a variable can only be zero or one. Variables are denoted by letters.
• A term is a collection of variables, e.g. ABCD.

The simplification of Boolean expressions can lead to more effective computer programs, algorithms and circuits.

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.

This article describes a Boolean functions' minimisation programme which is based on the Quine-McCluskey method. The programme has been developed on Microsoft Quick Basic and supports minimisation on 64 minterms of 64 variables each (maximum).

1. The Quine-McCluskey minimisation algorithm

1.1 Introduction of the algorithm

The Quine-McCluskey method (which is also known as the "tabular method") is particularly useful when minimising functions that have a large number of variables, e.g. The six-variable functions.

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 of them are redundant.

The Quine-McCluskey method makes repeated use of the law A + !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 (-).

1.2 Basic rules

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

Consider the function of four variables f(A,B,C,D):

Listing the two minterms shows they can be combined:

Now consider another function of four variables f(A,B,C,D):

Listing the two minterms shows they cannot be combined:

They cannot be combined because we have difference in more than one digit position. This is because the 1st rule of Quine-McCluskey 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:

For the above function the indexes are:

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.

1.3 Methodology

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

To make things easier, change the function into binary notation with index value and decimal value:

Tabulate the index groups in a column and insert the decimal value alongside :

From the first list, we combine terms that differ by 1 digit only from one index group to the next. These terms from the first list are then separated into groups in the second list. Note that the ticks [x] are just there to show that one term has been combined with another term. From the second list we can see that the expression is now reduced to:

From the second list note that the term having an index of 0 can be combined with the terms of index 1. Bear in mind that the dash indicates a missing variable and must line up in order to get a third list. The final simplified expression is:

Bear in mind that any unticked terms in any list must be included in the final expression (none occurred here except from the last list). Note that the only prime implicant here is f(A,B,C) = !B. The Quine-McCluskey method reduces the function to a set of prime implicants. Note that the above solution can be derived algebraically.

Now consider another function of four variables f(A,B,C,D):

in decimal form

in binary form

in index form

The prime implicants are:

The chart is used to remove redundant prime implicants. A grid is prepared having all the prime implicants listed at the left and all the minterms of the function along the top. Each minterm covered by a given prime implicant is marked in the appropriate position.

From the above chart, BD is an essential prime implicant. It is the only prime implicant that covers the minterm decimal 15 and it also includes 5, 7 and 13. !B!D is also an essential prime implicant. It is the only prime implicant that covers the minterm denoted by decimal 10 and it also includes the terms 0, 2 and 8. The other minterms of the function are 1, 3 and 12. Minterm 1 is present in !A!B and !AD. Similarly for minterm 3. We can therefore use either of these prime implicants for these minterms. Minterm 12 is present in A!C!D and AB!C, so again either can be used.

Thus, one minimal solution is:

2. Minimisation software

2.1 Basic routines

2.1.1 The Q0FINDSIMILARITY routine

The goal of this routine is to compare the SRCA$ and SRCB$ minterms (string variables) bit by bit and find the identical bits that their values are "1"s or "X"s. The number of the identical bits (that their values are "1"s or "X"s) is stored in the SIMILARITY (integer variable) and the result of comparison is stored in the TRG$ (string variable). In TRG$, the identical bits are stored as they are and the different bits are stored as "0"s.

For example, in case we have the minterms SRCA$ = "10X1" and SRCB$ = "00X1", the result will be TRG$ = "00X1" (because the 1st bit is different and the rest are identical) and SIMILARITY = 2 (because from the three identical bits we have one "X" and one "1").

The source code of the Q0FINDSIMILARITY routine is the following:

SUB Q0FINDSIMILARITY (SRCA$, SRCB$, TRG$, SIMILARITY)
 
  TRG$ = ""
  SIMILARITY = 0
 
  LENGTHA = LEN(SRCA$)
  LENGTHB = LEN(SRCB$)
  DIFLENGTH = LENGTHA - LENGTHB
  IF DIFLENGTH <0 THEN LENGTHC="LENGTHB" SRCA$="STRING$(-DIFLENGTH," "0") + SRCA$ ELSEIF DIFLENGTH="0" THEN LENGTHC="LENGTHB" ELSEIF DIFLENGTH> 0 THEN
    LENGTHC = LENGTHA
    SRCB$ = STRING$(DIFLENGTH, "0") + SRCB$
  END IF

  FOR I = 1 TO LENGTHC
    CHARSRCA$ = LEFT$(RIGHT$(SRCA$, I), 1)
    CHARSRCB$ = LEFT$(RIGHT$(SRCB$, I), 1)
    IF CHARSRCA$ = CHARSRCB$ AND NOT CHARSRCA$ = "0" THEN
      TRG$ = CHARSRCA$ + TRG$
      SIMILARITY = SIMILARITY + 1
    ELSE
      TRG$ = "0" + TRG$
    END IF
  NEXT I

END SUB

2.1.2 The Q1FINDDIFFERENCE routine

The goal of this routine is to compare the SRCA$ and SRCB$ minterms (string variables) bit by bit and find the different bits. The number of the different bits is stored in the DIFFERENCE (integer variable) and the result of the comparison is stored in the TRG$ (string variable). In TRG$, the identical bits are stored as they are and the different bits are stored as "X"s.

For example, in case we have the minterms SRCA$ = "10X1" and SRCB$ = "00X1" the result will be TRG$ = "X0X1" (because the 1st bit is different and the rest are identical) and DIFFERENCE = 1 (because the last three bits are identical "0X1" and only the 1st bit is different).

The source code of the Q1FINDDIFFERENCE routine is the following:

SUB Q1FINDDIFFERENCE (SRCA$, SRCB$, TRG$, DIFFERENCE)
  
  TRG$ = ""
  DIFFERENCE = 0
  
  LENGTHA = LEN(SRCA$)
  LENGTHB = LEN(SRCB$)
  DIFLENGTH = LENGTHA - LENGTHB
  IF DIFLENGTH <0 THEN LENGTHC="LENGTHB" SRCA$="STRING$(-DIFLENGTH," "0") + SRCA$ ELSEIF DIFLENGTH="0" THEN LENGTHC="LENGTHB" ELSEIF DIFLENGTH> 0 THEN
    LENGTHC = LENGTHA
    SRCB$ = STRING$(DIFLENGTH, "0") + SRCB$
  END IF

  FOR I = 1 TO LENGTHC
    CHARSRCA$ = LEFT$(RIGHT$(SRCA$, I), 1)
    CHARSRCB$ = LEFT$(RIGHT$(SRCB$, I), 1)
    IF CHARSRCA$ = CHARSRCB$ THEN
      TRG$ = CHARSRCA$ + TRG$
    ELSE
      TRG$ = "X" + TRG$
      DIFFERENCE = DIFFERENCE + 1
    END IF
  NEXT I

END SUB

2.1.3 The Q2COPYMTRXTOMTRX routine

The goal of this routine is to duplicate a minterms' matrix. So the contents of the SRC$() matrix are copied to the TRG$() matrix and the number of the elements of the source matrix (SNUM) become equal to the elements of the target matrix (TNUM).

The source code of the Q2COPYMTRXTOMTRX routine is the following:

SUB Q2COPYMTRXTOMTRX (SRC$(), SNUM, TRG$(), TNUM)

  TNUM = SNUM
  FOR I = 0 TO SNUM - 1
    TRG$(I) = SRC$(I)
  NEXT I

END SUB

2.1.4 The Q3LIMITSRCMATRIX routine

The goal of this routine is to compress the size of a minterms' matrix SRC$() from the identical minterms and to limit the number of the elements (SNUM) to 255 (maximum).

The source code of the Q3LIMITSRCMATRIX routine is the following:

SUB Q3LIMITSRCMATRIX (SRC$(), SNUM)

  DIM TRG$(SNUM)
  TNUM = 0

  FOR I = 0 TO SNUM - 1
    USEDBEFORE = 0
    FOR J = 0 TO TNUM - 1
      IF TRG$(J) = SRC$(I) THEN
        USEDBEFORE = USEDBEFORE + 1
      END IF
    NEXT J
    IF USEDBEFORE = 0 THEN
      TRG$(TNUM) = SRC$(I)
      TNUM = TNUM + 1
    END IF
  NEXT I
 
  CALL Q2COPYMTRXTOMTRX(TRG$(), TNUM, SRC$(), SNUM)

  IF SNUM > 255 THEN SNUM = 255

END SUB

2.1.5 The Q4MAKEMINTMATRIX routine

The goal of this routine is to create an TMIN$() "identity" matrix with elements and bits per element, equal to TNUM. The bits (that their index number is equal to the element number that they belong) are "X"s and the rest are "0"s.

For example in case we have TNUM = 4 the result will be TMIN$ = (X000, 0X00, 00X0, 000X).

The source code of the Q4MAKEMINTMATRIX routine is the following:

SUB Q4MAKEMINTMATRIX (TMIN$(), TNUM)

  FOR I = 0 TO TNUM - 1
    TMIN$(I) = STRING$(I, "0") + "X" + STRING$(TNUM - 1 - I, "0")
  NEXT I

END SUB

2.1.6 The Q5COMBINEIMPLICS routine

The goal of this routine is to combine the minterms of a SRC$() matrix (witch has SNUM number of minterms) and prepare the SMIN$() chart that is used to remove the redundant prime implicants (at the last step of the minimisation). The results of this combination are stored in the TRG$(), TMIN$() and TNUM variables. The COMBINED (integer variable) counts the number of the combinations that took place during a single execution of this routine. Multiple executions of this routine (until COMBINED = 0) will lead the minterms' TRG$() matrix to include only the prime implicants and the TMIN$() chart to its final form.

The source code of the Q5COMBINEIMPLICS routine is the following:

SUB Q5COMBINEIMPLICS (SRC$(), SMIN$(), SNUM, TRG$(), TMIN$(), TNUM, COMBINED)
    
  COMBINED = 0
  TNUM = 0
  DIM USEDNUM(SNUM)
    
  FOR I = 0 TO SNUM - 1
    FOR J = I + 1 TO SNUM - 1
      CALL Q1FINDDIFFERENCE(SRC$(I), SRC$(J), RESULT$, DIFFERENCE)
      IF DIFFERENCE = 1 THEN
        COMBINED = COMBINED + 1
        USEDNUM(I) = USEDNUM(I) + 1
        USEDNUM(J) = USEDNUM(J) + 1
        USEDBEFORE = 0
        FOR K = 0 TO TNUM - 1
          IF TRG$(K) = RESULT$ THEN
            USEDBEFORE = USEDBEFORE + 1
          END IF
        NEXT K
        IF USEDBEFORE = 0 THEN
          TRG$(TNUM) = RESULT$
          CALL Q1FINDDIFFERENCE(SMIN$(I), SMIN$(J), TMIN$(TNUM), DIFFERENCE)
          TNUM = TNUM + 1
        END IF
      END IF
    NEXT J
  NEXT I
    
  FOR L = 0 TO SNUM - 1
    IF USEDNUM(L) = 0 THEN
      TRG$(TNUM) = SRC$(L)
      TMIN$(TNUM) = SMIN$(L)
      TNUM = TNUM + 1
    END IF
  NEXT L

END SUB

2.1.7 The Q6FINDEPRIMPLICS routine

The goal of this routine is to remove the redundant prime implicants (that are stored in the minterms' SRC$() matrix which has SNUM number of prime implicants) and store the essential prime implicants in the TRG$() matrix (which has TNUM number of minterms). This is the last step of the minimisation which is based on the use of the SMIN$() chart (that took its final form from the repeated execution of the Q5COMBINEIMPLICS routine).

The source code of the Q6FINDEPRIMPLICS routine is the following:

SUB Q6FINDEPRIMPLICS (SRC$(), SMIN$(), SNUM, TRG$(), TNUM)
 
  TNUM = 0
 
  MNUM = LEN(SMIN$(0))
  DIM MSK$(MNUM)
  CALL Q4MAKEMINTMATRIX(MSK$(), MNUM)

  ESMIN$ = ""
  ALLMIN$ = STRING$(MNUM, "X")
  DIM USEDNUM(SNUM)
 
  FOR I = 0 TO MNUM - 1
    NUMMACHED = 0
    LASTMACHED = 0
    FOR J = 0 TO SNUM - 1
      CALL Q0FINDSIMILARITY(MSK$(I), SMIN$(J), RESULT$, SIMILARITY)
      IF SIMILARITY = 1 THEN
        NUMMACHED = NUMMACHED + 1
        LASTMACHED = J
      END IF
    NEXT J
    IF NUMMACHED = 1 THEN
      CALL Q1FINDDIFFERENCE(SMIN$(LASTMACHED), ESMIN$, RESULT$, DIFFERENCE)
      ESMIN$ = RESULT$
      USEDNUM(LASTMACHED) = USEDNUM(LASTMACHED) + 1
      USEDBEFORE = 0
      FOR K = 0 TO TNUM - 1
        IF TRG$(K) = SRC$(LASTMACHED) THEN
          USEDBEFORE = USEDBEFORE + 1
        END IF
      NEXT K
      IF USEDBEFORE = 0 THEN
        TRG$(TNUM) = SRC$(LASTMACHED)
        TNUM = TNUM + 1
      END IF
    END IF
  NEXT I

  DO WHILE (NOT ESMIN$ = ALLMIN$)
    MAXSIMILARITY = 0
    LASTMACHED = 0
    FOR L = 0 TO SNUM - 1
      IF USEDNUM(L) = 0 THEN
        CALL Q1FINDDIFFERENCE(SMIN$(L), ESMIN$, RESULT$, DIFFERENCE)
        CALL Q0FINDSIMILARITY(RESULT$, ALLMIN$, NEWRESULT$, SIMILARITY)
        IF SIMILARITY > MAXSIMILARITY THEN
          MAXSIMILARITY = SIMILARITY
          LASTMACHED = L
          FINALRESULT$ = NEWRESULT$
        END IF
      END IF
    NEXT L
    IF MAXSIMILARITY > 0 THEN
      ESMIN$ = FINALRESULT$
      TRG$(TNUM) = SRC$(LASTMACHED)
      TNUM = TNUM + 1
    END IF
  LOOP

END SUB

2.2 Kernel routine

2.2.1 The QUINEMCCLUSKEY routine

The QUINEMCCLUSKEY routine is the kernel routine which uses all the above described routines to minimize Boolean functions. The Boolean functions are expressed in the "Sum Of Products" format. All (SNUM) the minterms ("products") of each function stored in the SRC$() matrix in binary format. To accomplish all the steps of the minimisation, this routine uses some temporary matrices and exchanges data between them with processing or copying directives (that are included in the above routines). After the execution of this routine the number of the essential prime implicants and their values stored back in the SNUM and SRC$() variables. Finally, the minimized expression of the function is expressed from the sum of the essential prime implicants.

The source code of the QUINEMCCLUSKEY routine is the following:

SUB QUINEMCCLUSKEY (SRC$(), SNUM)

  DIM MA$(2 ^ 9)
  DIM MAM$(2 ^ 9)
  DIM MB$(2 ^ 9)
  DIM MBM$(2 ^ 9)

  CALL Q3LIMITSRCMATRIX(SRC$(), SNUM)
  CALL Q2COPYMTRXTOMTRX(SRC$(), SNUM, MA$(), ANUM)
  CALL Q4MAKEMINTMATRIX(MAM$(), ANUM)
 
  DO
    CALL Q5COMBINEIMPLICS(MA$(), MAM$(), ANUM, MB$(), MBM$(), BNUM, COMBINED)
    CALL Q2COPYMTRXTOMTRX(MB$(), BNUM, MA$(), ANUM)
    CALL Q2COPYMTRXTOMTRX(MBM$(), BNUM, MAM$(), ANUM)
  LOOP UNTIL COMBINED = 0

  CALL Q6FINDEPRIMPLICS(MA$(), MAM$(), ANUM, MB$(), BNUM)
  CALL Q2COPYMTRXTOMTRX(MB$(), BNUM, SRC$(), SNUM)

END SUB

2.3 Main programme

The main programme is developed to demonstrate the usage of the above routines. It has a simple user interface and uses ASCII files to import and export data.

The ASCII files that will be used as import files should have the following format:

M {n}
V {m}
{0 minterm of m-variables}
{1 minterm of m-variables}
.....
{n minterm of m-variables}

The ASCII files that will be used as export files (and will be created by the programme) will have the above format.