Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

Информатика, программирование->Курсовая работа
База данных создается для информационного обслуживания администрации, рабочего персонала и клиентов. БД должна содержать списки всех менеджеров, их кл...полностью>>
Информатика, программирование->Лабораторная работа
Задание Составить систему меню обеспечивающую ввод и редактирование базы данных с применением форм, разработанных в работах № 5 и № , вывод управленче...полностью>>
Информатика, программирование->Курсовая работа
В данной курсовой работе рассматривается проблема отсутствия свободных мест на нужный сеанс во время прихода в кинотеатр. Следствием чего является впу...полностью>>
Информатика, программирование->Курсовая работа
Разработанная программа имеет название kurs11 и представляет собой файл kurs11.exe, занимающий на диске 84Кб. Данная программа реализует режимы учета ...полностью>>

Главная > Лабораторная работа >Информатика, программирование

Сохрани ссылку в одной из сетей:

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

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

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

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

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

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

import java.util.ArrayList;

public class Function {

private String funcName;

private ArrayList function;

private ArrayList argumentNames;

private ArrayList additionalConsts;

public Function(String fName, ArrayList argNames,

ArrayList func, ArrayList addConsts){

funcName = fName;

function = func;

argumentNames = argNames;

additionalConsts = addConsts;

}

public void prepare(){

prepareForMin(function);

prepareForMin(additionalConsts);

}

private void prepareForMin(ArrayList constList){

boolean xFined = false;

ArrayList impToRemove = new ArrayList();

ArrayList impToAdd = new ArrayList();

for(String impl: constList){

for(int i = 0; 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

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 minImps;

public Minimizator(){

minImps = new ArrayList();

}

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

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 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

numOfEntering+=mas[i];

}

return numOfEntering;

}

//return pointer on the entering implicant

private int getNumOfEntering(int[] mas){

for(int i =0; 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

if(mas[i]==0){

return false;

}

}

return true;

}

public ArrayList minimize(ArrayList constits,ArrayList notConsts ){

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

ArrayList zeroResult = new ArrayList();

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[i][j] = ifCover(constits.get(i),minImps.get(j));

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

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

}

}

}

ArrayList minimalForm = new ArrayList();

for(int i = 0; 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

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

return 0;

}

}

return 1;

}

public void createMinImps(ArrayList implicants, ArrayList xImplicants){

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

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

ArrayList > impTable= new ArrayList >();

ArrayList newImps= new ArrayList();

for(int i = 0;i

impTable.add(new ArrayList());

}

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

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.


Загрузить файл

Похожие страницы:

  1. Основы логических методов построения устройств противоаварийной автоматики подстанций с электродвигателями

    Книга >> Промышленность, производство
    ... учебной литературе по курсу автоматизации электроэнергетических систем и ... включающий комбинационные функции, временные булевы функции и последовательностные логические функции, для ... выбор совокупности признаков (минимизация признакового пространства) и ...
  2. Экономико-математическая модель оптимизации распределения трудовых ресурсов

    Дипломная работа >> Экономико-математическое моделирование
    ... методов решения задач минимизации (максимизации) линейных функций при линейных ... универсальных алгоритмических языков и средств автоматизации программирования. Как известно, ... собой задачу нелинейного булевого программирования у которой функцией цели является ...
  3. Разработка эффективных систем защиты информации в автоматизированных системах

    Дипломная работа >> Информатика
    ... и комплекса средств автоматизации его деятельности, реализующую информационную технологию выполнения установленных функций. В зависимости ... полном охвате контролем. Учитывая необходимость минимизации выражения полных потерь, целесообразность использования ...
  4. Развитие систем автоматизированного проектирования

    Реферат >> Информатика
    ... прочности конструкции путем минимизации потенциальной энергии. ... отдельными поверхностями, используя булевы и поверхностные процедуры. ... IGES. В области автоматизации проектирования унификация основных ... изображения в функциях виртуального графического ...
  5. Модуль накопления для задач многомерной мессбауэровской спектрометрии

    Дипломная работа >> Физика
    ... 128 байт; булевый процессор; два ... функции. Число дизъюнкторов равно числу вырабатываемых функций N. Воспроизводимые функции ... и относительная простота автоматизации любых преобразований, ... соединений, логическая минимизация проекта, формирование загрузочного ...

Хочу больше похожих работ...

Generated in 0.0018348693847656