6826

Автоматизация минимизации булевых функций

Лабораторная работа

Информатика, кибернетика и программирование

Автоматизация минимизации булевых функций Номер зачётной книжки: Основные этапы минимизации методом Квайна-МакКласки: Сначала определяем основные конститутенты, далее подготавливаем к склеиванию термов. Склеиваим все ...

Русский

2013-01-08

181 KB

27 чел.

Автоматизация минимизации булевых функций

Номер зачётной книжки: 831910 =100000011111112;

 

Основные этапы минимизации методом Квайна-МакКласки:

Сначала определяем основные конститутенты, далее подготавливаем к склеиванию термов. Склеиваим все возможные термы между собой. Если склеивание прошло удачно, выполняем повторное склеивание, иначе переходим на следующий этап в котором формируем таблицу покрытия конституент. Далее определяем ядра функции. Покрываем все конституенты ядрами. Если не все конституенты покрыты, поочередно выбираем импликанты которые покрывают непокрытые конституенты, и покрываем их до тех пор, пока все конституенты не будут покрыты.

Скриншот программы:

Листинг программы:

import java.util.ArrayList;

public class Function {

 private String funcName;

 

 private ArrayList<String> function;

 private ArrayList<String> argumentNames;

 private ArrayList<String> additionalConsts;

 

 public Function(String fName, ArrayList<String> argNames,

  ArrayList<String> func, ArrayList<String> addConsts){

 funcName = fName;

 function = func;

 argumentNames = argNames;

 additionalConsts = addConsts;

}

 public void prepare(){

 prepareForMin(function);

 prepareForMin(additionalConsts);

}

 

 private void prepareForMin(ArrayList<String> constList){

 boolean xFined = false;

 ArrayList<String> impToRemove = new ArrayList<String>();

 ArrayList<String> impToAdd = new ArrayList<String>();

 for(String impl: constList){

  for(int i = 0; i<impl.length(); i++) {

   if(impl.charAt(i)=='X'){

    impToAdd.add(impl.replaceFirst("X", "0"));

    impToAdd.add(impl.replaceFirst("X", "1"));

    impToRemove.add(impl);

    xFined = true;    }

  }

 }

 for(String impl:impToRemove){

  constList.remove(impl);

 }

 for(String impl:impToAdd){

  constList.add(impl);

 }

 if(xFined){

  prepareForMin(constList);

 }

}

 

 public void minimize(){

 Minimizator min = new Minimizator();

 function = min.minimize(function, additionalConsts);

}

// public String toStringKvain(){

//  String func = funcName+" = ";

//  for(String impl:function) {

//   String strImplicant = "(";

//   strImplicant += impl;

//   strImplicant += ")U";

//   func+=strImplicant;

//  }

//  return func.substring(0, func.length()-1);

// }

 

 public String toString(){

 String func = funcName+" = ";

 if(function.get(0).charAt(0)=='!'){

  return func+function.get(0).charAt(1);  }

 

 for(String impl:function) {

  String strImplicant = " (";

  for(int i = 0; i<impl.length(); i++) {

   if(impl.charAt(i)=='0'){

    strImplicant+="Not"+argumentNames.get(i)+" ";

    continue;

   }

   if(impl.charAt(i)=='1'){

    strImplicant+=argumentNames.get(i)+" ";

    continue;

   }

  }

  strImplicant += ") v";

  func+=strImplicant;

 }

 return func.substring(0, func.length()-1);

 }

}

import java.util.ArrayList;

public class Minimizator {

 

 private ArrayList<String> minImps;

 

 public Minimizator(){

 minImps = new ArrayList<String>();

}

 

 private String createImplicant(String s1, String s2) {//поглощение

 String implicant = "";

 for (int i = 0; i < s1.length(); i++) {

  if (s1.charAt(i) != s2.charAt(i)) {

   implicant += 'X';

  } else {

   implicant += s1.charAt(i);

  }

 }

 return implicant;

}

 

 private int differentBits(String s1, String s2) {

 int count = 0;

 for (int i = 0; i < s1.length(); i++) {  

  if (s1.charAt(i) != s2.charAt(i)) {

   count++;

  }

 }

 return count;

}

 

 private int getNumOf1(String s) {

 int k = 0;

 for (int i = 0; i < s.length(); i++)

  if (s.charAt(i) == '1') k++;

 return k;

}

 

 

 private int getMinimizationPhase(String s){

 int k = s.length();

 for(int i = 0; i<s.length();i++) {

  if(s.charAt(i)=='X'){

   k--;

  }

 }

 return k;

}

 private boolean impExists(String s){

 for(String imp:minImps){

  if(imp.equals(s)) return true;

 }

 return false;

}

 

 //checking if implicant exists in current list of implicants

 private boolean impExists(ArrayList<String> imps, String s){

 for(String imp:imps){

  if(imp.equals(s)) return true;

 }

 return false;

}

 

