Reversible Circuit Synthesis Using Binary Decision Diagrams

K. Podlaski (Univ. Lodz, Poland)

Reversible circuit synthesis is an important branch of low power consumption circuit design. The idea of a logic circuit with no losses of information during computation has impact on power consumption and on the other hand makes the use of classical circuit synthesis algorithms impossible. In the area of reversible circuit design there is still lack of good algorithms. During last 15 years many heuristic algorithms have been developed, however, they construct circuit implementations which are far from optimal. In the paper the new implementation of known transformation based algorithm is presented. The existing transfromation based algorithm uses truth table during computation, this brings important memory restrictions on the algorithm. On the other hand any boolean unction can be represented using Binary Decision Diagrams (BBD), this representation is more compact and uses less memory than truth table representation. Presented new implementation of transformation based algorithm can be used for synthesis of reversible functions for much bigger functions than for original version of the algorithm.