Logic Pro: C program to minimize boolean expressions

C program to minimize boolean expressions using Qc Mccluskey algorithm:

#include <stdio.h>
#include <string.h>
#include <math.h>

void bsort(int *p, int n)
{
 /*Sorts the array in increasing order*/
}

int bsearch(int *p, int n, int sh)
{
 /*Searches sh in the array. If found returns 1 else returns 0 */
}

main()
{
 int nm, nd, i, j, larg=0, nvar, temp, flag, col, a, b, min[100], min1[100][2],
  count[10][10], count1[100], search[100][100][100], count2[20], list[100];
 char temp1[10], nim[100][10];
 struct group
 {
  struct table
  {
   char mint[100];
   char var[10], T;
  } t[20][20];
 } gr[20];
 struct prime
 {
  char mint1[100], var1[10];
  int mint2[20];
 }pi[20];
 printf("\nEnter no. of minterms: ");
 scanf("%d", &nm);
 printf("\nEnter no. of don’t care terms: ");
 scanf("%d", &nd);
 for(i=0; i<nm; i++)
 {
  printf("\nEnter minterm%d: ", (i+1));
  scanf("%s", nim[i]);
  min[i] = atoi(nim[i]);
  if(larg < min[i])
  {
   larg = min[i];
  }
 }
 bsort(min, nm);
 for(i=0; i<nm; i++)
 {
  min1[i][0] = min[i];
  min1[i][1] = 0;
 }
 for(i=0; i<nd; i++)
 {
  printf("\nEnter don’t care term%d: ", i+1);
  scanf("%s", nim[nm+i]);
  min[nm+i] = atoi(nim[nm+i]);
  if(larg < min[nm+i])
  {
   larg = min[nm+i];
  }
 }
 bsort(min, (nm+nd));
 for(i=0; pow(2,i) < larg; i++)
 {
  ;
 }
 nvar = i;
 for(i=0; i<(nvar+1); i++)
 {
  for(j=0; j<(nvar+1); j++)
  {
   count[i][j] = 0;
  }
 }
 /*Initialization of 1st column*/
 for(i=0; i<(nm+nd); i++)
 {
  temp = min[i];
  for(j=0, flag=0; j<nvar; j++)
  {
   if((temp%2) != 0)
   {
    flag++;
   }
   temp = temp/2;
  }
  temp = min[i];
  for(a=0; a<(nm+nd); a++)
  {
   if(temp == atoi(nim[a]))
   {
    break;
   }
  }
  strcpy(gr[flag].t[count[flag][0]][0].mint, nim[a]);
  strcat(gr[flag].t[count[flag][0]][0].mint, " ");
  gr[flag].t[count[flag][0]][0].T = ‘X’;
  for(j=(nvar-1); j>=0; j–)
  {
   if(temp%2 == 0)
   {
    gr[flag].t[count[flag][0]][0].var[j] = ‘0’;
   }
   if(temp%2 == 1)
   {
    gr[flag].t[count[flag][0]][0].var[j] = ‘1’;
   }
   temp = temp/2;
  }
  count[flag][0]++;
 }
 /*Comparison*/
 for(col = 0; col < nvar; col++)
 {
  for(i = 0; i < nvar; i++)
  {
   for(a = 0; a < count[i][col]; a++)
   {
    for(b = 0; b < count[i+1][col]; b++)
    {
     flag = 0;
     for(j = 0; j < nvar; j++)
     {
      if(gr[i].t[a][col].var[j] != gr[i+1].t[b][col].var[j])
      {
       temp = j;
       flag++;
      }
     }
     if(flag == 1)
     {
      gr[i].t[a][col].T = ‘C’;
      gr[i+1].t[b][col].T = ‘C’;
      for(j = 0; j < nvar; j++)
      {
       gr[i].t[count[i][col+1]][col+1].var[j] = gr[i].t[a][col].var[j];
      }
      gr[i].t[count[i][col+1]][col+1].var[temp] = ‘-‘;
      gr[i].t[count[i][col+1]][col+1].T = ‘X’;
      strcpy(gr[i].t[count[i][col+1]][col+1].mint, gr[i].t[a][col].mint);
      strcat(gr[i].t[count[i][col+1]][col+1].mint, gr[i+1].t[b][col].mint);
      count[i][col+1]++;
      larg = col + 1;
     }
    }
   }
  }
 }
 /*Cancelling repeated terms*/
 for(col = 0; col <= larg; col++)
 {
  for(i = 0; i < (nvar + 1); i++)
  {
   if(count[i][col] != 0)
   {
    for(a = 0; a < (count[i][col] – 1); a++)
    {
     for(b = (a+1); b < (count[i][col]);b++)
     {
      if(strcmp(gr[i].t[a][col].var, gr[i].t[b][col].var) == 0)
      {
       gr[i].t[b][col].T = ‘C’;
      }
     }
    }
   }
  }
 }
 /*Selection of Prime Implicants*/
 for(col = 0, temp = 0; col <= larg; col++)
 {
  for(i = 0; i < (nvar + 1); i++)
  {
   if(count[i][col] != 0)
   {
    for(j = 0; j < (count[i][col]); j++)
    {
     if(gr[i].t[j][col].T != ‘C’)
     {
      strcpy(pi[temp].mint1, gr[i].t[j][col].mint);
      strcpy(pi[temp].var1, gr[i].t[j][col].var);
      temp++;
     }
    }
   }
  }
 }
 /*Converting minterms to integers*/
 for(i = 0; i < temp; i++)
 {
  count1[i] = 0;
 }
 for(i = 0; i < temp; i++)
 {
  for(j = 0; j < strlen(pi[i].mint1);)
  {
   for(a = 0; pi[i].mint1[j] != ‘ ‘; a++, j++)
   {
    temp1[a] = pi[i].mint1[j];
   }
   pi[i].mint2[count1[i]] = atoi(temp1);
   strcpy(temp1, " ");
   count1[i]++;
   j++;
  }
 }
 /*Counting*/
 for(i = 0; i < temp; i++)
 {
  for(j = 0; j < count1[i]; j++)
  {
   for(a = 0; a < nm; a++)
   {
    if(pi[i].mint2[j] == min1[a][0])
    {
     min1[a][1]++;
    }
   }
  }
 }
 for(a = 0; a < nm; a++)
 {
  if(min1[a][1] == 1)
  {
   for(i = 0; i < temp; i++)
   {
    for(j = 0; j < count1[i]; j++)
    {
     if(pi[i].mint2[j] == min1[a][0])
     {
      printf("\n");
      printf("%s", pi[i].var1);
      for(b = 0; b < nm; b++)
      {
       for(col = 0; col < count1[i]; col++)
       {
        if(min1[b][0] == pi[i].mint2[col])
        {
         min1[b][1] = 0;
        }
       }
      }
     }
    }
   }
  }
 }
 /*Extracting only minterms*/
 for(i = 0, flag = 0; i < nm; i++)
 {
  if(min1[i][1] != 0)
  {
   min[flag] = min1[i][0];
   flag++;
  }
 }
 /*Initializing search*/
 for(i = 0; i < temp; i++)
 {
  for(j = 0; j < temp; j++)
  {
   for(a = 0; a < count1[j]; a++)
   {
    search[i][j][a] = pi[j].mint2[a];
   }
  }
 }
 for(i = 0; i < temp; i++)
 {
  larg = 1;
  for(j = 0; ; )
  {
label1:
   if(larg == 1)
   {
    count2[j] = 0;
   }
   if(larg == 0)
   {
    count2[j]++;
   }
   for(; count2[j] < temp; count2[j]++)
   {
    if(i != j)
    {
     j++;
     larg = 1;
     goto label1;
    }
    for(j=0, b=0; j <=i; j++)
    {
     for(a = 0; a < count1[count2[j]]; a++)
     {
      list[b] = search[j][count2[j]][a];
      b++;
     }
    }
    for(col = 0, nvar = 0; col < flag; col++)
    {
     nvar = bsearch(list, b, min[col]);
     if(nvar == 0)
     {
      break;
     }
    }
    if(nvar == 1)
    {
     for(j = 0; j <= i; j++)
     {
      printf("\n%s", pi[count2[j]].var1);
     }
     printf("\n\n");
     exit(0);
    }
    j–;
   }
   if(j==0)
   {
    break;
   }
   else
   {
    larg = 0;
    j–;
    goto label1;
   }
  }
 }
 printf("\n\n");
}

void bsort(int *p, int n)
{
 int i, j, flag, t;
 for(i = 1; i < n; i++)
 {
  flag = 0;
  for(j = 0; j < (n-i); j++)
  {
   if(*(p+j) > *(p+j+1))
   {
    t = *(p+j);
    *(p+j) = *(p+j+1);
    *(p+j+1) = t;
    flag = 1;
   }
  }
  if(flag == 0)
  {
   return;
  }
 }
}

int bsearch(int *p, int n, int sh)
{
 int k;
 for(k = 0; k < n; k++)
 {
  if(sh == *(p+k))
  {
   return(1);
  }
 }
 return(0);
}

Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s