Reversible Logic Synthesis Algorithm Based on Distribution of Error Bits

Synthesis of reversible logical functions is an important procedure for constructing reversible circuits. Truth table transformation based method is prevalent due to its understandability and easy implementation, but it contains many redundant gates in resulting circuit and needs further optimization work. To create a transformation based method, which will be able to generate preferable circuits without optimization, we have made a lot of effort. Firstly, we gave a definition of error bits in truth table, proposed and proved capacity of common reversible gates (NOT, CNOT, and Toffoli) to reduce error bits, investigated overall error distribution situations of all three-variable reversible logic functions, and extracted 79 different distribution patterns of error bits from these situations. According to whether exists certain gate used to reduce error according to the pattern only, we divided all patterns into two kinds. For the first kind, we determine specific heuristic rules to reduce error, and use this rule immediately when run into this pattern during synthesis. And we design trial rules for patterns of second kind, when encounter this pattern, we try to find gate to reduce error, if none is found, we find gate to convert this pattern to other pattern of same error count but more easily dealt with. Secondly, we generated optimal circuits for all three-variable reversible logic functions using exhausting method, and learned heuristic rules from optimal circuits by manual observation and analysis, these rules are used to determine which pattern should be converted to when run into patterns of second kind and reducing trial is failed. Thirdly, we presented a novel transformation based synthesis algorithm using extended generalized Toffoli gate family as gate library. The algorithm comprises two components. The first one is the preprocessing part which is used to add inverters to columns whose error count exceeds 2 n-1, and n is the variable number. The second one is the reversible logic synthesis part based on pattern recognition and conversion of error distribution in truth table. This synthesis part keeps recognizing current pattern and converting to another pattern with less error count as soon and early as possible, until there is no error in truth table. We recognize current error distribution pattern of truth table according to total error count, the number of rows and columns containing error bits, and intersection of error bits between different columns. We determine from current pattern which error pattern should be converted to by means of heuristic rules learned in advance. The time complexity of this reversible logic synthesis algorithm is O(n*2 n), which is superior to existing similar reversible logic synthesis method. Finally, we implemented our algorithms with Java programming language, and used the Java program to synthesize reversible logic functions. We generated circuits for all three-variable reversible logic functions, and calculated weighted average gate count of all the circuits. The weighted average gate count is 6.19 percent less than the best similar algorithm we can find, and the time needed is as short as the best algorithm. Furthermore, we generated circuits for seven different Benchmark functions from other papers. The result shows that circuits from our method has smaller size in gate count than other similar algorithms. © 2018, Science Press. All right reserved.