Publication detail

The Improvement of Quine-McCluskey Method Using Set Covering Problem for Safety Systems

ŠEDA, P. ŠEDA, M. HOŠEK, J. DVOŘÁK, J. ŠEDOVÁ, J.

Original Title

The Improvement of Quine-McCluskey Method Using Set Covering Problem for Safety Systems

English Title

The Improvement of Quine-McCluskey Method Using Set Covering Problem for Safety Systems

Type

conference paper

Language

en

Original Abstract

When designing complex safety systems which consist of large scale logical circuits, the basic requirement is to minimise the number of elements that will implement the given logical functions. This will increase the reliability, and thus potentially the security of the devices. For logical functions with a number of variables of no more than 4, Karnaugh maps are preferred. However, in practice, we encounter much more complex functions, either directly applying Boolean algebra laws or using the Quine-McCluskey method, which is based on their systematic use. However, because this method does not provide a minimal form of logical function, and as a result, there may be redundant expressions, we will show that the additional phase of minimisation means solving the problem of covering all inputs by the obtained output expressions. For the purpose of clear representation and implementation process of post-processing method, the genetic algorithms and simulated annealing were implemented on OR-Library benchmarks.

English abstract

When designing complex safety systems which consist of large scale logical circuits, the basic requirement is to minimise the number of elements that will implement the given logical functions. This will increase the reliability, and thus potentially the security of the devices. For logical functions with a number of variables of no more than 4, Karnaugh maps are preferred. However, in practice, we encounter much more complex functions, either directly applying Boolean algebra laws or using the Quine-McCluskey method, which is based on their systematic use. However, because this method does not provide a minimal form of logical function, and as a result, there may be redundant expressions, we will show that the additional phase of minimisation means solving the problem of covering all inputs by the obtained output expressions. For the purpose of clear representation and implementation process of post-processing method, the genetic algorithms and simulated annealing were implemented on OR-Library benchmarks.

Keywords

logic circuits, minimisation, set covering problem, simulated annealing

Released

09.09.2019

Location

Yichang, China

ISBN

9781467361217

Book

The 4rd International Conference on Intelligent Green Building and Smart Grid (IGBSG 2019)

Pages from

244

Pages to

248

Pages count

5

BibTex


@inproceedings{BUT157806,
  author="Pavel {Šeda} and Miloš {Šeda} and Jiří {Hošek} and Jan {Dvořák} and Jindřiška {Šedová}",
  title="The Improvement of Quine-McCluskey Method Using Set Covering Problem for Safety Systems",
  annote="When designing complex safety systems which consist of large scale logical circuits, the basic requirement is to minimise the number of elements that will implement the given logical functions. This will increase the reliability, and thus potentially the security of the devices. For logical functions with a number of variables of no more than 4, Karnaugh maps are preferred. However, in practice, we encounter much more complex functions, either directly applying Boolean algebra laws or using the Quine-McCluskey method, which is based on their systematic use. However, because this method does not provide a minimal form of logical function, and as a result, there may be redundant expressions, we will show that the additional phase of minimisation means solving the problem of covering all inputs by the obtained output expressions. For the purpose of clear representation and implementation process of post-processing method, the genetic algorithms and simulated annealing were implemented on OR-Library benchmarks.
",
  booktitle="The 4rd International Conference on Intelligent Green Building and Smart Grid (IGBSG 2019)",
  chapter="157806",
  doi="10.1109/IGBSG.2019.8886174",
  howpublished="online",
  year="2019",
  month="september",
  pages="244--248",
  type="conference paper"
}