FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 29, No 4, December 2016, pp. 701 - 720 DOI: 10.2298/FUEE1604701A Anas N. Al-Rabadi1,2 Received November 28, 2015; received in revised form April 13, 2016 Corresponding author: Anas N. Al-Rabadi Electrical Engineering Department, Philadelphia University, Jordan & Computer Engineering Department, The University of Jordan, Amman-Jordan (email: alrabadi@yahoo.com) FACtA uNiVeRsitAtis Series: electronics and energetics Vol. 28, No 4, December 2015, pp. 507 - 525 DOi: 10.2298/FUEE1504507S hoRiZoNtAl CuRReNt BipolAR tRANsistoR (hCBt) – A loW-Cost, hiGh-peRFoRMANCe FlexiBle BiCMos teChNoloGy FoR RF CoMMuNiCAtioN AppliCAtioNs tomislav suligoj1, Marko Koričić1, Josip Žilak1, hidenori Mochizuki2, so-ichi Morita2, Katsumi shinomura2, hisaya imai2 1University of Zagreb, Faculty of Electrical Engineering and Computing, Department of Electronics, Micro- and Nano-electronics laboratory, Croatia 2Asahi Kasei Microdevices Co. 5-4960, Nobeoka, Miyazaki, 882-0031, Japan Abstract. In an overview of Horizontal Current Bipolar Transistor (HCBT) technology, the state-of-the-art integrated silicon bipolar transistors are described which exhibit fT and fmax of 51 GHz and 61 GHz and fTBVCEO product of 173 GHzV that are among the highest-performance implanted-base, silicon bipolar transistors. HBCT is integrated with CMOS in a considerably lower-cost fabrication sequence as compared to standard vertical-current bipolar transistors with only 2 or 3 additional masks and fewer process steps. Due to its specific structure, the charge sharing effect can be employed to increase BVCEO without sacrificing fT and fmax. Moreover, the electric field can be engineered just by manipulating the lithography masks achieving the high-voltage HCBTs with breakdowns up to 36 V integrated in the same process flow with high-speed devices, i.e. at zero additional costs. Double-balanced active mixer circuit is designed and fabricated in HCBT technology. The maximum IIP3 of 17.7 dBm at mixer current of 9.2 mA and conversion gain of -5 dB are achieved. Key words: BiCMOS technology, Bipolar transistors, Horizontal Current Bipolar Transistor, Radio frequency integrated circuits, Mixer, High-voltage bipolar transistors. 1. iNTRODUCTiON in the highly competitive wireless communication markets, the RF circuits and systems are fabricated in the technologies that are very cost-sensitive. in order to minimize the fabrication costs, the sub-10 GHz applications can be processed by using the high-volume silicon technologies. it has been identified that the optimum solution might Received March 9, 2015 Corresponding author: Tomislav Suligoj University of Zagreb, Faculty of Electrical Engineering and Computing, Department of Electronics, Micro- and Nano-electronics laboratory, Croatia (e-mail: tom@zemris.fer.hr) FACTA UNiVERSiTATiS, SERi ES: ElECTRONi CS AND ENERGETi CS vol. 22, No. 4, December 2016, 100-118 UDK: DOi: Multi-Valued Galois shannon - davio trees and their Complexity Anas N. Al-Rabadi 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 di- agrams 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 cal- culate 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: Complexity, Galois Field Sum-of-Product (GFSOP), Galois Forms, inclusive Forms, Multi-Valued logic, Quaternary logic, Shannon-Davio (S/D) Trees. 1 introduction Spectral transforms play an important role in the synthesis, analysis, testing, classification, formal verification and simulation of logic circuits and systems. Dyadic families of dis- crete transforms; Reed-Muller and Green-Sasao hierarchy, Walsh, Arithmetic, Adding and Haar transforms and their generalizations to p-adic (multi-valued) transforms, have found a fruitful use in digital system design [1, 2, 6-35]. Reed-Muller-like spectral transforms [2-6, 12-14, 16-18, 21, 25, 27, 29, 33, 35] have found a variety of useful applications in minimizing Exclusive Sum-Of-Products (ESOP) and Galois field SOP (GFSOP) expres- sions, creation of new forms, binary decision diagrams, spectral decision diagrams, regular Manuscript received July 15, 2015; revised Electrical Engineering Department, Philadelphia University, Jordan & Computer Engineering Department, The University of Jordan, Amman-Jordan E-mail: alrabadi@yahoo.com This research was performed during sabbatical leave in 2015-2016 granted from the University Jordan and spent at Philadelphia University 101 Multi-VAlued GAlois shANNoN - dAVio tRees ANd theiR CoMplexity 1Electrical Engineering Department, Philadelphia University, 2Jordan & Computer Engineering Department, The University of Jordan, Amman-Jordan 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 in- troduced. 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. Key words: Complexity, Galois Field Sum-of-Product (GFSOP), Galois Forms, Inclusive Forms, Multi-Valued Logic, Quaternary Logic, Shannon-Davio (S/D) Trees. 702 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 703 Multi-Valued Galois Shannon - Davio Trees and Their Complexity structures, besides their well-known uses in digital communications, digital signal process- ing, digital image processing and fault detection and testing [1-7, 12, 13, 15-19, 21-25, 27, 29, 32, 35]. The method of generating the new families of multi-valued Shannon and Davio spectral transforms is based on the fundamental multi-valued Shannon and Davio expansions, respectively. The remainder of this paper is organized as follows: basic definitions of the fundamen- tal binary expansions and their multi-valued extensions are given in Section 2. Section 3 presents the quaternary Galois Shannon-Davio (S/D) Trees. The number of S/D inclusive forms and the new iFn,2 triangles are introduced in Section 4. Conclusions and future work are presented in Section 5. 2 Basic shannon and davio decompositions This Section presents necessary mathematical background and the fundamental formalisms of the work that will be introduced and further developed in the following Sections. Nor- mal canonical forms play an important role in the synthesis of logic circuits which includes synthesis, testing and optimization [2, 8, 13, 15, 17, 18, 21, 23, 25, 27, 29, 32, 35-37]. The main algebraic structure which is used in this work for developing the canonical normal forms is the Galois field (GF) algebraic structure, which is a fundamental algebraic struc- ture in the theory of algebras [2, 8, 17, 18, 21, 32]. Galois field has proven high efficiency in various applications of logic synthesis, such as in the design for test, error correction codes, and even in the proof of the well-known Fermat’s last theorem. The importance of GF for logic synthesis results from the fact that every finite field is isomorphic to a Galois field. In general, the attractive properties of GF-based circuits, such as high testability of such circuits, are due to the fact that the GF operators exhibit the Cyclic Group - also called Latin Square - property which can be explained, for example, using GF(4) (quaternary) operators as shown in Figures 1(a) and 1(b), respectively; note that in any row and column of the addition table in Figure 1(a), the elements are all different which is cyclic, and that the elements have a different order in each row and column. Another cyclic group can be observed in the multiplication table; if the zero elements are removed from the multiplica- tion table in Figure 1(b), then the remaining elements form a cyclic group. in binary, for example, GF(2) addition operator - EXOR - has the cyclic group property. + 0 1 2 3 0 0 1 2 3 1 1 0 3 2 2 2 3 0 1 3 3 2 1 0 ∗ 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 3 1 3 0 3 1 2 (a) (b) Fig. 1: GF(4) addition and multiplication tables. Reed-Muller based normal forms have been classified using the Green-Sasao hierarchy. The Green-Sasao hierarchy of families of canonical forms and corresponding decision di- 102 702 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 703 Multi-Valued Galois Shannon - Davio Trees and Their Complexity agrams is based on three generic expansions; Shannon, positive Davio and negative Davio expansions. The corresponding Shannon, positive Davio and negative Davio expansions are given as follows [2, 32]: f (x1,x2,...,xn) = x̄1 · f0(x1,x2,...,xn)⊕ x1 · f1(x1,x2,...,xn), = [ x̄1 x1 ] [ 1 0 0 1 ][ f0 f1 ] , (1) f (x1,x2,...,xn) = 1 · f0(x1,x2,...,xn)⊕ x1 · f2(x1,x2,...,xn), = [ 1 x1 ] [ 1 0 1 1 ][ f0 f1 ] , (2) f (x1,x2,...,xn) = 1 · f1(x1,x2,...,xn)⊕ x̄1 · f2(x1,x2,...,xn) = [ 1 x̄1 ] [ 0 1 1 1 ][ f0 f1 ] , (3) where f0(x1,x2,...,xn) = f (0,x2,...,xn) = f0 is the negative cofactor of variable x1, f1(x1,x2,...,xn) = f (1,x2,...,xn) = f1 is the positive cofactor of variable x1, and f2(x1,x2,...,xn) = f (0,x2,...,xn) ⊕ f (1,x2,...,xn) = f0 ⊕ f1. An arbitrary n-variable function f (x1,x2,...,xn) can be represented using the Positive Polarity Reed-Muller (PPRM) expansion as follows: f (x1,x2,...,xn) =a0 ⊕ a1x1 ⊕ a2x2 ⊕ ...⊕ anxn ⊕ a12x1x2 ⊕ a13x1x3 ⊕ an−1,nxn−1xn ⊕ ...⊕ a12...nx1x2 ...xn. (4) For each function f , the coefficients ai in Equation (4) are determined uniquely, so PPRM is a canonical form. if we use either only the positive literal or only the negative literal for each variable in Equation (4) we obtain the Fixed Polarity Reed-Muller (FPRM) form. There are 2n possible combinations of polarities and as many FPRMs for any given logic function [2, 32]. if we freely choose the polarity of each literal in Equation (4), we obtain the Generalized Reed-Muller (GRM) form. in GRMs, contrary to FPRMs, the same variable can appear in both positive and negative polarities. There are n2(n−1) literals in Equation (4) so there are 2n2 (n−1) polarities for an n-variable function and as many GRMs [32]. Each of the polarities determines a unique set of coefficients, and thus each GRM is a canonical representation of a function. Two other types of expansions result from the flattening of certain binary trees that will produce Kronecker (KRO) forms and Pseudo Kronecker (PKRO) forms for Shannon, positive Davio and negative Davio expansions. There are 3n and at most 32 n−1 different KROs and PKROs, respectively [32]. The good selection of the various permutations using the Shannon and Davio expan- sions as internal nodes in decision trees (DTs) and diagrams (DDs) will result in DTs and DDs, that represent the corresponding logic functions, with smaller sizes in terms of the total number of hierarchical levels used, and the total number of internal nodes needed. The minimization of the size of DD, to represent a logic function, will result in speeding up the manipulations of logic functions using DD as data structure, and the minimization of the use of memory space during the execution of such manipulations. One can observe that 103 704 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 705 Multi-Valued Galois Shannon - Davio Trees and Their Complexity by going from PPRM to GRM forms, less constraints are imposed on the canonical forms due to the enlarged set of polarities that one can choose from. The gain of more freedom (less constraints) on the polarity of the canonical expansions will provide an advantage of obtaining Exclusive-Sum-Of-Product (ESOP) expressions with less number of terms and literals, and consequently expressing Boolean functions using ESOP forms will produce on average expressions with less size as if compared to Sum-Of-Product (SOP) expressions. In general, a literal can be defined as any function of a single variable [2, 18, 32]. ba- sis functions in the general case of multi-valued expansions are constructed using literals. Galois field SOP expansions can be performed on variety of literals. For example, one can use among others: K-Reduced Post literal (K-RPl) to produce K-RPl GFSOP, Post literal to produce Pl GFSOP, Window literal to produce Wl GFSOP, Generalized (Post) literal to produce Gl GFSOP, or Universal literal to produce Ul GFSOP. Figure 2 demonstrates set-theoretic relationships between the various literals, where the shaded Reduced Post lit- eral is the type of literal that will be used through this paper. One may note that the RPl in the discrete domain is analogous to the delta function in the continuous domain. Reduced Post Literal Post Literal Window Literal Generalized (Post) Literal Universal Literal Fig. 2: inclusion relationship of various types of literals. example 1. Figure 3 demonstrates several literal types, where one proceeds from the sim- plest RPL literal in Figure 3(a) to the more complex WL literal in Figure 3(c). For RPL in Figure 3(a), a value K is produced by the literal when the value of the variable is equal to a specific state, and in this particular example a value K = 1 is generated by the 1-RPL when the value of variable x is equal to certain state (here this state is equal to one). Figure 3(b) shows PL where the value generated by the literal at a specific state is equal to the maximum value (i.e., radix) of that logic, and WL in Figure 3(c) generates a value equal to the radix for a "window" of specific states. Since K-RPl GFSOP is as simple as Pl and it is simpler from implementation point of view than other kind of literals, we will perform all of the GFSOP expansions utilizing the corresponding 1-Reduced Post Literal GFSOP. Consequently, let us define the 1-RPL as [2, 32]: ix = 1 iff x = i else ix = 0. (5) For example { 0x, 1x, 2x} are the zero, first and second polarities of the 1-Reduced Post Literal, respectively. Also, let us define the ternary shifts over x variable {x,x′,x′′} as 104 704 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 705 Multi-Valued Galois Shannon - Davio Trees and Their Complexity 1 0 1 2 3 4 x 2 3 4 1 x 0 1 2 3 4 x 1 2 3 4 L 1 (x) 0 1 2 3 4 x 1 2 3 4 L [1:2] (x) (a) (b) (c) Fig. 3: An example of different types of literals over an arbitrary five-radix logic: (a) 1-Reduced Post literal (1-RPl), (b) Post literal (Pl), and (c) Window literal (Wl). the zero, first and second shifts of the variable x respectively (i.e., x = x + 0, x′ = x + 1 and x′′ = x+ 2, respectively), and x can take any value in the set {0,1,2}. We chose to represent the 1-Reduced Post literals in terms of shifts and powers, among others, because of the ease of the implementation of powers of shifted variables in hardware such as in Universal logic Modules (UlMs) [2]. Analogously to the binary and ternary cases, quaternary Shannon expansion over GF(4) for a function with single variable is: f = 0x f0 + 1x f1 + 2x f2 + 3x f3, (6) where f0 is the cofactor of f with respect to variable x of value 0, f1 is the cofactor of f with respect to variable x of value 1, f2 is the cofactor of f with respect to variable x of value 2, and f3 is the cofactor of f with respect to variable x of value 3. example 2. Let f (x1,x2) = x′′1 x2 +x ′′′ 2 x1. By using Figure (1), the quaternary truth vector in the variable order {x1,x2} is F = [0,3,1,2,2,1,3,0,3,0,2,1,1,2,0,3]T . Utilizing Equation (6), one obtains the following GF(4) Shannon expansion for f : f =2 · 0x1 1x2 + 3 · 0x1 2x2 + 0x1 3x2 + 3 · 1x1 0x2 + 1x1 1x2 + 2 · 1x1 3x2 + 2x1 0x2 + 3 · 2x1 1x2 + 2 · 2x1 2x2 + 2 · 3x1 0x2 + 3x1 2x2 + 3 · 3x1 3x2. Using the axioms of GF(4) that are manifested in the operators shown in Figure 1, the 1-RPL defined in Equation (5) is related to the shifts of variables over GF(4) in terms of powers [2-5] as follows: 105 706 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 707 Multi-Valued Galois Shannon - Davio Trees and Their Complexity 0x = x3 + 1, (7) 0x = x′ + (x′)2 + (x′)3, (8) 0x = 3(x′′)+ 2(x′′)2 + (x′′)3, (9) 0x = 2(x′′′)+ 3(x′′′)2 + (x′′′)3, (10) 1x = x + (x)2 + (x)3, (11) 1x = (x′)3 + 1, (12) 1x = 2(x′′)+ 3(x′′)2 + (x′′)3, (13) 1x = 3(x′′′)+ 2(x′′′)2 + (x′′′)3, (14) 2x = 3(x)+ 2(x)2 + (x)3, (15) 2x = 2(x′)+ 3(x′)2 + (x′)3, (16) 2x = (x′′)3 + 1, (17) 2x = x′′′ + (x′′′)2 + (x′′′)3, (18) 3x = 2(x)+ 3(x)2 + (x)3, (19) 3x = 3(x′)+ 2(x′)2 + (x′)3, (20) 3x = x′′ + (x′′)2 + (x′′)3, (21) 3x = (x′′′)3 + 1, (22) where { 0x, 1x, 2x, 3x} are the zero, first, second and third polarities of the 1-RPL, respec- tively. Also, {x,x′,x′′,x′′′} are the zero, first, second and third shifts (inversions) of the variable x respectively, and variable x can take any value of the set {0,1,2,3}. Analo- gous to the ternary case, we chose to represent the 1-RPl in terms of shifts and powers, among others, because of the ease of the implementation of powers of shifted variables in hardware. After the substitution of Equations (7) - (22) in Equation (6), and after the rearrangement and reduction of terms according to the GF(4) operations in Figure 1, one obtains: f = 1 · f0 + x( f1 + 3 f2 + 2 f3)+ (x)2( f1 + 2 f2 + 3 f3)+ (x)3( f0 + f1 + f2 + f3), (23) f = 1 · f1 + (x′)( f0 + 2 f2 + 3 f3)+ (x′)2( f0 + 3 f2 + 2 f3)+ (x′)3( f0 + f1 + f2 + f3), (24) f = 1 · f2 + (x′′)(3 f0 + 2 f1 + f3)+ (x′′)2(2 f0 + 3 f1 + f3)+ (x′′)3( f0 + f1 + f2 + f3), (25) f = 1 · f3 + (x′′′)( f2 + 3 f1 + 2 f0)+ (x′′′)2( f2 + 2 f1 + 3 f0)+ (x′′′)3( f0 + f1 + f2 + f3). (26) Equations (6) and (23) - (26) are the 1-RPL quaternary Shannon (S) and Davio (D0,D1,D2,D3} expansions for a single variable, respectively. These Equations can be re-written in the following matrix-based convolution-like forms, respectively: 106 706 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 707 Multi-Valued Galois Shannon - Davio Trees and Their Complexity f = � 0x 1x 2x 3x �     1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1         f0 f1 f2 f3     , (27) f = � 1 x x2 x3 �     1 0 0 0 0 1 3 2 0 1 2 3 1 1 1 1         f0 f1 f2 f3     , (28) f = � 1 x′ (x′)2 (x′)3 �     0 1 0 0 1 0 2 3 1 0 3 2 1 1 1 1         f0 f1 f2 f3     , (29) f = � 1 x′′ (x′′)2 (x′′)3 �     0 0 1 0 3 2 0 1 2 3 0 1 1 1 1 1         f0 f1 f2 f3     , (30) f = � 1 x′′′ (x′′′)2 (x′′′)3 �     0 0 0 1 2 3 1 0 3 2 1 0 1 1 1 1         f0 f1 f2 f3     . (31) One can observe that Equations (27) - (31) are expansions for a single variable. Yet, these canonical expressions can be generated for arbitrary number of variables N using the Kronecker (tensor) product. This can be expressed formally as in the following dis- crete convolution-like forms for Shannon (S), and Davio (D0, D1, D2 and D3) expressions, respectively [2, 32]: f = N � i=1 � 0xi 1xi 2xi 3xi � N � i=1 [S][�F], (32) f = N � i=1 � 1 xi x2i x 3 i � N � i=1 [D0][�F], (33) f = N � i=1 � 1 x′i (x ′ i) 2 (x′i) 3 � N � i=1 [D1][�F], (34) f = N � i=1 � 1 x′′i (x ′′ i ) 2 (x′′i ) 3 � N � i=1 [D2][�F], (35) f = N � i=1 � 1 x′′′i (x ′′′ i ) 2 (x′′′i ) 3 � N � i=1 [D3][�F]. (36) The following section utilizes the presented GF(4) spectral-based functional decompo- sitions for the synthesis of decision trees. in this spectral interpretation of decision trees, 107 708 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 709 Multi-Valued Galois Shannon - Davio Trees and Their Complexity different decision trees can be defined by using different decomposition forms which are specified by the corresponding transform matrices and multi-valued literals. The utilized decision trees can therefore be viewed as graphical representations of functional expres- sions where different trees produce different functional expressions, and by counting the number of possible different trees, that are derived by assigning different decomposition rules to their nodes, we can count the number of possible functional expressions. 3 Quaternary shannon-dvaio (s/d) trees The basic S, D0, D1, D2 and D3 quaternary expansions (i.e., flattened forms) introduced previously in Equations (32) - (36) can be represented in quaternary DTs (QuDTs) and the corresponding varieties of reduced quaternary DDs (RQuDDs) according to the cor- responding reduction rules. For one variable (i.e., one level of the DT), Figures 4(a) - 4(e) represent the expansion nodes for {S,D0,D1,D2,D3}, respectively, and the notation in Figure 4(f) means that x corresponds to the four possible shifts of the variable x as: x ∈ {x,x′,x′′,x′′′}, over GF(4). (37) 1 1 1 1 1 x ( ’)x ( ’’)x ( ’’’)x x x ( ’)x ( ’’)x ( ’’’)x ( )x 2 2 2 2 2 x ( ’)x ( ’’)x ( ’’’)x ( )x 3 3 3 3 3 0 x 1 x 2 x 3 x S D0 D1 D2 D3 D ( )a (d) ( )b (e) ( )c (f ) Fig. 4: Quaternary decision nodes: (a) Shannon in Eq. (32), (b) Davio0 in Eq. (33), (c) Davio1 in Eq. (34), (d) Davio2 in Eq. (35), (e) Davio3 in Eq. (36), and (f) generalized quaternary Davio defined in Eq. (37). Utilizing the two nodes defined for quaternary Shannon in Figure 4(a) and quaternary generalized Davio in Figure 4(f), and analogously to the binary and ternary cases, one can obtain the quaternary Shannon-Davio (S/D) trees for two variables (cf. Figure 5), where general family called Inclusive Forms (IFs) is obtained as flattened expressions generated by these S/D trees. For example, the corresponding S/D trees for iFs of two variables can be generated for variable order {a,b} and for variable order {b,a} as well. The number of these S/D trees per variable order is 2(4+1) = 32, where the number of QiFs per S/D tree will be later derived in Section 4 in two different ways; the first method 108 708 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 709 Multi-Valued Galois Shannon - Davio Trees and Their Complexity is by using the general formula for an arbitrary number of variables over GF(4) and the second method is performed by using the general formula for any radix. The number of all possible forms is important because it can be used as an upper-bound parameter in a search heuristic that searches for a minimum GFSOP expression using the corresponding S/D trees. Example 3 illustrates some of the quaternary S/D trees and some of the quaternary trees they produce. The numbers on top of S/D trees in Figures 5(a) and 6(a) are the numbers of total QIFs (i.e., total number of quaternary trees) that are generated. example 3. Utilizing the notation in Equation (37), we obtain, for the S/D trees in Figures 5(a) and 6(a), the corresponding S/D trees in Figures 5(b) - 5(c) and Figures 6(b) - 6(c), respectively. From the quaternary S/D trees shown in Figures 5 and 6, by taking any S/D tree, mul- tiplying the two-level cofactors (which are in the QuDT leafs) each by the corresponding path in that QuDT, and next summing all the resulting cubes (terms or products) over GF(4), one obtains the flattened IF form for the function f as a certain GFSOP expression (expan- sion). For each QuDT in Figures 5(a) and 6(a), there are as many iF forms obtained for the function f as the number of all possible permutations of the polarities of the variables in the second level branches of each QuDT. 4 Count of the Number of s/d inclusive Forms over GF(pK) and the New iFN,2 triangles This section provides the count for the numbers of inclusive Forms, which are flattened expressions generated by the corresponding S/D trees, where these counts can be used as numerical parameters for upper-bounds in search heuristics that search for minimum GFSOP expressions. theorem 1. For GF(3) and N variables, the total number of ternary IFs (TIFs) per vari- able order is: #TiFs = (3)N−1 ∑ k1=0 (3)N−2 ∑ k2=0 (3)N−3 ∑ k3=0 ··· (3)0 ∑ kN =0 {[ 3(N−1)! (3(N−1) − k1)!k1! 3(N−2)! (3(N−2) − k2)!k2! 3(N−3)! (3(N−3) − k3)!k3! ··· 3(0)! (3(0) − kN)!kN ! ] [ (32(3) 0 )k1 (32(3) 1 )k2(32(3) 2 )k3 ···(32(3) N−1 )kN ]} . (38) Proof. The following is the derivation of Equation (38) to calculate #TiFs per variable order. The total number of nodes for any GF(3) tree with N levels (N variables) equals: N−1 ∑ k=0 (3)k. (39) For any S-type node there is only one type of nodes as the branches have the possibility of single value each. Yet, for D-type node there are N possible types of nodes where N is the 109 710 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 711 Multi-Valued Galois Shannon - Davio Trees and Their Complexity 1 1 1 1 1 1 0 b 0 b 0 b 0 b 0 b 0 b b b b b b’’ b’ b 1 b 1 b b 1 b 1 b ( )b 2 (b’) 2 (b) 2 ( )b 2 (b’) 2 (b) 2 2 b 2 b 2 b 2 b 2 b 2 b ( )b 3 (b’) 3 (b’’) 3 ( )b 3 (b) 3 (b) 3 3 b 3 b 3 b 3 b 3 b 3 b S S S S S S S S S D D D D D D (a) (b) ( ) N= 4,096 0 a 0 a 0 a 1 a 1 a 1 a 2 a 2 a 2 a 3 a 3 a 3 a c Fig. 5: Examples of S/D trees: (a) quaternary S/D tree for two variables of order {a,b} with three Shannon nodes and two generalized Davio nodes, and (b) - (c) some of the quaternary trees that it generates. number of variables which is equal to the number of levels. The highest possible number of forms for the D-type node is when the D-type node exists in the first (highest) level, and the lowest possible number of forms for the D-type node is when the D-type node exists in the N-level (lowest level). Therefore, for certain number M of S-type nodes the following equation describes the number of the D-type nodes for N variables: #S = M ⇒ #D = [ N−1 ∑ k=o (3)k − M]. (40) it can be shown that for GF(3) (i.e., ternary decision tree (TDT)) and N-levels (N-variables), the general formulas that count the number of D-type nodes, and the number of all possible 110 1 1 710 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 711 Multi-Valued Galois Shannon - Davio Trees and Their Complexity 1 1 1 1 1 1 0 a 0 a 0 a 1 1 1 a a aa a’ a 1 a 1 a 1 a a a’’ a’’ ( )a 2 (a) 2 (a) 2 ( )a 2 (a’’) 2 (a’’) 2 2 a 2 a 2 a (a) 2 (a’’’) 2 (a) 2 ( )a 3 (a) 3 (a’) 3 ( )a 3 (a’’’) 3 (a’’) 3 3 a 3 a 3 a (a) 3 (a’) 3 (a’) 3 S S S D D S S S S D D D D D D (a) (b) N= 262,144 0 b 0 b 0 b 1 b 1 b 1 b 2 b 2 b 2 b 3 b 3 b 3 b (c) Fig. 6: Examples of S/D trees: (a) quaternary S/D tree for two variables of order {b,a} with two Shannon nodes and three generalized Davio nodes, and (b) - (c) some of the quaternary trees that it generates. forms for the D-type node in the k level of the N-level TDT are: #Dk =(3)(K−1), (41) |Dk|per node =(3)2(3) (N−K) , (42) where #Dk is the number of D-type nodes in k level, and |Dk| is the number of all possible forms for the D-type node in the k level. Let us define S/D tree category to be the S/D trees that have in common the same number of S-type nodes and same number of 111 (a)2 (a)3 D 712 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 713 Multi-Valued Galois Shannon - Davio Trees and Their Complexity D-type nodes within the same variable order. Also, define: Ψ ≡ number of variable orders, (43) Ω ≡ number of S/D tree categories per variable order, (44) φ ≡ number of S/D trees per category, (45) Φ ≡ number of TiFs per variable order. (46) From Equations (39) - (42), and using some elementary count rules, we can derive by mathematical induction the following general formulas for N being the number of variables: Ψ = N!, (47) Ω = N−1 ∑ k=0 (3)k + 1, (48) φ = [∑N−1k=0 (3) k]! [∑N−1k=0 (3) k − k]!k! , where k = 0,1,2,3,..., N−1 ∑ k=0 (3)k, (49) Φ = (3)N−1 ∑ k1=0 (3)N−2 ∑ k2=0 (3)N−3 ∑ k3=0 ··· (3)0 ∑ kN =0 {[ 3(N−1)! (3(N−1) − k1)!k1! 3(N−2)! (3(N−2) − k2)!k2! 3(N−3)! (3(N−3) − k3)!k3! ··· 3(0)! (3(0) − kN)!kN ! ][ (32(3) 0 )k1(32(3) 1 )k2(32(3) 2 )k3 ··· (32(3) (N−1) )kN ]} . (50) From Equations (47) - (50), it can be noticed that the total number of TiFs for all variable orders is equal to [N!][#TiFs per order]. example 4. For number of variables equal to two (N = 2), Φ reduces to: Φ = (3)1 ∑ k1=0 1 ∑ k2=0 { 31! (31 − k1)!k1! 30! (30 − k2)!k2! (32(3) 0 )k1(32(3) 1 )k2 } Φ =Φ|k1=0,k2=0 + Φ|k1=1,k2=0 + Φ|k1=2,k2=0 + Φ|k1=3,k2=0 +Φ|k1=0,k2=1 + Φ|k1=1,k2=1 + Φ|k1=2,k2=1 + Φ|k1=3,k2=1 =Φ00 + Φ10 + Φ20 + Φ30 + Φ01 + Φ11 + Φ21 + Φ31 =1 + 27 + 243 + 729 + 729 + 19683 + 177147 + 531441 = 730,000. Utilizing multi-valued map representation, there are N#Minterms different functions for N-valued input-output logic. Therefore, for ternary logic, there are 39 = 19,683 different ternary functions of two variables, and 730,000 ternary inclusive Forms generated by the S/D trees. Thus, on the average every function of two variables can be realized in approxi- mately 37 ways. 112 712 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 713 Multi-Valued Galois Shannon - Davio Trees and Their Complexity D-type nodes within the same variable order. Also, define: Ψ ≡ number of variable orders, (43) Ω ≡ number of S/D tree categories per variable order, (44) φ ≡ number of S/D trees per category, (45) Φ ≡ number of TiFs per variable order. (46) From Equations (39) - (42), and using some elementary count rules, we can derive by mathematical induction the following general formulas for N being the number of variables: Ψ = N!, (47) Ω = N−1 ∑ k=0 (3)k + 1, (48) φ = [∑N−1k=0 (3) k]! [∑N−1k=0 (3) k − k]!k! , where k = 0,1,2,3,..., N−1 ∑ k=0 (3)k, (49) Φ = (3)N−1 ∑ k1=0 (3)N−2 ∑ k2=0 (3)N−3 ∑ k3=0 ··· (3)0 ∑ kN =0 {[ 3(N−1)! (3(N−1) − k1)!k1! 3(N−2)! (3(N−2) − k2)!k2! 3(N−3)! (3(N−3) − k3)!k3! ··· 3(0)! (3(0) − kN)!kN ! ][ (32(3) 0 )k1(32(3) 1 )k2(32(3) 2 )k3 ··· (32(3) (N−1) )kN ]} . (50) From Equations (47) - (50), it can be noticed that the total number of TiFs for all variable orders is equal to [N!][#TiFs per order]. example 4. For number of variables equal to two (N = 2), Φ reduces to: Φ = (3)1 ∑ k1=0 1 ∑ k2=0 { 31! (31 − k1)!k1! 30! (30 − k2)!k2! (32(3) 0 )k1(32(3) 1 )k2 } Φ =Φ|k1=0,k2=0 + Φ|k1=1,k2=0 + Φ|k1=2,k2=0 + Φ|k1=3,k2=0 +Φ|k1=0,k2=1 + Φ|k1=1,k2=1 + Φ|k1=2,k2=1 + Φ|k1=3,k2=1 =Φ00 + Φ10 + Φ20 + Φ30 + Φ01 + Φ11 + Φ21 + Φ31 =1 + 27 + 243 + 729 + 729 + 19683 + 177147 + 531441 = 730,000. Utilizing multi-valued map representation, there are N#Minterms different functions for N-valued input-output logic. Therefore, for ternary logic, there are 39 = 19,683 different ternary functions of two variables, and 730,000 ternary inclusive Forms generated by the S/D trees. Thus, on the average every function of two variables can be realized in approxi- mately 37 ways. 112 Multi-Valued Galois Shannon - Davio Trees and Their Complexity theorem 2. For GF(4) and N variables, the total number of quaternary IFs (QIFs) per variable order is: #QiFs =Φ = (4)N−1 ∑ k1=0 (4)N−2 ∑ k2=0 ··· (4)0 ∑ kN =0 { 4(N−1)! (4(N−1) − k1)!k1! 4(N−2)! (4(N−2) − k2)!k2! ··· 4(0)! (4(0) − kN)!kN ! (43(4) 0 )k1 (43(4) 1 )k2(43(4) 2 )k3 ···(43(4) (N−1) )kN } . (51) Proof. A general proof that includes GF(4) as special case will be provided later in this Section. The extension of the concept of S/D trees to higher radices of Galois fields (i.e., higher than four) is a systematic and direct process that follows the same method developed for the ternary case and the quaternary case. The following example demonstrates the counts of QiFs using Theorem 2. example 5. For number of variables equal to two (N = 2), Equation (51) reduces to: Φ = (4)1 ∑ k1=0 (4)0 ∑ k2=0 { 4(1)! (4(1) − k1)!k1! 4(0)! (4(0) − k2)!k2! (43(4) 0 )k1 (43(4) 1 )k2 } =Φ|k1=0,k2=0 + Φ|k1=1,k2=0 + Φ|k1=2,k2=0 + Φ|k1=3,k2=0 + Φ|k1=4,k2=0 + Φ|k1=0,k2=1 + Φ|k1=1,k2=1 + Φ|k1=2,k2=1 + Φ|k1=3,k2=1 + Φ|k1=4,k2=1 =Φ00 + Φ10 + Φ20 + Φ30 + Φ40 + Φ01 + Φ11 + Φ21 + Φ31 + Φ41 =1 + 256 + 24,576 + 1,048,576 + 16,777,216 + 16,777,216 + 4,294,967,296 + 412,316,860,416 + 1.75921860444 × 1013 + 2.81477976711 × 1014 =2.99483809211 × 1014. Utilizing multi-valued map representation, we can easily prove that there are 416 = 4,294,967,296 quaternary functions of two variables, and 2.99483809211 × 1014 quater- nary inclusive Forms generated by the S/D trees. Thus, on the average, every function of two variables can be synthesized (realized) in approximately 69,729 ways. This high num- ber of realizations means that most functions of two variables are realized with less than five expansions, and all functions with at most five expansions. 4.1 General Formula to Compute the Number of iFs for an Arbitrary Variable Number and Arbitrary Galois Radix GF( pk) Although the S/D trees and inclusive Forms that were developed are for GF(4), the same concept can be directly and systematically extended to the case of n radix of Galois fields and N variables. Theorem 3 provides the total number of iFs per variable order for N variables (i.e., N decision tree levels) and n radix of any arbitrary algebraic field, including GF( pk) where p is a prime number and k is a natural number ≥ 1. The generality of Theorem 3 comes from the fact that algebraic structures specify the type of operations 113 714 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 715 Multi-Valued Galois Shannon - Davio Trees and Their Complexity (e.g., addition and multiplication operations) in the functional expansions but do not specify the counts which are an intrinsic property of the tree structure and are independent of the algebraic operations performed. Thus, Theorem 3 is valid, among others, for Galois fields of arbitrary radix. theorem 3. The total number of Inclusive Forms for N variables and n-radix Galois field logic is equal to: #nIF s = Φn,N = (n)N−1 ∑ k1=0 (n)N−2 ∑ k2=0 ··· (n)0 ∑ kN =0 { n(N−1)! (n(N−1) − k1)!k1! n(N−2)! (n(N−2) − k2)!k2! ··· n(0)! (n(0) − kN)!kN ! (n(n−1)(n) 0 )k1 (n(n−1)(n) 1 )k2 (n(n−1)(n) 2 )k3 ···(n(n−1)(n) N−1 )kN } . (52) Proof. The following is the derivation of the general Equation (52) to calculate the number of iFs per variable order. The total number of nodes for any GF(n) tree with N levels (i.e., N variables) equals to: N−1 ∑ k=0 (n)k. (53) For any S-type (i.e., Shannon type) node there is only one type of nodes as the branches of the Shannon node have the possibility of single value each. Yet, for D-type (i.e., Davio type) node there are N possible types of nodes where N is the number of variables which is equal to the number of levels. The highest possible number of forms for the D-type node exists when the Davio node exists in the first (highest) level, and the lowest possible number of forms for the D-type node is when the Davio node exists in the N-level (lowest level). Therefore, for certain number M of S-type nodes the following formula describes the number of the D-type nodes for N variables: #S = M ⇒ #D = N−1 ∑ k=0 (n)k − M. (54) it can be shown that for GF(n) (n-ary decision tree with N-levels, i.e., N variables), the general formulas that count the number of D-type nodes, and the number of all possible forms for the D-type node in the k level (where k is less than or equal the total number of levels N) are, respectively: #Dk =(n)k−1, (55) |Dk| =(n)(n−1)(n) (N−K) , (56) where #Dk is the number of D-type nodes in the k level and |Dk| is the number of all possible forms (per node) for the D-type node in the k level. Let us define the S/D tree category to be the S/D trees that have in common the same number of S-type nodes and the same number of D-type nodes within the same variable order. let us define the following 114 714 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 715 Multi-Valued Galois Shannon - Davio Trees and Their Complexity entities for n radix Galois field and N variables (i.e., N decision tree levels): Ψn,N ≡ number of variable orders, (57) Ωn,N ≡ number of S/D tree categories per variable order, (58) φn,N ≡ number of S/D trees per category, (59) Φn,N ≡ number of iFs per variable order. (60) From the previous Equations, and using elementary count rules, one can derive by mathe- matical induction the following general formulas for N being the number of variables and n being the field radix: Ψn,N = N!, (61) Ωn,N = N−1 ∑ k=0 (n)k + 1, (62) Φn,N = [∑N−1k=0 (n) k]! [∑N−1k=0 (n) k − k]!k! , where k = 0,1,2,3,...,N − 1, (63) Φn,N = (n)N−1 ∑ k1=0 (n)N−2 ∑ k2=0 ··· (n)0 ∑ kN =0 { n(N−1)! (n(N−1) − k1)!k1! n(N−2)! (n(N−2) − k2)!k2! ··· n(0)! (n(0) − kN)!kN ! (n(n−1)(n) 0 )k1(n(n−1)(n) 1 )k2 ···(n(n−1)(n) (N−1) )kN } . (64) One can note that the formula in Equation (52) used to obtain the total number of in- clusive Forms for N variables and n radix of Galois field is a very general formula that includes the ternary case in Equation (38) and the quaternary case in Equation (51) as spe- cial cases. Numerical counting results that are obtained from Equation (52) can be used in search heuristics as numerical bounds that could be incorporated into efficient search of S/D trees in order to obtain minimal GFSOP forms for specific multi-valued logic func- tions. Since such search for minimal forms is already a difficult problem in two-valued logic - for example using binary S/D trees - especially when the number of variables is large, the search for minimal GFSOP forms in multi-valued Galois logic will be very dif- ficult. Thus, further numerical evaluations have to be conducted in order to estimate the usefulness of the utilizations of the numerical bounds obtained from Equation (52) in such extended multi-valued search heuristics. example 6. The number of QIFs over GF(4) for two variables (i.e., N = 2 and n = 4) is: 115 716 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 717 Multi-Valued Galois Shannon - Davio Trees and Their Complexity Φ4,2 = (4)2−1 ∑ k1=0 (4)2−2 ∑ k2=0 { 4(2−1)! (4(2−1) − k1)!k1! 4(2−2)! (4(2−2) − k2)!k2! (4(4−1)(4) 0 )k1 (4(4−1)(4) 1 )k2 } , =Φ00|4,2 + Φ10|4,2 + Φ20|4,2 + Φ30|4,2 + Φ40|4,2 + Φ01|4,2 + Φ11|4,2 + Φ21|4,2 + Φ31|4,2 + Φ41|4,2 =1 + 256 + 24,576 + 1,048,576 + 16,777,216 + 16,777,216 + 4,294,967,296 + 412,316,860,416 + 1.75921860444 × 1013 + 2.81477976711 × 1014 =2.99483809211 × 1014. Corollary 1. From Equation (52), the count of IFs for N variables and second radix is: n−1 ∏ k=0 (1 + 22 n−k−1 )2 k = (2)N−1 ∑ k1=0 (2)N−2 ∑ k2=0 ··· (2)0 ∑ kN =0 { 2(N−1)! (2(N−1) − k1)!k1! 2(N−2)! (2(N−2) − k2)!k2! ··· 2(0)! (2(0) − kN)!kN ! (2(2−1)(2) 0 )k1 (2(2−1)(2) 1 )k2 ···(2(2−1)(2) (N−1) )kN } . (65) As previously mentioned, this enumeration can be useful as a terminating point of mini- mization algorithms for multi-valued functions. Yet, as shown, the number of combinations is so large that restriction to some particular cases of functional expressions can be more feasible. The following Section introduces a fast method to calculate the number of iFs for an arbitrary Galois field logic for functions with two variables. 4.2 the iFn,2 triangles: Fast Count Calculations of iFs for GF( pk) and two-Variable Functions The count of the number of iFs can be important in many applications, especially in provid- ing upper numerical boundaries for efficient search of a minimum GFSOP. Calculating the numbers of inclusive Forms can be very time consuming due to the time required to per- form the mathematical operationsin the general Equation (52). This is why a fast method to generate the number of iFs is needed. because functions with two variables find an impor- tant application such as in Universal logic Modules (UlMs) for pairs of control variables that generalize Shannon and Davio expansion modules [2], and since two-variable func- tions are attractive in logic synthesis since many functional decomposition methods exist that produce two control inputs for primitive cells in a standard library of standard cells such as in a multiplexer with two address lines, Theorem 4 provides a fast computational method to calculate the number of iFs over an arbitrary radix of Galois field GF(pk) for two-variable functions (i.e., N = 2). theorem 4. The following IFn,2 Triangles provide a fast computational method to calcu- late the number of IFs over an arbitrary n radix of Galois field GF( pk) for two-variable functions (N = 2). 116 716 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 717 Multi-Valued Galois Shannon - Davio Trees and Their Complexity Φ4,2 = (4)2−1 ∑ k1=0 (4)2−2 ∑ k2=0 { 4(2−1)! (4(2−1) − k1)!k1! 4(2−2)! (4(2−2) − k2)!k2! (4(4−1)(4) 0 )k1 (4(4−1)(4) 1 )k2 } , =Φ00|4,2 + Φ10|4,2 + Φ20|4,2 + Φ30|4,2 + Φ40|4,2 + Φ01|4,2 + Φ11|4,2 + Φ21|4,2 + Φ31|4,2 + Φ41|4,2 =1 + 256 + 24,576 + 1,048,576 + 16,777,216 + 16,777,216 + 4,294,967,296 + 412,316,860,416 + 1.75921860444 × 1013 + 2.81477976711 × 1014 =2.99483809211 × 1014. Corollary 1. From Equation (52), the count of IFs for N variables and second radix is: n−1 ∏ k=0 (1 + 22 n−k−1 )2 k = (2)N−1 ∑ k1=0 (2)N−2 ∑ k2=0 ··· (2)0 ∑ kN =0 { 2(N−1)! (2(N−1) − k1)!k1! 2(N−2)! (2(N−2) − k2)!k2! ··· 2(0)! (2(0) − kN)!kN ! (2(2−1)(2) 0 )k1 (2(2−1)(2) 1 )k2 ···(2(2−1)(2) (N−1) )kN } . (65) As previously mentioned, this enumeration can be useful as a terminating point of mini- mization algorithms for multi-valued functions. Yet, as shown, the number of combinations is so large that restriction to some particular cases of functional expressions can be more feasible. The following Section introduces a fast method to calculate the number of iFs for an arbitrary Galois field logic for functions with two variables. 4.2 the iFn,2 triangles: Fast Count Calculations of iFs for GF( pk) and two-Variable Functions The count of the number of iFs can be important in many applications, especially in provid- ing upper numerical boundaries for efficient search of a minimum GFSOP. Calculating the numbers of inclusive Forms can be very time consuming due to the time required to per- form the mathematical operationsin the general Equation (52). This is why a fast method to generate the number of iFs is needed. because functions with two variables find an impor- tant application such as in Universal logic Modules (UlMs) for pairs of control variables that generalize Shannon and Davio expansion modules [2], and since two-variable func- tions are attractive in logic synthesis since many functional decomposition methods exist that produce two control inputs for primitive cells in a standard library of standard cells such as in a multiplexer with two address lines, Theorem 4 provides a fast computational method to calculate the number of iFs over an arbitrary radix of Galois field GF(pk) for two-variable functions (i.e., N = 2). theorem 4. The following IFn,2 Triangles provide a fast computational method to calcu- late the number of IFs over an arbitrary n radix of Galois field GF( pk) for two-variable functions (N = 2). 116 Multi-Valued Galois Shannon - Davio Trees and Their Complexity 1 2 1 1 2 1 1 3 3 1 1 3 3 1 1 4 6 4 1 1 4 6 4 1 1 5 10 10 5 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 7 21 35 35 21 7 1 2 0 2 1 2 2 2 2 2 3 2 4 3 0 3 2 3 4 3 6 3 6 3 8 3 10 3 12 4 0 4 3 4 6 4 9 4 12 4 12 4 15 4 18 4 21 4 24 5 0 5 4 5 8 5 12 5 16 5 20 5 20 5 24 5 28 5 32 5 36 5 40 N 0(N-1) N 1(N-1) N 2(N-1) N 3(N-1) ... N ... (N-1)(N-1) N N(N-1) N N(N-1) N (N+1)(N-1) N (N+2)(N-1) N 2N(N-1) ( )a ( )b Fig. 7: The iFn,2 Triangles: (a) triangle of coefficients, and (b) triangle of values for fast calculation of the number of Inclusive Forms for arbitrary radix Galois field and functions of two-input variables. Proof. . The proof follows directly from mathematical induction of the number of iFs over GF( pk) for two- variable functions. This is deduced from the general Equation (52); if the iFn,2 Triangles are valid for n = q then they will be also valid for n = q + 1, for n = pk where p is a prime number and k ≥ 1. These triangles are important because the count complexity using Equation (52) for high dimensions is very high, and thus the ability of a computer to compute the counts for number of variables greater than five in a reasonable amount of time becomes difficult. Consequently, the IFn,2 triangles provide an alternative numerical and geometrical pattern of computing. it can be observed that the iFn,2 triangle of coefficients possesses a close similarity to the well-known Pascal Triangle. This occurs as follows: if one omits the first two rows of the Pascal Triangle and duplicates each row into another horizontally adjacent row, the iFn,2 triangle of coefficients will be obtained. This observation helps in creating algorithms that generates the iFn,2 triangle of coefficients since many efficient algorithms exist to generate the Pascal Triangle example 7. Utilizing IFn,2 Triangles from Figure 7, one calculates the following number of Inclusive Forms for GF(2), GF(3) and GF(4) for two variables, where the results are 117 (a) (b) . 718 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 719 Multi-Valued Galois Shannon - Davio Trees and Their Complexity identical to those obtained previously: Φ2,2 = 1 · 20 + 2 · 21 + 1 · 22 + 1 · 22 + 2 · 23 + 1 · 24 = 1 + 4 + 4 + 4 + 16 + 16 = 45. Φ3,2 = 1 · 30 + 3 · 32 + 3 · 34 + 1 · 36 + 1 · 36 + 3 · 38 + 3 · 310 + 1 · 312 = 730,000. Φ4,2 = 1 · 40 + 4 · 43 + 6 · 46 + 4 · 49 + 1 · 412 + 1 · 412 + 4 · 415 + 6 · 418 + 4 · 421 + 1 · 424 = 2.99483809211 × 1014. The iFn,2 Triangles, for N is the number of variables, possess the following interesting properties: 1. Number of positions (elements) in each row of the triangles in Figure 7 are even starting from six. 2. Sum of elements in each row in Figure 7(a) equals to the number of S/D trees per variable order. 3. Triangle in Figure 7(a) possesses even symmetry around an imaginary vertical axis in the middle. 4. The minimum number of columns required to generate the whole triangle in Figure 7(a) is equal to three due to even symmetry: one wing, one column neighbor to the middle column and one middle column. 5. The triangle in Figure 7(a) can be generated by the process of "Shift Diagonally and Add Diagonally" (SDAAD): shift the left wing diagonally from west to southeast direction and add two numbers diagonally from east to southwest direction, and shift the right wing diagonally from east to southwest direction and add two numbers diagonally from west to southeast direction. 6. The difference in powers in the triangle in Figure 7(b) per row element is (N − 1). 7. The first number in each row of the triangle in Figure 7(b) is N0 and the last number per row is N2N(N−1). 8. The middle two numbers in each row of the triangle in Figure 7(b) are always equal to NN(N−1). 5 Conclusions and Future Work Trees for generalized Shannon-Davio (S/D) expansions over quaternary Galois radix is presented, and the corresponding count for the number of inclusive Forms (iFs) per variable order for arbitrary Galois radix and arbitrary number of variables is introduced. Also, the iFn,2 Triangles as a new fast computational method to count the number of iFs for an arbitrary Galois radix and functions of two variables is introduced. Since Galois field of quaternary radix has some interesting properties including its implementation utilizing the well-established two-valued logic synthesis methods, the extension of the S/D trees to GF(4) is presented. in addition, the form of S/D trees is a general concept that can be used in applications for the generation of new diagrams and canonical forms, and in the Sum- Of-Product (SOP) minimization where S/D trees can be utilized for generating forms that include minimum Galois Field Sum-of-Products (GFSOP) circuits for binary and m-ary radices. 118 718 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity 719 Multi-Valued Galois Shannon - Davio Trees and Their Complexity Future work will investigate using other complex types of literals such as the presented Post literal (Pl) and window literal (Wl) to expand upon and consequently construct the corresponding new S/D trees. The utilization of the results from this research to create an efficient GFSOP minimizer for synthesis applications within the spaces of classical and reversible logic will also be conducted. REFERENCES [1] S. b. Akers, "binary Decision Diagrams," iEEE Trans. Comp., Vol. C-27, No. 6, pp. 509-516, June 1978. [2] A. N. Al-Rabadi, Reversible logic Synthesis: From Fundamentals to Quantum Computing, Springer-Verlag, 2004. [3] 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. [4] 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. [ 5] 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. [ 6] 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. [7] R. E. bryant, "Graph-based Algorithms for boolean Functions Manipulation," iEEE Trans. on Comp., Vol. C-35, No.8, pp. 667-691, 1986. [8] M. Cohn, Switching Function Canonical Form over integer Fields, Ph.D. Dissertation, Harvard University, 1960. [9] R. Drechsler, A. Sarabi, M. Theobald, b. becker, and M. A. Perkowski, "Efficient Represen- tation and Manipulation of Switching Functions based on Ordered Kronecker Functional Decision Diagrams," Proc. DAC, 1994, pp. 415-419. [10] M. Escobar and F. Somenzi, "Synthesis of AND/EXOR Expressions via Satisfiability," Proc. Reed-Muller, 1995, pp. 80-87. [11] 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. [12] 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. [13] H. Fujiwara, logic Testing and Design for Testability, MiT Press, 1985. [14] D. H. Green, "Families of Reed-Muller Canonical Forms," int. J. of Electronics, No. 2, pp. 259-280, 1991. [15] S. Hassoun, T. Sasao, and R. brayton (editors), logic Synthesis and Verification, Kluwer Acad. Publishers, 2001. [16] 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. [17] S. l. Hurst, D. M. Miller, and J. C. Muzio, Spectral Techniques in Digital Logic, Academic 119 Multi-Valued Galois Shannon - Davio Trees and Their Complexity Future work will investigate using other complex types of literals such as the presented Post literal (Pl) and window literal (Wl) to expand upon and consequently construct the corresponding new S/D trees. The utilization of the results from this research to create an efficient GFSOP minimizer for synthesis applications within the spaces of classical and reversible logic will also be conducted. REFERENCES [1] S. b. Akers, "binary Decision Diagrams," iEEE Trans. Comp., Vol. C-27, No. 6, pp. 509-516, June 1978. [2] A. N. Al-Rabadi, Reversible logic Synthesis: From Fundamentals to Quantum Computing, Springer-Verlag, 2004. [3] 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. [4] 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. [ 5] 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. [ 6] 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. [7] R. E. bryant, "Graph-based Algorithms for boolean Functions Manipulation," iEEE Trans. on Comp., Vol. C-35, No.8, pp. 667-691, 1986. [8] M. Cohn, Switching Function Canonical Form over integer Fields, Ph.D. Dissertation, Harvard University, 1960. [9] R. Drechsler, A. Sarabi, M. Theobald, b. becker, and M. A. Perkowski, "Efficient Represen- tation and Manipulation of Switching Functions based on Ordered Kronecker Functional Decision Diagrams," Proc. DAC, 1994, pp. 415-419. [10] M. Escobar and F. Somenzi, "Synthesis of AND/EXOR Expressions via Satisfiability," Proc. Reed-Muller, 1995, pp. 80-87. [11] 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. [12] 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. [13] H. Fujiwara, logic Testing and Design for Testability, MiT Press, 1985. [14] D. H. Green, "Families of Reed-Muller Canonical Forms," int. J. of Electronics, No. 2, pp. 259-280, 1991. [15] S. Hassoun, T. Sasao, and R. brayton (editors), logic Synthesis and Verification, Kluwer Acad. Publishers, 2001. [16] 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. [17] S. l. Hurst, D. M. Miller, and J. C. Muzio, Spectral Techniques in Digital Logic, Academic 119 Acknowledgement: This research was performed during sabbatical leave in 2015-2016 granted from The University of Jordan and spent at Philadelphia University. 720 A. N. Al-RAbADi Multi-Valued Galois Shannon - Davio Trees and Their Complexity Pb Multi-Valued Galois Shannon - Davio Trees and Their Complexity Press inc., 1985. [18] M. G. Karpovski, Finite Orthogonal Series in the Design of Digital Devices, Wiley, 1976. [19] C. Y. lee, "Representation of Switching Circuits by binary Decision Diagrams," bell Syst. Tech. J., Vol. 38, pp. 985-999, 1959. [20] C. Moraga, "Ternary Spectral logic," Proc. iSMVl, pp. 7-12, 1977. [21] J. C. Muzio and T. Wesselkamper, Multiple-Valued Switching Theory, Adam-Hilger, 1985. [22] D. K. Pradhan, "Universal Test Sets for Multiple Fault Detection in AND-EXOR Arrays," iEEE Trans. Comp., Vol. 27, pp. 181-187, 1978. [23] D. K. Pradhan, Fault-Tolerant Computing: Theory and Techniques, Vol. I, Prentice-Hall, 1987. [24] S. M. Reddy, "Easily Testable Realizations of logic Functions," iEEE Trans. Comp., C-21, pp. 1183-1188, 1972. [25] T. Sasao (editor), logic Synthesis and Optimization, Kluwer Academic Publishers, 1993. [26] 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. [27] T. Sasao and M. Fujita (editors), Representations of Discrete Functions, Kluwer Academic Pub- lishers, 1996. [28] T. Sasao, "Easily Testable Realizations for Generalized Reed-Muller Expressions," iEEE Trans. Comp., Vol. 46, pp. 709-716, 1997. [29] T. Sasao, Switching Theory for logic Synthesis, Kluwer Academic Publishers, 1999. [30] 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 De- sign, Vol. 15, No. 4, pp. 385-395, 1996. [31] R. S. Stanković, "Functional Decision Diagrams for Multiple-Valued Functions," Proc. iSMVl, 1995, pp. 284-289. [32] R. S. Stankovic, Spectral Transform Decision Diagrams in Simple Questions and Simple An- swers, Nauka, 1998. [33] R. S. Stanković, C. Moraga, and J. T. Astola, "Reed-Muller Expressions in the Previous Decade," Proc. Reed-Muller, Starkville, 2001, pp. 7-26. [34] b. Steinbach and A. Mishchenko, "A New Approach to Exact ESOP Minimization," Proc. Reed- Muller, Starkville, 2001, pp. 66-81. [35] S. N. Yanushkevich, logic Differential Calculus in Multi-Valued logic Design, Technical Univ. Szczecin, 1998. [36] I. Zhegalkin, "On the Techniques of Calculating Sentences in Symbolic logic," Math. Sb., Vol. 34, pp. 9-28, 1927. [37] i. Zhegalkin, "Arithmetic Representations for Symbolic logic," Math. Sb., Vol. 35, pp. 311-377, 1928. 120 Multi-Valued Galois Shannon - Davio Trees and Their Complexity Future work will investigate using other complex types of literals such as the presented Post literal (Pl) and window literal (Wl) to expand upon and consequently construct the corresponding new S/D trees. The utilization of the results from this research to create an efficient GFSOP minimizer for synthesis applications within the spaces of classical and reversible logic will also be conducted. REFERENCES [1] S. b. Akers, "binary Decision Diagrams," iEEE Trans. Comp., Vol. C-27, No. 6, pp. 509-516, June 1978. [2] A. N. Al-Rabadi, Reversible logic Synthesis: From Fundamentals to Quantum Computing, Springer-Verlag, 2004. [3] 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. [4] 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. [ 5] 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. [ 6] 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. [7] R. E. bryant, "Graph-based Algorithms for boolean Functions Manipulation," iEEE Trans. on Comp., Vol. C-35, No.8, pp. 667-691, 1986. [8] M. Cohn, Switching Function Canonical Form over integer Fields, Ph.D. Dissertation, Harvard University, 1960. [9] R. Drechsler, A. Sarabi, M. Theobald, b. becker, and M. A. Perkowski, "Efficient Represen- tation and Manipulation of Switching Functions based on Ordered Kronecker Functional Decision Diagrams," Proc. DAC, 1994, pp. 415-419. [10] M. Escobar and F. Somenzi, "Synthesis of AND/EXOR Expressions via Satisfiability," Proc. Reed-Muller, 1995, pp. 80-87. [11] 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. [12] 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. [13] H. Fujiwara, logic Testing and Design for Testability, MiT Press, 1985. [14] D. H. Green, "Families of Reed-Muller Canonical Forms," int. J. of Electronics, No. 2, pp. 259-280, 1991. [15] S. Hassoun, T. Sasao, and R. brayton (editors), logic Synthesis and Verification, Kluwer Acad. Publishers, 2001. [16] 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. [17] S. l. Hurst, D. M. Miller, and J. C. Muzio, Spectral Techniques in Digital Logic, Academic 119