A library-based synthesis methodology for reversible logic

Synthesis of reversible logic has received significant attention in the recent years and many synthesis approaches for reversible circuits have been proposed so far. In this paper, a library-based synthesis method-ology for reversible circuits is proposed where a reversible specification is considered as a permutation comprising a set of cycles. To this end, a pre-synthesis optimization step is introduced to construct a reversible specification from an irreversible function. In addition, a cycle-based rep-resentation model is presented to be used as an intermediate format in the proposed synthesis methodology. The selected intermediate format serves as a focal point for all potential representation models. In order to synthesize a given function, a library containing seven building blocks is used where each building block is a cycle of length less than 6. To synthesize large cycles, we also propose a decomposition algo-rithm which produces all possible minimal and inequivalent factorizations for a given cycle of length greater than 5. All decompositions contain the maximum number of disjoint cycles. The generated decompositions are used in conjunction with a novel cycle assignment algorithm which is proposed based on the graph matching problem to select the best possible cycle pairs. Then, each pair is synthesized by using the available compo-nents of the library. The decomposition algorithm together with the cycle assignment method are considered as a binding method which selects a building block from the library for each cycle. Finally, a post-synthesis optimization step is introduced to optimize the synthesis results in terms of different costs. To analyze the proposed methodology, various experiments are per-formed. Our analyses on the available reversible benchmark functions re-veal that the proposed library-based synthesis methodology can produce low-cost circuits in some cases compared with the current approaches. The proposed methodology always converges and it typically synthesizes a give function fast. No garbage line is used for even permutations. 1 a