卜登立

(1. 井冈山大学 电子与信息工程学院, 江西 吉安 343009；2. 流域生态与地理环境监测国家测绘地理信息局重点实验室, 江西 吉安 343009)

0 引 言

RM(Reed-Muller)逻辑是基于“与-异或”的逻辑表示， 和基于“与-或”的布尔逻辑相比， 其在算术、 通信、 校验电路等方面具有面积优势[1]， 并且能够实现具有通用测试集的可测试性电路设计[2]， 近年来在信息安全领域的电路设计中也得到了应用[3]， 因此RM逻辑受到了越来越广泛的关注.

积之异或和(Exclusive-or Sum of Products, ESOP)是最一般化的混合极性RM逻辑表示， 它对变量的出现形式没有任何限制， 相对于其他形式的RM逻辑， 其能够获得更为精简的表示， 更有助于降低电路实现开销， 因此被作为一种逻辑模型应用于纳电子电路设计中[4]， 通过对ESOP进行优化实现相应电路的优化. 另外， 由于其能够较为直接地映射到可逆电路中， 因此ESOP表示模型被广泛应用于可逆电路综合[5-6]， 即先由exorcism算法[7]产生ESOP覆盖， 然后再将乘积项映射到可逆门网络.

降低ESOP的复杂度， 有助于降低使用ESOP作为逻辑模型电路的面积[4]， 也有助于降低采用ESOP表示模型进行综合所得可逆电路的量子成本[6]， 因此ESOP最小化成为电路综合中一个非常重要的步骤. 当前也有一些ESOP最小化的研究工作， 如文献[4]结合极性转换和局部变换启发式地优化ESOP逻辑， 文献[8]通过细分立方体进行ESOP的精确最小化， 文献[9]提出了通过检查ESOP多项式包含乘积项数的上限和下限对搜索空间进行剪枝的精确ESOP最小化算法， 以及广泛应用于可逆电路……