Algorithm Based on Related Selection for Reversible Logic Synthesis

Reversible logic synthesis is an important part of reversible computing.To cope with the problem about how to cascade the reversible circuits and its optimization,this paper presents an algorithm based on related selection and its optimization algorithm for reversible logic synthesis.The reversible function,which is represented by truth table,is synthesized using several related target bits in order of truth table.The value of absolute chaos degree and relative chaos degree is calculated respectively,and selects the reversible logic gate with the principle of minimum chaos degree.The time complexity for the algorithm and its optimization algorithm is O(n²×2ⁿ),and its space complexity is O(n×2ⁿ),which is superior to the optimal algorithm's O(2n!).By using C+ + program language,the algorithm realizes the synthesis of the whole 3-variables functions and some part of 4-variables functions.In comparison with other algorithms for reversible logic synthesis,the results show some advantages in average gate number in the synthesis of the whole 3-variables functions and some examples in benchmark.