CAJ | 학술논문

针对多输出布尔函数系统混合极性对偶Reed-Muller展开（MPDRM）的极性转换问题, 提出了一种基于系数矩阵的极性转换方法。该方法通过分析使用转换矩阵进行极性转换时所需的矩阵运算, 进行子矩阵提取并将复杂的矩阵运算简化为子矩阵间的同或运算, 提高了极性转换速度。在此基础上, 给出了MPDRM精确化简算法, 该算法采用格雷码策略使得极性转换发生在相邻极性值的MPDRM之间, 并以和项数作为主要化简标准, 文字数作为次要化简标准, 通过采用穷举策略搜索极性空间求解最小MPDRM。实验结果表明, 使用文字数作为次要化简标准能够获得更优化的MPDRM, 与基于列表技术的极性转换方法相比, 所提出方法能够缩短精确化简过程49. 5%的时间。
침대다수출포이함수계통혼합겁성대우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 between 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 minimization criterion through polarity space exploration using exhaustive strategy. The experimental results show that, more optimal 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 process for MPDRM by 49. 5%.