基于系数矩阵的极性转换方法及其在MPDRM化简中的应用

Coefficient matrix based polarity conversion method and its application to MPDRM minimization

针对多输出布尔函数系统混合极性对偶Reed-Muller展开(MPDRM)的极性转换问题,提出了一种基于系数矩阵的极性转换方法。该方法通过分析使用转换矩阵进行极性转换时所需的矩阵运算,进行子矩阵提取并将复杂的矩阵运算简化为子矩阵间的同或运算,提高了极性转换速度。在此基础上,给出了MPDRM精确化简算法,该算法采用格雷码策略使得极性转换发生在相邻极性值的MPDRM之间,并以和项数作为主要化简标准,文字数作为次要化简标准,通过采用穷举策略搜索极性空间求解最小MPDRM。实验结果表明,使用文字数作为次要化简标准能够获得更优化的MPDRM,与基于列表技术的极性转换方法相比,所提出方法能够缩短精确化简过程49.5%的时间。

This paper proposed a coefficient matrix based method for polarity conversion of MPDRM for multi-output Boolean function systems. The method improved the speed of polarity conversion through extracting sub-matrices from the coefficient matrix and simplifying the expensive matrix operations to XNOR operation between the extracted sub-matrices by analyzing the matrix operations needed for polarity conversion using transform matrix. On the basis of the proposed polarity conversion met- hod, this paper presented an exact minimization algorithm for MPDRM. This algorithm made the polarity conversion occur be- tween MPDRMs with adjacent polarity numbers by using Gray code strategy, and obtained the minimized MPDRM by taking the number of sum terms in MPDRM as primary minimization criterion and the number of literals in MPDRM as secondary min- imization criterion through polarity space exploration using exhaustive strategy. The experimental results show that, more opti- mal MPDRM can be obtained by using the number of literals in MPDRM as secondary minimization criterion. Compared with the tabular technique based polarity conversion method, the proposed coefficient matrix based polarity conversion method can reduce the time consumed by exact minimization nrocess for MPDRM by 49.5%.