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

Reversible network cascade based on permutation group

作　　者：张义清[1] 管致锦[2] 吕彦明[1] 

机构地区：[1]南通大学理学院,江苏南通226019 [2]南京航空航天大学信息科学与技术学院,江苏南京210016

出　　处：《兰州理工大学学报》2008年第4期101-104,共4页Journal of Lanzhou University of Technology

基　　金：国家自然科学基金(60673127);江苏省高校自然科学基金(05KJB520107)

摘　　要：通过分析可逆门逻辑网络与置换群的等价关系,把可逆门网络级联转化为对称群的轮换问题.证明了任何一个相邻3轮换置换(u,s,t)可以通过4个(n-2)-CNOT门和至少2n位的NOT门生成,以此n位的偶数二元可逆网络可通过NOT和2-CNOT门构造.给出了通过对称群轮换置换级联可逆网络的方法,实例验证了该方法的正确性.结果表明,该方法没有垃圾信息输出,同时在可逆门转换方面更加灵活有效.By means of analyzing the equivalence relation of reversible gate logic network to permutation group, the reversible gate network cascade was converted into the cycle of symmetric group. It was verified that any neighboring 3-cycle permutation （u, s, t） could be generated by four （n=2）-CNOT gates and 2n NOT gates at least. Thus,n-digit even bivariate reversible network could be constructed with NOT and 2-CNOT gates. A constructing method of reversible network cascade was proposed by means of permutation of cycle of symmetric group. The validity of this method was verified by an example. The result showed that the network was without garbage output. Meantime, the trigger of the reversible gate was even more flexible and effective.

关 键 词：可逆逻辑门 置换群 轮换 网络级联 

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