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
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;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
