quine mccluskey on arduino uno

Can we implement quine-Mcculskey algorithm on an arduino uno and displaying the output on a lcd display.

really urgent.
thanks in advance

"Technically, anything is possible."

Got a link to this algorithm?

Hell's Bells! I haven't heard of that method since college!
I've never done it in C, only Algol60 :sunglasses:

the code is not mine I downloaded it from internet it is in c++.I want to implement it in arduino.

here goes the code and I dont understand one bit of it.

sorry if i appear to be free loader.
(code tags added by moderator…)

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <limits.h> 
#include <assert.h> 
#include <stdbool.h> 
#include <signal.h> 
#include <inttypes.h> 
#include <float.h> 
#include <ctype.h> 
#include <time.h> 
 
int *in,**d1,**d2,x,y,**g,**d; void create(int x,int y); int staging(int x,int y); int duplication(int x,int y); int indexing(int x,int y3,int y); void pimp(int x,int y3,int a); void decode(int x,int y3); 
void wxyz(int x,int y3); 
 
int main() 
{ int i,j,y1,y2,y3,a,q; 
printf("\n Please give the number of variables you want to minimize - "); scanf("%d",&x); 
printf("\n\n In this program your inputs are designated as : "); for(j=x-1;j>=0;j--) printf("a[%d]",j); 
printf("\n\n Please give the number of minterms that you want to minimize - "); scanf("%d",&y); 
in=(int *)malloc(y * sizeof(int)); d=d1=(int **)malloc(y * sizeof(int *)); for(i=0;i<y;i++) d[i]=d1[i]=(int *)malloc((x+1)*sizeof(int)); for(i=0;i<y;i++) 
{  
printf("\n Please give decimal indices of minterms one at a time :: "); scanf("%d",&in[i]);} create(x,y); y1=y*(y+1)/2; 
d2=(int **)malloc(y1*sizeof(int *)); for(i=0;i<y1;i++) 
d2[i]=(int *)malloc((x+1)*sizeof(int)); y2=staging(x,y); y3=duplication(x,y2); a=indexing(x,y3,y); pimp(x,y3,a); 
printf("\n\nThe essential prime implicants giving minimized expression are:\n\n"); decode(x,y3); 
} void create(int x,int y) 
{ 
int i,j,a; 
for(i=0;i<y;i++) 
{ a=in[i]; for(j=0;j<x;j++) 
{ 
d[i][j]=d1[i][j]=a%2; a=a/2; 
} d[i][x]=d1[i][x]=8; 
} 
} int staging(int x,int y) 
{ 
int i1,j1,k1,t1,i2,j2,t2,c; i2=0;c=0; 
for(i1=0;i1<(y-1);i1++) 
{ 
for(j1=i1+1;j1<y;j1++) 
{ t1=0; 
for(k1=0;k1<x;k1++) 
{ 
if(d1[i1][k1]!=d1[j1][k1]) 
{ t1++; t2=k1; 
} 
} if(t1==1) { for(j2=0;j2<t2;j2++) d2[i2][j2]=d1[i1][j2]; d2[i2][t2]=3; for(j2=t2+1;j2<y;j2++) d2[i2][j2]=d1[i1][j2]; d2[i2][x]=8; d1[i1][x]=9; d1[j1][x]=9; i2++; 
} 
} 
} for(i1=0;i1<y;i1++) { if(d1[i1][x]==8) { for(j1=0;j1<=x;j1++) d2[i2][j1]=d1[i1][j1]; i2++; 
} 
} for(j1=0;j1<x;j1++) { if(d1[0][j1]==d2[0][j1]) c++; 
} if(c<x) { 
d1=(int **)malloc(i2*sizeof(int *)); for(i1=0;i1<i2;i1++) d1[i1]=(int *)malloc((x+1)*sizeof(int)); for(i1=0;i1<i2;i1++) { for(j1=0;j1<=x;j1++) d1[i1][j1]=d2[i1][j1]; 
} staging(x,i2); 
} else return(i2); 
} int duplication(int x,int y) 
{ 
int i1,i2,j,c,t; t=0; for(i1=0;i1<(y-1);i1++) { for(i2=i1+1;i2<y;i2++) { c=0; for(j=0;j<x;j++) { if(d1[i1][j]==d1[i2][j]) c++; 
} if(c==x) d1[i2][x]=9; 
} 
} for(i1=0;i1<y;i1++) { if(d1[i1][x]==9) t++; 
} i2=y-t; d2=(int **)malloc(i2*sizeof(int *)); for(j=0;j<i2;j++) d2[j]=(int *)malloc((x+1)*sizeof(int)); i2=0; for(i1=0;i1<y;i1++) if(d1[i1][x]==8) { for(j=0;j<=x;j++) d2[i2][j]=d1[i1][j]; i2++; 
} return(i2); 
} int indexing(int x,int y3,int y) 
{ int i1,j,c1,i2,c,a; c=0;a=1; for(j=0;j<x;j++) if(d1[0][j]==3)c++; for(i1=0;i1<c;i1++) a=a*2; g=(int **)malloc(y3*sizeof(int *)); for(j=0;j<y3;j++) g[j]=(int *)malloc(a*sizeof(int)); for(i1=0;i1<y3;i1++) for(j=0;j<a;j++) g[i1][j]=-2; for(i1=0;i1<y3;i1++) { c=0; for(i2=0;i2<y;i2++) { c1=0; for(j=0;j<x;j++) { 
if((d2[i1][j]==d[i2][j])||(d2[i1][j]==3)) 
c1++; if(c1==x) { g[i1][c]=in[i2]; c++; 
} 
} 
} 
} return(a); 
} void pimp(int x,int y3,int a) 
{ 
int i1,i2,j1,j2,c,w,j3,c1,c2,j4,c3,c4; 
c=0; for(i1=0;i1<y3;i1++) { for(j1=0;j1<a;j1++) { if(g[i1][j1]!=-2) { for(i2=0;i2<y3;i2++) { if(i2!=i1) { for(j2=0;j2<a;j2++) if(g[i1][j1]!=g[i2][j2]) c++; 
} 
} if(c==a*(y3-1)) d2[i1][x]=91;c=0; 
} 
    } 
  } 
for(i1=0;i1<y3;i1++) { if(d2[i1][x]==91) { for(j1=0;j1<a;j1++) { if(g[i1][j1]!=-2) { for(i2=0;i2<y3;i2++) { if(i1!=i2) { for(j2=0;j2<a;j2++) if(g[i1][j1]==g[i2][j2]) g[i2][j2]=-3; 
} 
} 
} 
} 
} 
} for(i1=0;i1<y3;i1++) { if(d2[i1][x]==91) { for(j1=0;j1<a;j1++) if(g[i1][j1]!=-2)g[i1][j1]=-1; 
} 
} for(i1=0;i1<y3;i1++) { if(d2[i1][x]!=91) { for(j1=0;j1<a;j1++) { if(g[i1][j1]>=0) { for(i2=0;i2<y3;i2++) if(i2!=i1) 
{ for(j2=0;j2<a;j2++) { if(g[i2][j2]>=0) { if(g[i1][j1]==g[i2][j2]) 
{ w=i2; 
if((d2[w][x]==90)||(d2[w][x]==8)) 
{ for(j3=0,c1=0;j3<x;j3++) if(d2[i1][j3]==3) c1++; for(j3=0,c2=0;j3<x;j3++) if(d2[i2][j3]==3) c2++; if(c1>c2) { d2[i1][x]=90; g[i2][j2]=-1; } if(c2>c1) { d2[i1][x]=8; d2[i2][x]=90; g[i1][j1]=-1; 
} if(c2==c1) { 
for(j3=0,c3=0,c4=0;j3<a;j3++) 
{ if(g[i1][j3]==- 1)c3++; if(g[i2][j3]==-1)c4++; 
} if(c3>c4) { d2[i2][x]=90;d1[i1][x]=8; g[i1][j1]=-1; 
} if(c3==c4) { d2[i1][x]=90; g[i2][j2]=-1; 
} if(c3<c4) { d2[i1][x]=90; g[i2][j2]=-1; 
} 
  } 
} 
if(d2[w][x]==91) d1[w][x]=8; 
} 
} 
} 
} 
} 
} 
} 
} return; 
} void decode(int x,int y3) 
{ 
int i,j; 
for(i=0;i<y3;i++) 
{ 
if((d2[i][x]==91)||(d2[i][x]==90)) 
{ 
for(j=x-1;j>=0;j--) 
{ 
if(d2[i][j]==0)printf("a[%d]'",j); if(d2[i][j]==1)printf("a[%d]",j); 
} 
} printf("\n\n"); 
} return; 
}

