Encoder Front Page
SRS Home | Front Page | Monthly Issue | Index
Google
Search WWW Search seattlerobotics.org

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

Software Design & Development


George Vastianos

Electronics Engineer BSc.
Dipl. from Electronics Department,
Faculty of Technological Applications,
Technological Educational Institute of Piraeus, Greece

george.vastianos@ieee.org

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 :

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):

A!BC  : Is represented by 101. Binary notation, where A=1, B=0, C=1
!AB!C : Is represented by 010. Binary notation, where A=0, B=1, C=0
A!B   : Is represented by 10-. Binary notation, where A=1, B=0, C=X
AC    : Is represented by 1-1. Binary notation, where A=1, B=X, C=1

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

f(A,B,C,D) = SUM(0011, 1011) = !A!BCD + A!BCD = !BCD

Listing the two minterms shows they can be combined:

A B C D
-------
0 0 1 1
1 0 1 1
-------
- 0 1 1

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

f(A,B,C,D) = SUM(0111, 1011) = !ABCD + A!BCD

Listing the two minterms shows they cannot be combined:

A B C D
-------
0 1 1 1
1 0 1 1
-------
?

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:

f(A,B,C) = SUM(000, 010, 100, 101, 111)

For the above function the indexes are:

Index 0: 000
Index 1: 010, 100
Index 2: 101
Index 3: 111

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):

f(A,B,C) = !A!B!C + !A!BC + A!B!C + A!BC

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

f(A,B,C) = SUM(000, 001, 100, 101)
!A!B!C : Binary notation 000 : Index 0 : Decimal value 0
!A!BC  : Binary notation 001 : Index 1 : Decimal value 1
A!B!C  : Binary notation 100 : Index 1 : Decimal value 4
A!BC   : Binary notation 101 : Index 2 : Decimal value 5

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

 ----------------------------------------------------------------------------- 
|         1st List        |         2nd List        |         3rd List        |
 ----------------------------------------------------------------------------- 
|                         |                         |                         |
|             A B C       |             A B C       |             A B C       |
|   --------- -----       |   --------- -----       |   --------- -----       |
|      (0)    0 0 0 [x]   |     (0,1)   0 0 - [x]   |   (0,1,4,5) - 0 -       |
|   --------- -----       |     (0,4)   - 0 0 [x]   |   (0,4,1,5) - 0 -       |
|      (1)    0 0 1 [x]   |   --------- -----       |                         |
|      (4)    1 0 0 [x]   |     (1,5)   - 0 1 [x]   |                         |
|   --------- -----       |     (4,5)   1 0 - [x]   |                         |
|      (5)    1 0 1 [x]   |                         |                         |
|                         |                         |                         |
 ----------------------------------------------------------------------------- 

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:

f(A,B,C) = !A!B + !B!C + !BC + A!B

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:

f(A,B,C) = !B

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):

f(A,B,C,D) = SUM(0,1,2,3,5,7,8,10,12,13,15)

in decimal form

= SUM(0000,0001,0010,0011,0101,0111,1000,1010,1100,1101,1111)

in binary form

= SUM(0,1,1,2,2,3,1,2,2,3,4)

in index form

 ----------------------------------------------------------------------------------- 
|         1st List          |         2nd List          |         3rd List          |
 ----------------------------------------------------------------------------------- 
