基本信息
- 项目名称：
- 基于可逆逻辑门编码和变进制数的可逆网络级联
- 来源：
- 第十一届“挑战杯”国赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 作品提出了基于可逆逻辑门编码和变进制数的可逆门网络级联方法。该方法按垂直线条数从小到大，控制位个数从小到大自动构造不同输出向量所对应网络并且能够自动生成所需的单个可逆网路或批量连续序号可逆网络。通过变进制数与可逆网络输出向量的对应关系，能够快速地找到可逆网络输出向量所对应的序号，精准地判断输出向量是否已出现，减少了搜索的次数和搜索空间。与已有的Benchmark例题比较，控制位数、可逆逻辑门数得到一定改善。 本作品的研究结果可以直接应用于低功耗电路的可逆逻辑设计和可逆逻辑门库的构建，其中可逆逻辑门网络自动生成算法已成为可逆逻辑设计平台的组成部分。
- 详细介绍：
- 可逆门的逻辑级联是可逆逻辑综合的重要组成部分。可逆逻辑综合是一个新兴的研究领域，它是可逆计算研究的主要内容，并在低功耗电路设计、信息安全、纳米技术等其它一些现代科学领域有着重要应用。 由于构造可逆逻辑门网络有很强的限制，因此一直没有非常系统有效的设计方法，网络构造的规模也得不到提高。本作品通过对网络的输入/输出位、垂直线及水平线编号，构造出可逆网络的基本元素，同时基于变进制数，给出了可逆网络输出向量与序号之间的对应方法，调用可逆网络的构造函数自动构建网络。该构造函数按垂直线条数从小到大，控制位个数从小到大构造不同输出向量所对应网络，自动生成所需的单个可逆网络或批量连续序号可逆网络。而通过使用变进制数的方法，能够快速、方便地找到可逆网络输出向量所对应的序号。这种命名方法和变进制的灵活使用在解决可逆网络级联的问题中是首次使用，并且较好地解决了可逆网络级联规模小的问题和网络存储问题。 可逆逻辑门级联比较多的集中在3-4输入/输出的可逆网络中，而本作品能够自动生成3输入/输出以上的可逆网络。由于n变量可逆逻辑函数的数量是(2^n)!，目前已知的利用穷尽搜索法对所有3变量可逆逻辑函数最小化的技术还无法实现相关的存储。采用群论作为分析工具应用到可逆门的级联中，在内存需求和算法效率上有了一定改善，但还需要进行大量的排序，无法实现规模较大的可逆网络级联。本作品实现了全部1-4输入/输出和部分5输入/输出Benchmark例题的Toffoli可逆逻辑门网络的级联和相关存储。 在D.Maslov等人提出的模板方法中，由于模板种类的限制，只能实现部分可逆逻辑网络，无法实现全部可逆逻辑门网络的级联，本作品能够支持生成批量甚至是全部的可逆网络，并能精准地判断输出向量是否曾出现，大大减小了搜索空间和搜索次数。与Benchmark例题比较，在可逆逻辑门的数量和控制位的数量上都有一定的优势（见论文中相关结果分析和测试报告）。 本作品的研究结果可以直接应用于低功耗电路的可逆逻辑设计和可逆逻辑门库的构建，其中可逆逻辑门网络自动生成算法已成为可逆逻辑设计平台的组成部分，并实现了相应的可逆网络自动生成演示系统。 本作品的重要组成部分“The Generation of the Reversible Gate Network-based the Variable System Numbers”（基于变进制数可逆门网络的生成）和“The Reversible Network Cascade Based on Reversible Logic Gate Coding Method”（基于可逆逻辑门编码方法的可逆网络级联）均由本参赛作品的主要学生完成，已分别被“The 5th International Conference on Natural Computation (ICNC'09)”（2009年第五届自然计算国际学术会议）和“Fifth International Conference on Information Assurance and Security (IAS-2009)”（2009年第五届信息保障与安全国际会议）录用，并将在IEEE Computer Society出版。
作品专业信息
撰写目的和基本思路
- 目的：能精准判断可逆网络级联过程中状态空间是否出现，减少搜索次数和空间，自动生成可逆网络，克服网络规模小、级联代价高等问题。 基本思路：首先以Toffoli门为基础，构建可逆网络模型；对可逆网络的输入/输出位、垂直线及水平线编号；构造出具有不同意义的Toffoli门作为基本元素；给出基于变进制数的可逆网络输出向量序号表示方法；调用基本元素生成可逆网络并进行相应的实验验证。
科学性、先进性及独特之处
- 科学性：本作品为可逆逻辑综合的重要组成部分。研究过程中提出了相关定理和算法，通过国际标准的Benchmark例题验证算法的正确性和有效性。 先进性：可逆逻辑门级联比较多的集中在3-4输入/输出网络，本作品实现了1-4输入/输出网络和5输入/输出Benchmark例题。 独特之处：能自动生成所需的单个或批量可逆网络，突破了模板种类限制，较好地解决了网络级联规模小和存储问题。
应用价值和现实意义
- 可逆门网络级联是一个新兴的研究领域，它是量子计算和量子信息技术研究的重要组成部分，并在低功耗电路设计、信息安全、纳米技术等其它一些现代科学领域有着重要应用。 本课题的研究结果可以直接应用于低功耗电路的可逆逻辑设计和可逆逻辑门库的构建，其中3输入/输出的可逆网络的部分结果与可逆全加器的逻辑部件相对应。
学术论文摘要
- 本文提出了基于可逆逻辑门编码和变进制数的可逆网络级联方法。该方法按垂直线条数从小到大，控制位个数从小到大自动构造不同输出向量所对应的网络并且能够自动生成所需的单个可逆网路或批量连续序号可逆网络。通过变进制数与可逆网络输出向量的对应关系，能够快速地找到可逆网络输出向量所对应的序号，精准地判断输出向量是否已出现，大大减少了搜索的次数和搜索空间。与已有的Benchmark例题比较，控制位数、可逆逻辑门数得到一定改善。
获奖情况
- 本作品的重要组成部分"The Generation of the Reversible Gate Network-based the Variable System Numbers"(基于变进制数可逆门网络的生成)和"The Reversible Network Cascade Based on Reversible Logic Gate Coding Method"(基于可逆逻辑门编码方法的可逆网络级联)均由本参赛作品的主要学生完成，已分别被"The 5th International Conference on Natural Computation (ICNC'09)"(2009年第五届自然计算国际学术会议)和"Fifth International Conference on Information Assurance and Security (IAS-2009)"(2009年第五届信息保障与安全国际会议)录用，并将在IEEE Computer Society出版。 本作品获得某大学第二届大学生课外学术科技作品竞赛自然科学类论文一等奖。
鉴定结果
- “挑战杯”江苏省选拔赛专家意见：“可逆逻辑电路设计是新的方向，有广泛应用前景，本作品取得一定的研究成果”。
参考文献
- [1] 李志强，陈汉武，徐宝文，刘文杰，基于HaSH表的量子可逆逻辑电路综合的快速算法，计算机研究与发展，2008，45（12）:2162-2171. [2] Yang G., Song X W, Hung N. Perkowski, Group theory based synthesis of binary reversible circuits. The 3rd Annual Conference on Theory and Applications of Models of Computation(TAMC), Anaheim California, USA: IEEE/ACM, 2006, p. 365–374. [3] D. Maslov, G.W. Dueck, and D.M. Miller. Synthesis of Fridkin-Toffoli reversible networks. IEEE Transactions on VLSI systems, 2005, 13(6): 765-769. [4] D. Maslov , G. W. Dueck , D. M. Miller, Techniques for the synthesis of reversible Toffoli networks, ACM Transactions on Design Automation of Electronic Systems (TODAES), 2007(12): 42-46. [5] Pawel Kerntopf. A new heuristic algorithm for reversible logic synthesis. DAC 2004, p.834-837. [6] K. Iwama, Y. Kambayashi, S. Yamashita. Transformation rules for designing CNOT-based quantum circuits. Design Automation Conference, New Orleans, Louisiana, USA, ACM, 2002(149): 419-424.
同类课题研究水平概述
- 可逆逻辑门网络生成问题的研究是随着近些年量子计算和量子信息以及集成电路等技术的需求和发展才被真正给予重视，尚处于发展阶段。 尽管近几年来不断有新的可逆门级联模型和可逆门网络级联算法的研究成果出现，但目前可逆门级联模型及其相关算法所能实现的可逆门网络仍然存在着网络规模小、级联代价高、级联过程中时空复杂度高等一系列问题。 Shende提出了3输入变量可逆门的网络级联方法，M.Perkowski首先把分解因式方法用到可逆逻辑设计上。Iwama 等人给出了CNOT门的网络级联规则，分析了CNOT 门序列顺序变化的规律，其输出是标准型的Toffoli门，这个标准型是用PPRM直接实现可逆,同时也是一个Zhegalkin多项式。Iwama证明了任何一个可逆网络都能通过确定的可逆操作得到一个标准型。这样，标准型可以转化为一个最小化可逆逻辑门网络。遗憾的是，他们没有给出任何通过变换集简化可逆逻辑门网络的方法。 Shende等人利用穷尽搜索法对所有3变量可逆逻辑函数最小化进行了研究，结果表明，n变量可逆逻辑函数的数量是(2^n)!，用他们的技术还无法实现相关的存储。G.Yang等人尝试采用群论作为分析工具应用到可逆门的级联中，在内存需求和算法效率上有了一定改善，但还需要进行大量的排序，只能实现部分可逆逻辑网络，而且网络级联的规模较小。Dmitri Maslov等人提出了模板的方法进行可逆逻辑门级联，由于模板种类的限制，无法实现全部可逆逻辑门网络的级联。 我国在可逆逻辑门级联的研究也取得了一些重要成果。东南大学陈汉武等人实现了4输入/输出可逆逻辑门网络的级联。 本作品实现了全部1-4输入/输出可逆网络和部分5输入/输出Benchmark例题的Toffoli可逆逻辑门网络的级联和相关存储，与Benchmark例题比较，在可逆逻辑门的数量和控制位的数量上都有一定的优势。