Try this site,

appears to have a C++ implementation, Arduino should support.

does the c++ code work directly when copied directly in arduino ide.

You will need to gather all these libraries for it compile

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <math.h> 
#include <limits.h> 
#include <assert.h> 
#include <stdbool.h> 
#include <signal.h> 
#include <inttypes.h> 
#include <float.h> 
#include <ctype.h> 
#include <time.h>

Change the code a little. May need to

int *in,**d1,**d2,x,y,**g,**d; 
int staging(int x,int y); 
int duplication(int x,int y);
int indexing(int x,int y3,int y);
 
void setup(){
Serial.begin(9600);
}
void loop(){
 int i,j,y1,y2,y3,a,q; 
printf("\n Please give the number of variables you want to minimize - "); scanf("%d",&x); 
printf("\n\n In this program your inputs are designated as : "); for(j=x-1;j>=0;j--) printf("a[%d]",j); 
printf("\n\n Please give the number of minterms that you want to minimize - "); scanf("%d",&y); 
in=(int *)malloc(y * sizeof(int)); d=d1=(int **)malloc(y * sizeof(int *)); for(i=0;i<y;i++) d[i]=d1[i]=(int *)malloc((x+1)*sizeof(int)); for(i=0;i<y;i++) 
{  
printf("\n Please give decimal indices of minterms one at a time :: "); scanf("%d",&in[i]);} create(x,y); y1=y*(y+1)/2; 
d2=(int **)malloc(y1*sizeof(int *)); for(i=0;i<y1;i++) 
d2[i]=(int *)malloc((x+1)*sizeof(int)); y2=staging(x,y); y3=duplication(x,y2); a=indexing(x,y3,y); pimp(x,y3,a); 
printf("\n\nThe essential prime implicants giving minimized expression are:\n\n"); decode(x,y3); 
} 

