Abstract:
An algorithm based on coefficient matrix transformation for computing Mixed Polarity Reed-Muller(MPRM) expansions of Boolean functions with multiple outputs is proposed. The optimal MPRM is solved by taking the number of product terms in MPRM as minimization criterion and exercising exhaustive strategy for polarity space exploring. The proposed method is used to solve the optimal MPRM of MCNC and ISCAS benchmarks, and compared with the method using tabular technique, test results show that the proposed coefficient matrix transformation algorithm achieves 55.8% performance improvement on average for optimal MPRM solving.
Key words:
Mixed Polarity Reed-Muller(MPRM),
coefficient matrix transformation,
logic optimization,
list technique,
exhaustive strategy,
Gray code
摘要： 针对多输出布尔函数，给出一种求解混合极性Reed-Muller(MPRM)的系数矩阵变换算法。以MPRM中的乘积项数为化简标准，采用穷举策略进行极性空间搜索，求解最优MPRM。在MCNC和ISCAS基准电路上的测试结果表明，与采用列表技术相比，该系数矩阵变换算法能平均缩短55.8%的最优MPRM求解时间。
关键词:
混合极性Reed-Muller,
系数矩阵变换,
逻辑优化,
列表技术,
穷举策略,
格雷码
CLC Number:
BO De-Li, WEI Wei, CENG Xiao-Hui. Optimal MPRM Solving Method Based on Coefficient Matrix Transformation[J]. Computer Engineering, 2012, 38(22): 255-259.
卜登立, 魏韡, 曾小荟. 基于系数矩阵变换的最优MPRM求解方法[J]. 计算机工程, 2012, 38(22): 255-259.