Quine–McCluskey Implementation - https://repl.it/M2yV/43 #article

quine-mccluskey.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NL printf("\n")
int LOG = 0;


/* math */

int randomInt(int min, int max){
  long ltime = time(NULL);				
  int stime = (unsigned) ltime/2;
  srand(stime);
  int random = (rand() % (max - min)) + min;
  return random;
}
int* shuffleInts(int *arr, int length) {
  for (int i = length-1; i > 0; i--) {
    int j = randomInt(0, i + 1);
    int tmp = arr[j];
    arr[j] = arr[i];
    arr[i] = tmp;
  }
  return arr;
}
int* randomInts(int length) {
  int* arr = (int*) malloc((length-1)*sizeof(int));
  for (int i = 0; i < length; i++) arr[i] = i;
  return shuffleInts(arr, length);
}


int expInt(int b, int e) {
  if (!e) return 1;
  else {
    int r = 1;
    while (e--) r *= b;
    return r;
  }
}

int absInt(int x) {
  if (x < 0) return -1 * x;
  else return x;
}



/* BitString */

int BITSTRINGLENGTH = 4;


typedef enum Bool {
  False, 
  True
} Bool;


typedef enum Bit {
  Zero,
  One,
  Any
} Bit;

void printBit(Bit bit) {
  switch(bit) {
    case Any:   
      printf("-");
      break;
    default:
      printf("%d", bit);
      break;
  }
}

Bit compareBits(Bit a, Bit b) {
  if (a != Any && b!= Any) return a == b;
  if ((a == Any && b != Any) || (b == Any && a != Any)) return Any;
  if (a == Any && b == Any) return One;
  else return a == b;
}


typedef struct BitString {
  Bit* bits;
} BitString;

BitString* createBitString() {
  BitString* string = (BitString*) malloc(sizeof(BitString));
  string->bits = (Bit*) malloc(BITSTRINGLENGTH * sizeof(Bit));
  return string;
}

void printBitString(BitString* string) {
  for (int i = BITSTRINGLENGTH - 1; i >= 0; i--) printBit(string->bits[i]);
}

BitString* minterm2bitstring(int code) {
  BitString* bitString = createBitString();
  for (int i = 0; i < BITSTRINGLENGTH; i++) {
    int rem = code % 2;
    code = code / 2;
    bitString->bits[i] = rem;
  }
  return bitString;
}

Bit compareBitStrings(BitString* a, BitString* b) {
  int diff = 0;
  for (int i = 0; i < BITSTRINGLENGTH; i++) {
    Bit r = compareBits(a->bits[i], b->bits[i]);
    if (r != One) return r;
  }
  return One;
}

Bool areBitStringsGroupable(BitString* a, BitString* b) {
  int diff = 0;
  for (int i = 0; i < BITSTRINGLENGTH; i++) {
    if (compareBits(a->bits[i], b->bits[i]) != One) diff++;
    if (diff > 1) return False;
  }
  return True;
}

BitString* groupBitStrings(BitString* a, BitString* b) {
  BitString* c = createBitString();
  for (int i = 0; i < BITSTRINGLENGTH; i++) {
    c->bits[i] = a->bits[i] == b->bits[i] ? a->bits[i] : Any;
  }  
  return c;
}

Bool isCovered(BitString* imp, BitString* min) {
  for (int i = 0; i < BITSTRINGLENGTH; i++) {
    if (!compareBits(imp->bits[i], min->bits[i])) return False;
  }
  return True;
}

int countOnes(BitString* string) {
  int count = 0;
  for(int i = 0; i < BITSTRINGLENGTH; i++) {
    if (string->bits[i] == One) count++;
  }
  return count;
}


/* BitStringList */

typedef struct BitStringListNode {
  BitString* value;
  struct BitStringListNode* next;
} BitStringListNode;

typedef struct BitStringList {
  BitStringListNode* head;
  int length;
} BitStringList;

BitStringList* createBitStringList() {
  BitStringList* list = (BitStringList*) malloc(sizeof(BitStringList));
  list->head = NULL;
  list->length = 0;
  return list;
}

