MANY-VALUED GALOIS SHANNON-DAVIO TREES AND THEIR COMPLEXITY

Anas N. Al-Rabadi

DOI Number
Complexity, Galois Field Sum-of-Product (GFSOP), Galois Forms, Inclusive Forms, Multi-Valued Logic, Quaternary Logic, Shannon-Davio (S/D) Trees
First page
701
Last page
720

Abstract


The idea of Shannon-Davio (S/D) trees for binary logic is a general concept that found applications in the Sum-Of-Product (SOP) minimization and the generation of new diagrams and canonical forms. Extended S/D trees are used to generate forms that include a minimum Galois Field Sum-of-Products (GFSOP) forms. Since there exist many applications of Galois field of quaternary radix especially that GF(4) is considered as an important extension of GF(2), the extension of the S/D trees to GF(4) is presented here. A general formula to calculate the number of Inclusive Forms (IFs) per variable order for an arbitrary Galois field radix and arbitrary number of variables is derived and introduced. A new fast method to count the number of IFs for an arbitrary Galois radix and functions of two variables is also introduced; the IFn,2 Triangles. The results introduced in this work can be useful for the creation of an efficient GFSOP minimizer for Galois logic and in other applications such as in reversible logic synthesis.


Keywords

10.2298/FUEE1604701A

Full Text:

PDF

References


S. B. Akers, “Binary Decision Diagrams,” IEEE Trans. Comp., Vol. C-27, No. 6, pp. 509-516, June 1978.

A. N. Al-Rabadi, Reversible Logic Synthesis: From Fundamentals to Quantum Computing, Springer-Verlag, 2004.

A. N. Al-Rabadi, “Reversible Fast Permutation Transforms for Quantum Circuit Synthesis,” Proc. IEEE Int.

Symposium on Multiple-Valued Logic (ISMVL), Toronto, 2004, pp. 81-86.

A. N. Al-Rabadi, “Quantum Circuit Synthesis Using Classes of GF(3) Reversible Fast Spectral Transforms,” Proc.

IEEE Int. Symposium on Multiple-Valued Logic (ISMVL), Toronto, 2004, pp. 87-93.

A. N. Al-Rabadi, “Quantum Logic Circuit Design of Many-Valued Galois Reversible Expansions and Fast

Transforms,” J. Circuits, Systems, and Computers, World Scientific, Singapore, Vol. 16, No. 5, pp. 641 - 671, 2007.

A. N. Al-Rabadi, “Representations, Operations, and Applications of Switching Circuits in the Reversible and

Quantum Spaces,” Facta Universitatis (FU) – Electronics and Energetics, Vol. 20, No. 3, pp. 507 – 539, 2007.

R. E. Bryant, “Graph-based Algorithms for Boolean Functions Manipulation,” IEEE Trans. on Comp., Vol. C-35,

No.8, pp. 667-691, 1986.

M. Cohn, Switching Function Canonical Form over Integer Fields, Ph.D. Dissertation, Harvard University, 1960.

R. Drechsler, A. Sarabi, M. Theobald, B. Becker, and M. A. Perkowski, “Efficient Representation and Manipulation

of Switching Functions Based on Ordered Kronecker Functional Decision Diagrams,” Proc. DAC, 1994, pp. 415-419.

M. Escobar and F. Somenzi, “Synthesis of AND/EXOR Expressions via Satisfiability,” Proc. Reed-Muller, 1995,

pp. 80-87.

B. J. Falkowski and S. Rahardja, “Classification and Properties of Fast Linearly Independent Logic

Transformations,” IEEE Trans. on Circuits and Systems-II, Vol. 44, No. 8, pp. 646-655, August 1997.

B. Falkowski and L.-S. Lim, “Gray Scale Image Compression Based on Multiple-Valued Input Binary Functions,

Walsh and Reed-Muller Spectra,” Proc. ISMVL, 2000, pp. 279-284.

H. Fujiwara, Logic Testing and Design for Testability, MIT Press, 1985.

