厉康平， 汪鹏君， 张会红（宁波大学电路与系统研究所，浙江宁波 315211）

基于人口迁移算法的三值FPRM电路面积最佳极性搜索

厉康平， 汪鹏君， 张会红
（宁波大学电路与系统研究所，浙江宁波 315211）

人口迁移算法是一种新的全局优化搜索算法，主要模拟人口随着经济重心发生转移和随着压力增加而扩散的机制，其收敛性和全局寻优能力较强。三值固定极性RM（Fixed-polarity Reed-Muller，FPRM）电路的面积大小与其极性有关。通过对人口迁移算法的研究，提出了一种三值FPRM电路面积优化方案。首先根据三值FPRM表达式和电路面积之间的内在联系，建立面积优化模型；然后利用人口迁移算法对三值FPRM电路进行面积最佳极性搜索；最后对10个MCNC Benchmark电路进行测试。结果表明：与整体退火遗传算法相比，本文算法在面积和时间上分别平均节省10.04%和56.59%。

人口迁移算法；三值FPRM电路；面积优化；极性搜索

search

任意三值逻辑函数均可以用布尔逻辑和Reed-Muller（RM）逻辑来表示［1］，与传统的布尔逻辑相比，基于RM逻辑的通信电路、奇偶校验电路、运算电路等具有更紧凑的结构［2］和更好的可测性［3］。RM逻辑通常采用固定极性（Fixed-polarity Reed-Muller，FPRM）和混合极性（Mixed-polarity Reed-Muller，MPRM）两种表达方式。在n变量的三值FPRM逻辑函数中有3n个固定极性，对应3n个不同的三值FPRM表达式，其表达式的简单与复杂程度由极性决定，因此，极性对三值FPRM电路的功耗、面积等性能指标产生很大的影响。对较小规模的电路进行优化时，可以使用穷举法遍历每个极性；对较大规模电路进行优化时，由于极性与变量存在指数关系使得搜索空间急剧增加，穷举法很难在有限的时间内得到优化结果。……