Detail publikačního výsledku

Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method

ŠEDA, M.

Originální název

Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method

Anglický název

Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method

Druh

Článek recenzovaný mimo WoS a Scopus

Originální abstrakt

Finding the minimal logical functions has important applications in the design of logical circuits. This task is solved by many different methods but, frequently, they are not suitable for a computer implementation. We briefly summarise the well-known Quine-McCluskey method, which gives a unique procedure of computing and thus can be simply implemented, but, even for simple examples, does not guarantee an optimal solution. Since the Petrick extension of the Quine-McCluskey method does not give a generally usable method for finding an optimum for logical functions with a high number of values, we focus on interpretation of the result of the Quine-McCluskey method and show that it represents a set covering problem that, unfortunately, is an NP-hard combinatorial problem. Therefore it must be solved by heuristic or approximation methods. We propose an approach based on genetic algorithms and show suitable parameter settings.

Anglický abstrakt

Finding the minimal logical functions has important applications in the design of logical circuits. This task is solved by many different methods but, frequently, they are not suitable for a computer implementation. We briefly summarise the well-known Quine-McCluskey method, which gives a unique procedure of computing and thus can be simply implemented, but, even for simple examples, does not guarantee an optimal solution. Since the Petrick extension of the Quine-McCluskey method does not give a generally usable method for finding an optimum for logical functions with a high number of values, we focus on interpretation of the result of the Quine-McCluskey method and show that it represents a set covering problem that, unfortunately, is an NP-hard combinatorial problem. Therefore it must be solved by heuristic or approximation methods. We propose an approach based on genetic algorithms and show suitable parameter settings.

Klíčová slova

Karnaugh map, Quine-McCluskey method, set covering problem, genetic algorithm

Klíčová slova v angličtině

Karnaugh map, Quine-McCluskey method, set covering problem, genetic algorithm

Autoři

ŠEDA, M.

Vydáno

01.10.2007

ISSN

1304-2386

Periodikum

International Journal of Computational Intelligence

Svazek

4

Číslo

2

Stát

Turecká republika

Strany od

139

Strany do

143

Strany počet

5

BibTex

@article{BUT44468,
  author="Miloš {Šeda}",
  title="Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method",
  journal="International Journal of Computational Intelligence",
  year="2007",
  volume="4",
  number="2",
  pages="139--143",
  issn="1304-2386"
}