REVERSIBLE LOGIC GATE NETWORK CASCADE BASED ON PERMUTATION GROUP  

基于置换群的可逆逻辑门网络级联(英文)

作　　者：管致锦[1] 秦小麟[1] 戴华[1] 

机构地区：[1]南京航空航天大学信息科学与技术学院

出　　处：《Transactions of Nanjing University of Aeronautics and Astronautics》2008年第3期219-223,共5页南京航空航天大学学报（英文版）

基　　金：the National Natural Science Foundation of China(60673127);the National High Technology Research and Development Program of China(863Program)(2007AA01Z404)~~

摘　　要：The cascade of reversible logic gate network with n inputs and n outputs forms a group isomorphic to the symmetric group S2^n. Characteristics of a number of gates from the set of all generalized Toffoli gates are studied. Any permutation Sn is proved to be generated by a n-cycle 9 and a permutation τ= （ij,ik） together. It shows that any neighboring 2-cycle permutation can be generated by at most two NOT gates without ancilla bit. Based on the above theory, a cascade algorithm for reversible logic gate networks is proposed. A reversible example of logic gate network cascade is given to show the correctness of the algorithm.n输入n输出可逆逻辑门的级联构成一个群,它与对称群S2n同构。本文研究了生成Toffoli门集合的可逆逻辑门数的特点,证明了任意置换Sn可以由n-轮换δ和一个置换τ=(ij,ik)生成,同时证明了相邻2-轮换可由至多两个NOT门在不增加额外信息位的情况下生成。最后提出了一个基于上述理论的可逆逻辑门网络级联算法,并通过实例验证了该算法的正确性。

关 键 词：logic gates cascade connection permutation group 

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