void wxyz(int x,int y3);  // I don't see this in functions below - not needed?

void create(int x,int y) 
{ 
int i,j,a; 
for(i=0;i<y;i++) 
{ a=in[i]; for(j=0;j<x;j++) 
{ 
d[i][j]=d1[i][j]=a%2; a=a/2; 
} d[i][x]=d1[i][x]=8; 
} 
}

 int staging(int x,int y) 
{ 
int i1,j1,k1,t1,i2,j2,t2,c; i2=0;c=0; 
for(i1=0;i1<(y-1);i1++) 
{ 
for(j1=i1+1;j1<y;j1++) 
{ t1=0; 
for(k1=0;k1<x;k1++) 
{ 
if(d1[i1][k1]!=d1[j1][k1]) 
{ t1++; t2=k1; 
} 
} if(t1==1) { for(j2=0;j2<t2;j2++) d2[i2][j2]=d1[i1][j2]; d2[i2][t2]=3; for(j2=t2+1;j2<y;j2++) d2[i2][j2]=d1[i1][j2]; d2[i2][x]=8; d1[i1][x]=9; d1[j1][x]=9; i2++; 
} 
} 
} for(i1=0;i1<y;i1++) { if(d1[i1][x]==8) { for(j1=0;j1<=x;j1++) d2[i2][j1]=d1[i1][j1]; i2++; 
} 
} for(j1=0;j1<x;j1++) { if(d1[0][j1]==d2[0][j1]) c++; 
} if(c<x) { 
d1=(int **)malloc(i2*sizeof(int *)); for(i1=0;i1<i2;i1++) d1[i1]=(int *)malloc((x+1)*sizeof(int)); for(i1=0;i1<i2;i1++) { for(j1=0;j1<=x;j1++) d1[i1][j1]=d2[i1][j1]; 
} staging(x,i2); 
} else return(i2); 
}

 int duplication(int x,int y) 
{ 
int i1,i2,j,c,t; t=0; for(i1=0;i1<(y-1);i1++) { for(i2=i1+1;i2<y;i2++) { c=0; for(j=0;j<x;j++) { if(d1[i1][j]==d1[i2][j]) c++; 
} if(c==x) d1[i2][x]=9; 
} 
} for(i1=0;i1<y;i1++) { if(d1[i1][x]==9) t++; 
} i2=y-t; d2=(int **)malloc(i2*sizeof(int *)); for(j=0;j<i2;j++) d2[j]=(int *)malloc((x+1)*sizeof(int)); i2=0; for(i1=0;i1<y;i1++) if(d1[i1][x]==8) { for(j=0;j<=x;j++) d2[i2][j]=d1[i1][j]; i2++; 
} return(i2); 
} 

