基于错误位分布的可逆逻辑综合算法

• 作者: 卫丽华 朱鹏程 程学云 管致锦
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 可逆逻辑综合 错误位 模式识别 模式转换 启发式规则
• 年，卷（期）: 2018,（4）
• 所属期刊栏目: 算法与智能
• 页码范围: 796-808
• 页数: 13页
• 分类号: TP387
• 字数: 9370字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.00796

摘要

可逆逻辑综合是指根据可逆函数构造可逆电路的过程.真值表变换法是一种常见的可逆逻辑综合算法,其易懂并易实现,但生成的电路含较多冗余逻辑门,有待进一步的优化.为实现一种无需优化便可接近最优解的真值表变换法,给出关于真值表错误位的定义,提出并证明了NOT门、CNOT门以及Toffoli门的在减少错误位上的数量判定,以错误数和错误位分布情况为特征从全部三元可逆逻辑函数的真值表中提炼出79种错误分布模式,并将模式分为两类.为第一类模式直接确定在综合过程中用于减少错误数的规则,为第二类模式制订试探方案,并确定在试探失败的情况下向其他模式(错误数与原模式相同,但更易处理)的转换规则.以扩展广义Toffoli门为门库,提出一种基于错误位分布模式识别和转换的可逆逻辑综合算法,该算法通过不断识别模式并应用启发式规则,使得错误较多的模式尽快尽早地转换成错误较少的模式,直至真值表中无错误位存在为止.该算法在最坏情况下需要3*n*2n-2次迭代,算法的时间复杂度为O(n*2n),空间复杂度为O(n*2n),与具有代表性的同类算法比较,时间复杂度和空间复杂度都具有一定优势.采用代表性文献中选用的Benchmark函数和全部三元可逆函数进行实验,结果表明,该算法不仅在Benchmark函数上优于同类算法,而且由全部三元函数生成电路的平均门代价比同类较好算法优化后的结果降低6.19％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	程学云	南通大学计算机科学与技术学院	49	115	5.0	7.0
5	朱鹏程	南通大学现代教育技术中心	14	33	4.0	4.0
6	管致锦	南通大学计算机科学与技术学院	69	369	10.0	16.0
10	卫丽华	南通理工学院软件工程系	15	15	2.0	2.0