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.


 

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

47279. Структура тормозного управления автомобиля и требования, предъявляемые к нему 446.74 KB
  Каждая из этих систем включает в себя тормозные механизмы обеспечивающие создание сопротивления движению автомобиля и тормозной привод необходимый для управления тормозными механизмами. К тормозной системе автомобиля предъявляются высокие требования. Стояночная тормозная система выполняет также функцию аварийной тормозной системы в случае выхода из строя рабочей тормозной системы. Каждая тормозная система состоит из тормозных механизмов которые обеспечивают затормаживание колес или вал трансмиссий и тормозного привода приводящего в...
47280. Разработка сети электроснабжения нового района города и коттеджного поселка 5.19 MB
  Построение вариантов схемы сети 380 В города и коттеджного поселка. Техникоэкономическое сравнение и выбор оптимального варианта схемы городской сети 380 В. Построение конкурентно способных вариантов схемы сети 10 кВ с учетом коттеджного поселка и выбор электрооборудования.
47282. Классификация и общая характеристика учреждений, предоставляющих социальные услуги 235 KB
  Предоставление социальных услуг без обеспечения проживания это предоставление услуг социального характера консультаций материальной помощи помощи беженцам и аналогичных услуг отдельным лицам и семьям на дому или в других местах. К учреждениям оказывающим социальные услуги без обеспечения проживания относятся комплексные центры социального обслуживания центры социального обслуживания семьи и детей центры социального обслуживания лиц без определенного места жительства и т. В центрах социального обслуживания населения и в отделах...
47283. Управление дебиторской задолженностью открытого акционерного общества «Коммунальные системы БАМа» 680.5 KB
  Сущность дебиторской задолженности Факторы влияющие на уровень дебиторской задолженности. Пути снижения дебиторской задолженности. Управление дебиторской задолженностью на примере ОАО Коммунальные Системы БАМа. Анализ дебиторской задолженности предприятия в целом.
47284. Цех подготовки фабрики газетной бумаги в г. Шклове 2.47 MB
  Определение крановых нагрузок В данном дипломном проекте выполнен расчет одной подкрановой балки расположенной по оси 1 расчётной рамы разрез 11 в пролете 14 которая идентична подкрановой балке по оси 4. Вариант 1 2 крана Используя правило Винклера устанавливаем два груза на балке и находим положение равнодействующей R относительно опоры А: мм Расстояние от критического груза до равнодействующей: С = 24 3 = 06 м По теореме Винклера устанавливаем колёса крана на балке таким образом чтобы расстояние от левой опоры до...