|                           |                           |                           |
|               A B C D     |               A B C D     |               A B C D     |
| ------------- -------     | ------------- -------     | ------------- -------     |
|     (00)      0 0 0 0 [x] |    (00,01)    0 0 0 - [x] | (00,01,02,03) 0 0 - - (3) |
| ------------- -------     |    (00,02)    0 0 - 0 [x] | (00,02,01,03) 0 0 - -     |
|     (01)      0 0 0 1 [x] |    (00,08)    - 0 0 0 [x] | (00,02,08,10) - 0 - 0 (4) |
|     (02)      0 0 1 0 [x] | ------------- -------     | (00,08,02,10) - 0 - 0     |
|     (08)      1 0 0 0 [x] |    (01,03)    0 0 - 1 [x] | ------------- -------     |
| ------------- -------     |    (01,05)    0 - 0 1 [x] | (01,03,05,07) 0 - - 1 (5) |
|     (03)      0 0 1 1 [x] |    (02,03)    0 0 1 - [x] | (01,05,03,07) 0 - - 1     |
|     (05)      0 1 0 1 [x] |    (02,10)    - 0 1 0 [x] | ------------- -------     |
|     (10)      1 0 1 0 [x] |    (08,10)    1 0 - 0 [x] | (05,07,13,15) - 1 - 1 (6) |
|     (12)      1 1 0 0 [x] |    (08,12)    1 - 0 0 (1) | (05,13,07,15) - 1 - 1     |
| ------------- -------     | ------------- -------     |                           |
|     (07)      0 1 1 1 [x] |    (03,07)    0 - 1 1 [x] |                           |
|     (13)      1 1 1 1 [x] |    (05,07)    0 1 - 1 [x] |                           |
| ------------- -------     |    (05,13)    - 1 0 1 [x] |                           |
|     (15)      1 1 1 1 [x] |    (12,13)    1 1 0 - (2) |                           |
|                           | ------------- -------     |                           |
|                           |    (07,15)    - 1 1 1 [x] |                           |
|                           |    (13,15)    1 1 - 1 [x] |                           |
 ----------------------------------------------------------------------------------- 

The prime implicants are:

!A!B + !B!D + !AD + BD + A!C!D + AB!C

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.

IMPLICANTS  00   01   02   03   05   07   08   10   12   13   15  
            ----------------------------------------------------- 
!A!B       | x    x    x    x                                    |
!B!D       | x         x                   x   (x)               |
!AD        |      x         x    x    x                          |
BD         |                     x    x                   x   (x)|
A!C!D      |                               x         x           |
AB!C       |                                         x    x      |
            ----------------------------------------------------- 
Essential    x         x         x    x    x   (x)        x   (x) 

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:

Z = !B!D + BD + !A!B + A!C!D

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.

Files to download : QMCCLIB.BAS (5,23 KBytes), QMCCMIN.BAS (9,11 KBytes) & QMCCMIN.EXE (51,8 KBytes).

2.3.1 Minimisation examples

2.3.1.1 Minimisation example 1

Input ASCII file:

M 4
V 3
000
001
100
101

Output ASCII file:

M 1
V 3
X0X

2.3.1.2 Minimisation example 2

Input ASCII file:

M 12
V 4
0000
1000
0100
1010
0110
1110
0001
1001
0011
1011
0111
1111

Output ASCII file:

M 5
V 4
X00X
1X1X
X11X
X0X1
0X00

2.3.1.3 Minimisation example 3

Input ASCII file:

M 40
V 6
000000
000001
000010
000011
000100
001001
001010
001011
001100
001111
010010
010011
010100
010101
010110
010111
011010
011011
011100
011101
100000
100001
100110
100111
101000
101001
101010
101011
101110
101111
110000
110011
110100
110101
110110
110111
111000
111001
111110
111111

Output ASCII file:

M 12
V 6
0XX100
X01X11
0XX01X
01X10X
1XX11X
X10X11
X101XX
1X100X
X0000X
00X0X1
X0101X
1XX000

2.3.1.4 Minimisation example 4

Input ASCII file:

