基于置换群的可逆逻辑门网络级联

n输入n输出可逆逻辑门的级联构成一个群，它与对称群Sτ同构。本文研究了生成Toffoli门集合的可逆逻辑门数的特点，证明了任意置换Sn可以由n-轮换δ和一个置换τ=（ij，ik）生成，同时证明了相邻2一轮换可由至多两个NOT门在不增加额外信息位的情况下生成。最后提出了一个基于上述理论的可逆逻辑门网络级联算法，并通过实例验证了该算法的正确性。

REVERSIBLE LOGIC GATE NETWORK CASCADE BASED ON PERMUTATION GROUP

The cascade of reversible logic gate network with n inputs and n outputs forms a group isomorphic to the symmetric group S2n.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 δ 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.