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

摘要：

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

关键词：可逆逻辑综合、错误位、模式识别、模式转换、启发式规则

所属期刊栏目：41

分类号：TP387(计算技术、计算机技术)

资助基金：国家自然科学基金61402244;江苏省高校自然科学基金16KJB520039;江苏省研究生科研与实践创新计划项目KYCX17-1916

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

页数：共13页

页码：796-808