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 stu...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.展开更多
基金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.
