Authors: Janković, Dragan
Stanković, Radomir 
Moraga, Claudio
Title: Optimization of polynomial expressions by using the extended dual polarity
Journal: IEEE Transactions on Computers
Volume: 58
Issue: 12
First page: 1710
Last page: 1725
Issue Date: 1-Dec-2009
Rank: M21
ISSN: 0018-9340
DOI: 10.1109/TC.2009.113
Reed-Muller expressions and their various extensions and generalizations for binary and multiple-valued logic functions are an important class of discrete function representations that are often used in practical applications. These expressions can be uniformly viewed as discrete polynomial expressions over finite fields GF(2) and GF(q) or the field of rational numbers in the case of expressions with integer-valued coefficients. The optimization of them in the number of product terms count is performed by selecting either positive or negative literals (polarities) for variables in the functions to be represented. Since there are no ways to select in advance the polarity for variables that will result in most compact expression for a given function, all possible expressions have to be generated and the simplest of them selected. This is a task computationally very demanding, the complexity of which is O(q^n \times C), where C is the time to calculate a particular polarity. Since the reduction of the first factor may lead to missing the most compact expression, the reduction of C is the single option to speed up the procedure. In this paper, we propose an approach to the solution of this problem by exploiting the notion of extended dual polarity, which provides a simple way of ordering polarities to obtain an effective way of finding the optimal one by reducing the time to move between them. The method still implies exhaustive search, but it is an optimized search, which may be expressed in very simple rules resulting in efficient implementation. Experimental results illustrate the effectiveness of the proposed method.
Keywords: Fixed-polarity expressions. | Multiple-valued functions | Polynomial expressions | Reed-Muller expressions | Switching functions
Publisher: IEEE

Show full item record


checked on May 22, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.