DC FieldValueLanguage
dc.contributor.authorJanković, Draganen
dc.contributor.authorStanković, Radomiren
dc.contributor.authorMoraga, Claudioen
dc.date.accessioned2020-05-01T20:29:12Z-
dc.date.available2020-05-01T20:29:12Z-
dc.date.issued2009-12-01en
dc.identifier.issn0018-9340en
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/2070-
dc.description.abstractReed-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.en
dc.publisherIEEE-
dc.relation.ispartofIEEE Transactions on Computersen
dc.subjectFixed-polarity expressions. | Multiple-valued functions | Polynomial expressions | Reed-Muller expressions | Switching functionsen
dc.titleOptimization of polynomial expressions by using the extended dual polarityen
dc.typeArticleen
dc.identifier.doi10.1109/TC.2009.113en
dc.identifier.scopus2-s2.0-74549158238en
dc.relation.firstpage1710en
dc.relation.lastpage1725en
dc.relation.issue12en
dc.relation.volume58en
dc.description.rankM21-
item.openairetypeArticle-
item.cerifentitytypePublications-
item.fulltextNo Fulltext-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.grantfulltextnone-
Show simple item record

SCOPUSTM   
Citations

14
checked on Jun 14, 2024

Page view(s)

35
checked on May 9, 2024

Google ScholarTM

Check

Altmetric

Altmetric


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