基于矩形覆盖的FPRM电路多级面积优化

Rectangular overlays based multi-level area optimization of FPRM circuit

Reed-Muller(RM)逻辑因其优越的性能而广泛应用于数字电路,本文提出一种固定极性RM(FixedPolarityRM,FPRM)逻辑函数的多级优化方法.首先将电路表示成XOR/AND形式的FPRM逻辑函数,再计算函数的kernels和co-kernels,并由其生成矩阵,然后从矩阵中搜索尽可能多的矩形覆盖,利用矩阵分块和贪心策略逐步提取公共变量,最后生成多级逻辑表达式.MCNC Benchmarks测试后的结果表明,本方法得到的表达式比原RM逻辑表达式减少66%的文字(literals)数目,比onset表方法的优化结果减少19%.

Reed-Muller(RM) logic is widely used in digital circuits for its superior performance. A multi-level optimization method for Fixed Polarity RM(FPRM) logic function is proposed in this paper. First, logic circuits are converted into FPRM logic function in XOR/AND form. Next, the kernels and co-kernels of the function are calculated to generate a matrix. Then rectangular overlays are searched for in the matrix, in which process the matrix partition and greedy strategy are used to gradually extract the public variables. Finally, the multi-level logic expressions are generated. The results tested using the MCNC Benchmarks show that the number of literals obtained by the proposed method is 66% less than that of polarity optimization, and 19% less than that of the onset table method.