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.


 

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

74098. Ыбырай Алтынсарин 24.63 KB
  Ыбырай 1841 жылы қазан айының 20сында қазіргі Қостанай облысы Қостанай ауданында дүниеге келеді. Сөйтіп немересі кішкентай Ыбырайды Орынборда ашылады деп күтілген орысқазақ мектебіне күні бұрын жаздырып қояды. Атаң мұнда анаңмен есенаман Сүйіп сәлем жазады бүгін саған.
74099. Скиф-сақ әлеміндегі қоғамдық ұйымдар 24.17 KB
  I мыңжылдықтың басы сақ қоғамындағы алғашқы рулық қатынастар ыдырап жаңа әлеуметтік құрылымның қалыптасу үрдісінің жедел жүруімен сипатгалады. Сол кездің өзіндеақ алғашқы ірі қоғамдық еңбек бөлінісінен мыс пен қола металлургиясының тууы мен дамуынан кейін алғашында үлкен патриархаттық ал одан кейін шағын және моногамиялы отбасылар окшаулана бастады. Археологиялық деректер жеке адамдық ал кейін барып отбасылық меншіктің шыққанын айқын көрсетеді. II мыңжылдыктың аяғында және I мыңжылдыктың басында қыш ыдыстар мен кейбір қола заттарға...
74100. Қаңлы мемлекеті 22.17 KB
  II ғасырдың екінші жартысында ЧжанЦянь Қаңлы жерлерінің оңтүстігінде юечжиге ал солтүстігінде ғұндарға тәуелді екенін айтса біздің заманымыздағы I ғасырда мұндағы жағдай өзгереді. Егер Чжан Цянь юечжи әскерін 100200 мың ал қаңлы әскерін 90 мың деп хабарлаған болса ЦаньХаньШу енді қаңлы әскерін 120 мың юечжи әскерін 100 мың дейді14. Бұл кезенде Орта Азиядағы қос өзен аралығында юечжилердің негізгі бөлігінің оңтүстікке сол жағалаудағы Бактрияға ығысуы жерге отырықшылық орын алып жекежеке бес иелікке бөлінгенін мұның өзі қаңлымен...
74101. Қазан Хандығы 21.84 KB
  Қазанға орнығып бұл хандықтың дербес болуына негіз салды. Қазан Хандығы тұрғындарының негізгі кәсібі егіншілік болды; оған қосымша мал шаруашылығы баубақша жабайы араның балын жинау аңшылық балықшылық кәсіптерімен айналысты. Қазан Хандығында жоғары өкімет билігі ханның қолында болды бірақ оған ірі ақсүйектер кеңесі диуан бағыт сілтеп бақылау жүргізіп отырды.
74102. Қазақстан жеріндегі әскери қозғалыстар мен соғысқа кіруі 21.52 KB
  Қазақстан азамат соғысы жылдарында 19181920 жж. Ленин қол қойған халық комитетінің декреті бойынша қырғыз қазақ революциялық комитеті қүрылды. Оның қарамағына Қазақ Совет автономиясы жарияланып өлке Советтерінщ құрылтай съезі шақырылғанға дейін қазақ тұрғындары мекендеген Орал ТорғайАқмола Семей облысы мен Астрахань губерниясы жерівдегі барлық жоғарғы әскериазаматтық басқармалар берілді.
74103. Көтерілістің шығу себептері 21.34 KB
  Қатардағы қарапайым қазақтар жерді солардан жалға алып пайдаланды. Қазақ ақсүйектері орыс помещиктерінен жалға алған жерлерді өздерінің жеке қалауы бойынша қазақ ауылдарынакөтеріңкі қымбат бағаға тағы да қайыра жалға беріп отырды. Сөйтіп қазақтардан әр түрлі айыппұлдар мен алымсалықты еселеп алып тұрды 1836 жылы халық көтерілісі басталды.
74104. соты және олардың қазақ қоғамы өміріндегі атқарған рөлі 21.14 KB
  XIX ғасырдың 20жылдарынан бастап патша үБилер билер соты және олардың қазақ қоғамы өміріндегі атқарған рөлі[өңдеу] Ресей Қазақстан аумағына азаматтық және әскери сот жүйесін енгізгенге дейін мұнда дәстүрлі билер соты болатын. Қазақ қоғамында билер ешқашан сайланып та тағайындалып та қойылмаған. Ондай билердің атақдаңқы жөніндегі хабар дала тұрғындары арасына тез таралатын.