快速启发式ESOP电路面积优化算法

摘要：

针对积之异或和(ESOP)电路面积优化的时间效率问题, 提出一种快速的启发式算法. 该算法使用多输出立方体表示乘积项, 首先由基于伪Kronecker判决图的方法得到初始ESOP覆盖, 然后使用启发式局部极性转换与局部变换交替迭代的方式进行面积优化. 为提高算法效率, 启发式局部极性转换仅尝试改变立方体中单个变量的极性,并且仅接受对减少电路面积有帮助的极性转换, 该转换有助于使优化过程跳出局部极小; 局部变换则通过对 ESOP覆盖中距离为1或2的立方体进行变形来减少电路面积, 该变换有助于算法的收敛. 实验结果表明, 文中算法能够适用于具有较多输入变量的多输出电路;与MPRM电路相比, ESOP电路能够降低电路面积开销;与其他ESOP电路优化算法相比, 该算法能够显著改善面积优化的时间效率.

关键词：Reed-Muller逻辑、ESOP电路、面积优化、局部极性转换、局部变换、启发式方法

所属期刊栏目：27

分类号：TP391.72(计算技术、计算机技术)

资助基金：江西省自然科学基金计划20122BAB201038;江西省青年科学基金计划20122BAB216030;江西省教育厅科技计划项目GJJ13538

在线出版日期：2015-11-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2161-2168