Research On ESOP-based Synthesis And Optimization Of Reversible Logic

Research on reversible logic is motivated mainly by possible applications in low-power CMOS and quantum computing.In the near future,irreversible operations in the circuits will become the main reason that restricts the development of high-performance integrated circuits.Quantum reversible circuits may replace traditional irreversible circuits to solve classical computing problems.As a key step in the design of reversible circuits,it is still an open problem to find the optimal or quasi-optimal synthesis method due to the complexity of the reversible synthesis.ESOP-based reversible synthesis method has attracted much attention for its ability to handle large functions over hundreds of variables,but there are high quantum cost and need to further optimization.This paper will focus on improving ESOP-based synthesis of reversible logic and the main contributions of the paper are listed as follows.1.Reed-Muller logic synthesis: There are several classes of AND-EXOR(Reed-Muller,RM)expansion.Since the complexity of RM logic directly affects the quantum cost of reversible circuits,the problem of optimizing reversible and quantum logic may be preprocessed in the RM domain.In view of the scalable synthesis of ESOP,an ESOP minimization method based on hierarchical hypercube is proposed by simplifying the optimal coverage search of global space to the simplest mapping of subspaces.Designing the general cube rewriting operations(i.e.conversion rules),a cubed-based method is presented to achieve extremely fast conversion between different canonical forms or between canonical forms and ESOPs.2.Synthesis and optimization of reversible logic using MPMCT gate: The cascade of mixed-polarity multiple-control Toffli gate(MPMCT)is functionally equivalent to an ESOP,it is difficult to obtain reversible circuits with lower quantum cost because the existing synthesis and optimization process has different goals before and after.For single-output function,an MPMCT network with lower quantum cost is obtained by temporarily changing the functionality of a given function,and an optimization technique based on pre-inserted CNOT gate is proposed.For multiple-output function,utilizing the structural similarity between different output functions and the common control lines between different cubes to construct the MPMCT network,an optimization technology based on shared strategies is proposed.Referring to the multi-level logic synthesis,an affine reversible cascade structure is introduced and a reversible synthesis method based on affine decomposition is proposed.3.Complexity analysis of reversible logic circuits: As an overall performance measure of different reversible synthesis methods,upper bounds for the number of reversible gates is important to understand the complexity of reversible circuits and quantum cost.In the reversible level,according to the linear upper bound of a single target(ST)gate,two decomposition methods(functional decomposition and ESOP product term cascade)are employed to map the ST gate to a cascade of Toffoli gates,thereby new upper bounds on the number of MPMCT gates are derived.In the mapping level,based on three map technologies of Barenco,Nielsen and Miller,the complexities of NCT(NOT-Feynman-Toffoli)in the MPMCT gate,ST gate and the general reversible circuit are given.4.Function realization of reversible logic circuits: Design of classical logic blocks using the concept of reversible gates is one of trending topic in reversible design.In view of the reversible circuit design for an adder(essential arithmetic part in all digital systems),a flagged BCD adder structure is proposed to improve calculation efficiency.A BCD adder using Binary to BCD converter is proposed to improve the cascading depth.To achieve BCD addition/subtraction function in a single reversible circuit,a unified n-digit reversible BCD adder/subtractor is constructed.The proposed four designs for reversible BCD adder have better performance than existing designs in terms of quantum cost,ancilla,gate counter and depth.The research results in this paper improve the efficiency of the reversible synthesis and reduce the quantum cost of the reversible circuit to some extent.It provides a technological basis for function realization of reversible logic circuits and reversible change of the traditional integrated circuit.