AN EXTENDED GREEN-SASAO HIERARCHY OF CANONICAL TERNARY GALOIS FORMS AND UNIVERSAL LOGIC MODULES

Anas N. Al-Rabadi

DOI Number
10.2298/FUEE1701049A
First page
49
Last page
66

Abstract


A new extended Green-Sasao hierarchy of families and forms with a new sub-family for many-valued Reed-Muller logic is introduced. Recently, two families of binary canonical Reed-Muller forms, called Inclusive Forms (IFs) and Generalized Inclusive Forms (GIFs) have been proposed, where the second family was the first to include all minimum Exclusive Sum-Of-Products (ESOPs). In this paper, we propose, analogously to the binary case, two general families of canonical ternary Reed-Muller forms, called Ternary Inclusive Forms (TIFs) and their generalization of Ternary Generalized Inclusive Forms (TGIFs), where the second family includes minimum Galois Field Sum-Of-Products (GFSOPs) over ternary Galois field GF(3). One of the basic motivations in this work is the application of these TIFs and TGIFs to find the minimum GFSOP for many-valued input-output functions within logic synthesis, where a GFSOP minimizer based on IF polarity can be used to minimize the many-valued GFSOP expression for any given function. The realization of the presented S/D trees using Universal Logic Modules (ULMs) is also introduced, whereULMs are complete systems that can implement all possible logic functions utilizing the corresponding S/D expansions of many-valuedShannon and Davio spectral transforms.   

 


Keywords

Canonical Forms, Galois Field Forms, Green-Sasao Hierarchy, Inclusive Forms, Multiple-Valued Logic, Shannon-Davio Trees, Ternary Logic, Universla Logic Modules

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, “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.

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. 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.

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

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.

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.

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