FACTA UNIVERSITATIS Series: Electronics and Energetics vol. xx, 2018, xx-xx COMPACT XOR-BI-DECOMPOSITION FOR LATTICES OF BOOLEAN FUNCTIONS ∗ Bernd Steinbach1 and Christian Posthoff2 1Freiberg University of Mining and Technology, Institute of Computer Science, Freiberg, Germany 2The University of the West Indies, Department of Computing and Information Technology, Saint Augustine, Trinidad & Tobago Abstract: Bi-Decomposition is a powerful approach for the synthesis of multi-level combinational circuits because it utilizes the properties of the given functions to find small circuits, with low power consumption and low delay. Compact bi-decompo- sitions restrict the variables in the support of the decomposition functions as much as possible. Methods to find compact AND-, OR-, or XOR-bi-decompositions for a given completely specified function are well known. A lattice of Boolean functions represents all possible functions which are defined by an incompletely specified function. Lattices of Boolean Functions significantly in- crease the possibilities to synthesize a minimal circuit. However, so far only methods to find compact AND- or OR-bi-decompositions for lattices of Boolean functions are known. This gap, i.e., a method to find a compact XOR-bi-decomposition for a lattice of Boolean functions, has been closed by the approach suggested in this paper. Keywords: synthesis, combinational circuit, lattice of Boolean functions, XOR-bi- decomposition, Boolean Differential Calculus, derivative operations. 1 INTRODUCTION The aim of all decomposition methods in circuit design is to find decomposition functions that are simpler than the given function. The bi-decomposition is an ap- Manuscript received September 18, 2017 Corresponding author: Bernd Steinbach Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta- Str. 2, D-09596 Freiberg, Germany (e-mail: steinb@informatik.tu-freiberg.de). ∗A preliminary version of this paper was presented at the Reed-Muller 2017 Workshop, Novi Sad, Serbia, May 24-25, 2017. 1 2 B. Steinbach and C. Posthoff: proach that decomposes a given Boolean function into two simpler decomposition functions which are combined by an AND-, an OR-, or an XOR-gate. For the aim of simplification, the bi-decomposition utilizes the properties of the given Boolean function to design circuit structures of a small area, low power consumption, and low delay [1]. There are several types of bi-decompositions. Both decomposition functions of each strong bi-decomposition are simpler than the given function because they depend on fewer variables. Unfortunately, there are functions for which no strong bi-decomposition exists. Le [2] bridged this gap by means of the weak bi-decom- position. He found that each function, for which neither a weak OR bi-decom- position nor a weak AND bi-decomposition exists, can be simplified by a strong XOR bi-decomposition. A simplified proof of the completeness of the strong and weak bi-decomposition is given in [3, 4]. An implementation that reuses already decomposed blocks outperforms other synthesis approaches [5]. A drawback of the weak bi-decomposition is that the synthesized circuits can have a large difference between the shortest and the longest path (unbalanced circuits). Recently, vectorial bi-decompositions were suggested as supplement to strong and weak bi-decompositions [6, 7]. The decomposition functions of these bi- decompositions are simpler than the given function because they are independent of the simultaneous change of several variables. Vectorial bi-decompositions can exist for functions without any strong bi-decomposition. Benefits of the vectorial bi-decomposition are their contribution to balanced circuits and the increased num- ber of decomposition possibilities in comparison to the strong bi-decomposition. All bi-decomposition approaches mentioned above utilize the Boolean Differential Calculus (BDC) [3, 4, 8–12] to find optimal bi-decompositions. There are several other approaches of bi-decompositions which demonstrate the interest on this useful synthesis method; however, these other approaches are not directly helpful to solve the problem explored in this paper. In [13] a method for disjoint bi-decompositions with an extension to non-disjoint bi-decompositions for a single common variable are suggested. A graph-based approach for bi-decompo- sitions was suggested in [14]. Unfortunately, the used benchmarks in [5] and [14] overlap only partially. One common benchmark is t481 where our approach from [5] outperforms the graph-based approach from [14] in the number of gates (17/25). Recently, semi-tensor products of matrices were suggested for bi-decompositions of Boolean and multi-valued functions [15]. However, this paper does not contain experimental results of benchmark circuits. It is a property of the given function whether it can be decomposed into two simpler decomposition functions using a certain type of bi-decomposition. The possibility to find a bi-decomposition increases when the function to decompose can be chosen from a lattice of Boolean functions. Incompletely specified functions FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 31, No 2, June 2018, pp. 223 - 240 https://doi.org/10.2298/FUEE1802223S Bernd Steinbach1, Christian Posthoff2 Received October 21, 2017; received in revised form January 24, 2018 Corresponding author: Bernd Steinbach Institute of Computer Science, Freiberg University of Mining and Technology, Bernhard-von-Cotta-Str. 2, D-09596 Freiberg, Germany (E-mail: steinb@informatik.tu-freiberg.de) *An earlier version of this paper was presented as an invited address at the Reed-Muller 2017 Workshop, Novi Sad, Serbia, May 24-25, 2017 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) COMPACT XOR-BI-DECOMPOSITION FOR LATTICES OF BOOLEAN FUNCTIONS* 1Freiberg University of Mining and Technology, Institute of Computer Science, Freiberg, Germany 2The University of the West Indies, Department of Computing and Information Technology, Saint Augustine, Trinidad and Tobago Abstract. Bi-Decomposition is a powerful approach for the synthesis of multi-level combinational circuits because it utilizes the properties of the given functions to find small circuits, with low power consumption and low delay. Compact bi-decompositions restrict the variables in the support of the decomposition functions as much as possible. Methods to find compact AND-, OR-, or XOR-bi-decompositions for a given completely specified function are well known. A lattice of Boolean functions represents all possible functions which are defined by an incompletely specified function. Lattices of Boolean Functions significantly increase the possibilities to synthesize a minimal circuit. However, so far only methods to find compact AND- or OR-bi-decompositions for lattices of Boolean functions are known. This gap, i.e., a method to find a compact XOR-bi-decomposition for a lattice of Boolean functions, has been closed by the approach suggested in this paper. Key words: synthesis, combinational circuit, lattice of Boolean functions, XOR-bidecomposition, Boolean Differential Calculus, derivative operations. 2 B. Steinbach and C. Posthoff: proach that decomposes a given Boolean function into two simpler decomposition functions which are combined by an AND-, an OR-, or an XOR-gate. For the aim of simplification, the bi-decomposition utilizes the properties of the given Boolean function to design circuit structures of a small area, low power consumption, and low delay [1]. There are several types of bi-decompositions. Both decomposition functions of each strong bi-decomposition are simpler than the given function because they depend on fewer variables. Unfortunately, there are functions for which no strong bi-decomposition exists. Le [2] bridged this gap by means of the weak bi-decom- position. He found that each function, for which neither a weak OR bi-decom- position nor a weak AND bi-decomposition exists, can be simplified by a strong XOR bi-decomposition. A simplified proof of the completeness of the strong and weak bi-decomposition is given in [3, 4]. An implementation that reuses already decomposed blocks outperforms other synthesis approaches [5]. A drawback of the weak bi-decomposition is that the synthesized circuits can have a large difference between the shortest and the longest path (unbalanced circuits). Recently, vectorial bi-decompositions were suggested as supplement to strong and weak bi-decompositions [6, 7]. The decomposition functions of these bi- decompositions are simpler than the given function because they are independent of the simultaneous change of several variables. Vectorial bi-decompositions can exist for functions without any strong bi-decomposition. Benefits of the vectorial bi-decomposition are their contribution to balanced circuits and the increased num- ber of decomposition possibilities in comparison to the strong bi-decomposition. All bi-decomposition approaches mentioned above utilize the Boolean Differential Calculus (BDC) [3, 4, 8–12] to find optimal bi-decompositions. There are several other approaches of bi-decompositions which demonstrate the interest on this useful synthesis method; however, these other approaches are not directly helpful to solve the problem explored in this paper. In [13] a method for disjoint bi-decompositions with an extension to non-disjoint bi-decompositions for a single common variable are suggested. A graph-based approach for bi-decompo- sitions was suggested in [14]. Unfortunately, the used benchmarks in [5] and [14] overlap only partially. One common benchmark is t481 where our approach from [5] outperforms the graph-based approach from [14] in the number of gates (17/25). Recently, semi-tensor products of matrices were suggested for bi-decompositions of Boolean and multi-valued functions [15]. However, this paper does not contain experimental results of benchmark circuits. It is a property of the given function whether it can be decomposed into two simpler decomposition functions using a certain type of bi-decomposition. The possibility to find a bi-decomposition increases when the function to decompose can be chosen from a lattice of Boolean functions. Incompletely specified functions Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 3 were traditionally used as a source of a lattice of Boolean functions. The ON-set- function fq(x) and the OFF-set-function fr(x) are the preferred mark functions of these lattices. The introduction of derivative operations for lattices of Boolean functions [4, 16, 17] facilitates the application of lattices in circuit design. A strong bi-decomposition divides the variables of the function to decompose into three disjoint subsets. The variables xa control only the decomposition func- tion g, the variables xb control only the decomposition function h, and the variables xc are commonly used for both the decomposition functions g and h. The more variables in the dedicated sets of variables xa and xb the simpler are the decom- position functions g and h. A compact strong bi-decomposition uses the largest possible sets of xa and xb. There are formulas [3, 4, 10–12] containing operations of the Boolean Differen- tial Calculus that can be used to decide whether a lattice of Boolean functions con- tains a compact strong AND- or a compact strong OR-bi-decomposition. Unfor- tunately, so far it is only possible to find a compact strong XOR-bi-decomposition for a single decomposition function or to assign only a single variable to the set xa for the check whether a lattice of Boolean functions contains a strong XOR- bi-decomposition [18]. We suggest in this paper an approach to find also compact strong XOR-bi-decompositions for a lattice of Boolean functions. This new method combines the ideas of simplifications used in both the strong and the vectorial bi- decomposition. Hence, we are going to solve a problem that is more than 20 years known as unsolved. The rest of this paper is organized as follows. Section 2 briefly describes lat- tices of Boolean functions and single derivatives of functions belonging to such a lattice. Section 3 summarizes the known approach to find and determine non- compact XOR-bi-decompositions. Section 4 introduces into the theory of compact XOR-bi-bi-decompositions, concludes the main theorem and the consequence for compact XOR-bi-bi-decompositions, and provides two consecutive algorithms that solve this task using XBOOLE [19, 20]. Section 5 demonstrates the benefits of the suggested new decomposition method by means of a simple example. Section 6 concludes the paper. 2 LATTICES OF BOOLEAN FUNCTIONS Lattices of Boolean functions occur, e.g., in circuit design where each function of the lattice can be chosen as a function to realize the circuit structure. Hence, lattices of Boolean functions provide a possibility for optimization in circuit design. Widely used are lattices which can be modeled as incompletely specified func- tion (ISF). Such an incompletely specified Boolean function divides the 2n patterns 224 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 225 2 B. Steinbach and C. Posthoff: proach that decomposes a given Boolean function into two simpler decomposition functions which are combined by an AND-, an OR-, or an XOR-gate. For the aim of simplification, the bi-decomposition utilizes the properties of the given Boolean function to design circuit structures of a small area, low power consumption, and low delay [1]. There are several types of bi-decompositions. Both decomposition functions of each strong bi-decomposition are simpler than the given function because they depend on fewer variables. Unfortunately, there are functions for which no strong bi-decomposition exists. Le [2] bridged this gap by means of the weak bi-decom- position. He found that each function, for which neither a weak OR bi-decom- position nor a weak AND bi-decomposition exists, can be simplified by a strong XOR bi-decomposition. A simplified proof of the completeness of the strong and weak bi-decomposition is given in [3, 4]. An implementation that reuses already decomposed blocks outperforms other synthesis approaches [5]. A drawback of the weak bi-decomposition is that the synthesized circuits can have a large difference between the shortest and the longest path (unbalanced circuits). Recently, vectorial bi-decompositions were suggested as supplement to strong and weak bi-decompositions [6, 7]. The decomposition functions of these bi- decompositions are simpler than the given function because they are independent of the simultaneous change of several variables. Vectorial bi-decompositions can exist for functions without any strong bi-decomposition. Benefits of the vectorial bi-decomposition are their contribution to balanced circuits and the increased num- ber of decomposition possibilities in comparison to the strong bi-decomposition. All bi-decomposition approaches mentioned above utilize the Boolean Differential Calculus (BDC) [3, 4, 8–12] to find optimal bi-decompositions. There are several other approaches of bi-decompositions which demonstrate the interest on this useful synthesis method; however, these other approaches are not directly helpful to solve the problem explored in this paper. In [13] a method for disjoint bi-decompositions with an extension to non-disjoint bi-decompositions for a single common variable are suggested. A graph-based approach for bi-decompo- sitions was suggested in [14]. Unfortunately, the used benchmarks in [5] and [14] overlap only partially. One common benchmark is t481 where our approach from [5] outperforms the graph-based approach from [14] in the number of gates (17/25). Recently, semi-tensor products of matrices were suggested for bi-decompositions of Boolean and multi-valued functions [15]. However, this paper does not contain experimental results of benchmark circuits. It is a property of the given function whether it can be decomposed into two simpler decomposition functions using a certain type of bi-decomposition. The possibility to find a bi-decomposition increases when the function to decompose can be chosen from a lattice of Boolean functions. Incompletely specified functions Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 3 were traditionally used as a source of a lattice of Boolean functions. The ON-set- function fq(x) and the OFF-set-function fr(x) are the preferred mark functions of these lattices. The introduction of derivative operations for lattices of Boolean functions [4, 16, 17] facilitates the application of lattices in circuit design. A strong bi-decomposition divides the variables of the function to decompose into three disjoint subsets. The variables xa control only the decomposition func- tion g, the variables xb control only the decomposition function h, and the variables xc are commonly used for both the decomposition functions g and h. The more variables in the dedicated sets of variables xa and xb the simpler are the decom- position functions g and h. A compact strong bi-decomposition uses the largest possible sets of xa and xb. There are formulas [3, 4, 10–12] containing operations of the Boolean Differen- tial Calculus that can be used to decide whether a lattice of Boolean functions con- tains a compact strong AND- or a compact strong OR-bi-decomposition. Unfor- tunately, so far it is only possible to find a compact strong XOR-bi-decomposition for a single decomposition function or to assign only a single variable to the set xa for the check whether a lattice of Boolean functions contains a strong XOR- bi-decomposition [18]. We suggest in this paper an approach to find also compact strong XOR-bi-decompositions for a lattice of Boolean functions. This new method combines the ideas of simplifications used in both the strong and the vectorial bi- decomposition. Hence, we are going to solve a problem that is more than 20 years known as unsolved. The rest of this paper is organized as follows. Section 2 briefly describes lat- tices of Boolean functions and single derivatives of functions belonging to such a lattice. Section 3 summarizes the known approach to find and determine non- compact XOR-bi-decompositions. Section 4 introduces into the theory of compact XOR-bi-bi-decompositions, concludes the main theorem and the consequence for compact XOR-bi-bi-decompositions, and provides two consecutive algorithms that solve this task using XBOOLE [19, 20]. Section 5 demonstrates the benefits of the suggested new decomposition method by means of a simple example. Section 6 concludes the paper. 2 LATTICES OF BOOLEAN FUNCTIONS Lattices of Boolean functions occur, e.g., in circuit design where each function of the lattice can be chosen as a function to realize the circuit structure. Hence, lattices of Boolean functions provide a possibility for optimization in circuit design. Widely used are lattices which can be modeled as incompletely specified func- tion (ISF). Such an incompletely specified Boolean function divides the 2n patterns Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 3 were traditionally used as a source of a lattice of Boolean functions. The ON-set- function fq(x) and the OFF-set-function fr(x) are the preferred mark functions of these lattices. The introduction of derivative operations for lattices of Boolean functions [4, 16, 17] facilitates the application of lattices in circuit design. A strong bi-decomposition divides the variables of the function to decompose into three disjoint subsets. The variables xa control only the decomposition func- tion g, the variables xb control only the decomposition function h, and the variables xc are commonly used for both the decomposition functions g and h. The more variables in the dedicated sets of variables xa and xb the simpler are the decom- position functions g and h. A compact strong bi-decomposition uses the largest possible sets of xa and xb. There are formulas [3, 4, 10–12] containing operations of the Boolean Differen- tial Calculus that can be used to decide whether a lattice of Boolean functions con- tains a compact strong AND- or a compact strong OR-bi-decomposition. Unfor- tunately, so far it is only possible to find a compact strong XOR-bi-decomposition for a single decomposition function or to assign only a single variable to the set xa for the check whether a lattice of Boolean functions contains a strong XOR- bi-decomposition [18]. We suggest in this paper an approach to find also compact strong XOR-bi-decompositions for a lattice of Boolean functions. This new method combines the ideas of simplifications used in both the strong and the vectorial bi- decomposition. Hence, we are going to solve a problem that is more than 20 years known as unsolved. The rest of this paper is organized as follows. Section 2 briefly describes lat- tices of Boolean functions and single derivatives of functions belonging to such a lattice. Section 3 summarizes the known approach to find and determine non- compact XOR-bi-decompositions. Section 4 introduces into the theory of compact XOR-bi-bi-decompositions, concludes the main theorem and the consequence for compact XOR-bi-bi-decompositions, and provides two consecutive algorithms that solve this task using XBOOLE [19, 20]. Section 5 demonstrates the benefits of the suggested new decomposition method by means of a simple example. Section 6 concludes the paper. 2 LATTICES OF BOOLEAN FUNCTIONS Lattices of Boolean functions occur, e.g., in circuit design where each function of the lattice can be chosen as a function to realize the circuit structure. Hence, lattices of Boolean functions provide a possibility for optimization in circuit design. Widely used are lattices which can be modeled as incompletely specified func- tion (ISF). Such an incompletely specified Boolean function divides the 2n patterns 224 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 225 4 B. Steinbach and C. Posthoff: x of the Boolean space Bn into three disjoint sets: x ∈ don’t-care-set ⇔ fϕ (x1,...,xn) = 1 ⇔ it is allowed to choose the function value of f (x) without any restrictions; x ∈ ON-set ⇔ fq(x1,...,xn) = 1 ⇔ ( fϕ (x1,...,xn) = 0)∧( f (x1,...,xn) = 1) ; x ∈ OFF-set ⇔ fr(x1,...,xn) = 1 ⇔ ( fϕ (x1,...,xn) = 0)∧( f (x1,...,xn) = 0) . Each pair of these mark functions can be used to specify all functions of the lattice. A function f (x) belongs to the lattice L 〈 fq(x), fr(x) 〉 if fq(x) ≤ f (x) ≤ fr(x) . The single derivatives with regard to xi of all functions of a lattice L 〈 fq(x), fr(x) 〉 results again in a lattice of Boolean function that is specified by the mark functions: f ∂ xiq (x1) = maxxi fq(xi,x1)∧ max xi fr(xi,x1) , (1) f ∂ xir (x1) = minxi fq(xi,x1)∨ min xi fr(xi,x1) . (2) 3 KNOWN NON-COMPACT XOR-BI-DECOMPOSITIONS FOR LATTICES OF BOOLEAN FUNCTIONS A lattice of Boolean functions L 〈 fq(xa,xb,xc), fr(xa,xb,xc) 〉 contains at least one function f (xa,xb,xc) that is strongly XOR-bi-decomposable with regard to the sin- gle variable xa and the set of variables xb if and only if max xb m f ∂ xaq (xb,xc)∧ f ∂ xa r (xb,xc) = 0 . (3) The decomposition function g(xa,xc) of this XOR-bi-decomposition is uniquely specified by g(xa,xc) = xa ∧ max xb m f ∂ xaq (xb,xc) , (4) and the associated decomposition function h(xb,xc) can be chosen from the lattice with the mark functions hq(xb,xc) = max xa ((g(xa,xc)∧ fq(xa,xb,xc))∨(g(xa,xc)∧ fr(xa,xb,xc))) , (5) hr(xb,xc) = max xa ((g(xa,xc)∧ fr(xa,xb,xc))∨(g(xa,xc)∧ fq(xa,xb,xc))) . (6) More details about strong and weak bi-decompositions are given in [3, 4, 10, 11]. 226 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 227 4 B. Steinbach and C. Posthoff: x of the Boolean space Bn into three disjoint sets: x ∈ don’t-care-set ⇔ fϕ (x1,...,xn) = 1 ⇔ it is allowed to choose the function value of f (x) without any restrictions; x ∈ ON-set ⇔ fq(x1,...,xn) = 1 ⇔ ( fϕ (x1,...,xn) = 0)∧( f (x1,...,xn) = 1) ; x ∈ OFF-set ⇔ fr(x1,...,xn) = 1 ⇔ ( fϕ (x1,...,xn) = 0)∧( f (x1,...,xn) = 0) . Each pair of these mark functions can be used to specify all functions of the lattice. A function f (x) belongs to the lattice L 〈 fq(x), fr(x) 〉 if fq(x) ≤ f (x) ≤ fr(x) . The single derivatives with regard to xi of all functions of a lattice L 〈 fq(x), fr(x) 〉 results again in a lattice of Boolean function that is specified by the mark functions: f ∂ xiq (x1) = maxxi fq(xi,x1)∧ max xi fr(xi,x1) , (1) f ∂ xir (x1) = minxi fq(xi,x1)∨ min xi fr(xi,x1) . (2) 3 KNOWN NON-COMPACT XOR-BI-DECOMPOSITIONS FOR LATTICES OF BOOLEAN FUNCTIONS A lattice of Boolean functions L 〈 fq(xa,xb,xc), fr(xa,xb,xc) 〉 contains at least one function f (xa,xb,xc) that is strongly XOR-bi-decomposable with regard to the sin- gle variable xa and the set of variables xb if and only if max xb m f ∂ xaq (xb,xc)∧ f ∂ xa r (xb,xc) = 0 . (3) The decomposition function g(xa,xc) of this XOR-bi-decomposition is uniquely specified by g(xa,xc) = xa ∧ max xb m f ∂ xaq (xb,xc) , (4) and the associated decomposition function h(xb,xc) can be chosen from the lattice with the mark functions hq(xb,xc) = max xa ((g(xa,xc)∧ fq(xa,xb,xc))∨(g(xa,xc)∧ fr(xa,xb,xc))) , (5) hr(xb,xc) = max xa ((g(xa,xc)∧ fr(xa,xb,xc))∨(g(xa,xc)∧ fq(xa,xb,xc))) . (6) More details about strong and weak bi-decompositions are given in [3, 4, 10, 11]. Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 5 4 COMPACT XOR-BI-DECOMPOSITION FOR LATTICES OF BOOLEAN FUNCTIONS A compact bi-decomposition is determined by maximal numbers of variables in the dedicated sets xa and xb. The number of commonly used variables xc is as small as possible, and consequently the decomposition functions g(xa,xc) and h(xb,xc) will be the simplest in case of a desirable compact bi-decomposition. Condition (3) allows us to find a maximal number of possible variables for the dedicated set xb of an XOR-bi-decomposition, but it unfortunately restricts to a single variable xa of the dedicated set xa. As initial solution we can calculate the decomposition function g(xa,xc) using (4) and the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 , using (5) and (6), from which the decomposition function h(xb,xc) can be chosen. The set of all variables x is distributed to the three disjoint sets xa = xa, xb, and xc. We assume that xb contains as much as possible variables, because it can be verified by (3) that no other variable can be added to the dedicated set xb without loosing the property of an XOR-bi-decomposition of the given lattice. A given XOR-bi-decomposition is not compact if at least one variable can be moved from xc to xa. Moving a variable xi from xc to xa does not change the set of variables the function g(xa,xc) is depending on; however, it reduces the support of the function h(xb,xc). The set of variables xc is split into xi and xc0. Due to the evaluation of Condition (3) for all variables, we know that the function h(xb,xc) depends on all variables (xb,xc). Hence, only another function h′(xb,xc0) is able to solve the problem. In the context of the XOR-bi-decomposi- tion, the following transformation steps show the key idea to solve the problem: g(xa0,xc)⊕ h(xb,xc) (7) = g(xa0,xc0,xi)⊕ h(xb,xc0,xi) (8) = g(xa0,xc0,xi)⊕(xi ⊕ h′(xb,xc0)) (9) = (g(xa0,xc0,xi)⊕ xi)⊕ h′(xb,xc0) (10) = g′(xa0,xi,xc0)⊕ h′(xb,xc0) (11) = g′(xa,xc0)⊕ h′(xb,xc0) ; (12) • the step from (7) to (8) emphasizes the variable xi as element of the given set of variables xc; • the step from (8) to (9) requires that the function h(xb,xc0,xi) is linear in xi. This property enables or prohibits the whole transformation; • the step from (9) to (10) moves the variable xi to the other decomposition function of the XOR-bi-decomposition; 226 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 227 6 B. Steinbach and C. Posthoff: • the step from (10) to (11) includes the variable xi into the new decompo- sition function g′(xa0,xi,xc0). This transformation is possible without any restriction; • the step from (11) to (12) emphasizes that xi does not belong to the com- monly used variables xc0, because h′(xb,xc0) does not depend on xi; hence, xi extends the dedicated set of variables xa0 to xa = (xa,xi). The only condition for the transformation from (7) to (12) is that the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 contains at least one function that satisfies: ∂ h(x1,xi) ∂ xi = 1 . Theorem 1 (Linear Separation of a Variable for a Function of a Lattice) A lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 contains at least one function h(x1,xi) that can be represented by h(x1,xi) = xi ⊕ h′(x1) (13) if and only if the condition h∂ xir (x1) = 0 (14) is satisfied. Proof 1 necessary: Due to Condition (14) the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 contains at least one function that satisfies ∂ h(x1,xi) ∂ xi = 1 . (15) It is well-known that (15) is satisfied if the function h(x1,xi) is linear with regard to the variable xi as shown in (13). Hence, we have Theo- rem 1 in the direction (14) ⇒ (13). sufficient: Function h(x1,xi) (13) belongs to the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 so that it holds: hq(xb,xc) ≤ h(x1,xi) ≤ hr(xb,xc) . (16) Using (13), the inequality (16) can be split into the two inequalities hq(xb,xc) ≤ h(x1,xi) = xi ⊕ h′(x1) hq(xb,xc) ≤ (xi ∨ h′(x1))(xi ∨ h′(x1)) , (17) 228 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 229 6 B. Steinbach and C. Posthoff: • the step from (10) to (11) includes the variable xi into the new decompo- sition function g′(xa0,xi,xc0). This transformation is possible without any restriction; • the step from (11) to (12) emphasizes that xi does not belong to the com- monly used variables xc0, because h′(xb,xc0) does not depend on xi; hence, xi extends the dedicated set of variables xa0 to xa = (xa,xi). The only condition for the transformation from (7) to (12) is that the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 contains at least one function that satisfies: ∂ h(x1,xi) ∂ xi = 1 . Theorem 1 (Linear Separation of a Variable for a Function of a Lattice) A lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 contains at least one function h(x1,xi) that can be represented by h(x1,xi) = xi ⊕ h′(x1) (13) if and only if the condition h∂ xir (x1) = 0 (14) is satisfied. Proof 1 necessary: Due to Condition (14) the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 contains at least one function that satisfies ∂ h(x1,xi) ∂ xi = 1 . (15) It is well-known that (15) is satisfied if the function h(x1,xi) is linear with regard to the variable xi as shown in (13). Hence, we have Theo- rem 1 in the direction (14) ⇒ (13). sufficient: Function h(x1,xi) (13) belongs to the lattice L 〈 hq(xb,xc),hr(xb,xc) 〉 so that it holds: hq(xb,xc) ≤ h(x1,xi) ≤ hr(xb,xc) . (16) Using (13), the inequality (16) can be split into the two inequalities hq(xb,xc) ≤ h(x1,xi) = xi ⊕ h′(x1) hq(xb,xc) ≤ (xi ∨ h′(x1))(xi ∨ h′(x1)) , (17) Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 7 and hr(xb,xc) ≥ h(x1,xi) = xi ⊕ h′(x1) hr(xb,xc) ≤ h(x1,xi) = xi ⊕ h′(x1) hr(xb,xc) ≤ (xi ∨ h′(x1))(xi ∨ h′(x1)) . (18) The right-hand-side functions of (17) and (18) are equal to or larger than the mark functions hq(xb,xc) and hr(xb,xc). The mark function h∂ xir (x1) of Condition (14) is defined by: h∂ xir (x1) = minxi hq(xi,x1)∨ min xi hr(xi,x1) . (19) Now, we substitute the function h(x1,xi) of (17) for hq(xb,xc) and the function h(x1,xi) of (18) for hr(xb,xc) into (19). These functions are equal to or larger than the replaced functions. So we get: h∂ xir (x1) = minxi ( (xi ∨ h′(x1))∧(xi ∨ h′(x1)) ) ∨ min xi ( (xi ∨ h′(x1))∧(xi ∨ h′(x1)) ) = min xi (xi ∨ h′(x1))∧ min xi (xi ∨ h′(x1))∨ min xi (xi ∨ h′(x1))∧ min xi (xi ∨ h′(x1)) = ( h′(x1)∨ min xi (xi) ) ∧ ( h′(x1)∨ min xi (xi) ) ∨ ( h′(x1)∨ min xi (xi) ) ∧ ( h′(x1)∨ min xi (xi) ) = ( h′(x1)∨ 0 ) ∧ ( h′(x1)∨ 0 ) ∨ ( h′(x1)∨ 0 ) ∧ ( h′(x1)∨ 0 ) = h′(x1)∧ h′(x1)∨ h′(x1)∧ h′(x1) = 0 ∨ 0 = 0 . Hence, Condition (14) is not only satisfied for the two mark functions hq(xb,xc) and hr(xb,xc), but also for the function (13) which is linear with regard to xi and belongs to the evaluated lattice. That shows the implication (13) ⇒ (14) and completes Theorem 1. Consequence 1 An XOR-bi-decomposition is compact, if the set of variables xb is as large as possible (verified by Condition (3)), and within an iterative procedure 228 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 229 8 B. Steinbach and C. Posthoff: all variables xi of the initial set xc that satisfy Condition (14) are used to transform g(xa0,xc0,xi) to g′(xa,xc0) by g′(xa,xc0) = xi ⊕ g(xa0,xc0,xi) (20) and the associated new lattice L 〈 h′q(xb,xc0),h ′ r(xb,xc0) 〉 is adjusted by h′q(xb,xc0) = maxxi (xi hq(xb,xc0,xi)∨ xi hr(xb,xc0,xi)) , (21) h′r(xb,xc0) = maxxi (xi hr(xb,xc0,xi)∨ xi hq(xb,xc0,xi)) . (22) A precondition for a compact XOR-bi-decomposition is the existence of two variables xa and xb for which the given lattice L 〈 fq(x), fr(x) 〉 contains at least one function which has a strong XOR-bi-decomposition with regard to these variables. Algorithm 1 analyzes whether there is an XOR-bi-decomposition for the given lat- tice with regard to one pair of variables xa and xb. Algorithm 1 determines these variables if they exist. Algorithm 1 Initial XOR-bi-decomposition of the lattice L 〈 fq(x), fr(x) 〉 with re- gard to the variables xa and xb Require: TVLs of fq(x)and fr(x) in ODA-form Ensure: Boolean variable hasX ORbd: it is true if the given lattice contains at least one XOR-bi-decomposable function and f alse otherwise Ensure: set of variables (SV) of xa and xb: variables for which the lattice contains at least one function with a strong XOR-bi-decomposition 1: all var ← SV UNI( fq, fr) 2: hasX ORbd ← f alse 3: xa ← /0 4: while hasX ORbd ∧ SV NEXT(all var,xa,xa) do 5: xb ← xa 6: f ∂ xaq ← ISC(MAXK( fq,xa),MAXK( fr,xa)) 7: f ∂ xar ← UNI(MINK( fq,xa),MINK( fr,xa)) 8: while hasX ORbd ∧ SV NEXT(all var,xb,xb) do 9: if TE ISC(MAXK( f ∂ xaq ,xb), f ∂ xa r ) then 10: hasX ORbd ← true 11: end if 12: end while 13: end while 14: return (hasX ORbd,xa,xb) 230 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 231 8 B. Steinbach and C. Posthoff: all variables xi of the initial set xc that satisfy Condition (14) are used to transform g(xa0,xc0,xi) to g′(xa,xc0) by g′(xa,xc0) = xi ⊕ g(xa0,xc0,xi) (20) and the associated new lattice L 〈 h′q(xb,xc0),h ′ r(xb,xc0) 〉 is adjusted by h′q(xb,xc0) = maxxi (xi hq(xb,xc0,xi)∨ xi hr(xb,xc0,xi)) , (21) h′r(xb,xc0) = maxxi (xi hr(xb,xc0,xi)∨ xi hq(xb,xc0,xi)) . (22) A precondition for a compact XOR-bi-decomposition is the existence of two variables xa and xb for which the given lattice L 〈 fq(x), fr(x) 〉 contains at least one function which has a strong XOR-bi-decomposition with regard to these variables. Algorithm 1 analyzes whether there is an XOR-bi-decomposition for the given lat- tice with regard to one pair of variables xa and xb. Algorithm 1 determines these variables if they exist. Algorithm 1 Initial XOR-bi-decomposition of the lattice L 〈 fq(x), fr(x) 〉 with re- gard to the variables xa and xb Require: TVLs of fq(x)and fr(x) in ODA-form Ensure: Boolean variable hasX ORbd: it is true if the given lattice contains at least one XOR-bi-decomposable function and f alse otherwise Ensure: set of variables (SV) of xa and xb: variables for which the lattice contains at least one function with a strong XOR-bi-decomposition 1: all var ← SV UNI( fq, fr) 2: hasX ORbd ← f alse 3: xa ← /0 4: while hasX ORbd ∧ SV NEXT(all var,xa,xa) do 5: xb ← xa 6: f ∂ xaq ← ISC(MAXK( fq,xa),MAXK( fr,xa)) 7: f ∂ xar ← UNI(MINK( fq,xa),MINK( fr,xa)) 8: while hasX ORbd ∧ SV NEXT(all var,xb,xb) do 9: if TE ISC(MAXK( f ∂ xaq ,xb), f ∂ xa r ) then 10: hasX ORbd ← true 11: end if 12: end while 13: end while 14: return (hasX ORbd,xa,xb) Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 9 Algorithm 1 uses two nested while-loops for the selection of the variables xa and xb. The basic set of all variables is prepared in line 1 using the XBOOLE- function SV UNI (set of variables - union). The sequential selection of the variables xa and xb is realized by two XBOOLE-functions SV NEXT (set of variables - next variable) that control these while-loops. The variable hasX ORbd is used to indicate the Boolean result whether the lattice contains at least one function with a strong XOR-bi-decomposition. This variable is also used to terminate both while-loops if a strong XOR-bi-decomposition is detected. XBOOLE-functions ISC (intersection), UNI (union), MAXK (k-fold maxi- mum), and MINK (k-fold minimum) calculate in lines 6 and 7 the mark functions of the derivative of the given lattice with regard to the single variables xa. XBOOLE- function TE ISC (test empty - intersection) checks in line 9 Condition (3) for the strong XOR-bi-decomposition with regard to the actually selected variables xa and xb. In the case that this condition is satisfied, the control variable hasX ORbd is changed to the value true in line 10. Algorithm 2 extends a found initial XOR-bi-decomposition to a compact one. Initial steps determine all variables (line 1), the basic sets of commonly used vari- ables xc (line 2) and dedicated variables xb (line 3), and the precondition (line 4) for the selection of variables xb by means of the XBOOLE-function SV NEXT in line 8. The mark functions of the derivative of the given lattice with regard to the single variables xa are needed in Condition (3) to decide about the possibility to extend the set xb; they are calculated in lines 5 and 6 based on (1) and (2). The help-function h0 stores the intermediate result of the k-fold maximum with regard to the already known variables of the set xb (line 7). The while-loop in lines 8 to 13 extends the set xb to the maximal possible num- ber of variables of a strong XOR-bi-decomposition for the given lattice. Condition (3) is verified in line 9 for the temporally extended set xb. If this condition is satis- fied for the set of variables xb ∪ xb, the set of variables xb is permanently extended in line 10 and the help-function h0 is adjusted in line 11. Knowing the maximal set of variables xb, basic versions of the wanted functions can be calculated: • g(xa,xc) based on (4) in line 14; • hq(xb,xc) based on (5) in line 15; and • hr(xb,xc) based on (6) in line 16. In a second while-loop (lines 20 to 28) the set of variables xa is extended. Initial steps determine the new set of commonly used variables xc (line 17), the basic set 230 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 231 10 B. Steinbach and C. Posthoff: Algorithm 2 Compact strong XOR-bi-decomposition of the lattice L 〈 fq(x), fr(x) 〉 Require: TVLs of fq(x) and fr(x); initial SVs of xa and xb Ensure: TVL of g(xa,xc): decomposition function Ensure: TVLs of hq(xb,xc) and hr(xb,xc): decomposition lattice Ensure: SVs of xa, xb, and xc: disjoint sets of variables 1: all var ← SV UNI( fq, fr) 2: xc ← SV DIF(SV DIF(all var,xa),xb)) 3: xb ← xb 4: xb ← /0 5: f ∂ xaq ← ISC(MAXK( fq,xa),MAXK( fr,xa)) 6: f ∂ xar ← UNI(MINK( fq,xa),MINK( fr,xa)) 7: h0 ← MAXK( f ∂ xaq ,xb) 8: while SV NEXT(xc,xb,xb) do 9: if TE ISC(MAXK(h0,xb), f ∂ xar ) then 10: xb ← SV UNI(xb,xb) 11: h0 ← MAXK( f ∂ xaq ,xb) 12: end if 13: end while 14: g ← ISC(SV GET(xa),h0) 15: hq ← MAXK(UNI(ISC(g, fq),ISC(g, fr)),xa) 16: hr ← MAXK(UNI(ISC(g, fr),ISC(g, fq)),xa) 17: xc ← SV DIF(SV DIF(all var,xa),xb)) 18: xa ← xa 19: xi ← /0 20: while SV NEXT(xc,xi,xi) do 21: if TE UNI(MINK(hq,xi),MINK(hr,xi)) then 22: xa ← SV UNI(xa,xi) 23: xi ← SV GET(xi) 24: g ← SYD(xi,g) 25: hq ← MAXK(UNI(ISC(xi,hq),ISC(xi,hr)),xi) 26: hr ← MAXK(UNI(ISC(xi,hr),ISC(xi,hq)),xi) 27: end if 28: end while 29: xc ← SV DIF(xc,xa) 30: return (g,hq,hr,xa,xb,xc) of variables xa (line 18), and the selection variable xi (line 19) needed to evaluate the possibility of the extension of xa. 232 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 233 10 B. Steinbach and C. Posthoff: Algorithm 2 Compact strong XOR-bi-decomposition of the lattice L 〈 fq(x), fr(x) 〉 Require: TVLs of fq(x) and fr(x); initial SVs of xa and xb Ensure: TVL of g(xa,xc): decomposition function Ensure: TVLs of hq(xb,xc) and hr(xb,xc): decomposition lattice Ensure: SVs of xa, xb, and xc: disjoint sets of variables 1: all var ← SV UNI( fq, fr) 2: xc ← SV DIF(SV DIF(all var,xa),xb)) 3: xb ← xb 4: xb ← /0 5: f ∂ xaq ← ISC(MAXK( fq,xa),MAXK( fr,xa)) 6: f ∂ xar ← UNI(MINK( fq,xa),MINK( fr,xa)) 7: h0 ← MAXK( f ∂ xaq ,xb) 8: while SV NEXT(xc,xb,xb) do 9: if TE ISC(MAXK(h0,xb), f ∂ xar ) then 10: xb ← SV UNI(xb,xb) 11: h0 ← MAXK( f ∂ xaq ,xb) 12: end if 13: end while 14: g ← ISC(SV GET(xa),h0) 15: hq ← MAXK(UNI(ISC(g, fq),ISC(g, fr)),xa) 16: hr ← MAXK(UNI(ISC(g, fr),ISC(g, fq)),xa) 17: xc ← SV DIF(SV DIF(all var,xa),xb)) 18: xa ← xa 19: xi ← /0 20: while SV NEXT(xc,xi,xi) do 21: if TE UNI(MINK(hq,xi),MINK(hr,xi)) then 22: xa ← SV UNI(xa,xi) 23: xi ← SV GET(xi) 24: g ← SYD(xi,g) 25: hq ← MAXK(UNI(ISC(xi,hq),ISC(xi,hr)),xi) 26: hr ← MAXK(UNI(ISC(xi,hr),ISC(xi,hq)),xi) 27: end if 28: end while 29: xc ← SV DIF(xc,xa) 30: return (g,hq,hr,xa,xb,xc) of variables xa (line 18), and the selection variable xi (line 19) needed to evaluate the possibility of the extension of xa. Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 11 Condition (14) of Theorem 1 is verified in line 21 using the formula (2) to determine the OFF-set of the derivative of a lattice with regard to the single variable xi. If this condition is satisfied: • the set of variables xa is extended by xi in line 22 using the XBOOLE- function SV UNI (set of variables - union); • xi is transformed in line 23 from a set of variables into the TVL representing x1 = 1 using the XBOOLE-function SV GET (set of variables - get); • the new function g is calculated in line 24 based on (20) using the XBOOLE- function SYD (symmetric difference); • the new ON-set function hq(x) is calculated in line 25 based on (21); and • the new OFF-set function hr(x) is calculated in line 26 based on (22). The restriction of the set of commonly used variables xc is realized in line 29 out- side of the loop, because the unchanged basic set xc is needed in the XBOOLE- function SV NEXT in line 20 to select the next variable xi. The complement oper- ations in lines 15, 16, 24, and 25 are realized using the XBOOLE-function CPL. 5 EXAMPLE 5.1 The Chosen Lattice and Conditions for the Synthesis 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 x3 0 0 1 1 1 1 0 0 x2 0 0 0 0 1 1 1 1 x1 Φ Φ Φ x4 x5 L 〈 fq(x), fr(x) 〉 (a) 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 x3 0 0 1 1 1 1 0 0 x2 0 0 0 0 1 1 1 1 x1 x4 x5 y = f (x) (b) Fig. 1. Karnaugh-maps of (a) the given lattice, and (b) chosen function of both bi-decompositions. Figure 1 (a) shows the Karnaugh-map of a lattice of eight Boolean functions. The simplest multi-level circuit structure for one of these functions must be found using AND-, OR-, and XOR-gates of two inputs where these inputs arbitrary can 232 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 233 12 B. Steinbach and C. Posthoff: be negated. The gates can be reused to simplify the circuit. As basis for com- parison serves a minimal disjunctive form, calculated by means of the well known Quine McCluskey algorithm. The synthesis of the given lattice of functions by bi-decompositions has been realized using both the know non-compact XOR-bi- decomposition and the new compact XOR-bi-decomposition. Using conditions given in [3, 4, 11] it can be verified that this lattice does not contain any function which has a strong bi-decomposition with regard to any dedicated sets of variables xa and xb for an AND- or an OR-gate. Figure 1 (b) shows the function chosen by both the known and the new bi-decomposition approach. Two don’t-cares are assigned to 0 and the other to 1. The simplest minimal disjunctive form realizes the function fq(x) of the lattice where all don’t-cares are assigned to 0. 5.2 Synthesis by Covering Using a Minimal Disjunctive Form The execution of the Quine McCluskey algorithm results in two minimal disjunc- tive forms of the same complexity. Both of them realize the ON-set function fq(x) and require the same number of gates and levels in a circuit. The chosen minimal disjunctive form is: fq(x) = (x1x2)x3 ∨(x1x2)(x4x5)∨(x1x2)(x4x5)∨(x2x3)(x4x5)∨ (x1x2)(x3x4)∨(x1x3)(x4x5)∨(x1(x2x3))(x4x5)∨(x2(x1x3))(x4x5) . (23) The parentheses in the conjunctions in (23) emphasize the chosen two-input AND- gates. Figure 2 shows the associated circuit structure in which as much as possible AND-gates are reused. The disjunction of eight conjunctions is realized by a tree of seven OR-gates. Seven AND-gates could be reused to build another conjunction. In total there are 18 AND-gates. The complete circuit consists of 25 two-input gates on six levels. 5.3 Synthesis Using the Known Non-Compact XOR-Bi-Decomposition Using Condition (3) it was found that the lattice of Figure 1 (a) contains at least one function that is XOR-bi-decomposable with regard to the single variable xa = x1 and the dedicated set xb = (x3,x5). Hence, the set of commonly used variables xc = (x2,x4). The decomposition function g(xa,xc) of an XOR-bi-decomposition is uniquely specified by (4), and we get g1(x1,x2,x4) = x1 ∧(x2 ∧ x4) . (24) It can directly be seen that there is a strong AND-bi-decomposition of g1(x1,x2,x4) into g2 = x1 and h2 = (x2 ∧ x4). No further decomposition is needed for these functions. 234 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 235 12 B. Steinbach and C. Posthoff: be negated. The gates can be reused to simplify the circuit. As basis for com- parison serves a minimal disjunctive form, calculated by means of the well known Quine McCluskey algorithm. The synthesis of the given lattice of functions by bi-decompositions has been realized using both the know non-compact XOR-bi- decomposition and the new compact XOR-bi-decomposition. Using conditions given in [3, 4, 11] it can be verified that this lattice does not contain any function which has a strong bi-decomposition with regard to any dedicated sets of variables xa and xb for an AND- or an OR-gate. Figure 1 (b) shows the function chosen by both the known and the new bi-decomposition approach. Two don’t-cares are assigned to 0 and the other to 1. The simplest minimal disjunctive form realizes the function fq(x) of the lattice where all don’t-cares are assigned to 0. 5.2 Synthesis by Covering Using a Minimal Disjunctive Form The execution of the Quine McCluskey algorithm results in two minimal disjunc- tive forms of the same complexity. Both of them realize the ON-set function fq(x) and require the same number of gates and levels in a circuit. The chosen minimal disjunctive form is: fq(x) = (x1x2)x3 ∨(x1x2)(x4x5)∨(x1x2)(x4x5)∨(x2x3)(x4x5)∨ (x1x2)(x3x4)∨(x1x3)(x4x5)∨(x1(x2x3))(x4x5)∨(x2(x1x3))(x4x5) . (23) The parentheses in the conjunctions in (23) emphasize the chosen two-input AND- gates. Figure 2 shows the associated circuit structure in which as much as possible AND-gates are reused. The disjunction of eight conjunctions is realized by a tree of seven OR-gates. Seven AND-gates could be reused to build another conjunction. In total there are 18 AND-gates. The complete circuit consists of 25 two-input gates on six levels. 5.3 Synthesis Using the Known Non-Compact XOR-Bi-Decomposition Using Condition (3) it was found that the lattice of Figure 1 (a) contains at least one function that is XOR-bi-decomposable with regard to the single variable xa = x1 and the dedicated set xb = (x3,x5). Hence, the set of commonly used variables xc = (x2,x4). The decomposition function g(xa,xc) of an XOR-bi-decomposition is uniquely specified by (4), and we get g1(x1,x2,x4) = x1 ∧(x2 ∧ x4) . (24) It can directly be seen that there is a strong AND-bi-decomposition of g1(x1,x2,x4) into g2 = x1 and h2 = (x2 ∧ x4). No further decomposition is needed for these functions. Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 13 y = fq(x)x1 x2 x3 x4 x5 Fig. 2. Circuit structure synthesized by Quine-McCluskey and reused two-input gates. y = f (x) g1g2 h2 h1 g3 h3 g4 h4 x1 x2 x3 x4 x5 Fig. 3. Circuit structure synthesized using the old non-compact XOR-bi-decomposition. The lattice of the decomposition function h1 can be calculated by (5) and (6) and contains in this example the single function h1(x2,x3,x4,x5) = (x3 ∧(x4 ⊕ x5))⊕(x2 ⊕ x3) . (25) By means of Condition (3) it can be verified that an XOR-bi-decomposition of L 〈 h1q,h1r 〉 with regard to xa = x2 and xb = (x4,x5) exists. Hence, only the variable x3 belongs to the set of commonly used variables xc. The decomposition function g(xa,xc) of this second XOR-bi-decomposition 234 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 235 14 B. Steinbach and C. Posthoff: was again calculated by (4): g3(x2,x3) = x2 ⊕ x3 . The lattice L 〈 h3q,h3r 〉 contains only the single function h3(x3,x4,x5) = x3 ∧(x4 ⊕ x5) for which a strong AND-bi-decomposition into g4 = x3 and h4 = (x4 ⊕ x5) exists. No further decomposition is needed for these functions. Figure 3 shows the syn- thesized circuit consisting of seven gates on four levels. 5.4 Optimized Synthesis Using the New Compact XOR-Bi-Decomposition For direct comparison we demonstrated the approach of the utilization of a linearly separable variable to get a compact XOR-bi-decomposition using the same lattice (shown in Figure 1 (a)) as before. y = f (x) g1 g2 h2 h1 g3 h3 x1 x2 x3 x4 x5 Fig. 4. Circuit structure synthesized using the new compact XOR-bi-decomposition. Using Condition (3) in Algorithm 1 the initial XOR-bi-decomposition with re- gard to the single variables xa = x1 and xb = x3 is found. In the first part of Al- gorithm 2 (lines 1 to 13) the dedicated set xb could be extended to (x3,x5) due to the check of variables x2, x4, and x5 within line 9 embedded in the loop of lines 8 to 13. Hence, the basic set of commonly used variables is xc = (x2,x4) which is determined in line 17. Algorithm 2 finds by Condition (14) in line 21 in the while-loop in lines 20 to 28 that the so fare detected lattice of h1 contains a function that is linear with regard to x2. Hence, x2 is included into the set xa in line 22, the new function g1 is calculated in lines 23 and 24 using the basic function g′1 (24): g1(x1,x2,x4) = x2 ⊕ g′1(x1,x2,x4) = x2 ⊕ ( x1 ∧(x2 ∧ x4) ) = (x1 ⊕ x2)∨(x2 ∧ x4) . (26) 236 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 237 14 B. Steinbach and C. Posthoff: was again calculated by (4): g3(x2,x3) = x2 ⊕ x3 . The lattice L 〈 h3q,h3r 〉 contains only the single function h3(x3,x4,x5) = x3 ∧(x4 ⊕ x5) for which a strong AND-bi-decomposition into g4 = x3 and h4 = (x4 ⊕ x5) exists. No further decomposition is needed for these functions. Figure 3 shows the syn- thesized circuit consisting of seven gates on four levels. 5.4 Optimized Synthesis Using the New Compact XOR-Bi-Decomposition For direct comparison we demonstrated the approach of the utilization of a linearly separable variable to get a compact XOR-bi-decomposition using the same lattice (shown in Figure 1 (a)) as before. y = f (x) g1 g2 h2 h1 g3 h3 x1 x2 x3 x4 x5 Fig. 4. Circuit structure synthesized using the new compact XOR-bi-decomposition. Using Condition (3) in Algorithm 1 the initial XOR-bi-decomposition with re- gard to the single variables xa = x1 and xb = x3 is found. In the first part of Al- gorithm 2 (lines 1 to 13) the dedicated set xb could be extended to (x3,x5) due to the check of variables x2, x4, and x5 within line 9 embedded in the loop of lines 8 to 13. Hence, the basic set of commonly used variables is xc = (x2,x4) which is determined in line 17. Algorithm 2 finds by Condition (14) in line 21 in the while-loop in lines 20 to 28 that the so fare detected lattice of h1 contains a function that is linear with regard to x2. Hence, x2 is included into the set xa in line 22, the new function g1 is calculated in lines 23 and 24 using the basic function g′1 (24): g1(x1,x2,x4) = x2 ⊕ g′1(x1,x2,x4) = x2 ⊕ ( x1 ∧(x2 ∧ x4) ) = (x1 ⊕ x2)∨(x2 ∧ x4) . (26) Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 15 Using (21) and (22) the new lattice L 〈 h1q,h1r 〉 is calculated in lines 25 and 26 of Algorithm 2. Due to the special case of the completely specified function h′1 (25) the result is also a completely specified function that is calculated by (21): h1(x3,x4,x5) = max x2 ( x2 ⊕ h′1(x2,x3,x4,x5)) ) = max x2 (x2 ⊕(x3 ∧(x4 ⊕ x5))⊕(x2 ⊕ x3)) = (x3 ∧(x4 ⊕ x5))⊕ x3 = (x4 ⊕ x5)∨ x3 . (27) Hence, h1(x3,x4,x5) depends only on three variables, and the comparison with g1(x1,x2,x4) confirms that only the variable x4 is shared. In this way the single variable of the dedicated set xa is implicitly extended to xa = (x1,x2). Algorithm 2 explicitly realizes this extension in line 22 using the XBOOLE operation SV UNI (set of variables - union). The expressions (26) and (27) show that there are OR-bi-decompositions for both decomposition functions g1 and h1. Figure 4 shows that the circuit structure, realized be means of the new method, only needs six gates on three levels. 5.5 Comparison of the Synthesis Results Table 1 summarizes the results of the synthesis of the given lattice of Boolean functions realized by: • the covering method using the Quine McCluskey approach to get a minimal disjunctive form which has been split into two-input gates that are reused as much as possible; • the bi-decomposition method where the known XOR-bi-decomposition of a lattice is restricted to the assignment of a single variable to the dedicated set xa; • the bi-decomposition method using the new XOR-bi-decomposition for a lattice that is able to realize a compact XOR-bi-decomposition. Both the needed area and the power consumption are estimated by the number of gates. The benefit of the bi-decomposition in comparison to the covering method is evident; the number of gates could be reduced, despite the seven reused gates in the covering approach, from 25 to seven in case of the known bi-decomposition and even to six when the new compact XOR-bi-decomposition is used. This is a reduction to 24% of the needed area as well as the power consumption of the new 236 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 237 16 B. Steinbach and C. Posthoff: Table 1. Comparison of needed area, power consumption, and maximal delay effect to used count covering method used XOR-bi-decomposition ratios known new compact new compactcovering new compact known area number of gates 25 7 6 24.0 % 85.7 % power number of gates 25 7 6 24.0 % 85.7 % delay number of gates in the longest path 6 4 3 50.0 % 75.0 % compact XOR-bi-decomposition in comparison to the covering method or to 85.7% regarding the so far used non-compact XOR-bi-decomposition. The maximal delay of the synthesized circuit can be estimated by the number of gates in the longest path that is equal to the number of gate levels. The bi- decomposition outperforms the covering method also regarding the maximal delay. The new compact XOR-bi-decomposition was able to reduce the maximal delay to one half in comparison to the covering method or 75% according to the known non-compact XOR-bi-decomposition. 6 CONCLUSIONS Lattices of Boolean functions provide the possibility to choose the function for which the circuit needs a small area, a low power consumption, and has a short delay time. The bi-decomposition is a very powerful method to synthesize circuits that improve these parameters in comparison to covering methods. The theory to find compact strong bi-decompositions was so far only known for AND- and OR- gates. However, strong XOR-bi-decompositions were restricted to a single variable in the dedicated set xa. The results of this paper close this gap of a missing compact XOR-bi-decom- position for lattices of Boolean functions. It provides both the needed new theory and their application in Algorithms using XBOOLE [19, 20] for the calculation of compact XOR-bi-decompositions for lattices of Boolean functions. In a very simple example the gate count (needed area, power consumption) could be reduced to 24 percent in comparison to an exact covering method and to 85 percent regarding the known bi-decomposition. For the same example the length of the longest path (maximal delay) could be reduced to one half in comparison to an exact covering method and to 75 percent according to the known bi-decomposition. 238 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 239 16 B. Steinbach and C. Posthoff: Table 1. Comparison of needed area, power consumption, and maximal delay effect to used count covering method used XOR-bi-decomposition ratios known new compact new compactcovering new compact known area number of gates 25 7 6 24.0 % 85.7 % power number of gates 25 7 6 24.0 % 85.7 % delay number of gates in the longest path 6 4 3 50.0 % 75.0 % compact XOR-bi-decomposition in comparison to the covering method or to 85.7% regarding the so far used non-compact XOR-bi-decomposition. The maximal delay of the synthesized circuit can be estimated by the number of gates in the longest path that is equal to the number of gate levels. The bi- decomposition outperforms the covering method also regarding the maximal delay. The new compact XOR-bi-decomposition was able to reduce the maximal delay to one half in comparison to the covering method or 75% according to the known non-compact XOR-bi-decomposition. 6 CONCLUSIONS Lattices of Boolean functions provide the possibility to choose the function for which the circuit needs a small area, a low power consumption, and has a short delay time. The bi-decomposition is a very powerful method to synthesize circuits that improve these parameters in comparison to covering methods. The theory to find compact strong bi-decompositions was so far only known for AND- and OR- gates. However, strong XOR-bi-decompositions were restricted to a single variable in the dedicated set xa. The results of this paper close this gap of a missing compact XOR-bi-decom- position for lattices of Boolean functions. It provides both the needed new theory and their application in Algorithms using XBOOLE [19, 20] for the calculation of compact XOR-bi-decompositions for lattices of Boolean functions. In a very simple example the gate count (needed area, power consumption) could be reduced to 24 percent in comparison to an exact covering method and to 85 percent regarding the known bi-decomposition. For the same example the length of the longest path (maximal delay) could be reduced to one half in comparison to an exact covering method and to 75 percent according to the known bi-decomposition. REFERENCES 17 REFERENCES [1] D. Bochmann, F. Dresig, and B. Steinbach. “A New Decomposition Method for Multilevel Circuit Design”. In: Proceedings of the Conference on Euro- pean Design Automation. EDAC ’91. Amsterdam, The Netherlands: IEEE Computer Society, 1991, pp. 374–377. [2] T. Le. “Testbarkeit kombinatorischer Schaltungen - Theorie und Entwurf”. written in German, English title: Testability of Combinational Circuits - The- ory and Design. PhD thesis. TU Karl-Marx-Stadt, Germany, 1989. [3] C. Posthoff and B. Steinbach. Logic Functions and Equations – Binary Models for Computer Science. Dordrecht, The Netherlands: Springer, 2004. [4] B. Steinbach and C. Posthoff. Boolean Differential Calculus. Synthesis Lec- turers on Digital Circuits and Systems 52. San Rafael, CA, USA: Morgan & Claypool, 2017. [5] A. Mishchenko, B. Steinbach, and M. Perkowski. “An Algorithm for Bi- decomposition of Logic Functions”. In: Proceedings of the 38th Annual De- sign Automation Conference. DAC ’01. Las Vegas, Nevada, USA: ACM, 2001, pp. 103–108. [6] B. Steinbach. “Vectorial Bi-Decompositions of Logic Functions”. In: Pro- ceedings of the Reed-Muller Workshop 2015. RM 4. Waterloo, Canada, 2015. [7] B. Steinbach and C. Posthoff. “Vectorial Bi-Decompositions for Lattices of Boolean Functions”. In: Proceedings of the 12th International Workshops on Boolean Problems. IWSBP. Freiberg, Germany: Freiberg University of Mining and Technology, 2016, pp. 93–104. [8] A. Thayse. “Boolean Differential Calculus”. In: Philips Research Reports 26 (1971). R 764, pp. 229–246. [9] M. Davio and A. Thayse. “Boolean Differential Calculus and its Applica- tion to Switching Theory”. In: IEEE Transactions on Computes 22.4 (1973), pp. 409–420. [10] B. Steinbach and C. Posthoff. Logic Functions and Equations - Examples and Exercises. Springer Science + Business Media B.V., 2009. [11] B. Steinbach and C. Posthoff. “Boolean Differential Calculus - Theory and Applications”. In: Journal of Computational and Theoretical Nanoscience 7.6 (2010), pp. 933–981. 238 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions 239 18 REFERENCES [12] B. Steinbach and C. Posthoff. “Boolean Differential Calculus”. In: Progress in Applications of Boolean Functions. Synthesis Lecturers on Digital Cir- cuits and Systems 26. San Rafael, CA, USA: Morgan & Claypool, 2010, pp. 55–78. [13] T. Sasao and J. Butler. “On Bi-Decompositions of Logic Functions”. In: 6th International Workshop on Logic & Synthesis. IWLS. Granlibakken Resort - Tahoe City, CA, USA, 1997, pp. 1–6. [14] M. Choudhury and K. Mohanram. “Bi-Decomposition of Large Boolean Functions Using Blocking Edge Graphs”. In: 2010 IEEE/ACM International Conference on Computer-Aided Design. ICCAD. 2010, pp. 586–591. [15] D. Cheng and X. Xu. “Bi-Decomposition of Logical Mappings via Semi- Tensor Product of Matrices”. In: Automatica 49.7 (2013), pp. 51–76. [16] B. Steinbach. “Generalized Lattices of Boolean Functions Utilized for Deri- vative Operations”. In: Materiały konferencyjne KNWS’13. KNWS ’13. Ła- gów, Poland, 2013, pp. 1–17. [17] B. Steinbach. “Derivative Operations for Lattices of Boolean Functions”. In: Proceedings of the Reed-Muller Workshop 2013. RM ’13. Toyama, Japan, 2013, pp. 110–119. [18] B. Steinbach and A. Wereszczynski. “Synthesis of Multi-Level Circuits Us- ing EXOR-Gates”. In: IFIP WG 10.5 - Workshop on Applications of the Reed-Muller Expansion in Circuit Design. Chiba - Makuhari, Japan, 1995, pp. 161–168. [19] B. Steinbach. “XBOOLE - A Toolbox for Modelling, Simulation, and Anal- ysis of Large Digital Systems”. In: Systems Analysis and Modelling Simula- tion 9.4 (1992), pp. 297–312. [20] B. Steinbach and M. Werner. “XBOOLE-CUDA - Fast Calculations of Large Boolean Problems on the GPU”. In: Problems and New Solutions in the Boolean Domain. Ed. by B. Steinbach. Newcastle upon Tyne, UK: Cam- bridge Scholars Publishing, 2016, pp. 117–149. 240 B. STEINBACH, C. POSTHOFF Compact XOR-Bi-Decomposition for Lattices of Boolean Functions PB