 //return number of entering into this constituant with all minimal implicants

 private int countEntering(int[] mas){

 int numOfEntering = 0;

 for(int i =0; i<mas.length; i++){

  numOfEntering+=mas[i];

 }

 return numOfEntering;

}

 

 //return pointer on the entering implicant

 private int getNumOfEntering(int[] mas){

 for(int i =0; i<mas.length; i++){

  if(mas[i]==1){

   return i;

  }

 }

 

 return 0;

}

 //checking if all constituant are covered

 private boolean allCovered(int[] mas){

 for(int i = 0; i<mas.length; i++) {

  if(mas[i]==0){

   return false;

  }

 }

 return true;

}

 

 

 public ArrayList<String> minimize(ArrayList<String> constits,ArrayList<String> notConsts ){

 if(constits.size()==0){

  ArrayList<String> zeroResult = new ArrayList<String>();

  zeroResult.add("!0");

  return zeroResult;

 }

 createMinImps(constits, notConsts);

 int[] coveredConst = new int[constits.size()];

 int[][] coveringTable = new int[constits.size()][minImps.size()];

 for(int i =0; i< coveringTable.length;i++){

  coveredConst[i] = 0;

  for(int j = 0; j<coveringTable[0].length;j++){

   coveringTable[i][j] = ifCover(constits.get(i),minImps.get(j));

   if(coveringTable[i][j]==1){

    //System.out.println(constits.get(i)+"  ->"+minImps.get(j));

   }

  }

 }

 

 ArrayList<String> minimalForm = new ArrayList<String>();

 

 for(int i = 0; i<coveringTable.length;i++){

  if(countEntering(coveringTable[i])==1){

   int pCoreImp = getNumOfEntering(coveringTable[i]);

   String coreImp =minImps.get(pCoreImp);

   if(impExists(minimalForm, coreImp)){

    continue;

   }

   minimalForm.add(coreImp);

   for(int j = 0; j < constits.size();j++) {

    if(coveringTable[j][pCoreImp]==1){

     coveredConst[j] = 1;

    }

   }

   

  }

 }

 //проверить все ли покрыты, и покрывать пока не покроет все

 while(!allCovered(coveredConst)){

  for(int i = 0; i< constits.size();i++){

   if(coveredConst[i]==0){

    int addImp =-1;

    for(int j = 0; j < coveringTable[0].length;j++){

     if(coveringTable[i][j]==1){

      coveredConst[i] = 1;

      minimalForm.add(minImps.get(j));

      addImp = j;

      break;

     }

    }

    for(int j = 0; j < coveringTable.length;j++){

     if(coveringTable[j][addImp]==1){

      coveredConst[j] = 1;

     }

    }

    break;

   }

  }

 }

 for(String s:minimalForm){

  //System.out.println(s);

 }

 return minimalForm;

}

 

 public int ifCover(String constit, String implic){

 for(int i = 0; i<constit.length();i++) {

  if((constit.charAt(i)!=implic.charAt(i))&&(implic.charAt(i)!='X')){

   return 0;

  }

 }

 return 1;

}

 

 

 public void createMinImps(ArrayList<String> implicants, ArrayList<String> xImplicants){

 

 

 int size = implicants.get(0).length();

 int numOfBits = getMinimizationPhase(implicants.get(0));

 

 ArrayList<ArrayList<String>> impTable= new ArrayList<ArrayList<String>>();

 ArrayList<String> newImps= new ArrayList<String>();

 for(int i = 0;i <numOfBits+1;i++){

  impTable.add(new ArrayList<String>());

 }

 for(String imp:implicants){

  int numOf1= getNumOf1(imp);

  impTable.get(numOf1).add(imp);

  if(numOfBits==size)

   minImps.add(imp);

 }

 if(xImplicants!=null){

  for(String imp:xImplicants){

   int numOf1= getNumOf1(imp);

   impTable.get(numOf1).add(imp);

  }

 }

 

 for(int i = 0;i<impTable.size()-1;i++){

  for(String imp1:impTable.get(i)){

   for(String imp2:impTable.get(i+1)){

    if(differentBits(imp1,imp2)==1){

     String newImp =createImplicant(imp1,imp2);

     minImps.remove(imp1);

     minImps.remove(imp2);

     if(!impExists(newImp)){

      minImps.add(newImp);

      newImps.add(newImp);

     }

    }

   }

  }

 }

 if(newImps.size()!=0){

  createMinImps(newImps, null);

 }

}

}

Выводы

В результате выполнения данной лабораторной работы я приобрёл навыки автоматизации процедуры минимизации булевых функций методом Квайна-МакКласки. Мной были реализованы процедуры построения функций переходов и функций возбуждения тригеров, минимизации этих функций. Все процедуры были реализованы на языке программирования Java.


 

А также другие работы, которые могут Вас заинтересовать