int indexing(int x,int y3,int y) 
{ int i1,j,c1,i2,c,a; c=0;a=1; for(j=0;j<x;j++) if(d1[0][j]==3)c++; for(i1=0;i1<c;i1++) a=a*2; g=(int **)malloc(y3*sizeof(int *)); for(j=0;j<y3;j++) g[j]=(int *)malloc(a*sizeof(int)); for(i1=0;i1<y3;i1++) for(j=0;j<a;j++) g[i1][j]=-2; for(i1=0;i1<y3;i1++) { c=0; for(i2=0;i2<y;i2++) { c1=0; for(j=0;j<x;j++) { 
if((d2[i1][j]==d[i2][j])||(d2[i1][j]==3)) 
c1++; if(c1==x) { g[i1][c]=in[i2]; c++; 
} 
} 
} 
} return(a); 
} 

void pimp(int x,int y3,int a) 
{ 
int i1,i2,j1,j2,c,w,j3,c1,c2,j4,c3,c4; 
c=0; for(i1=0;i1<y3;i1++) { for(j1=0;j1<a;j1++) { if(g[i1][j1]!=-2) { for(i2=0;i2<y3;i2++) { if(i2!=i1) { for(j2=0;j2<a;j2++) if(g[i1][j1]!=g[i2][j2]) c++; 
} 
} if(c==a*(y3-1)) d2[i1][x]=91;c=0; 
} 
    } 
  } 
for(i1=0;i1<y3;i1++) { if(d2[i1][x]==91) { for(j1=0;j1<a;j1++) { if(g[i1][j1]!=-2) { for(i2=0;i2<y3;i2++) { if(i1!=i2) { for(j2=0;j2<a;j2++) if(g[i1][j1]==g[i2][j2]) g[i2][j2]=-3; 
} 
} 
} 
} 
} 
} for(i1=0;i1<y3;i1++) { if(d2[i1][x]==91) { for(j1=0;j1<a;j1++) if(g[i1][j1]!=-2)g[i1][j1]=-1; 
} 
} for(i1=0;i1<y3;i1++) { if(d2[i1][x]!=91) { for(j1=0;j1<a;j1++) { if(g[i1][j1]>=0) { for(i2=0;i2<y3;i2++) if(i2!=i1) 
{ for(j2=0;j2<a;j2++) { if(g[i2][j2]>=0) { if(g[i1][j1]==g[i2][j2]) 
{ w=i2; 
if((d2[w][x]==90)||(d2[w][x]==8)) 
{ for(j3=0,c1=0;j3<x;j3++) if(d2[i1][j3]==3) c1++; for(j3=0,c2=0;j3<x;j3++) if(d2[i2][j3]==3) c2++; if(c1>c2) { d2[i1][x]=90; g[i2][j2]=-1; } if(c2>c1) { d2[i1][x]=8; d2[i2][x]=90; g[i1][j1]=-1; 
} if(c2==c1) { 
for(j3=0,c3=0,c4=0;j3<a;j3++) 
{ if(g[i1][j3]==- 1)c3++; if(g[i2][j3]==-1)c4++; 
} if(c3>c4) { d2[i2][x]=90;d1[i1][x]=8; g[i1][j1]=-1; 
} if(c3==c4) { d2[i1][x]=90; g[i2][j2]=-1; 
} if(c3<c4) { d2[i1][x]=90; g[i2][j2]=-1; 
} 
  } 
} 
if(d2[w][x]==91) d1[w][x]=8; 
} 
} 
} 
} 
} 
} 
} 
} return; 
} 

