IEEE International Symposium on Multiple-Valued Logic (ISMVL)

Ternary Galois field expansions for reversible logic and Kronecker decision diagrams for ternary GFSOP minimization [Galois field sum of products]

Mozammel H. A. Khan, Marek A. Perkowski, Mujibur R. Khan

Published Sep 28, 2004• 21 citations

Abstract

Ternary Galois field sum of products (TGFSOP) expressions are found to be good choice for ternary reversible, and especially quantum, logic design. In this paper, we propose 16 ternary Galois field expansions (TGFE) and introduce three ternary Galois field decision diagrams (TGFDD) using the proposed TGFEs, which are useful for reversible and quantum logic design. We also propose a heuristic for creating TGFDDs and a method for flattening the TGFDDs for determining TGFSOP expressions. We provide experimental results to show the effectiveness of the developed methods.

DOI: 10.1109/ismvl.2004.1319921

Related papers

GFSOP-based ternary quantum logic synthesis

Mozammel H. A. Khan

Quantum technology is one of the most promising technologies for future computing systems, since quantum algorithms solve problems much more efficiently than classical algorithms. All quantum algorithms are made up of quantum logic circuits. A quantum logic circuit is made up of quantum gates (reversible in nature) and is designed using reversible logic synthesis methods. For a given Hilbert space, ternary quantum system requires 0.63 times qutrits than the corresponding number of qubits. Thus, the ternary quantum system provides a much more compact and efficient information encoding. Beside other technologies, ternary quantum logic system can be realized using photon polarization. These advantages of ternary quantum system open avenue for developing ternary quantum algorithms. Galois field sum of products (GFSOP) based synthesis of ternary quantum logic circuit is the most practical approach, since any ternary logic function with many inputs can be represented as GFSOP expression and the GFSOP expression can be implemented as cascade of ternary quantum gates. Here we discuss minimization of ternary logic function as GFSOP expression using quantuminspired evolutionary algorithm. We also discuss a method of realization of ternary GFSOP expression using ternary quantum gates. Experimental results are given to show the effectiveness of the ternary GFSOP minimization technique.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEAug 19, 201014 citations

GF(4) Based Synthesis of Quaternary Reversible/Quantum Logic Circuits.

Mozammel H. A. Khan, Marek A. Perkowski

Galois field sum of products (GFSOP) has been found to be very promising for reversible/quantum implementation of multiplevalued logic. In this paper, we show nine quaternary Galois field expansions, using which quaternary Galois field decision diagrams (QGFDD) can be constructed. Flattening of the QGFDD generates quaternary GFSOP (QGFSOP). These QGFSOP can be implemented as cascade of quaternary 1-qudit gates and multi-qudit Feynman and Toffoli gates. We also show the realization of quaternary Feynman and Toffoli gates using liquid ion-trap realizable 1-qudit gates and 2-qudit Muthukrishnan-Stroud gates. Besides the quaternary functions, this approach can also be used for synthesis of encoded binary functions by grouping 2-bits together into quaternary value. For this purpose, we show binary-to-quaternary encoder and quaternary-to-binary decoder circuits using quaternary 1-qudit gates and 2-qudit Muthukrishnan-Stroud gates.

Jan 1, 20072 citations

Minimized reversible/quantum synthesis of non-reversible quinary logic function

Mozammel H. A. Khan, Raqibul Hasan

Reversible/quantum multiple-valued logic circuit has several advantages over reversible/quantum binary logic circuit. Galois field sum of products (GFSOP) based synthesis of multiple-valued logic function is more promising and practical than other approaches. In this paper, we have developed 196 Galois field expansions (GFE) and have proposed a method of minimization of GFSOP expression for non-reversible quinary logic function using the application of these GFEs. We have also proposed a method of realization of quinary GFSOP expression as cascade of quinary reversible/quantum gates. Experimental results with 26 functions having up to six inputs and two outputs show that a significant minimization can be achieved using the proposed minimization method.

International Conference on Computer and Information Technology (ICCIT)Dec 1, 20110 citations

Ternary max-min algebra for representation of reversible logic functions

Musharrat Khan, Jacqueline E. Rice

Ternary reversible logic functions are generally represented as ternary Galois field sum of products (TGFSOP) expressions and the TGFSOP expressions are mapped to reversible circuits using cascades of Feynman and Toffoli gates. Although a ternary logic function with a large number of variables can be minimized as a TGFSOP expression, the process is computationally expensive and the resulting reversible circuit tends to have a high quantum cost and ancilla inputs. To overcome these limitations, in this work we propose a new method of representing ternary reversible logic functions as Max of Min-terms (Max-Min) expressions, which can be mapped to a reversible circuit using multiple-controlled unary gates requiring lower quantum cost and fewer ancilla inputs. We propose a map-based minimization method for Max-Min expressions of up to four variables focusing on restrictions of the reversible circuit mapping technique.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20168 citations

GF(4) Based Synthesis of Quaternary Reversible/Quantum Logic Circuits

Mozammel H. A. Khan, Marek A. Perkowski

Galois field sum of products (GFSOP) has been found to be very promising for reversible/quantum implementation of multiple-valued logic. In this paper, we show ten quaternary Galois field expansions, using which quaternary Galois field decision diagrams (QGFDD) can be constructed. Flattening of the QGFDD generates quaternary GFSOP (QGFSOP). These QGFSOP can be implemented as cascade of quaternary 1-qudit gates and multi-qudit Feynman and Toffoli gates. We also show the realization of quaternary Feynman and Toffoli gates using liquid ion-trap realizable 1-qudit gates and 2-qudit Muthukrishnan-Stroud gates. Besides the quaternary functions, this approach can also be used for synthesis of encoded binary functions by grouping 2-bits together into quaternary value. For this purpose, we show binary-to-quaternary encoder and quaternary-to- binary decoder circuits using quaternary 1-quidit gates and 2-qudit Muthukrishnan-Stroud gates.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 200730 citations

Synthesis of reversible logic functions using ternary Max-Min algebra

Musharrat Khan, Jacqueline E. Rice

Ternary reversible circuits are normally realized as Toffoli cascades using ternary Galois field sum of products (TGFSOP) expressions. In this work we propose a new method for realization of ternary reversible circuits using ternary Max-Min expressions. The proposed method uses ternary multiple-controlled unary gates to map Max-Min expression into reversible circuit. We also present techniques for realizations of multiple-controlled unary gates using M-S gates at the quantum level. Preliminary results show that the proposed method produces better results than TGFSOP-based method in terms of both quantum cost and ancilla inputs.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20167 citations