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.


 

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

73829. Комплексные числа 388 KB
  Определение комплексного числа. Первая компонента комплексного числа действительное число называется действительной частью числа это обозначается так; вторая компонента действительное число называется мнимой частью числа. Два комплексных числа и равны тогда и только тогда когда равны их действительные и мнимые части.
73830. Многочлены -ой степени 536.5 KB
  Многочленом ой степени называется функция где постоянные комплексные числа коэффициенты многочлена комплексная переменная. Число в котором многочлен принимает нулевое значение называется корнем многочлена. Представим в виде многочлена по степеням. Очевидно отсюда следует утверждение: для того чтобы число было корнем многочлена необходимо и достаточно чтобы коэффициент при нулевой степени в разложении по степеням был равен нулю: .
73831. Линейные пространства 451.5 KB
  Обозначим множества векторов направленных отрезков на прямой на плоскости в пространстве соответственно с обычными операциями сложения векторов и умножения векторов на число. Вместо свободных векторов можно рассмотреть соответствующие множества радиус-векторов. Например множество векторов на плоскости имеющих общее начало т. Множество радиус-векторов единичной длины не образует линейное пространство так как для любого из этих векторов сумма не принадлежит рассматриваемому множеству.
73832. Проектирование операционных технологических процессов обработки заготовок 67.5 KB
  обработки позволяет правильно выбрать станок из имеющегося парка или по каталогу. По типу обработки устанавливают группу станков: токарный сверлильный В соответствии с назначением станка его компоновкой степенью автоматизации определяют тип станка: токарный одношпиндельный многошпиндельный револьверный полуавтомат и т. Если эти требования выполнимы на различных станках то при выборе учитывают следующие факторы: 1 соответствие основных размеров станка габаритным размерам обрабатываемой заготовки или нескольких одновременно...
73833. Анализ технологичности конструкции деталей 43 KB
  Ее следует отрабатывать на технологичность комплексно учитывая зависимость технологичности от следующих факторов: исходной заготовки вида обработки технологичности СЕ в которую эта деталь входит. Конструкция должна быть такой чтобы для ее изготовления можно было применять высокопроизводительные методы обработки. Повышение технологичности конструкции изделия предусматривает проведение следующих мероприятий: Создание конфигурации деталей и подбор их материалов позволяющих применение наиболее совершенных исходных заготовок сокращающих объем...
73834. Выбор вариантов схем базирования 40.5 KB
  Для создания возможности повышения уровня концентрации обработки в операции и снижения разнообразия технологической оснастки лучше принять в качестве базы для обработки всех поверхностей детали одну и туже базу – Е. Синтез маршрута обработки заготовки Первый шаг синтеза маршрута обработки заготовки – распределение отобранных переходов обработки типовых поверхностей заготовки по этапам типовой схемы изготовления деталей соответствующего класса или подкласса. Типовая схема обработки является вариантом полного типового решения. Причиной...
73835. Проектирование маршрутных технологических процессов механической обработки 52 KB
  Маршрутное описание ТП заключается в сокращенном описании всех технологических операций в маршрутной карте в последовательности их выполнения без переходов и технологических режимов. Операционное описание ТП характеризуется полным описанием всех технологических операций в последовательности их выполнения с указанием переходов и технологических режимов. Маршрутнооперационным описанием ТП называют сокращенное описание технологических операций в маршрутной карте в последовательности их выполнения с полным описанием отдельных операций в других...
73836. Особенности проектирования технологических процессов обработки заготовок на автоматизированных участках и автоматических линиях 51.5 KB
  В необходимых случаях подготовку технологических баз при обработке на автоматической линии или при установке заготовки в приспособлениеспутник производят на отдельных операциях вне автоматической линии; маршрутный технологический процесс разрабатывают с учетом максимальной концентрации операций соблюдения принципа единства баз выполнения чистовых и отделочных операций в конце технологического процесса; при проектировании автоматических операций анализируют возможность совмещения технологических и вспомогательных переходов во времени. Для...
73837. Особенности проектирования технологических процессов для станков с ЧПУ и ГПС 58 KB
  Особенности проектирования технологических процессов для станков с ЧПУ и ГПС При проектировании технологических операций для станков с ЧПУ необходимо учитывать ряд особенностей обработки. Порядок обработки поверхностей заготовок для деталей типа валов следующий. Черновая и чистовая обработка дополнительных форм поверхности если имеются дополнительные формы требующие черновой обработки. Обработка дополнительных форм поверхности не требующих черновой обработки.