void decode(int x,int y3) 
{ 
int i,j; 
for(i=0;i<y3;i++) 
{ 
if((d2[i][x]==91)||(d2[i][x]==90)) 
{ 
for(j=x-1;j>=0;j--) 
{ 
if(d2[i][j]==0)printf("a[%d]'",j); if(d2[i][j]==1)printf("a[%d]",j); 
} 
} printf("\n\n"); 
} return; 
}

Use CNTL-T will also clean up the indenting and make this more readable.

shouldn’t the code be in void setup,since we need it to run only once?

about the libraries you mentioned what should i do? :blush:

Libraries:
Delete them all, add back in one at a time and see which are really being used, then hunt those down.
You can put the stiff in loop() into setup() if you only want it to run one time.

skopize:

...

{ t1++; t2=k1;
}
} if(t1==1) { for(j2=0;j2<t2;j2++) d2[i2][j2]=d1[i1][j2]; d2[i2][t2]=3; for(j2=t2+1;j2<y;j2++) d2[i2][j2]=d1[i1][j2]; d2[i2]=8; d1[i1]=9; d1[j1]=9; i2++;
}
}

Pretty ugly formatting.
But if you remove all the libraries from the code, it compiles just fine with the Arduino IDE.

So it should be easily possible to adapt the code, which seems to be written

  • for a PC with input from keyboard and output to console screen
  • and adapt to an Arduino with input from Serial and output to Serial

What’s the problem with doing so?

I want to make it portable,by adding buttons or push buttons for inputs and puuting on 16x2 lcd for the output.

Do you think the code can do that?

skopize:
I want to make it portable,by adding buttons or push buttons for inputs and puuting on 16x2 lcd for the output.

Do you think the code can do that?

When looking at the code, the program will require several input numbers:

1st number
"Please give the number of variables you want to minimize - "

2nd number is y
"Please give the number of minterms that you want to minimize - "

input loop for input of y numbers
"Please give decimal indices of minterms one at a time :: "

So after you have made the input by providing a bunch of decimal numbers, the algorithm starts, calculates the results, and prints them to several lines of output.

So to make the program compatible with an Arduino + LCD + a few buttons, you would have to create:

  1. An input routine for "LCD and buttons" that enables the input of edited decimal numbers by pressing buttons (instead of taking numbers from PC keyboard input).

  2. Processing of calculations would need no change

  3. As there will be (most likely) more lines of output than the two lines of your 16x2 LCD, you'd need to provide some kind of "up/down scrolling output" on the LCD, so that you can scroll up and down in the result listing of lines.

For what might that be good for?

In times when everybody got a "smart" phone that could provide input and output on a HTML page with doing the calculations in Javascript if you need a solution you can carry with you in the jacket pocket?

You are going to have some problems with that code.
The staging(), indexing() and duplication() functions use malloc() but do NOT use free() and, even worse, the staging() function is recursive. This all means that with only 2kb of ram on the UNO, the sketch will probably hang when trying to minimize a function of more than about 5 variables. It also means that if you modify the code to allow you to do more than one minimization at a time, you won't be able to do very many without having to restart the sketch, because the free space is continuously used up and not freed and the code will eventually hang.
Adding an LCD display will further reduce the size of problem that you can handle.

Pete

…though you could save a little by using “byte” instead of “int” :slight_smile:
Still difficult.