Publication detail

The Optimisation of Large Scale Logical Circuits

ŠEDA, P.

Original Title

The Optimisation of Large Scale Logical Circuits

English Title

The Optimisation of Large Scale Logical Circuits

Type

conference paper

Language

en

Original Abstract

In the phase of designing the logical circuits, it is essential to minimise the number of elements because it leads to the more reliable, more secure, and cheaper solution. For the logical functions with less than 4 variables, the Karnaugh maps are suitable. However, in practice, we encounter usually a much more complex function, in those cases, we could apply Boolean algebra laws directly or use the Quine-McCluskey method, which is based on their systematic use. Unfortunately, this method does not usually provide a minimal form of logical function for really large scale logical functions, and in a result may be redundant expressions. For that reason, we show that we could apply an additional phase which leads to the set covering problem which needs to cover all the inputs by the obtained outputs. Since this problem is NP-hard, it is necessary to use heuristic methods, such as simulated annealing.

English abstract

In the phase of designing the logical circuits, it is essential to minimise the number of elements because it leads to the more reliable, more secure, and cheaper solution. For the logical functions with less than 4 variables, the Karnaugh maps are suitable. However, in practice, we encounter usually a much more complex function, in those cases, we could apply Boolean algebra laws directly or use the Quine-McCluskey method, which is based on their systematic use. Unfortunately, this method does not usually provide a minimal form of logical function for really large scale logical functions, and in a result may be redundant expressions. For that reason, we show that we could apply an additional phase which leads to the set covering problem which needs to cover all the inputs by the obtained outputs. Since this problem is NP-hard, it is necessary to use heuristic methods, such as simulated annealing.

Keywords

logic circuits, minimisation, set covering problem, simulated annealing

Released

25.04.2019

Location

Brno

ISBN

978-80-214-5735-5

Book

Proceedings of the 25th Conference STUDENT EEICT 2019

Edition number

1

Pages from

469

Pages to

473

Pages count

5

URL

Documents

BibTex


@inproceedings{BUT156671,
  author="Pavel {Šeda}",
  title="The Optimisation of Large Scale Logical Circuits",
  annote="In the phase of designing the logical circuits, it is essential to minimise the number of elements because it leads to the more reliable, more secure, and cheaper solution. For the logical functions with less than 4 variables, the Karnaugh maps are suitable. However, in practice, we encounter usually a much more complex function, in those cases, we could apply Boolean algebra laws directly or use the Quine-McCluskey method, which is based on their systematic use. Unfortunately, this method does not usually provide a minimal form of logical function for really large scale logical functions, and in a result may be redundant expressions. For that reason, we show that we could apply an additional phase which leads to the set covering problem which needs to cover all the inputs by the obtained outputs. Since this problem is NP-hard, it is necessary to use heuristic methods, such as simulated annealing.
",
  booktitle="Proceedings of the 25th Conference STUDENT EEICT 2019",
  chapter="156671",
  howpublished="online",
  year="2019",
  month="april",
  pages="469--473",
  type="conference paper"
}