基于置换中循环分解的可逆电路综合算法

发布时间：2020-04-11 11:41

【摘要】：可逆计算的研究在许多领域有重要应用,例如信号处理,密码学,计算机图形学,纳米学和光子电路。例如,可逆计算的理论是量子计算的基础。量子计算的电路模型的一个重要特点就是可逆性,可逆性也是量子力学假定发展的结果。可逆计算的一个重要问题是可逆电路综合。但是,目前可逆逻辑电路综合算法还存在着适用电路规模过小、时空代价过高等一系列问题,还不能满足未来可逆计算及其相关领域对可逆逻辑电路的要求。因此,系统而深入地研究可逆电路的合成及优化技术,寻找更为高效的合成和优化可逆电路的算法是很有必要的。我们对可逆逻辑及其综合算法进行了深入研究,主要研究工作及成果如下:1、基于置换中循环分解的可逆电路综合算法可逆函数与置换同构,任意置换都有其相应的循环表示。文中我们基于探索置换的循环表示的性质的思路,提出了一种新的基于置换中循环分解的可逆电路综合算法。该算法由两部分组成,第一部分根据异位数判定是否需增加逻辑非门达到减少输入和输出向量的汉明距离;第二部分依据置换以及置换的循环表示的性质,将置换中循环分解,渐渐接近恒等置换,直至变为恒等置换,这部分电路由正反控制的Toffoli门实现。该算法提供了一种新的思路,且仍可以通过改进算法来优化最终结果,并且这种思路也可以扩展到4量子比特乃至更多比特位的电路综合。2、基于CUDA的可逆电路综合算法加速的研究CUDA是目前应用最为广泛的通用并行计算架构,借助GPU(图像处理器)的并行处理能力,在不增加额外成本的情况下就能较大幅度的提升程序的运行速度和相应的求解能力。这部分工作中,我们将借助CUDA并行架构,实现一种计算Hash函数的快速算法以及实现置换的乘积运算以模拟可逆电路的级联,分别对其加速比进行了研究,完成了一种高效的可逆电路综合算法在CUDA运算平台的并行化实现。
【图文】：

序列,逻辑网络,可逆函数

扇入；③没有反馈；④网络分层级联。逡逑一个可逆函数可以用真值表的形式表示，可以把它看作一个整数序列｛０，１，…，２ｎ－ｌ｝到自逡逑身的一一映射，还可以用整数集合的置换表示。图２－１为一个３变量的可逆逻辑网络，表逡逑２－１为其可逆函数的真值表表示，式（２．３）为其可逆函数的置换表示。逡逑Ｘ３邋逦逦Ｏ逦少３逡逑Ｘ！逦逦Ｏ逦ｙｉ逡逑ｘ邋丨逦？—？—＾逡逑图２－１邋—个３输入／输出可逆逻辑网络逡逑表２－１是图２－１所示可逆逻辑网络的真值表表示：逡逑表２－１邋—个３ｘ３的可逆逻辑函数逡逑输入逦输出逡逑逦尤邋３逦＆邋ａ逦ｙ３邋Ｖ２邋ｙｉ逡逑０

双射,逻辑函数,逻辑门

１逦１逦１１＾逦、｜１１逦１逡逑图２－２该可逆逻辑函数的双射关系逡逑式（２．３）为图２－１所示的可逆逻辑网络的置换表示，，该式的含义是：ｆ（０）＝２，邋ｆ（ｌ）＝６，…，逡逑ｆ（７）＝４。逡逑／０逦１逦２逦３逦４逦５逦６逦７＼逡逑ａ＝邋（２逦６逦０逦１逦７逦３逦５逦４）逦（２３）逡逑我们论文的主要内容就是基于可逆逻辑网络（可逆逻辑函数）的置换这一表示形式的逡逑性质，这一小节是这篇论文的重要理论基础。下一小结为大家介绍可逆逻辑网络构成的基逡逑本元素一可逆逻辑门。逡逑２．３可逆逻辑门逡逑可逆逻辑门是逻辑网络的基本元素。可逆逻辑门的级联，可以构造形成可逆网络，用逡逑以实现复杂的逻辑和算术运算。也就是说，上一节中我们所说的可逆逻辑函数是用可逆逻逡逑辑门来实现的，可逆逻辑门也对应着相应的可逆逻辑函数。可逆逻辑门所对应的逻辑函数逡逑一定是实现双射。即可逆逻辑门的输入和输出必须有一个一对的映射关系，输出可由输入逡逑唯一确定，同样它的输入也能由输出唯一确定。逡逑因此，设一个（ｍ，ｎ）的逻辑门有ｍ个输入和ｎ个输出，ｍ＝ｎ是一个逻辑门可逆的必要逡逑条件。如果一个逻辑门是可逆的
【学位授予单位】：扬州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP38

【相似文献】