Reversible Logic Function Classifi-Cation And Equivalence Judgment

Reversible logic synthesis plays a key role in quantum computing and solvingcomputer power dissipation, and the amount of reversible logic functions has beenconcerned especially in reversible logic synthesis. The amount of ω-bit reversiblelogic functions is2ω!. The number of reversible logic functions dramatic increase withthe increase of variables, so it become extremely difficult to synthetize high bitreversible logic functions completely. Because of the templates can be used repeatedlythrough classification in reversible logic synthesis, the reversible logic functionclassification was suggested.In this thesis, the NP-NP equivalence of reversible logic functions is discussed.Then the novel algorithms of computing the number of equivalence class and animproved algorithm of equivalent judgment are proposed:1.The definition of NP-NP equivalence for reversible logic functions can be giventhrough extending the definition of NP-N equivalence for Boolean functions to thereversible logic functions, the NP-NP equivalence classes of reversible logic functionscan be converted to the double coset equivalence classes of permutation group by meansof one-to-one mapping reversible logic functions into permutation group.2. The properties of the subgroup generated by the permutation corresponding tothe logic NOT gate and Swap gate are studied, draw lots of nice collusions. Whichcombined with the formula of computing the number of the double coset in permutationgroup, a novel algorithm of computing the number of equivalence class is prosed. Thenumber of equivalence classes for3-bit reversible logic functions is at most computedwith the exhaust algorithm on a regular computer. But it is8-bit’s that can be computedwith this method on the same one.3. The judgment of NP-NP equivalence for3-bit reversible logic functions isstudied, Divide all3-varible Boolean functions that everyone of them has exactly fourminterms into five classes by their cofactor weight vectors, and calculate the fixedpolarity Reed-Muller Form of each class, the method are proposed. It is efficaciouswhen the reversible logic function is presented by a group of Boolean functions. 4. It is concluded that the judgment of NP-NP equivalence for reversible logic functions can’t be resolved in polynomial time through analysing its complexity. Because the problem of membership test in a permutation group can be resolved in polynomial time, the algorithms of the judgment of NP-NP equivalence for reversible logic functions can be improved by it. The complexity now is O(2ωω!p)less than O((2ω ω!)2).