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

《基于规则的可逆Toffoli电路优化算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第４０卷第１０期计算机科学Ｖｏｌ．４０Ｎｏ．１０２０１３年１０月ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅＯｃｔ２０１３基于规则的可逆Ｔｏｆｆｏｌｉ电路优化算法程学云１１２１管致锦张海豹丁卫平（南通大学计算机科学与技术学院南通２２６０１９）１２（南通大学电子信息学院南通２２６０１９）摘要可逆电路的优化是可逆逻辑综合的关键问题之一。为了解决可逆Ｔｏｆｆｏｌｉ电路优化问题中算法复杂度高和电路规模可扩充性差的问题，分析归纳了相邻Ｔｏｆｆｏｌｉ门的关系，提出并证明了可逆Ｔｏｆｆｏｌｉ电路中子序列的移动和化简规则，并基于这些规则给出了可逆Ｔｏｆｆｏｌｉ电路的优化算法。根据移动规则对可逆电路进行正向和反向扫描，寻

2、找满足化简规则的子序列进行优化，直到可逆电路不发生变化为止。该优化算法与可逆电路的输入线数无关，无需存储额外信息，适用于各种不同类型的Ｔｏｆｆｏｌｉ电路合成方法，算法复杂度为Ｏ（ｓ３），优于通常使用的模板优化的复杂度Ｏ（ｎ！ｔ２３）。在具体实例和国际认可的所有３变量可逆函数上的验证结果表明，该优化算法能有效地减少可逆电路的门ｓ数和控制位数，降低可逆电路的代价。关键词可逆逻辑综合，可逆函数，Ｔｏｆｆｏｌｉ门，可逆电路优化中图法分类号ＴＰ３０２文献标识码ＡＲｕｌｅ－ｂａｓｅｄＯｐｔｉｍｉｚａｔｉｏｎｏｆＲｅｖｅｒｓｉｂｌｅＴｏｆｆｏｌｉＣｉｒｃｕｉｔｓ１１２１ＣＨＥＮＧＸｕｅ－ｙｕｎＧＵＡＮＺ

3、ｈｉ－ｊｉｎＺＨＡＮＧＨａｉ－ｂａｏＤＩＮＧＷｅｉ－ｐｉｎ（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＮａｎｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｔｏｎｇ２２６０１９，Ｃｈｉｎａ）１（ＣｏｌｌｅｇｅｏｆＥｌｅｃｔｒｏｎｉｃｓａｎｄＩｎｆｏｒｍａｔｉｏｎ，ＮａｎｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｔｏｎｇ２２６０１９，Ｃｈｉｎａ）２ＡｂｓｔｒａｃｔＯｐｔｉｍｉｚａｔｉｏｎｏｆｒｅｖｅｒｓｉｂｌｅｃｉｒｃｕｉｔｓｉｓｏｎｅｏｆｋｅｙｐｒｏｂｌｅｍｓｏｆｒｅｖｅｒｓｉｂｌｅｌｏｇｉｃｓｙｎｔｈｅｓｉｓ．Ｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｈｉｇｈａｌｇｏｒｉｔｈｍ

4、ｃｏｍｐｌｅｘｉｔｙａｎｄｐｏｏｒｓｃａｌａｂｉｌｉｔｙｏｆｒｅｖｅｒｓｉｂｌｅＴｏｆｆｏｌｉｃｉｒｃｕｉｔｓ，ｔｈｅｐａｐｅｒａｎａｌｙｚｅｄａｎｄｓｕｍｍａｒｉｚｅｄｒｅｌａ－ｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎａｄｊａｃｅｎｔＴｏｆｆｏｌｉｇａｔｅｓ，ｐｒｏｐｏｓｅｄａｎｄｐｒｏｖｅｎｔｈｅｍｏｖｉｎｇａｎｄｓｉｍｐｌｉｆｉｃａｔｉｏｎｒｕｌｅｓｏｆｓｕｂ－ｓｅｑｕｅｎｃｅｏｆｒｅ－ｖｅｒｓｉｂｌｅｃｉｒｃｕｉｔｃａｓｃａｄｅｄｂｙＴｏｆｆｏｌｉｇａｔｅｓ，ａｎｄｇａｖｅｔｈｅｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｔｈｅｓｅｒｕｌｅｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｅｘａｍｉ－

