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

Reversible Logic Synthesis Algorithm Based on Distribution of Error Bits

作　　者：朱鹏程 程学云[2,3] 卫丽华 管致锦 ZHU Peng-Cheng;CHENG Xue-Yun;WEI Li-Hua;GUAN Zhi-Jin(Department of Computer Science and Technology Modern Educational Technology Center,Nantong University Xinglin College,Nantong,Jiangsu 226019;College of Computer Science and Technology,Nantong University,Nantong,Jiangsu 226019;College of Electronic and Information,Nantong University,Nantong,Jiangsu 226019;Department of Software Engineering,Nantong Polytechnic College,Nantong,Jiangsu　226002)

机构地区：[1]南通大学现代教育技术中心杏林学院计算机科学与技术系,江苏南通226019 [2]南通大学计算机科学与技术学院,江苏南通226019 [3]南通大学电子信息学院,江苏南通226019 [4]南通理工学院软件工程系,江苏南通226002

出　　处：《计算机学报》2018年第4期796-808,共13页Chinese Journal of Computers

基　　金：本课题得到国家自然科学基金(61402244)、江苏省高校自然科学基金(16KJB520039)、江苏省研究生科研与实践创新计划项目(KYCX17-1916)资助.

摘　　要：可逆逻辑综合是指根据可逆函数构造可逆电路的过程.真值表变换法是一种常见的可逆逻辑综合算法,其易懂并易实现,但生成的电路含较多冗余逻辑门,有待进一步的优化.为实现一种无需优化便可接近最优解的真值表变换法,给出关于真值表错误位的定义,提出并证明了NOT门、CNOT门以及Toffoli门的在减少错误位上的数量判定,以错误数和错误位分布情况为特征从全部三元可逆逻辑函数的真值表中提炼出79种错误分布模式,并将模式分为两类.为第一类模式直接确定在综合过程中用于减少错误数的规则,为第二类模式制订试探方案,并确定在试探失败的情况下向其他模式(错误数与原模式相同,但更易处理)的转换规则.以扩展广义Toffoli门为门库,提出一种基于错误位分布模式识别和转换的可逆逻辑综合算法,该算法通过不断识别模式并应用启发式规则,使得错误较多的模式尽快尽早地转换成错误较少的模式,直至真值表中无错误位存在为止.该算法在最坏情况下需要3*n*2^(n-2)次迭代,算法的时间复杂度为O(n*2~n),空间复杂度为O(n*2~n),与具有代表性的同类算法比较,时间复杂度和空间复杂度都具有一定优势.采用代表性文献中选用的Benchmark函数和全部三元可逆函数进行实验,结果表明,该算法不仅在Benchmark函数上优于同类算法,而且由全部三元函数生成电路的平均门代价比同类较好算法优化后的结果降低6.19%.Synthesis of reversible reversible logical functions is an important procedure for constructing reversible circuits.Truth table transformation based method is prevalent due to its understandability and easy implementation,but it contains many redundant gates in resulting circuit and needs further optimization work.To create a transformation based method,which will be able to generate preferable circuits without optimization,we have made a lot of effort.Firstly,we gave a definition of error bits in truth table,proposed and proved capacity of common reversible gates(NOT,CNOT,and Toffoli)to reduce error bits,investigated overall error distribution situations of all three-variable reversible logic functions,and extracted 79 different distribution patterns of error bits from these situations.According to whether exists certain gate used to reduce error according to the pattern only,we divided all patterns into two kinds.For the first kind,we determine specific heuristic rules to reduce error,and use this rule immediately when run into this pattern during synthesis.And we design trial rules for patterns of second kind,when encounter this pattern,we try to find gate to reduce error,if none is found,we find gate to convert this pattern to other pattern of same error count but more easily dealt with.Secondly,we generated optimal circuits for all three-variable reversible logic functions using exhausting method,and learned heuristic rules from optimal circuits by manual observation and analysis,these rules are used to determine which pattern should be converted to when run into patterns of second kind and reducing trial is failed.Thirdly,we presented a novel transformation based synthesis algorithm using extended generalized Toffoli gate family as gate library.The algorithm comprises two components.The first one is the preprocessing part which is used to add inverters to columns whose error count exceeds 2 n-1,and n is the variable number.The second one is the reversible logic synthesis part based on pattern recognition an

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

分 类 号：TP387[自动化与计算机技术—计算机系统结构]