DocumentCode
1421850
Title
Comments on "Sympathy: fast exact minimization of fixed polarity Reed-Muller expansion for symmetric functions"
Author
Butler, Jon T. ; Dueck, Gerhard W. ; Shmerko, Vlad P. ; Yanuskevich, Svetlana
Author_Institution
Dept. of Electr. & Comput. Eng., Naval Postgraduate Sch., Monterey, CA, USA
Volume
19
Issue
11
fYear
2000
Firstpage
1386
Lastpage
1388
Abstract
The above paper finds an optimal fixed-polarity Reed-Muller expansion of an n-variable totally symmetric function using an OFDD-based algorithm that requires O(n/sup 7/) time and O(n/sup 6/) storage space. However, an algorithm based on Suprun´s transient triangles requires only O(n/sup 3/) time and O(n/sup 2/) storage space. An implementation of this algorithm yields computation times lower by several orders of magnitude.
Keywords
Reed-Muller codes; data structures; decision diagrams; logic CAD; minimisation of switching nets; OFDD-based algorithm; Suprun´s transient triangles; Sympathy; computation time; exact minimization; fixed polarity Reed-Muller expansion; n-variable totally symmetric function; storage space; Computer science; Data structures; Design automation; Integrated circuit yield; Logic; Minimization; Symmetric matrices;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/43.892862
Filename
892862
Link To Document