5、ｎｅｓｔｈｅｃｉｒｃｕｉｔｂｉｄｉｒｅｃｔｉｏｎａｌｌｙａｃｃｏｒｄｉｎｇｔｏｔｈｅｍｏｖｉｎｇｒｕｌｅｓ，ｓｅａｒｃｈｅｓｔｈｅｓｕｂ－ｓｅｑｕｅｎｃｅｓａｔｉｓｆｙｉｎｇｓｉｍｐｌｉｆｉｃａｔｉｏｎｒｕｌｅｓ，ｐｅｒｆｏｒｍｓｃｏｒｒｅｓｐｏｎｄｉｎｇｏｐｔｉｍｉｚａｔｉｏｎ，ａｎｄｔｈｅｐｒｏｃｅｓｓｉｓｒｅｐｅａｔｅｄｕｎｔｉｌｔｈｅｃｉｒｃｕｉｔｄｏｅｓ’ｔｃｈａｎｇｅ．Ｔｈｅａｌｇｏｒｉｔｈｍｉｓｉｒｒｅｌｅ－ｖａｎｔｔｏｔｈｅｎｕｍｂｅｒｏｆｉｎｐｕｔｌｉｎｅｓ，ｄｏｅｓ’ｔｎｅｅｄｔｏｓｔｏｒｅｅｘｔｒａｉｎｆｏｒｍａｔｉｏｎ，ｉｓｓｕｉｔａｂｌｅｔｏｄｉｆｆｅｒｅｎｔＴｏ

6、ｆｆｏｌｉｃｉｒｃｕｉｔｓｙｎｔｈｅｓｉｓ３），ｗｈｉｃｈｉｓｓｕｐｅｒｉｏｒｔｏＯ（ｎ！ｔ２３）ｏｆｇｅｎｅｒａｌｌｙｕｓｅｄｔｅｍｐｌａｔｅｏｐｔｉｍｉｚａｔｉｏｎｍｅｔｈｏｄｓ，ａｎｄｉｔｓａｌｇｏｒｉｔｈｍｃｏｍｐｌｅｘｉｔｙｉｓＯ（ｓｓｔｅｃｈｎｉｑｕｅ．Ｒｅｓｕｌｔｓｏｆｅｘａｍｐｌｅｓａｎｄｅｘｐｅｒｉｍｅｎｔｓｏｎａｌｌ３－ｂｉｔｒｅｖｅｒｓｉｂｌｅｆｕｎｃｔｉｏｎｓｓｈｏｗｔｈａｔｔｈｅｎｕｍｂｅｒｏｆｇａｔｅｓａｎｄｔｈｅｃｏｎｔｒｏｌｂｉｔｓｃａｎｂｅｒｅｄｕｃｅｄｅｆｆｅｃｔｉｖｅｌｙａｎｄｔｈｅｃｏｓｔｏｆｒｅｖｅｒｓｉｂｌｅｃｉｒｃｕｉｔｉｓｄｅｃｒｅａｓｅｄ．

7、ＫｅｙｗｏｒｄｓＲｅｖｅｒｓｉｂｌｅｌｏｇｉｃｓｙｎｔｈｅｓｉｓ，Ｒｅｖｅｒｓｉｂｌｅｆｕｎｃｔｉｏｎ，Ｔｏｆｆｏｌｉｇａｔｅ，Ｏｐｔｉｍｉｚａｔｉｏｎｏｆｒｅｖｅｒｓｉｂｌｅｃｉｒｃｕｉｔ法一般具有较低的时间和空间复杂度，然而得到的可逆电路１引言往往不是最优电路。为了得到最优电路，需要在不改变可逆［１］、低电路功能的条件下，对电路进行重组、替换和逻辑门约简等，可逆逻辑综合是可逆计算的重要内容，在量子计算［２］、纳米技术