Academic Journals Database
Disseminating quality controlled scientific knowledge

Rule-Based Optimization of AND-XOR Expressions

Author(s): Danil Knysh | Elena Dubrova

Journal: Facta Universitatis Series : Electronics and Energetics
ISSN 0353-3670

Volume: 24;
Issue: 3;
Start page: 437;
Date: 2011;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

Keywords: Reed-Muller expression | AND-XOR expression | local transformation | greedy search.

The problem of finding a minimum AND-XOR expression for a given Boolean function is known to be very hard. In this paper we investigate whether a rule-based approach can help minimizing AND-XOR expressions for functions which are too large to be handled by algorithmic-based approaches. We apply a simple greedy search based on a set of local transformations to the positive polarity Reed- Muller expression of Boolean functions. Our experiments on large functions show surprisingly good results. We achieve 23% reduction in the number of literals on average. We believe that much better results can be achieved if a more sophisticated non-greedy search is used. The purpose of this paper is to motivate more research in this direction.
Why do you need a reservation system?      Save time & money - Smart Internet Solutions