65534. МАЛЕ ПІДПРИЄМНИЦТВО В СИСТЕМІ РЕГІОНАЛЬНОГО РОЗВИТКУ 322 KB
  Хоч протягом усього пeрiоду ринкових рeформ в eкономiчнiй лiтeртурi бгто увги придiлялося проблeмм розвитку в Укрїнi млого бiзнeсу лe його стн всe щe злишється нeздовiльним. Проблeм полягє нвiть нe в кiлькiсних прмeтрх функцiонувння цiєї сфeри якi поступово полiпшуються нсмпeрeд у структурi вiтчизняного...
65535. Інформаційна технологія синтезу моделей систем управління автоматизованими процесами 1.05 MB
  При створенні нових інформаційних технологій ІТ сучасні компютери та різні спеціалізовані математичні моделі слугують фундаментом побудови нових методів перетворення інформації для складних систем управління ССУ.
65536. РЕФРАКЦІЙНА КЕРАТОПЛАСТИКА АМЕТРОПІЙ (ВДОСКОНАЛЕННЯ ТЕХНОЛОГІЇ, ПРОГНОЗУВАННЯ РЕЗУЛЬТАТІВ, ПОПЕРЕДЖЕННЯ РОЗВИТКУ УСКЛАДНЕНЬ) 389.5 KB
  Тенденції світової офтальмохірургії за останні роки переконливо свідчать про бурхливий розвиток керато-рефракційної хірургії заснованої на моделюванні передньої поверхні рогівки шляхом пошарового її зрізання методом кератомільозу.
65537. АВТОМАТИЧНИЙ КОНТРОЛЬ СТУПЕНЯ ЗДРІБНЕННЯ РУДИ В ТЕХНОЛОГІЧНИХ КОМПЛЕКСАХ ФЛОТАЦІЙНОГО ТА МАГНІТНОГО ЗБАГАЧЕННЯ 272.5 KB
  Завданням автоматизації здрібнення перед флотаційним або магнітним збагаченням є розкриття руд зі змінними фізикомеханічними властивостями тобто здрібнення їх до такої оптимальної крупності при якій частки корисного мінералу дезінтегруються з порожньою породою...
65538. Етіопатогенетичне обґрунтування способу лікування карієсу у дітей молодшого шкільного віку 156 KB
  Карієс зубів обумовлений прогресуючою демінералізацією зубних тканин викликаною кислотоутворюючими автохтонними бактеріями ротової порожнини серед яких найбільший карієсогенний потенціал мають стрептококи.
65539. МІЦНІСТЬ ТА ДЕФОРМАЦІЇ ЗАЛІЗОБЕТОННИХ ЕЛЕМЕНТІВ З ВИСОКОМІЦНОГО БЕТОНУ З УРАХУВАННЯМ ТРИВАЛОСТІ НАВАНТАЖЕННЯ І НЕРІВНОМІРНОГО НАГРІВАННЯ ДО +200 С 5.05 MB
  Для даного часу характерна характерною тенденціэю тенденцією в будівельній галузі є інтенсивний розвиток висотного будівництва з монолітного залізобетону із застосуванням сучасних високоякісних бетонів які мають високі характеристики міцності...
65540. ЕФЕКТИВНІСТЬ ВІДНОВЛЕННЯ СИНУСОВОГО РИТМУ У ХВОРИХ З ТРІПОТІННЯМ ПЕРЕДСЕРДЬ МЕТОДОМ ЧЕРЕЗСТРАВОХІДНОЇ ЕЛЕКТРОКАРДІОСТИМУЛЯЦІЇ 183.5 KB
  Тріпотіння передсердь – одне з найбільш поширених порушень серцевого ритму, яке складає біля 10 % від всіх пароксизмальних надшлуночкових тахіаритмій. Воно є частим ускладненням гострого інфаркту міокарда і хірургічних втручань на відкритому серці.
65541. ПОЛІТИЧНІ ЦЕНТРИ ВПЛИВУ НА ЄВРОПЕЙСЬКОМУ КОНТИНЕНТІ: ВНУТРІШНЬОДЕРЖАВНІ ТА МІЖДЕРЖАВНІ ВИМІРИ 172 KB
  Прискорення глобалізаційних процесів у світі загалом та у Європі зокрема поставили перед сучасною політичною наукою питання актуалізації та перегляду існуючих моделей політики, владних відносин тощо. Головними проблемами в цьому аспекті стали питання гармонізації політики...
65542. РОЗРОБКА ТЕХНОЛОГІЧНИХ ТА ОРГАНІЗАЦІЙНИХ РІШЕНЬ РЕМОНТУ ТА ВІДНОВЛЕННЯ ВОДОПРОВІДНИХ ТРУБОПРОВОДІВ 8.81 MB
  Трубопровідні системи які транспортують воду для будьякого населеного пункту є найдорожчими і найуразливішими частинами інженерної інфраструктури. Як свідчать результати досліджень велика кількість водопровідних трубопроводів країн СНД у тому числі України...