Contributions To Several Issues Of Logic Synthesis In Reversible Computing

Reversible computing is considered as a rapidly developing research area. It is of increasing importance to many future coputer technologies. Reversible logic synthesis is an important part of reversible computing. Interest in reversible logic is sparked by its necessity in low power dispation dissipation and quantum information technologies. Reversible implementations are also found in cryptography, Information security, nanotechnology. The basis of reversible computation is reversible logic synthesis. The theory of the reversible computing is based on invertible primitives and composition rules that invertibility. An important component of the reversible computing is reversible synthesis. Fan-outs and loops are not permitted due to the target technology. Outputs from one gate are used as inputs to the next gate. This results in a high degree of interdependence among gates. Therefore, reversible logic synthesis have many research challenges remain, e.g., the structure of reversible network, and size of reversible logic synthesis, and cost of reversible logic synthesis and so on. The major contributions in this paper are that:1. On the cascade of reversible logic gate: An in-depth is gaven to relationship of the between output of homeotypic Toffoli gate series and number of Toffoli gate. An enumeration of reversible network in Toffoli gate series is derived. The relationship of number of bit-vector with bit-number of bit-vectio for Hamming weight H ( w)≥n? 1 in the input vector (0,1,…, 2 n ?1). A method of calculation is presented for kinds of transform of network in Toffoli gate series. Three reversible logic gate cascade method are proposed respectively for the Toffoli gate network of series connection and parallel connection and mix connection. Make use of some method to structure a reversible network cascade system, and completeness and effectiveness of the reversible metwork system are validated.2. A reversible network cascade model is provided. This model can be controlled with positive/negative, and the algorithm of reversible synthesis is proposed for the model. Using the approach, we create a program and run it to synthesis the NCMC Benchmark functions with less than twelve variables. The experimental results show a proper improvement for the number of garbage outputs and number of gates, and the method can be minimize the number of NOTs in reversible network.3. On method of reversible logic synthesis, the following three researches are carried out.(1) A logic function reversible synthesis method is presented. In the method, first, minimizing a standard logic function for obtained a SOP of optimization. This facilitates efficient conversion between SOP and fixed polarity Reed-Muller forms. The results show that the algorithm is efficient in terms of time and space. Next, we present the synthesis algorithm for reversible functions. It uses Fixed Polarity Reed-Muller decomposition at each stage to synthesize the function as a network of Toffoli gates. The key contribution of the work is that the heuristic finds very good solutions for reversible functions with a large number of inputs. Some examples of NCMC benchmarks with a large number of variables were also presented to demonstrate the suitability of the algorithm for synthesizing complex functions.(2) Reversible logic gate network with n inputs and n outputs together with the action of cascading form a group, isomorphic to the symmetric group on {1, 2, 3, , 2 n }. Therefore, we investigate a number of gates from the set of all generalized Toffoli gates are considered. A proof is presented for any transposition S ncan be generated by any n-cycleδand a transpositionτtogether. It show that any neighboring 2-cycle permutation can be generated by at most 2 NOT gates without ancilla bit. A reversible logic gate networks cascade algorithm is proposed based on above theory. We give a reversible logic gate network cascade example based on this algorithm, which shows that the correctness of the algorithm.(3) An algorithm of iterative construct reversible network by cascade operation is presented. The cascade operation is implemented with Boolean permutation. We proposed two important decision condition of Boolean permutation, and changed to choose balance function of suffice Boolean permutation condition for the problem of construct reversible network. The result of algorithm analysis show that it is can be implemented fleetly. Two important decision condition of Boolean permutation were proposed. A method is presented constructed an orthomorphic permutation of n variables with two orthomorphic permutation of n-2 variables. A provable constructive reversible network cascade algorithm is derived by orthomorphics permutation operation. The analysis of algorithm is easy express implements on complexity.4. On the application of reversible computing. The ALU is major power hungry operations in the cryptosystem. The use of reversible logic is proposed for designing the ALU of a cryptosystem. Ideally, reversible circuits dissipate zero energy. Thus, it would be of great significance to apply reversible logic to designing secure cryptosystems. In a prototype of a reversible ALU for a crypto-processor, reversible designs of adders and Montgomery multipliers are presented. The reversible designs of a carry propagate adder, four-to-two and five to two carry save adders are presented using a reversible PNC gate. One of the important properties of the PNC gate is that it can work singly as a reversible full adder. In order to design the reversible Montgomery multiplier, the reversible sequential circuits are also proposed which are integrated with the proposed adders to design a reversible modulo multiplier.