基于规则的可逆Toffoli电路优化算法

可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.     

基于卡诺图的三变量可逆逻辑综合算法

提出了一种基于卡诺图的可逆逻辑综合算法,该算法可以快速地求解带垃圾位的可逆逻辑综合问题。大量特定的可逆逻辑门都不可避免地带有一定的垃圾位, 如果使用真值表、置换群等经典可逆逻辑综合算法求解这些带垃圾位的可逆逻辑门,则因无法获得全局状态而很难得到结果。根据卡诺图的特点,将可逆逻辑问题分解为多个变量分别求解,无需关心全局状态。提出的卡诺图可逆逻辑综合算法 根据在卡诺图上的邻接性将3变量可逆逻辑问题划分为5个等价类;对每个等价类分别进行计算,在常数时间内解决了带垃圾位的可逆逻辑综合问题。     

基于汉明距离递减变换的可逆逻辑综合算法

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.现有的可逆逻辑综合算法虽然通过后期优化能够得到近似最优解,但是都存在生成的原始电路门数较多的问题,增加了后期优化工作的难度.文中提出一种基于真值表异位数计算的综合方法,根据异位数判定是否需增加逻辑非门达到减少输入和输出向量的汉明距离,从而实现边计算边简化函数,最后采用汉明距离递减变换的方法生成最终的电路.通过实验表明,相比于其他的综合算法,该算法得到的原始电路更接近于最优解或近似最优解,很大程度上减少了算法后续的优化工作量.     

基于带权有向图的可逆逻辑综合改进算法

为减少可逆逻辑综合中使用的可逆门,通过对基于带权有向图的可逆逻辑综合算法的分析,针对函数转换过程中过渡门数较多及电路优化算法简单的问题,提出了有效的等复杂度基本输出变换的概念,扩充并证明了Toffoli门序列的移动和化简规则,给出了改进的基于带权有向图的可逆逻辑综合算法。实验结果表明,该算法不仅减少了可逆电路构成时所使用的可逆门,而且对构建的可逆电路实现了有效化简,大幅度减少了门数和控制位数,降低了可逆电路代价。     

量子可逆逻辑电路综合的快速算法研究

可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.     

量子逻辑电路中控制点失效错误的定位

确保可逆电路的正确性与可靠性,错误检测必不可少,错误定位难度更高.通过分析发现当可逆电路中规模为k的可逆门发生控制点失效时仅对2<'n-k>个输入向量的输出产生影响,据此给出了一种把当前错误集分成若干个子集的方法生成控制点失效错误定位树.传统的错误定位方法都是通过生成真值表和错误表来产生错误定位树;该方法不需要生成和存储真值表以及错误表就能够有效定位电路中控制点失效错误.与Rfault算法相比,空间复杂度和时间复杂度更小,算法效率更高,能应用于更大规模的电路.     

基于正反控制模型的可逆逻辑综合

对一般Toffoli门进行了衍变和推广,给出了一个正反控制可逆级联模型(PNCRC),该模型拥有五种基本线型,并能正反控制目标位的输出.基于该模型给出了相应的可逆综合算法.对输入数不大于16的NCMCBench-mark函数进行测试并与已有的可逆综合方法比较,结果表明,利用该模型进行的可逆综合,垃圾信息数和可逆门数的优化效果都具有一定程度的改善.     

量子可逆逻辑综合的关键技术及其算法

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.     

汉诺塔非递归算法研究

汉诺塔(Tower of Hanoi)问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).     

基于相似函数与相似网络的可逆网络化简

提出了可逆函数的相似函数及可逆网络的相似网络,在此基础上构建了可逆网络化简方法。由可逆函数求出其所有的相似函数,对每个相似函数利用可逆逻辑综合算法生成可逆网络,再将其转换成对应的相似网络,并从中选取最优。该网络化简算法实现了生成三变量全部可逆函数和多变量可逆函数的可逆网络,与相关文献及Benchmark中的例题相比,构造可逆网络的门数较少,具有一定的优势。