Dizajn i minimizacija rekurzivnih Bulovih formula za memristivna logička kola

Abstract

U radu je razmatran problem dizajna i minimizacije rekurzivne Bulove formule konstruisane za proizvoljnu Bulovu funkciju y:BN →B. U cilju rešavanja ovog problema, predstavljene su dve algoritamske heuristike za minimizaciju rekurzivne Bulove formule. Minimizacija rekurzivne Bulove formule vrši se korišćenjem regularnih poredaka pozitivnih proizvod termova. U disertaciji je dokazano kako je ova regularnost poredaka zapravo potreban i dovoljan uslov da željena Bulova funcija y bude korektno predstavljena rekurzivnom Bulovom formulom konstruisanom na osnovu tih poredaka. Pokazano je i kako predstavljeni algoritmi daju bolje rezultate za veći broj instanci problema u poređenju sa algoritmima dostupnim u literaturi.

In this thesis, the problem of design and minimization of recursive Boolean formula, based on an arbitrary Boolean function y:BN →B , is considered. As a solution of a problem, two heuristic algorithms that minimize the length of recursive Boolean formula, were presented. Minimization, itself, is done by using regular orders of positive product terms. In the thesis it was proved that the regularity of orders represents necessary and sufficient condition for correct representation of Boolean function y by recursive Boolean formula based on such regular order. Developed algorithms are compared with other heuristic algorithms for recursive Boolean formula minimization, available in the literature, and it is shown how algorithms proposed in this thesis provide better results for more problem instances.