D. H. Green, “Families of Reed-Muller Canonical Forms,” Int. J. of Electronics, No. 2, pp. 259-280, 1991.

S. Hassoun, T. Sasao, and R. Brayton (editors), Logic Synthesis and Verification, Kluwer Acad. Publishers, 2001.

M. Helliwell and M. A. Perkowski, “A Fast Algorithm to Minimize Multi-Output Mixed-Polarity Generalized

Reed-Muller Forms,” Proc. Design Automation Conference, 1988, pp. 427-432.

S. L. Hurst, D. M. Miller, and J. C. Muzio, Spectral Techniques in Digital Logic, Academic Press Inc., 1985.

M. G. Karpovski, Finite Orthogonal Series in the Design of Digital Devices, Wiley, 1976.

C. Y. Lee, “Representation of Switching Circuits by Binary Decision Diagrams,” Bell Syst. Tech. J., Vol. 38,

pp. 985-999, 1959.

C. Moraga, “Ternary Spectral Logic,” Proc. ISMVL, 1977, pp. 7-12, 1977.

J. C. Muzio and T. Wesselkamper, Multiple-Valued Switching Theory, Adam-Hilger, 1985.

D. K. Pradhan, “Universal Test Sets for Multiple Fault Detection in AND-EXOR Arrays,” IEEE Trans. Comp.,

Vol. 27, pp. 181-187, 1978.

D. K. Pradhan, Fault-Tolerant Computing: Theory and Techniques, Vol. I, Prentice-Hall, 1987.

S. M. Reddy, “Easily Testable Realizations of Logic Functions,” IEEE Trans. Comp., C-21, pp. 1183-1188, 1972.

T. Sasao (editor), Logic Synthesis and Optimization, Kluwer Academic Publishers, 1993.

T. Sasao, “EXMIN2: A Simplified Algorithm for Exclusive-OR-Sum-Of-Products Expressions for Muliptle-Valued

Input Two-Valued Output Functions,” IEEE Trans. Computer Aided Design, Vol. 12, No. 5, pp. 621-632, 1993.

T. Sasao and M. Fujita (editors), Representations of Discrete Functions, Kluwer Academic Publishers, 1996.

T. Sasao, “Easily Testable Realizations for Generalized Reed-Muller Expressions,” IEEE Trans. Comp., Vol. 46,

pp. 709-716, 1997.

T. Sasao, Switching Theory for Logic Synthesis, Kluwer Academic Publishers, 1999.

N. Song and M. Perkowski, “Minimization of Exclusive Sum of Products Expressions for Multi-Output Multiple-

Valued Input Incompletely Specified Functions,” IEEE Trans. Computer Aided Design, Vol. 15, pp. 285-395, 1996.

R. S. Stankovic, “Functional Decision Diagrams for Multiple-Valued Functions,” Proc. ISMVL, 1995, pp. 284-289.

R. S. Stankovic, Spectral Transform Decision Diagrams in Simple Questions and Simple Answers, Nauka, 1998.

R. S. Stankovic, C. Moraga, and J. T. Astola, “Reed-Muller Expressions in the Previous Decade,” Proc.

Reed-Muller, Starkville, 2001, pp. 7-26.

B. Steinbach and A. Mishchenko, “A New Approach to Exact ESOP Minimization,” Proc. Reed-Muller, Starkville,

, pp. 66-81.

S. N. Yanushkevich, Logic Differential Calculus in Multi-Valued Logic Design, Technical Univ. Szczecin, 1998.

I. Zhegalkin, “On the Techniques of Calculating Sentences in Symbolic Logic,” Math. Sb., Vol. 34, pp. 9-28, 1927.

I. Zhegalkin, “Arithmetic Representations for Symbolic Logic,” Math. Sb., Vol. 35, pp. 311-377, 1928.


Refbacks

  • There are currently no refbacks.


ISSN: 0353-3670 (Print)

ISSN: 2217-5997 (Online)

COBISS.SR-ID 12826626