kennethw@tekecs.UUCP (01/10/84)
The following program is the second of 4 programs I received to do
logic reduction by the Quine-McCluskey method. I have received
several requests for copies of anything I got, so I'm posting them
here.
(Message inbox:41)
From: tektronix!decvax!ucf-cs!alan
To: decvax!microsoft!uw-beaver!tektronics!orca!tekecs!kennethw
Received: from decvax.uucp by tektronix ; 27 Dec 83 18:15:04 PST
Received: by decvax.UUCP (4.12/4.13), id AA29761; Tue, 27 Dec 83 20:51:58 est
Date: Tue, 27 Dec 83 20:51:58 est
Message-Id: <8312280151.AA29761@decvax.UUCP>
Subject: Quine-McCluskey.
#
# This csh script will create a directory called qm
# and place the files README, qm.c and samplein.
# to run the script, strip off the header and trailer
# mailer messages (up to the last `EOF`), make the resulting
# file executable and run it.
#
# This program is used to create the prime implicant table
# for a set of minterms.
#
mkdir qm
cat << `EOF` > qm/README
Author : R. Alan Eustace
University of Central Florida
Orlando, FL. 32817
(305) 275-2341
alan!ucf-cs
alan.ucf-cs@rand-relay
This program takes as input the maximum number of bits
in a minterm, and a list of minterms. Is output is
a list of all prime implicants, the covers associated
with each, and the number of useful (not don't care)
minterms in the cover. I used this information to
derive the prime implicant table. A very useful
and fairly straightforward addition
to the program would be to derive the reduced prime
implicant chart.
The algorithm used is by Quine-McClusky. The minterms
are grouped into bins according to the number of
one bits in the string.
This algorithm may be distributed as long as the author's
name is credited.
Please mail additions, corrections or any distribution
information to me at alan!ucf-cs.
An example of the input and outputs of the program are provided.
Don't care inputs have an 'x' appended.
4
2
3
7
9
11
13
1x
10x
15x
A blank is "required" following each non-don't care minterm (Sorry. I
generated the minterms using another program).
The program output is as follows:
1 -01- * 2 3 10x 11 /* 3 */
2 -0-1 * 1x 3 9 11 /* 3 */
3 --11 * 3 7 11 15x /* 3 */
4 1--1 * 9 11 13 15x /* 3 */
The first column is the product term number, the second column is
the product terms equation (e.g. if the four bits stand for abcd, then
the first product term is b'c.) The third column is the product terms
covered and the forth is the number of non-don't care terms in the
cover. Using this information, it is trivial to come create the
prime implicant table.
The example shown comes from the book "Fundamentals of
Logic Design". Second Edition. by Roth. pg. 143.
It is compiled using the commands
cc -O qm.c -o qm
and executed by the command
qm < minterm.file
This program was created to "minimize" to save me the work of
minimizing a particular 9 input 5 output function.
It is not capable of doing any multiple output minimizations
and almost no time was spent commenting the code
or doing error checking. It served my purposes fairly
well and I hope it may be of some use to you.
Good luck.
alan
`EOF`
cat << `EOF` > qm/samplein
4
2
3
7
9
11
13
1x
10x
15x
`EOF`
cat << `EOF` > qm/qm.c
/* Author : R. Alan Eustace
University of Central Florida
Orlando, FL. 32817
(305) 275-2341
alan!ucf-cs
*/
#include <stdio.h>
#define MAXBIN 1000
#define MAXBITS 15
#define MAXMINT 600
#define MAXSTACK 400
struct arry
{
char arr[MAXBIN][MAXBITS];
char npi[MAXBIN];
int next;
};
struct pass
{
struct arry bin[MAXBITS];
} arr1,arr2,*to,*from,*save;
int totbits;
char dcflag[MAXMINT];
main()
{
int ones,bits,min,it,combine;
int cnt,nmin,i,ibin,bi,nbi,flag,ich;
char bit[MAXBITS];
char new[MAXBITS];
char dc;
cnt = 0;
scanf("%d",&bits);
totbits = bits-1;
from = &arr1;
to = &arr2;
/* Init -
initializes each bit bin.
*/
init(bits,from);
/* end init */
/* read and place */
for(;;)
{
if(scanf("%d%c",&min,&dc)==EOF) break;
dcflag[min]=dc;
ones = 0;
for(it=0;it<=totbits;it++)
{
nmin = min/2;
bit[it] = min -(nmin*2) + '0';
if (bit[it]=='1') ones = ones + 1;
min = nmin;
}
bit[it+1] = '\0';
reverse(bit);
if (from->bin[ones].next >= MAXBIN-1)
{
printf("\n\nBIN %d SIZE EXCEEDED\n\n",ones);
exit(1);
}
copy(bit,from->bin[ones].arr[from->bin[ones].next]);
from->bin[ones].npi[from->bin[ones].next]= ' ';
from->bin[ones].next += 1;
}
/* end read and place */
combine = 1;
while(combine&& bits >=0)
{
init(bits,to);
for (ibin=0;ibin<=bits;ibin++)
{
for(bi=0;bi<=from->bin[ibin].next-1;bi++)
{
for (nbi=0;nbi<=from->bin[ibin+1].next-1;nbi++)
{
ones=0;
if (test(from->bin[ibin].arr[bi],
from->bin[ibin+1].arr[nbi],
new,&ones))
{
from->bin[ibin].npi[bi]='@';
from->bin[ibin+1].npi[nbi]='@';
/* check if new */
flag=0;
for(ich=0;ich<to->bin[ones].next;ich++)
{
if(strcmp(to->bin[ones].arr[ich],new)==0)
{
flag = 1;
break;
}
}
/* end new check */
if(flag==0)
{
if (to->bin[ones].next >= MAXBIN-1)
{
printf("\n\nBIN %d SIZE EXCEEDED\n\n",ones);
exit(1);
}
copy(new,to->bin[ones].arr[to->bin[ones].next]);
to->bin[ones].npi[to->bin[ones].next]=' ';
to->bin[ones].next += 1;
}
}
}
}
}
/* end compare */
/* output */
combine =0;
/*printf("____________\n");*/
for(ibin=0;ibin<=bits+1;ibin++)
{
/*printf("\nones = %d\n\n",ibin);*/
for(i=0;i<=from->bin[ibin].next-1;i++)
{
if(from->bin[ibin].npi[i]!='@')
{
cnt += 1;
printf("%d %s ",cnt,from->bin[ibin].arr[i]);
printf(" * ");
minterm(from->bin[ibin].arr[i]);
printf("\n");
}
else combine=1;
}
/*if(i!=0) printf("____________\n");*/
}
/* end output */
save = from;
from = to;
to = save;
bits = bits-1;
}
}
test(s1,s2,new,ones)
char s1[];
char s2[];
char new[];
int *ones;
{
int il,notmatch;
notmatch = 0;
for(il=0;il<=totbits;il++)
{
if (s1[il] == s2[il])
{
new[il] = s1[il];
if (s1[il] == '1')
*ones += 1;
}
else
{
if (s1[il]=='-'||s2[il]=='-'||notmatch>=1)
return(0);
else
{new[il]='-';
notmatch += 1;
}
}
}
new[il+1]='\0';
return(1);
}
init(bits,ptr)
int bits;
struct pass *ptr;
{
int i;
for(i=0;i<=bits+1;i++)
{
ptr->bin[i].next = 0;
}
}
copy(s1,s2)
char s1[],s2[];
{
int i;
i = 0;
while ((s2[i] = s1[i]) != '\0')
i++;
}
reverse(s)
char s[];
{
int c,i,j;
for (i=0,j=strlen(s)-1; i<j;i++,j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
minterm(str)
char str[];
{
int ndc,top,pow,i,is,oldtop;
int stack[MAXSTACK];
top = 0;
pow = 1;
stack[0]= 0;
for (i=totbits;i>=0;i--)
{
if (str[i]=='0' || str[i]=='1')
{
for(is=0;is<=top;is++)
{
stack[is] = stack[is]+pow*(str[i]-'0');
}
}
else
{
oldtop = top;
for(is=0;is<=top;is++)
stack[top+is+1] = stack[is];
top =(top+1)*2-1;
for (is = oldtop + 1;is<=top;is++)
stack[is] = stack[is] + pow;
}
pow = pow * 2;
}
ndc=0;
for(i=0;i<=top;i++)
{
if(i%16==0&&i!=0) printf("\n ");
printf("%d%c ",stack[i],dcflag[stack[i]]);
if (dcflag[stack[i]]!='x') ndc += 1;
}
printf(" /* %d */ ",ndc);
}
`EOF`