卜登立

(1. 井冈山大学 电子与信息工程学院，江西 吉安 343009；2. 同济大学 软件学院，上海 201804)



基于SADPSO的MPRM最小化算法

卜登立1,2

(1. 井冈山大学 电子与信息工程学院，江西 吉安 343009；2. 同济大学 软件学院，上海 201804)

摘要：针对混合极性Reed-Muller (mixed-polarity Reed-Muller, MPRM) 逻辑最小化问题，提出一种基于SADPSO (hybrid simulated annealing and discrete particle swarm optimization) 的智能算法。该算法将模拟退火 (simulated annealing, SA) 与离散粒子群优化 (discrete particle swarm optimization, DPSO) 相结合，对DPSO所得到的最佳解应用SA，帮助算法跳出局部极小。使用所提出算法和已有智能MPRM最小化算法分别对23个MCNC基准电路进行逻辑最小化，并对算法结果质量进行定量评价。结果表明，与已有智能MPRM最小化算法相比，所提出算法具有更好的全局收敛能力，能够提高算法结果质量。

关键词：混合极性Reed-Muller; 逻辑最小化; 智能算法; 模拟退火; 离散粒子群优化

0引言

Reed-Muller(RM)逻辑是布尔函数基于AND/XOR的表示，对于线性电路、通信系统和算术逻辑等电路而言，与基于AND/OR的布尔逻辑相比，RM逻辑可获得面积、功耗和可测性方面的优势[1-2]。混合极性RM(mixed-polarity Reed-Muller, MPRM)是一种RM标准形表示，相对于固定极性RM(fixed-polarity Reed-Muller, FPRM)，MPRM有可能获得更为简洁的表示，因此，MPRM的最小化问题得到了广泛的关注。

MPRM最小化是RM电路逻辑综合过程中一个非常重要的阶段，由于MPRM最小化问题属于NP难优化问题[2]，因此，对输入数较多的电路，研究者倾向于采用智能优化方法来完成MPRM最小化。在MPRM中，变量的极性属性有3种类型[1]，由于智能优化算法在进行编码选择时需要遵守完备性、健全性和非冗余性3个基本原则[3]，因此，对于MPRM最小化不宜使用类似于FPRM最小化时常采用的二进制编码[4]，而应使用三进制编码。……