Reed-Muller tree-based minimisation of fixed polarity Reed-Muller expansions

作     者：Aborhey, S 

作者机构：Univ S Pacific Dept Technol Suva Fiji 

出 版 物：《IEE PROCEEDINGS-COMPUTERS AND DIGITAL TECHNIQUES》 (IEE Proc Comput Digital Tech)

年 卷 期：2001年第148卷第2期

页      面：63-70页

核心收录：

主　　题：Boolean functions computational complexity polarity selection Information theory Optimisation techniques Reed-Muller codes minimisation method Computational complexity heuristic method minimisation fixed polarity Reed-Muller expansions encoding Reed-Muller tree-based minimisation completely specified Boolean systems conceptual framework Formal logic coding method Codes Boolean system disjoint sum Karpovsky's complexity estimates 

摘      要：A heuristic method for the determination of optimum or near-optimum fixed polarity Reed-Muller (FPRM) representation of multiple output, completely specified Boolean systems is presented. The Reed-Muller (RM) tree representation forms the conceptual framework for the method, which involves manipulations of arrays of cubes. A coding method that is well adapted to RM tree representation is presented. The minimisation method takes as input a disjoint sum of cubes representation of the Boolean system. Using Karpovsky s complexity estimates as the basis for polarity selection, the method obtains the FPRM expansion by generating in one run an optimum or near optimum Reed-Muller tree representation.