BitStringList* addToBitStringList (BitStringList* list, BitString* string) {
  BitStringListNode* node = (BitStringListNode*) malloc(sizeof(BitStringListNode));
  node->value = string;
  node->next = list->head;
  list->head = node;
  list->length++;
  return list;
}

Bool hasInBitStringList (BitStringList* list, BitString* string) {
  for (BitStringListNode* i = list->head; i != NULL; i = i->next) {
    if (compareBitStrings(i->value, string) == One) return True;
  }
  return False;
}

void printBitStringList (BitStringList* list) {
  printf("[ ");
  for (BitStringListNode* i = list->head; i != NULL; i = i->next) {
    printBitString(i->value);
    printf(" ");
  }
  printf("]");
}

void freeBitStringList(BitStringList* list) {
  BitStringListNode* next;
  for (BitStringListNode* i = list->head; i != NULL; i = next) {
    next = i->next;
    free(i);
  }
}

BitString* getIthFromBitStringList(BitStringList* list, int i) {
  BitStringListNode* a = list->head;
  while (i > 0 && a != NULL) {
    a = a->next;
    i--;
  }
  return a->value;
}

/* Quine–McCluskey */

BitStringList* findPrimeImplicants(BitStringList* terms) {
  if (LOG) { printf("Finding prime implicatants..."); NL; }
  
  BitStringList* primeImps = createBitStringList();
  
  BitStringList* candidates = terms;
  BitStringList* imps = createBitStringList();
  for (int i = 0; expInt(2, i) <= BITSTRINGLENGTH; i++) {
    
    if (LOG) {
      printf("  Looking for size %d implicants: \n", expInt(2, i+1));
      printf("    Candidates:\n      "); printBitStringList(candidates); 
      NL;
    }
    
    BitStringListNode* a = candidates->head;
    while (a != NULL) {
      
      Bool prime = True;
      
      BitStringListNode* b = candidates->head;
      while (b != NULL) {
        if (a->value != b->value) 
          // if (absInt(countOnes(a->value) - countOnes(b->value)) <= 1) // Makes little difference here.
            if (areBitStringsGroupable(a->value, b->value)) {
              BitString* c = groupBitStrings(a->value, b->value);
              if (LOG) if (!hasInBitStringList(imps, c)){
                printf("    ");
                printBitString(a->value); printf(" + "); 
                printBitString(b->value); printf(" = "); printBitString(c); 
                NL;
              }
              if (!hasInBitStringList(imps, c)) addToBitStringList(imps, c);
              prime = False;
            }
        
        b = b->next;
      }
      
      if (prime) addToBitStringList(primeImps, a->value);
      
      a = a->next;
    }
    
    if (i) freeBitStringList(candidates);
    candidates = imps;
    imps = createBitStringList();
    
  }
  freeBitStringList(imps);
  
  if (LOG) {
    printf("  Prime implicatants found: ");
    printBitStringList(primeImps);
    NL;
    NL; 
  }
  
  return primeImps;
}

BitStringList* findEssentialImplications(BitStringList* minterms, BitStringList* primeImps) {
  if (LOG) { printf("Finding essential prime implicatants..."); NL; }
  
  BitStringList* essentialImps = createBitStringList();
  
  Bool** arr = (Bool**) malloc((primeImps->length)*sizeof(Bool*));
  
  for (int i = 0; i < primeImps->length; i++) {
    arr[i] = (Bool*) malloc((minterms->length)*sizeof(Bool));
  }
  
  BitStringListNode* a = primeImps->head;
  int i = 0;
  while (a != NULL) {
    BitStringListNode* b = minterms->head;
    int j = 0;
    while (b != NULL) {
      arr[i][j] = isCovered(a->value, b->value);
      b = b->next;
      j++;
    }
    a = a->next;
    i++;
  }
  
  /*if (LOG) {
    printf("  Essentiality matrix: "); NL;
    for (int i = 0; i < primeImps->length; i++) {
      for (int j = 0; j < minterms->length; j++) printf("\t%d", arr[i][j]);
      NL; 
    };
  }*/
  
  //FEATURE: Do obvious essentials.
  //FEATURE: Implement Petrick's algorithm instead.
  
  int* order = randomInts(primeImps->length); // Shuffle prime implicants to test.
  for (int i = 0; i < primeImps->length; i++) {
    int r = order[i];
    BitString* x = getIthFromBitStringList(primeImps, r);
    
    if (LOG) { 
      printf("  ");
      printBitString(x); 
      printf(" "); 
    }
    
    Bool essential = False;
    for (int j = 0; j < minterms->length; j++) {
      if (arr[r][j]) {
        essential = True;
        for (int i = 0; i < primeImps->length; i++) {
            arr[i][j] = False;
        }
      }
    }
    if (essential) addToBitStringList(essentialImps, x);

    if (LOG) {
      if (essential) printf("is essential."); 
      else printf("is not essential.");
      NL;
      /*printf("    Essentiality matrix: "); NL;
      for (int i = 0; i < primeImps->length; i++) {
        printf("  ");
        for (int j = 0; j < minterms->length; j++) printf("\t%d", arr[i][j]);
        NL; 
      };*/
    }
  }
  
  if (LOG) {
    printf("  Essential prime implicants found: "); 
    printBitStringList(essentialImps); 
    NL; 
    NL; 
  }
  
  return essentialImps;
}



