Publication detail

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

ŠEDA, M.

Czech title

Zlepšení Quine-McCluskeyho metody dodatečnou heuristikou založenou na řešení problému pokrytí

English title

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

Type

conference paper

Language

en

Original abstract

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.

Czech abstract

Hledání minimálních logických funkcí má významné aplikace v návrhu logických obvodů. Tato úloha se řeší mnoha různými metodami, ty ale často nejsou vhodné pro implementaci v počítači. Stručně shrneme známou Quine-McCluskeyho metodu, která dává jednoznačný postup výpočtu, a tedy ji lze snadno implementovat, avšak dokonce i pro jednoduché příklady negarantuje nalezení optimálního řešení. Protože Petráčkovo rozšíření Quine-McCluskeyho metody není obecně použitelné pro nalezení minima logických funcí s větším počtem hodnot, soustředíme se na interpretaci výsledku Quine-McCluskeyho metody a ukážeme, že představuje problém pokrytí, který však bohužel patří mezi NP-lěžké kombinatorické problémy. Proto musí být řešen heuristickými nebo aproximativními metodami. Navrhujeme přístup založený na genetických algoritmech ukážeme vhodné nastavení jeho parametrů.

English abstract

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.

Keywords in Czech

Karnaughova mapa, Quine-McCluskeyho metoda, problém pokrytí, genetický algoritmus

Keywords in English

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

RIV year

2007

Released

01.08.2007

Publisher

WASET

Location

Berlin (Germany)

Book

Proceedings of WASET International Conference on Computer, Electrical and Systems Science and Engineering CESSE 2007

Pages from–to

256–260

Pages count

5

BIBTEX


@inproceedings{BUT23386,
  author="Miloš {Šeda},
  title="Heuristic Set-Covering-Based Postprocessing for Improving the Quine-McCluskey Method",
  booktitle="Proceedings of WASET International Conference on Computer, Electrical and Systems Science and Engineering CESSE 2007",
  year="2007",
  month="August",
  pages="256--260",
  publisher="WASET",
  address="Berlin (Germany)"
}