M 64
V 64
0000000000011101101001110010010100000000100111000110111011110101
0000000000011101101001110010110100000000100111000110111011110101
0000000000011101101001110011010100000000100111000110111011110101
0000000000011101101001110011110100000000100111000110111011110101
0000000000100011110101011101001000000001001000000010111100110011
0000000000100011110101011101001000100001001000000010111100110011
0000000000100011110101011101001001000001001000000010111100110011
0000000000100011110101011101001001100001001000000010111100110011
0000000010011100011011101111010100000001100111100111110100001100
0000000010011100011011101111010100001001100111100111111100001100
0000000010011100011011101111010100010001100111100111110100001100
0000000010011100011011101111010100011001100111100111110100001100
0000000010100010001111000111001000000001101000010010000111010011
0000000010100010001111000111001000000001101000010010000111011011
0000000010100010001111000111001000000001101000010010000111110011
0000000010100010001111000111001000000001101000010010000111110011
0000000010100010001111000111001000000001101000010010000111111011
0000000010100010101111000111001000000001101000010010000111110011
0000000010100011001111000111001000000001101000010010000111110011
0000000010100011101111000111001000000001101000010010000111110011
0000000100100000001011110011001100000000101000100011110001110010
0000000100100000001011110011001100010000101000100011110001110010
0000000100100000001011110011001100100000101000100011110001110010
0000000100100000001011110011001100110000101000100011110001110010
0000000101111111000010011011110100000000111111001001101101110100
0000000101111111000010011011110100100000111111001001101101110100
0000000101111111000010011011110101000000111111001001101101110100
0000000101111111000010011011110101100000111111001001101101110100
0000000110000001010000101010001100000000010000110101000101100010
0000000110000001010000101010001100000001010000110101000101100010
0000000110000001010000101010001100000010010000110101000101100010
0000000110000001010000101010001100000011010000110101000101100010
0000000110111110000000001101110000000000011111010001001000111101
0000000110111110000000001101110000100000011111010001001000111101
0000000110111110000000001101110001000000011111010001001000111101
0000000110111110000000001101110001100000011111010001001000111101
0000000111101110100001000000001100000000000000111001011010000010
0000000111101110100001000000001100100000000000111001011010000010
0000000111101110100001000000001101000000000000111001011010000010
0000000111101110100001000000001101100000000000111001011010000010
0000011000001110100101011001100000000111000011000100111101011001
0000011000001110110101011001100000000111000011000100111101011001
0000011000001111100101011001100000000111000011000100111101011001
0000011000001111110101011001100000000111000011000100111101011001
0000011001100111001000000000000100000111011001001011001010000000
0000011001110101000000101100100100000110011101110001000100101000
0000011001110101001000101100100100000110011101110001000100101000
0000011001110101010000101100100100000110011101110001000100101000
0000011001110101011000101100100100000110011101110001000100101000
0000011011010110111010110011000000000111110101011111100001110001
0000011101110100100010111010100100000110111101101001100011101000
0001011011010110111010110011000000000111110101011111100001110001
0001011101110100100010111010100100000110111101101001100011101000
0010011000110111111001101111000000000111001101000000110100001001
0010011000110111111001101111000001000111001101000000110100001001
0010011000110111111001101111000010000111001101000000110100001001
0010011000110111111001101111000011000111001101000000110100001001
0010011011010110111010110011000000000111110101011111100001110001
0010011101110100100010111010100100000110111101101001100011101000
0011011011010110111010110011000000000111110101011111100001110001
0011011101110100100010111010100100000110111101101001100011101000
0100011001100111001000000000000100000111011001001011001010000000
1000011001100111001000000000000100000111011001001011001010000000
1100011001100111001000000000000100000111011001001011001010000000

Output ASCII file:

M 18
V 64
000000000001110110100111001XX10100000000100111000110111011110101
000000000010001111010101110100100XX00001001000000010111100110011
00000000100111000110111011110101000X0001100111100111110100001100
0000000010011100011011101111010100001001100111100111111100001100
000000001001110001101110111101010001X001100111100111110100001100
0000000010100010001111000111001000000001101000010010000111X1X011
000000001010001XX01111000111001000000001101000010010000111110011
0000000100100000001011110011001100XX0000101000100011110001110010
000000010111111100001001101111010XX00000111111001001101101110100
00000001100000010100001010100011000000XX010000110101000101100010
000000011011111000000000110111000XX00000011111010001001000111101
000000011110111010000100000000110XX00000000000111001011010000010
000001100000111X1X0101011001100000000111000011000100111101011001
XX00011001100111001000000000000100000111011001001011001010000000
00000110011101010XX000101100100100000110011101110001000100101000
00XX011011010110111010110011000000000111110101011111100001110001
00XX011101110100100010111010100100000110111101101001100011101000
00100110001101111110011011110000XX000111001101000000110100001001

3. References

  1. George Vastianos, "Boolean functions' minimisation software based on the Quine-McCluskey method", Software Notes, (Draft Version), Athens-GR, April 1998.
  2. David Belton, "Minimisation of Boolean Functions", Combinational Logic & Systems Tutorial Guide, University of Surrey, Surrey-UK, April 1998.