/* main */

int main() {
  LOG = True; //DEBUG
  
  
  BITSTRINGLENGTH = 4;
  BitString* M[16];
  for (int i = 0; i < 16; i++) M[i] = minterm2bitstring(i);
  
  
  BitStringList* minterms = createBitStringList();
  BitStringList* dontCareTerms = createBitStringList();
  BitStringList* allTerms = createBitStringList();
  int mintermCodes[6] = {4, 8, 10, 11, 12, 15}; 
  for (int i = 0; i < 6; i++) {
    addToBitStringList(minterms, M[mintermCodes[i]]);
    addToBitStringList(allTerms, M[mintermCodes[i]]);
  }
  int dontCareCodes[2] = {9, 14};
  for (int i = 0; i < 2; i++) {
    addToBitStringList(dontCareTerms, M[dontCareCodes[i]]);
    addToBitStringList(allTerms, M[dontCareCodes[i]]);
  }
  
  
  printf("f(a, b, c, d) = SOP of the minterms "); printBitStringList(minterms); NL;
  printf("  w/ don't cares "); printBitStringList(dontCareTerms); NL;
  NL;
  
  BitStringList* primeImps = findPrimeImplicants(allTerms);
  
  // printf("...have the following prime implicants:\n    "); printBitStringList(primeImps); NL; 
  // NL;
  
  BitStringList* essentialImps = findEssentialImplications(minterms, primeImps);
  
  // printf("...have the following quasi-essential prime implicants:\n    "); printBitStringList(essentialImps); NL; 
  // NL;
  
  return 0;
}

quine-mccluskey.stdout

f(a, b, c, d) = SOP of the minterms [ 1111 1100 1011 1010 1000 0100 ]
  w/ don't cares [ 1110 1001 ]

Finding prime implicatants...
  Looking for size 2 implicants: 
    Candidates:
      [ 1110 1001 1111 1100 1011 1010 1000 0100 ]
    1110 + 1111 = 111-
    1110 + 1100 = 11-0
    1110 + 1010 = 1-10
    1001 + 1011 = 10-1
    1001 + 1000 = 100-
    1111 + 1011 = 1-11
    1100 + 1000 = 1-00
    1100 + 0100 = -100
    1011 + 1010 = 101-
    1010 + 1000 = 10-0
  Looking for size 4 implicants: 
    Candidates:
      [ 10-0 101- -100 1-00 1-11 100- 10-1 1-10 11-0 111- ]
    10-0 + 10-1 = 10--
    10-0 + 11-0 = 1--0
    101- + 111- = 1-1-
  Looking for size 8 implicants: 
    Candidates:
      [ 1-1- 1--0 10-- ]
  Prime implicatants found: [ 10-- 1--0 1-1- -100 ]

Finding essential prime implicatants...
  1--0 is essential.
  -100 is essential.
  1-1- is essential.
  10-- is not essential.
  Essential prime implicants found: [ 1-1- -100 1--0 ]