6826

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

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

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

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

Русский

2013-01-08

181 KB

29 чел.

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

Номер зачётной книжки: 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.


 

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

24663. Організація і методика аналізу фінансового стану підприємства в ринкових умовах 29 KB
  Відносні показники фінансового стану розподіляються на коефіцієнти розподілення і координації. Коефіцієнт розподілення відображають яку частину той чи інший абсолютний показник становить від підсумкового показника складовою частиною якого є цей показник.аналіз рентабельності Аналіз рентабельності підприємства здійснюється шляхом розрахунку таких показників коефіцієнтів: коефіцієнт рентабельності активів коефіцієнт рентабельності власного капіталу коефіцієнт рентабельності діяльності та коефіцієнт рентабельності продукції.
24664. Аналіз динаміки, складу та структури майна підприємства 25 KB
  В процесі аналізу активу і пасиву балансу визначають показники структури динаміки балансу структурної динаміки балансу. Для загальної оцінки динаміки фінансового стану підприємства необхідно виконати групування статей балансу по окремих групах за відзнакою ліквідності за ознакою активу та пасиву і зобовязання. Використовуючи горизонтальний і вертикальний аналіз здійснення аналізу активу та пасиву балансу за групами.
24665. Аналіз структури джерел коштів підприємства 30.5 KB
  Аналіз структури джерел коштів підприємства. Як ми уже говорили раніше внутрішній аналіз структури джерел коштів підприємства пов'язаний з оцінкою альтернативних варіантів фінансування діяльності підприємства.До числа основних показників які характеризують структуру джерел коштів належить коефіцієнт фінансової незалежності автономії КАВТ як відношення загальної суми джерел власних коштів до підсумку балансу. Цей коефіцієнт є важливим і для інвесторів і для кредиторів тому що характеризує частку коштів вкладених власником у загальну...
24666. Аналіз дебіторсько-кредиторської заборгованості 37 KB
  Аналіз дебіторськокредиторської заборгованості. Значення аналізу дебіторської заборгованості особливо зростає в період інфляції коли іммобілізація власних оборотних активів стає дуже невигідною.У найзагальнішому вигляді зміни в обсязі дебіторської та кредиторської заборгованості за звітний період можуть бути охарактеризовані даними горизонтального та вертикального аналізу балансу. Особливу увагу в процесі аналізу дебіторської заборгованості приділяють статті Дебіторська заборгованість за товари роботи послуги яка має найбільшу питому вагу...
24667. Бюджетування є інструментом поточного планування підприємства 28.5 KB
  14 Бюджетування є інструментом поточного планування підприємства. Бюджетування процес планування майбутньої діяльності підприємства і оформлення його результатів у вигляді системи бюджетів. Забезпечення координації і кооперації підрозділів підприємства. Обґрунтування витрат підрозділів і підприємства в цілому.
24668. Виробнича собівартість 33.5 KB
  Напівпостійні залишаються постійними до визначених меж росту обсягу продукції.Собівартість продукції з погляду економічної теорії це сума всіх витрат повязаних з виробництвом та збутом продукції. Повна собівартість реалізованої продукції може бути розрахована за Звітом про фінансові результати. Виробничі підприємства складають калькуляцію виробничої собівартості продукції додаток до методичних рекомендацій №47 галузеві методичні вказівки.
24669. Основні методи обліку витрат і калькулювання собівартості продукції 39 KB
  Позамовний метод калькулювання широко використовується в зарубіжній практиці. Принципові особливості позамовного позамовного методу калькулювання полягають у наступному: в індивідуалізації обліку витрат і розрахунку собівартості на конкретне замовлення усі прямі витрати групуються в аналітичному обліку в суворій відповідності з відкритими замовленнями; калькуляція отриманої продукції складається після повного завершення робіт із замовлення незалежно від тривалості його виконання. Можна назвати принаймні два напрями модифікації позамовного...
24670. Робочий час менеджера 27 KB
  Ці рішення можуть стосуватися як довгострокових перспектив розвитку підприємства так і поточних проблем що виникають у процесі господарської діяльності. Довгострокові або стратегічні рішення пов'язані з майбутніми можливостями які прогнозуються і які потребують конкретних кроків сьогодні або найближчим часом. Поряд зі стратегічними рішеннями менеджери приймають рішення пов'язані з використанням ресурсів у процесі поточної діяльності. Такі рішення називають короткостроковими або ; операційними.
24671. Організація обліку витрат за економічними елементами 24.5 KB
  На основі переліку калькуляційних статей які встановлюються підприємством самостійно виходячи з особливостей технології та організації виробництва складаються форми калькуляційних розрахунків кошторисів та внутрішньої звітності.