Minimisation of Complex Logical Functions Using Soft Computing Techniques

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F08%3APU76868" target="_blank" >RIV/00216305:26210/08:PU76868 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Minimisation of Complex Logical Functions Using Soft Computing Techniques

Original language description

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

Minimalizace složitých logických funkcí s využitím technik soft computingu

Czech description

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í. Zaměřujeme se na interpretaci výsledku získaného Quine-McCluskeyho metodou a ukazujeme, že reprezentuje 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ů.

Type

D - Article in proceedings

CEP classification

JC - Computer hardware and software

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Proceedings of the 9th International Carpathian Control Conference ICCC '2008

ISBN

978-973-746-897-0

ISSN

—

e-ISSN

—

Number of pages

4

Pages from-to

—

Publisher name

Editura Sitech Craiova

Place of publication

Sinaia (Romania)

Event location

Sinaia

Event date

May 25, 2008

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—