Regularity and Symmetry as a Base for Efficient Realization of Reversible Logic Circuits

Marek A. Perkowski, Paweł Kerntopf, Andrzej Buller, Malgorzata Chrzanowska-Jeske, Alan Mishchenko, Xiaoyu Song B, Anas N. Al‐Rabadi, L. Jóźwiak, A. Coppola

Published Jan 1, 2001• 53 citations

OpenAlex

Abstract

We introduce a Reversible Programmable Gate Array (RPGA) based on regular structure to realize binary functions in reversible logic. This structure, called a 2 * 2 Net Structure, allows for more efficient realization of symmetric functions than the methods shown by previous authors. In addition, it realizes many non-symmetric functions even without variable repetition. Our synthesis method to RPGAs allows to realize arbitrary symmetric function in a completely regular structure of reversible gates with smaller “garbage” than the previously presented papers. Because every Boolean function is symmetrizable by repeating input variables, our method is applicable to arbitrary multi-input, multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of garbage gate outputs. The method can be also used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.

Related papers

Regular realization of symmetric functions using reversible logic

Marek A. Perkowski, Paweł Kerntopf, Andrzej Buller +7 more

Reversible logic is of increasing importance to many future computer technologies. We introduce a regular structure to realize symmetric functions in binary reversible logic. This structure, called a 2*2 net structure, allows for a more efficient realization of symmetric functions than the methods introduced by the other authors. Our synthesis method allows us to realize arbitrary symmetric function in a completely regular structure of reversible gates with relatively little "garbage". Because every Boolean function can be made symmetric by repeating input variables, our method is applicable to arbitrary multi-input multi-output Boolean functions and realizes such arbitrary function in a circuit with a relatively small number of additional gate outputs. The method can also be used in classical logic. Its advantages in terms of numbers of gates and inputs/outputs are especially seen for symmetric or incompletely specified functions with many outputs.

Euromicro Conference on Digital System Design (DSD)Nov 13, 200251 citations

Efficient reversible and quantum implementations of symmetric Boolean functions

D. Maslov

It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.

IEE Proceedings - Circuits Devices and SystemsJan 1, 200616 citations

Reversible Synthesis of Symmetric Functions with a Simple Regular Structure and Easy Testability

Arighna Deb, Debesh Kumar Das, Hafizur Rahaman +3 more

In this article, we introduce a novel method of synthesizing symmetric Boolean functions with reversible logic gates. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of circuit inputs may increase slightly when such cascades are used. In order to reduce their number, we next propose a postsynthesis optimization phase that allows judicious reuse of circuit lines. In addition to offering a cost-effective synthesis methodology, the proposed reversible logic structure supports elegant testability properties. With respect to all single or partial missing gate faults (SMGFs and PMGFs), or repeated gate faults (RGFs) in such an n -input circuit module, we show that it admits a universal test set of constant cardinality (=3) for any value of n . Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.

ACM Journal on Emerging Technologies in Computing SystemsJun 27, 20164 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOct 30, 2006379 citations

Reversible synthesis of symmetric boolean functions based on unate decomposition

Arighna Deb, Debesh Kumar Das, Hafizur Rahaman +1 more

In this paper, we introduce a new method to realize symmetric Boolean functions with reversible logic based on unate decomposition. In contrast to earlier synthesis methods, our solution uses a simpler circuit structure of reversible gates, which enables a significant reduction with respect to quantum cost. The resulting design offers an improved solution to reversible synthesis of symmetric Boolean functions.

ACM Great Lakes Symposium on VLSI (GLSVLSI)May 2, 20134 citations

Synthesis of quantum arrays with low quantum costs from Kronecker Functional Lattice Diagrams

Dipal Shah, Marek A. Perkowski

Reversible logic has many applications such as Quantum computing, low power CMOS circuit design, Optical computing. Hence reversible logic synthesis has attracted attention especially in quantum computing community. A logic function is reversible if it is a one-to-one mapping between input and output vectors. In this paper we present a new approach to synthesis of reversible circuits using Kronecker Functional Lattice Diagrams. Unlike other contemporary algorithms for synthesis of reversible function that use n × n Toffoli gates, our method invariably synthesizes functions using only 3×3 Toffoli gates, Feynman gates and NOT gates. This reduces the quantum cost. Our method adds small cost by adding extra ancilla bits. Moreover, our circuits are always (4-neighbors) regular, which is an asset when they are mapped to 2-Dimensional arrays in Ion Trap (quantum) technology.

IEEE Congress on Evolutionary Computation (CEC)Jul 1, 20104 citations