# A Generalized If-Then-Else Operator for the Representation of Multi-Output Functions

Authors: Ilya Levin; Osnat Keren
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

The paper deals with fundamentals of systems of Boolean functions called multi-output functions (MOFs). A new approach to representing MOFs is introduced based on a Generalized If-Then-Else (GITE) function. It is shown that known operations on MOFs may be expressed by a GITE function. The GITE forms the algebra of MOFs. We use the properties of this algebra to solve an MOF-decomposition problem. The solution provides a compact representation of MOFs.


---

## Body

## 1. Introduction

Logic design, as a scientific discipline, has a fascinating history. This field was intensively studied from the 1950s to the 1970s. This produced many remarkable results including the theorem of function completeness, optimization techniques, decomposition techniques, a number of spectral methods, and a theory of multivalued functions [1–7]. However, there are topics in logic design which are still interesting and have untapped potential from a theoretical point of view [8, 9]. One such topic is “systems of logic functions” (logic systems) and their corresponding representations. The most popular representations of logic systems are (a) the matrix (which is actually a Karnaugh-like form) and (b) the Multiterminal Binary Decision Diagram (MTBDD) [10–14]. There are three known ways to treat and optimize systems of logic functions: (a) as a set of single decision diagrams with two terminal nodes that may share conditional nodes (Shared Binary Decision Diagrams (SBDDs)) [15]; (b) as a single, so-called characteristic function, where the output of each function of the system is considered to be an additional input variable of the characteristic function [16]; (c) as a single decision diagram whose terminals are words [14].In this paper, we present a different approach. We represent a system of logic functions as a network of interconnected subfunctions. In other words, we decompose a given system into a number of subsystems of lower complexity, thus achieving a compact representation of the given system.We introduce a new Generalized If-Then-Else operator, denoted as GITE, and an algebra based on this operator. A system of logic functions can be described as a GITE formula. In this sense, the conventional algebra of the Boolean formulas is a particular case of the GITE algebra. In turn, the new operator is considered to be a generalization of the known If-Then-Else (ITE) operator that is widely used in computer science.GITE-algebra makes it possible to formulate and solve various optimization problems. In our work, we formulate a general optimization problem, which is the decomposition of a system into acompact network of GITE components with predefined characteristics. We present a solution of this task in the form of an optimization algorithm. The decomposition algorithm is based on a theorem of GITE formula transformation presented in Section 4.The paper is organized as follows. Basics of the theory of logic functions and Boolean formula are briefly reviewed in Section2. The GITE operator is introduced in Section 3. A polynomial representation of GITE formulas is presented in Section 4. The optimization problem is formulated in Section 5. A solution to the optimization problem is given in Section 6. Section 7 includes experimental results. Conclusions are given in Section 8.


## 2. Preliminaries

In this section we review some fundamentals of logic design underlying our work.


### 2.1. Representation of a Single Logic Function

A logic functionf(x1,…,xn) is a function that takes the values of 0 and 1. An expression obtained by substitution of functions into each other followed by renaming variables is called a formula that describes this substitution. The formula-based representation of logic functions is an analytical expression.Letf be a set of functions, and let ℱ be a set of formulas. We define the depth of a formula F∈ℱ as follows.Definition 1.
Symbols representing the input variables are considered to be formulas ofdepth0. A formula F has depth (k+1) if F can be expressed as fi(F1,…,Fni), where fi∈f,  F1,…,Fni∈ℱ are formulas of the maximal depth k, and ni is the number of arguments of fi.The formulasF1,…,Fni are called subformulas of F. Function fi is called the outside or the main operation of formula F. All subformulas of the F1,…,Fni are also considered as subformulas of F.When talking about a formula corresponding to a specific function, it is acceptable to say that a formularepresents the function. Unlike the truth table representation of a function, the formula representation is not unique. Formulas representing one and the same function are equivalent. Actually, in most cases, we do not deal with functions but rather with formulas representing these functions. In other words, we deal with the algebra of formulas [17, 18].One of the popular forms for the representation of a logic function is a Binary Decision Diagram (BDD) [17]. A fundamental operator enabling operations between BDDs is the If-Then-Else (ITE) operator [19]. In our paper, we use the ITE operator as an operator on the system of logic functions and not just on the set of BDDs.The ITE operator serves to represent any function of two variables [17, 19] and consequently may be considered as a universal basis for the set of logic functions. In other words, any function of n variables can be represented as a substitution of ITEs. We define the depth of an ITE formula as follows.Definition 2.
Symbols representing the input variables are considered ITE formulas ofdepth0. An ITE formula F has depth (k+1) if F can be expressed as fi(F1,…,Fni), where fi∈f, F1,…Fni∈ℱ are ITE formulas of the maximal depth k.


### 2.2. Representation of the System of Functions

The present study deals primarily with a system of logic functions and not necessarily a single Boolean function. The system of logic functions can be considered as a single function ofn input Boolean variables and m Boolean output variables. Such functions are called multi-output functions (MOFs) [10, 11, 20–23]. The domain and range of an MOF are the n-dimensional and m-dimensional Boolean cubes, 𝔹n and 𝔹m, respectively. We refer to a vertex of a Boolean cube by its corresponding integer value or as a minterm (A literal is a variable or its complement. A minterm is a product of all the literals). An MOF can be defined by a truth vector (also called a truth table); that is, a list of all possible input combinations with the corresponding output values (vectors). In this paper we refer to the output vectors by their corresponding integer values. An analytical representation of MOFs differs from the conventional Boolean representation. An analytical MOF representation is the focus of the present study.Multiterminal Binary Decision Diagram (MTBDD) is a data structure for representation and efficient manipulations with MOFs [10, 24]. Unlike the conventional BDD that has two terminal nodes, the MTBDD has a number of the terminal nodes.Definition 3.
An MTBDD is a directed acyclic graph, representing an MOF or a set of logic functionsf:𝔹n→𝔹m.Properties of MTBDD and other MOF representations and their applications have been studied intensively [25–33]. To the best of our knowledge, some aspects of the representation of MOFs and especially an algebra for MOFs have never been developed, although two main operations on MOF, the Apply and the ITE, were studied in [10]. The Apply may be used to accomplish a large number of matrix operations. Its definition is Apply(f,g,∘)=f∘g, where f and g are MOFs and ∘ is any binary operation on two operands, for example, +,-, min, max, and so forth.The ITE operator has three arguments. The first argument takes0 or 1. The second and third arguments are MOFs. ITE is defined as follows:
(1)ITE(f,g,h)={giff=1hiff=0.The following example illustrates the above operations. To simplify the explanation we use the truth vector representation of MOFs. That is, a functionf of n variables is represented as a vector of length 2n, f=[v0,v1,…,v2n-1], where vω is the value of the function f(x) at x=ω.Example 4.
Letf,g, and h be three MOF functions specified by the following truth vectors:
(2)f=[1,0,0,1],g=[4,4,2,2],h=[3,3,3,3],
and let op stand for addition of integers. Then,
(3)Apply(f,g,+)=[5,4,2,3],ITE(f,g,h)=[4,3,3,2].In the following section we generalize these two operations to define the algebra of MOFs.


### 2.3. Partition on a Boolean Cube

In this section we describe the concept of partition on Boolean cubes.Definition 5.
A partitionπ on a set S is a collection of w disjoint subsets of S whose set union is S; that is, π={Bi}i=1w such that Bi∩Bj=∅(i≠j) and ∪i=1wBi=S.We refer to the subsets ofπ as blocks of π.The fact that two distinct elementss and t are in the same block k of π is denoted as s≡t(π). In other words, s≡t(π) if and only if there exists k such that s∈Bk and t∈Bk.Definition 6 (intersection of partitions).
Letπ1 and π2 be two partitions. The product π=π1*π2 is a partition comprising intersections of blocks of π1 and π2, such that
(4)s≡t(π1*π2)⟺s≡t(π2),s≡t(π1).Definition 7 (summation of partitions).
Letπ1 and π2 be two partitions. The sum π=π1+π2 consists of blocks for which s≡t(π1+π2) if and only if a chain s0,s1,…,sn exists in S such as: s=s0,s1,…,sn=t for which either si≡si+1(π1) or si≡si+1(π2), 0≤i≤n-1.We denote the product and the sum of partitions as(5)∏i=1nπi=π1*⋯*πn,∑i=1n‍πi=π1+⋯+πn,
respectively.Forπ1 and π2, we say that π1 is larger or equal to π2 and write π1≥π2 if and only if every block of π2 is contained in a block of π1. Thus, π1≥π2 if  π1*π2=π2 and if and only if π1+π2=π1. The algebraic structure of partitions is known as a lattice. This lattice has both Zero (the smallest partition) and One (the largest partition). These elements are
(6)π0={{s1};…;{sm}},π1={s1,…,sm}.
Obviously,
(7)π0≤π1*π2≤π1,π2≤π1+π2≤π1.In this paper, the partition is performed on then-dimensional Boolean cube 𝔹n. A block of the partition is the subsets of vertices of the cube. Vertices that belong to the same block must have the same output value. The Zero partition π0 on a Boolean cube corresponds to the Sum-Of-Minterms (SOM) representation of a function.Example 8.
Consider a functionf(x2,x1,x0) specified by the truth vector
(8)f=[v0,…v7]=[2,2,1,1,1,1,2,0]
and a partition
(9)π={B1,B2,B3,B4}={{0,1};{2,3,4,5};{6};{7}}.
Note that all the elements in a block are associated with the same value of the function, for example, v0=v1=2. Consider a different partition
(10)π^={{0};{1,6};{2,3,4,5};{7}}.
The product of partitions is
(11)π*π^={{0};{1};{2,3,4,5};6;{7}}.
The sum of partitions is
(12)π+π^={{0,1,6};{2,3,4,5};{7}}.
Since we are dealing with partitions of the Boolean cube, blocks in the partition can be expressed as Boolean functions. For example, the Boolean functions that correspond to the blocks of
(13)π={{0,1};{2,3,4,5};{6};{7}}
are
(14){0,1}⟹x-2x-1,{2,3,4,5}⟹x-2x1+x2x-1,{6}⟹x2x1x-0,{7}⟹x2x1x0.


## 2.1. Representation of a Single Logic Function

A logic functionf(x1,…,xn) is a function that takes the values of 0 and 1. An expression obtained by substitution of functions into each other followed by renaming variables is called a formula that describes this substitution. The formula-based representation of logic functions is an analytical expression.Letf be a set of functions, and let ℱ be a set of formulas. We define the depth of a formula F∈ℱ as follows.Definition 1.
Symbols representing the input variables are considered to be formulas ofdepth0. A formula F has depth (k+1) if F can be expressed as fi(F1,…,Fni), where fi∈f,  F1,…,Fni∈ℱ are formulas of the maximal depth k, and ni is the number of arguments of fi.The formulasF1,…,Fni are called subformulas of F. Function fi is called the outside or the main operation of formula F. All subformulas of the F1,…,Fni are also considered as subformulas of F.When talking about a formula corresponding to a specific function, it is acceptable to say that a formularepresents the function. Unlike the truth table representation of a function, the formula representation is not unique. Formulas representing one and the same function are equivalent. Actually, in most cases, we do not deal with functions but rather with formulas representing these functions. In other words, we deal with the algebra of formulas [17, 18].One of the popular forms for the representation of a logic function is a Binary Decision Diagram (BDD) [17]. A fundamental operator enabling operations between BDDs is the If-Then-Else (ITE) operator [19]. In our paper, we use the ITE operator as an operator on the system of logic functions and not just on the set of BDDs.The ITE operator serves to represent any function of two variables [17, 19] and consequently may be considered as a universal basis for the set of logic functions. In other words, any function of n variables can be represented as a substitution of ITEs. We define the depth of an ITE formula as follows.Definition 2.
Symbols representing the input variables are considered ITE formulas ofdepth0. An ITE formula F has depth (k+1) if F can be expressed as fi(F1,…,Fni), where fi∈f, F1,…Fni∈ℱ are ITE formulas of the maximal depth k.


## 2.2. Representation of the System of Functions

The present study deals primarily with a system of logic functions and not necessarily a single Boolean function. The system of logic functions can be considered as a single function ofn input Boolean variables and m Boolean output variables. Such functions are called multi-output functions (MOFs) [10, 11, 20–23]. The domain and range of an MOF are the n-dimensional and m-dimensional Boolean cubes, 𝔹n and 𝔹m, respectively. We refer to a vertex of a Boolean cube by its corresponding integer value or as a minterm (A literal is a variable or its complement. A minterm is a product of all the literals). An MOF can be defined by a truth vector (also called a truth table); that is, a list of all possible input combinations with the corresponding output values (vectors). In this paper we refer to the output vectors by their corresponding integer values. An analytical representation of MOFs differs from the conventional Boolean representation. An analytical MOF representation is the focus of the present study.Multiterminal Binary Decision Diagram (MTBDD) is a data structure for representation and efficient manipulations with MOFs [10, 24]. Unlike the conventional BDD that has two terminal nodes, the MTBDD has a number of the terminal nodes.Definition 3.
An MTBDD is a directed acyclic graph, representing an MOF or a set of logic functionsf:𝔹n→𝔹m.Properties of MTBDD and other MOF representations and their applications have been studied intensively [25–33]. To the best of our knowledge, some aspects of the representation of MOFs and especially an algebra for MOFs have never been developed, although two main operations on MOF, the Apply and the ITE, were studied in [10]. The Apply may be used to accomplish a large number of matrix operations. Its definition is Apply(f,g,∘)=f∘g, where f and g are MOFs and ∘ is any binary operation on two operands, for example, +,-, min, max, and so forth.The ITE operator has three arguments. The first argument takes0 or 1. The second and third arguments are MOFs. ITE is defined as follows:
(1)ITE(f,g,h)={giff=1hiff=0.The following example illustrates the above operations. To simplify the explanation we use the truth vector representation of MOFs. That is, a functionf of n variables is represented as a vector of length 2n, f=[v0,v1,…,v2n-1], where vω is the value of the function f(x) at x=ω.Example 4.
Letf,g, and h be three MOF functions specified by the following truth vectors:
(2)f=[1,0,0,1],g=[4,4,2,2],h=[3,3,3,3],
and let op stand for addition of integers. Then,
(3)Apply(f,g,+)=[5,4,2,3],ITE(f,g,h)=[4,3,3,2].In the following section we generalize these two operations to define the algebra of MOFs.


## 2.3. Partition on a Boolean Cube

In this section we describe the concept of partition on Boolean cubes.Definition 5.
A partitionπ on a set S is a collection of w disjoint subsets of S whose set union is S; that is, π={Bi}i=1w such that Bi∩Bj=∅(i≠j) and ∪i=1wBi=S.We refer to the subsets ofπ as blocks of π.The fact that two distinct elementss and t are in the same block k of π is denoted as s≡t(π). In other words, s≡t(π) if and only if there exists k such that s∈Bk and t∈Bk.Definition 6 (intersection of partitions).
Letπ1 and π2 be two partitions. The product π=π1*π2 is a partition comprising intersections of blocks of π1 and π2, such that
(4)s≡t(π1*π2)⟺s≡t(π2),s≡t(π1).Definition 7 (summation of partitions).
Letπ1 and π2 be two partitions. The sum π=π1+π2 consists of blocks for which s≡t(π1+π2) if and only if a chain s0,s1,…,sn exists in S such as: s=s0,s1,…,sn=t for which either si≡si+1(π1) or si≡si+1(π2), 0≤i≤n-1.We denote the product and the sum of partitions as(5)∏i=1nπi=π1*⋯*πn,∑i=1n‍πi=π1+⋯+πn,
respectively.Forπ1 and π2, we say that π1 is larger or equal to π2 and write π1≥π2 if and only if every block of π2 is contained in a block of π1. Thus, π1≥π2 if  π1*π2=π2 and if and only if π1+π2=π1. The algebraic structure of partitions is known as a lattice. This lattice has both Zero (the smallest partition) and One (the largest partition). These elements are
(6)π0={{s1};…;{sm}},π1={s1,…,sm}.
Obviously,
(7)π0≤π1*π2≤π1,π2≤π1+π2≤π1.In this paper, the partition is performed on then-dimensional Boolean cube 𝔹n. A block of the partition is the subsets of vertices of the cube. Vertices that belong to the same block must have the same output value. The Zero partition π0 on a Boolean cube corresponds to the Sum-Of-Minterms (SOM) representation of a function.Example 8.
Consider a functionf(x2,x1,x0) specified by the truth vector
(8)f=[v0,…v7]=[2,2,1,1,1,1,2,0]
and a partition
(9)π={B1,B2,B3,B4}={{0,1};{2,3,4,5};{6};{7}}.
Note that all the elements in a block are associated with the same value of the function, for example, v0=v1=2. Consider a different partition
(10)π^={{0};{1,6};{2,3,4,5};{7}}.
The product of partitions is
(11)π*π^={{0};{1};{2,3,4,5};6;{7}}.
The sum of partitions is
(12)π+π^={{0,1,6};{2,3,4,5};{7}}.
Since we are dealing with partitions of the Boolean cube, blocks in the partition can be expressed as Boolean functions. For example, the Boolean functions that correspond to the blocks of
(13)π={{0,1};{2,3,4,5};{6};{7}}
are
(14){0,1}⟹x-2x-1,{2,3,4,5}⟹x-2x1+x2x-1,{6}⟹x2x1x-0,{7}⟹x2x1x0.


## 3. The Generalized ITE Operator

The first argument in the definition of the ITE operator can be interpreted as a two-block partition of the Boolean cube or as a Boolean function. The present paper is focused on aGeneralized ITE (GITE) operator which uses an n-block partition instead of the two-block partition.


### 3.1. Definition of the GITE Operator

First, we define the GITE operator on MOFs that are specified by truth vectors.Definition 9.
Letπ be a partition of the n-dimensional Boolean cube comprising w blocks: π={Bi}i=1w, and let {hi}i=1w be a set of MOFs defined by their truth vectors:
(15)hi=[vhi,0,vhi,1,…vhi,2n-1].
Then, the GITE operator is g=GITE(π,h1,…hw), where the jth element in the truth vector g is
(16)vg,j=∑i=1w‍bi,jvhi,j,0≤j<2n,
where
(17)bi,j={1ifj∈Bi0ifotherwise.Example 10.
Letπ be a 4-block partition of 𝔹3, and let the vertices of the Boolean cube be addressed by their corresponding integer value, for example, 6=(110),
(18)π={B1,B2,B3,B4}={1;2;{3,4,7};{0,5,6}}.
Letg=GITE(π,h1,h2,h3,h4), where
(19)h1=[1,1,2,1,1,1,2,2],h2=[3,3,3,3,3,3,3,3],h3=[2,2,4,4,2,2,4,4],h4=[5,6,5,6,5,6,5,6].
Then g is
(20)g=[vg,0,vg,1,…,vg,7]=[vh4,0,vh1,1,vh2,2,vh3,3,vh3,4,vh4,5,vh4,6,vh3,7]=[5,1,3,4,2,6,5,4].Now we are ready to formulate the concept of MOF in terms of GITE.Definition 11.
An MOF is a mapping from𝔹n to 𝔹m, which is a GITE(π,Y) operation defined on two sets: the set of partitions and the set Y,  Y⊆𝔹m of terminals (In [10], the values of an MOF, that is, the Y’s, are called terminal nodesor terminals (this is different from the internal nodes that correspond to variables). In Algorithmic State Machine theory, the values of the MOF represent operations to be performed and hence are called operators [34]. In this paper we use the term “terminals.”).In other words, the GITE comprises apartition portion and a terminals portion. The GITE operation maps a partition of the Boolean cube 𝔹n on the predefined set Y.


### 3.2. GITE Formulas

In this section we introduce the algebra of GITE formulas. The elements of the algebra are MOFs, and the basic operator is the GITE. We define the depth of the GITE formula as follows.Definition 12.
Symbols of given terminals from the finite setY={Y1,…,Yn}⊆𝔹m are considered as GITE formulas of depth0. A GITE formula G has depth (k+1) if G can be expressed as G=GITE(π,(G1,…,Gni)), where G1,…,Gni are formulas of the maximal depth k and ni is the number of blocks in the partition π.Unlike the case of the algebra of Boolean functions, the algebra of GITE formulas contains an additional operationcomposition. The composition operation (Compose) corresponds to the known Apply operation in the algebra of ITE. Composition means to construct a GITE from two other GITEs. The values of the composed GITE are calculated by performing a bitwise operation denoted by “∘” on the values of the given GITEs.Definition 13 (composition).
Let(21)G1=GITE(π1,Y1,1,…,Y1,k),G2=GITE(π2,Y2,1,…,Y2,m),
then,
(22)Compose(G1,G2)=defG1∘G2=GITE(π1*π2;Y1,1∘Y2,1,…,Y1,k∘Y2,m).In other words, the composition of the GITE is performed by multiplying the corresponding partitionsπ1 and π2 and pairwise “∘” operations on terminal Y.Example 14.
Let(23)π1={B11,B21,B31,B41}={1;2;{3,4,7};{0,5,6}},π2={B12,B22,B02}={{1,2,3};{0,4,7};{5,6}}},
and let
(24)G1=GITE(π1,Y1,1,Y1,2,Y1,3,Y1,4),G2=GITE(π2,Y2,1,Y2,2,Y2,0),
where
(25)Y1,1=2,Y1,2=6,Y1,3=5,Y1,4=11,Y2,1=3,Y2,2=8,Y2,0=0.
Let the “∘” stand for a bitwise XOR between two integers represented in radix two. Then,
(26)π=π1*π2={0;1;2;3;{4,7};{5,6}},G1∘G2=Compose(G1,G2)=GITE(π;Y1,4∘Y2,2,Y1,1∘Y2,1,Y1,2∘Y2,1,Y1,3∘Y2,1,Y1,3∘Y2,2,Y1,4∘Y2,0)=GITE(π;3,1,5,6,13,11).


## 3.1. Definition of the GITE Operator

First, we define the GITE operator on MOFs that are specified by truth vectors.Definition 9.
Letπ be a partition of the n-dimensional Boolean cube comprising w blocks: π={Bi}i=1w, and let {hi}i=1w be a set of MOFs defined by their truth vectors:
(15)hi=[vhi,0,vhi,1,…vhi,2n-1].
Then, the GITE operator is g=GITE(π,h1,…hw), where the jth element in the truth vector g is
(16)vg,j=∑i=1w‍bi,jvhi,j,0≤j<2n,
where
(17)bi,j={1ifj∈Bi0ifotherwise.Example 10.
Letπ be a 4-block partition of 𝔹3, and let the vertices of the Boolean cube be addressed by their corresponding integer value, for example, 6=(110),
(18)π={B1,B2,B3,B4}={1;2;{3,4,7};{0,5,6}}.
Letg=GITE(π,h1,h2,h3,h4), where
(19)h1=[1,1,2,1,1,1,2,2],h2=[3,3,3,3,3,3,3,3],h3=[2,2,4,4,2,2,4,4],h4=[5,6,5,6,5,6,5,6].
Then g is
(20)g=[vg,0,vg,1,…,vg,7]=[vh4,0,vh1,1,vh2,2,vh3,3,vh3,4,vh4,5,vh4,6,vh3,7]=[5,1,3,4,2,6,5,4].Now we are ready to formulate the concept of MOF in terms of GITE.Definition 11.
An MOF is a mapping from𝔹n to 𝔹m, which is a GITE(π,Y) operation defined on two sets: the set of partitions and the set Y,  Y⊆𝔹m of terminals (In [10], the values of an MOF, that is, the Y’s, are called terminal nodesor terminals (this is different from the internal nodes that correspond to variables). In Algorithmic State Machine theory, the values of the MOF represent operations to be performed and hence are called operators [34]. In this paper we use the term “terminals.”).In other words, the GITE comprises apartition portion and a terminals portion. The GITE operation maps a partition of the Boolean cube 𝔹n on the predefined set Y.


## 3.2. GITE Formulas

In this section we introduce the algebra of GITE formulas. The elements of the algebra are MOFs, and the basic operator is the GITE. We define the depth of the GITE formula as follows.Definition 12.
Symbols of given terminals from the finite setY={Y1,…,Yn}⊆𝔹m are considered as GITE formulas of depth0. A GITE formula G has depth (k+1) if G can be expressed as G=GITE(π,(G1,…,Gni)), where G1,…,Gni are formulas of the maximal depth k and ni is the number of blocks in the partition π.Unlike the case of the algebra of Boolean functions, the algebra of GITE formulas contains an additional operationcomposition. The composition operation (Compose) corresponds to the known Apply operation in the algebra of ITE. Composition means to construct a GITE from two other GITEs. The values of the composed GITE are calculated by performing a bitwise operation denoted by “∘” on the values of the given GITEs.Definition 13 (composition).
Let(21)G1=GITE(π1,Y1,1,…,Y1,k),G2=GITE(π2,Y2,1,…,Y2,m),
then,
(22)Compose(G1,G2)=defG1∘G2=GITE(π1*π2;Y1,1∘Y2,1,…,Y1,k∘Y2,m).In other words, the composition of the GITE is performed by multiplying the corresponding partitionsπ1 and π2 and pairwise “∘” operations on terminal Y.Example 14.
Let(23)π1={B11,B21,B31,B41}={1;2;{3,4,7};{0,5,6}},π2={B12,B22,B02}={{1,2,3};{0,4,7};{5,6}}},
and let
(24)G1=GITE(π1,Y1,1,Y1,2,Y1,3,Y1,4),G2=GITE(π2,Y2,1,Y2,2,Y2,0),
where
(25)Y1,1=2,Y1,2=6,Y1,3=5,Y1,4=11,Y2,1=3,Y2,2=8,Y2,0=0.
Let the “∘” stand for a bitwise XOR between two integers represented in radix two. Then,
(26)π=π1*π2={0;1;2;3;{4,7};{5,6}},G1∘G2=Compose(G1,G2)=GITE(π;Y1,4∘Y2,2,Y1,1∘Y2,1,Y1,2∘Y2,1,Y1,3∘Y2,1,Y1,3∘Y2,2,Y1,4∘Y2,0)=GITE(π;3,1,5,6,13,11).


## 4.D-Polynomials Analytical Representation of GITE Formulas

In this section we describe a special type of GITE formulas. This type corresponds to the case where a GITE formula is defined by partitions expressed in an analytic form—the form of a Boolean expression—the Sum-of-Products (SOP) form. We call this analytical representation aD-polynomial representation [35–37].Definition 15.
LetB1,…,Bm be Boolean functions expressed in an SOP form, and let π={B1,…,Bm,B0} be a partition, where B0=∨i=1mBi-. A D-polynomial is defined as follows:
(27)D=def∑i=1m‍BiYi+B0Y0=GITE(π,Y)=GITE(B1,…,Bm,B0;Y1,…,Ym,Y0),
where Y0=(0,…,0)∈𝔹m.AD-polynomial D can be interpreted as follows. If Bi evaluates to 1, then D=Yi. If all of the explicit functions Bi are equal to 0, then D=Y0.AD-polynomial of depth0 is a formula defined over a set of terminal Y. D-polynomials of depthk are defined in the same way as in the general case of GITE formulas.Since theD-polynomials are defined in the SOP-based analytical form, the Compose operation on the set of D-polynomials may be easier to perform than in the general case of GITE, namely, by using Boolean operations. In turn, the Compose operation is interpreted as a composition of D-polynomials.Definition 16 (composition ofD-polynomials).
Let(28)D1=∑i=1m‍Bi1Yi+B01Y0,D2=∑i=1m‍Bi2Yi+B02Y0.
The composition of D1 and D2 denoted by D1∘D2 is defined as
(29)D1∘D2=∑i,j‍(Bi1·Bj2){Yi∘Yj}+(B01·B02)Y0,
over each pair of products from D1 and D2, including the implicit terms B01Y0 and B02Y0.HereBi1·Bj2 is a logic product (AND) of the corresponding functions, and Yi∘Yj is a predefined bitwise operation between Yi and Yj. In other words, when Bi1·Bj2 evaluates to 1, the operation between Yi and Yj is performed.Note that partition algebra and Boolean algebra use different terminologies. Consequently, the terminologies of the GITE andD-polynomials are also different. In particular, if two partition blocks are disjoint, their corresponding Boolean functions are orthogonal.According to this definition, the composition operation corresponds to theproduct of the partition of D-polynomials. Next we show that the D-polynomial operation that corresponds to the sum of the partition portions is not a sum of D-polynomials (as may be expected), but is a factorization.Without loss of generality, let aD-polynomial D be represented as D=D1∘D2.Definition 17 (factorization ofD-polynomials).
The factorization ofD with respect to D1 and D2 is its representation in the following form:
(30)D=GITE(π1+π2;D^1,…,D^l),
where l is a number of blocks in (π1+π2) and D^1,…,D^l stand for D-polynomials corresponding to the remaining functions.Note that sum of the partition is equivalent to the max operation in lattices [22]. In this sense the sum is the minimal partition that is larger than both of them; that is, π1+π2≥π1,π2 (see Definition 7). Hence, the sum can be interpreted as a common factor.Example 18.
Consider two partitions:(31)π1={B11,B21,B31,B01}={x1,x-1x-2,x-1x2,0},π2={B12,B22,B32,B02}={x-1,x1x-3,x1x3,0}.
Let
(32)D1=GITE(π1,Y1,Y2,Y3,Y0)=x1Y1+x-1x-2Y2+x-1x2Y3,D2=GITE(π1,Y4,Y5,Y6,Y0)=x-1Y4+x1x-3Y5+x1x3Y6.
Then, π1+π2={x1,x-1,0}, and
(33)D1∘D2=GITE(π1+π2;D156,D234,Y0)=x1D156+x-1D234,
where
(34)D156=Y1∘(x-3Y5+x3Y6),D234=(x-2Y2+x2Y3)∘Y4.Laws and Properties of D-Polynomials.The D-polynomials are the special class of GITE formulas. In what follows we use the D-polynomial notation to represent and manipulate MOFs. There are two main reasons for using the D-polynomial notation: (a) D-polynomials are formulas; (b) D-polynomials support SOP function representations.We now introduce a substitution of certainD-polynomials into another D-polynomial as follows. Let D1,D2, and D3 be MOFs:
(35)D1=GITE(π1;Y11,Y12),D2=GITE(π2;Y21,…,Y2m),D3=GITE(π3;Y31,…,Y3k).After substitutionY11←D2,Y12←D3 we have D1′=GITE(π1;D2,D3) which is a hierarchical structure comprising a number of D-polynomials.In general, letD=GITE(π;Y1,…,Ym) be a formula representing a multi-output function f. A substitution of formula D1,…,Dm in the place of the terminals gives a new formula
(36)D′=GITE(π;D1,…,Dm).Obviously,D′≠D but we consider them as the same function (f) with different arguments. As a result, we can deal with the algebra of functions, which are determined by their partition portion of the corresponding GITE formula. The same situation is found in the conventional Boolean algebra of logic functions where we usually talk about logic operations (AND, OR, NOT, etc.) on the set of logic functions.A special class ofD-polynomials is the class of atomic D-polynomials; that is, D-binomials.Definition 19.
AD-binomial is a special case of D-polynomials, including exactly one product: D=B1Y1+B0Y0.The following theorem states that anyD-polynomial can be represented as a composition of all of its D-binomials.Theorem 20.
An arbitraryD-polynomial D=∑j‍BjYj+B0Y0 can be represented as a composition of D-binomials Dj=(BjYj+B0jY0), where B0=∏j‍B0j.The proof of this theorem is given in the Appendix.


## 5. The Decomposition Problem

Each class of hardware technology requires its own specific optimization criterion. Both the technology and the corresponding optimization criteria are changing continuously as a function of progress in the field of hardware and updates in design requirements. However, universal criteria of optimization do exist. These universal criteria relate to a measure of complexity of the formulas for the representation of a discrete function. Complexity may be consideredquantitatively and qualitatively. Here we consider the compactness of the formula representation as a quantitative complexity criterion and the modularity as the qualitatively complexity criterion. Compactness is an important parameter for storing and remote communication of information, as well as for software representations of discrete functions. In our experiments, we assessed compactness as the number of nodes in the corresponding decision diagram.The universal qualitative criterion for complexity is modularity. We represent a given discrete function as a hierarchical network of modular components, each performing part of a common functionality. There are number of reasons to prefer a modular (structured) representation. First of all, a structured representation simplifies the process of debugging and testing; further, modules are potentially reusable. Moreover, structured representations usually correspond to their specifications. This correspondence is highly desirable, since it helps understand and interpret the realization of the function and can be seen as a powerful measure of complexity of the representation of the function.Below we discuss methods for transforming a system of logic functions into a structured hierarchical network of interconnected components. We decompose the system while minimizing the total number of nodes in the resulting structure.Let us consider two extreme cases of decomposition ofD-polynomials that are the D-binomials (i.e., the binomial representation) and the monolith. The monolith corresponds to the D-polynomial D=GITE(π,Y1,…,Yk), where π is a partition corresponding to the Reduced Ordered MTBDD representation of MOF [17, 19, 20, 32]. The following example illustrates these two extreme cases.Example 21.
Consider the MOF specified in Table1. The function has five inputs and four outputs. Each row of the table corresponds to one D-binomial. Hence,
(37)D=D1∘D2∘D3∘D4∘D5,
where Di is the D-binomial that corresponds to the ith row in the table. For example, for i=1,
(38)π1={B1,B01}={x-0x1x-3,x-0x-1x-3-},
and therefore D1=8B1+0B01. The binomial representation of the function is shown in Figure 1, and the corresponding monolith is presented in Figure 2. The terminal nodes of the decision diagrams are marked by the decimal numbers of corresponding outputs. Note that, as a result of the composition operation, the sets of terminal nodes in the diagrams are not the same. In this example, let the ∘ be a bitwise-OR between corresponding output vectors. For example, terminal node “7” in Figure 2 corresponds to the two terminal nodes “6” and “3” in Figure 1. Such cases where new values are being created stem from the nonorthogonality of products (in our case, B2 and B3 are nonorthogonal).Table 1
The MOF for Example21.
i
x
0
x
1
x
2
x
3
x
4
F
0
F
1
F
2
F
3
Y
1
0
1
—
0
—
1
0
0
0
8
2
0
1
—
1
—
0
1
1
0
6
3
—
—
1
—
0
0
0
1
1
3
4
—
—
—
—
1
0
0
0
1
1
5
1
0
—
1
—
1
1
0
0
12Figure 1
Binomial representation of the MOF in Example21.Figure 2
Monolith representation of the MOF in Example21.Note that the monolith can be derived by composing all theD-binomials. However, this procedure has high complexity. For example to obtain the monolith representation in Example 21 one has to compose the five D-binomials of D. The first Compose is quite simple since B1 and B2 are orthogonal (B1B2=0); that is,
(39)D1∘D2=8B1+6B2+0B01,2.
The second Compose is
(40)(D1∘D2)∘D3=(8∘3)B1B3+(6∘3)B2B3+(0∘3)B01,2B3+(8∘0)B1B03+(6∘0)B2B03+0B01,2B3=11B1B3+7B2B3+3B01,2B3+8B1B03+6B2B03+0B01,2B3.It is possible to avoid this complex calculation and, at the same time, reduce the resulting number of MTBDD nodes by factorization on subsets ofD-binomials. The proposed decomposition presented below is based on this principle.There are many ways to groupD-binomials to form a network of D-polynomials. Different groupings of the binomials yield different representations of MOF. Each D-polynomial in the network has its own optimal structure, that is, its own optimal header. This fact forms the basis of our decomposition approach. The decomposition goal is to represent the given D-polynomial in a compact form so as to optimize a certain cost function, for example, the number of nodes in the corresponding decision diagram. The number of nodes in the decomposed D-polynomial is upper bounded by min(2n,nm).In our example, Figure3 shows a compact representation of the MOF as a network of MTBDDs. Namely,
(41)D=Dleft∘Dright=(D1∘D2∘D5)∘(D3∘D4).
For comparison, in this example, the monolith MTBDD has 17 nonterminal nodes (NTNs), whereas the decomposition allows to reduce the number of nonterminal nodes to 8.Figure 3
Decomposed MTBDD corresponding to Example21.


## 6. Decomposition Algorithm

The main decomposition algorithm is a recursive grouping of the set of products representing the givenD-polynomial to a number of portions. The main decomposition algorithm is presented in Figure 4. Each recursion step comprises a fragmentation of current portion into a block and a remainder. In turn, a block is divided into a block header and a number of block fragments (tails). The fragmentation algorithm is described below and presented in Figure 5.Figure 4
Block diagram of the main decomposition procedure.Figure 5
Block diagram of the fragmentation Algorithm.The main decomposition algorithm uses a stack for saving a current portion of the givenD-polynomial. After the fragmentation of the current portion, each of the resulting tails   the remainder are saved in the stack sequentially. If the remainder portion is empty, which means that all products of the current portion of the D-polynomial are included in the block; then, obviously, nothing is saved into the stack. Similarly, if a certain resulting tail comprises just one product (one terminal), then nothing is saved into the stack. The main decomposition algorithm stops when the stack is empty. Clearly, this happens when all products of the given D-polynomial are distributed between blocks.


### 6.1. Fragmentation Algorithm

In each step, the fragmentation algorithm divides the set ofD-binomials (which is the set of products) into two subsets. One subset is called TB, and the second subset is called TR; TB consists of the products that determine the block D-polynomial—B, and TR contains the products that form the reminder D-polynomial—R. Formally,
(42)D^=B∘R=GITE(πh,D1,…Dj)∘R,
where the partition πh determines a common factor (block header) and Di’s (block fragments) of B. The block header is selected in such a way so as to provide a minimization of the resulting structure.Definition 22 (prefix).
LetP be a product in a block. Each product P′ covering the product P is called a prefix.The set of all prefixes associated with the products of the block defines the blockheader.The block header can be represented as a monolith whose internal nodes are associated with the prefix variables. The terminal nodes of the monolith correspond to the block fragments representing aD-polynomial with the remaining input variables. We call such fragments tails.In what follows we describe fragmentation algorithm.In each iteration the fragmentation algorithm chooses the prefixes for the current block. The prefixes that form the block header are chosen one by one. Each newly added prefix must be orthogonal to all prefixes accumulated so far. The algorithm is depicted in Figure5.Each iteration starts by preparing a list of candidate prefixes (see Section6.3). Then, the first (basic) prefix is chosen. The basic prefix defines the set of input variables that will determine the partition πh. Therefore it has special significance. The left hand side of Figure 5 shows the steps related to choosing the basic prefix. The set of criteria for ranking the candidate prefixes is described in Section 6.4. After choosing the prefix that is ranked the highest as the basic prefix, the algorithm constructs the block header by adding secondary prefixes. The right hand side of Figure 5 shows the algorithm that gathers all the prefixes that form the block header. The set of criteria for ranking the candidate secondary prefixes is described in Section 6.5. Let us start by presenting the notations.


### 6.2. Notations

(i)
T—the set of products for a given MOF.
(ii)
P—the prefix under consideration, that is, the basic prefix in the block header.
(iii)
P
s—a secondary prefix to be added to the block header.
(iv)
M—the number of variables in the prefix.
(v)
T
B
(
P
)—the set of products having prefix P. The set TB(P) is called the family of the prefix. When it is clear from the context we write TB instead of TB(P).
(vi)
T
R
(
P
)—the set of the products that do not depend on any of the prefix variables.
(vii)
T
U
(
P
)—the set of products depending on some of the prefix variables, TU=R∖(TP∪TR). Set TU is the “undecided” set, since these products are neither in the prefix family nor in its remainder.
(viii)
T
O
(
P
)—the set of products orthogonal to the prefix. Clearly, TO⊆TU.
(ix)
T
N
O
(
P
)—the set of products that are not orthogonal to the prefix, TNO=TU∖TO.
(x)
X
(
A
)—the set of variables in all the products in a set A.
(xi)
S
(
A
)—the number of literals in all the products in a set A.
(xii)
Y
(
A
)—the set of outputs corresponding to all the products in a set A.Example 23.
Consider the function specified in Table1. The function is specified by five products.
LetP=x-0x1 be a prefix under consideration. The number of variables in P is M=2. The family of P, that is, the set of products having prefix P, is TB={B1,B2}. There are two products in TB. Note that the set of variables in all the products of TB is X(TB)={x0,x1,x3}, the number of literals in all the products of TB is S(TB)=2·3=6, and the set of outputs corresponding to all the products of TB is Y(TB)={8,6}.
The set of the products that do not depend on any of the prefix variables isTR={B3,B4}, and the set of products depending on some of the prefix variables is TU={B5}. Note that B5 is orthogonal to the prefix; hence T0={B5}.


### 6.3. Preparing the List of Candidates

The prefix can be either a product or a product that covers it. A straightforward procedure is proposed below for constructing the list of the candidates from the products inTU(P).Letx,y be variables with values from {0,1,-}. Define an operator Ψ(x,y), that compares these two Boolean variables x and y, and returns the value of one of them if they are equal, and otherwise it returns a “−”. The function Common(T1,T2) accepts two products T1 and T2 and applies Ψ in a bitwise manner to each of the variables in the set X(T1)∪X(T2). The suggested procedure for constructing the list of candidates is presented in Algorithm 1.Algorithm 1:Constructing the list of candidates.
INPUT: List of productsTU.
OUTPUT: List of candidates.
O
u
t
p
u
t
←
I
n
p
u
t
T
e
m
p
1
←
O
u
t
p
u
t
REPEAT
Temp2←Φ
Compose common to every pair of
products fromTemp1.
If the result is not empty, add it toTemp2.
Output←Output∪Temp2
Temp1←Temp2
UNTIL|Temp1|=0


### 6.4.  Choosing the Basic Prefix

The basic prefix is the foundation of a block. It is chosen to simplify the representation of the block header. For this, the basic prefix has to attract the secondary prefixes “close” to it and repel those “far” from it.There are three main concerns to consider here: the input variables, the output functions, and the length of the prefix. In addition, since the secondary prefixes will be chosen from setTO, it is imperative to measure the orthogonality of TU. The four criteria are as follows.The first criterion fulfills the input requirement:(43)αX=1-|X(TB)∩X(TR)||(X(TB)∖X(P))∪X(TR)|.
It counts the variables common to the tail and the remainder corresponding to the prefix. The ratio must be reduced as much as possible to separate the block (with its tails) from the remainder. This criterion has values in the [0,1] interval, where 0 corresponds to the case, where all the remainder variables are present in the tail, and 1 to the opposite.The second criterion responds to the output requirement:(44)αY=1-|Y(TB)∩Y(TR)||Y(TB)∪Y(TR)|.
It counts the outputs common to the tail and the remainder corresponding to the prefix. The rationale here is the same as for the input requirement.The third criterion, calledPrefix Significance, measures the percentage of literals in the products of the prefix family:
(45)αP=M·|TB|S(TB).The reason for this is simple: the longer the basic prefix, the longer the list of candidates for the secondary prefixes.The last criterion, calledOrthogonality, responds to an additional requirement. It counts the number of literals in the products orthogonal to the prefix relative to the number of literals in all the candidates:
(46)αT=S(TO)S(TU).The weighted grade of a candidate prefix is defined asα=aXαX+aYαY+aPαP+aTαT. When choosing the basic prefix, the candidate with the highest α is taken. Note that the coefficients of the criteria should be chosen so as to reflect the relative significance/contribution of each criterion to the quality of the overall solution. In this paper (since it is conceptual) we assumed that all the criteria were equally significant; that is, the experimental results described in Section 7 were produced with aX=aY=aP=aT=1. Therefore, the results are suboptimal: they can be further improved. This however is left for future study.


### 6.5. Construction of the Block Header by Choosing the Secondary Prefixes

In the following equations, the superscript indicesi and i+1 stand for “current situation” and “after adding the target prefix,” respectively.The first criterion, calledAdditional Inputs, counts the number of variables common to the tail and to the remainder of the target prefix, but only those not yet present in the block,
(47)βX=1-|Xi+1(TB)∩Xi+1(TR)|-|Xi(TB)∩Xi(TR)||(Xi+1(TB)∖Xi+1(P))∪Xi+1(TR)|.The second criterion, calledAdditional Outputs, counts the number of output functions common to the tail and to the remainder of the prefix:
(48)βY=1-|Yi+1(TB)∩Yi+1(TR)|-|Yi(TB)∩Yi(TR)||Yi+1(TB)∪Yi+1(TR)|.
Here, as  in the previous criterion, only the newly added outputs are considered.The third criterion, calledOverhead, measures the literal overhead introduced to the block and removed from the remainder by selecting the target prefix,
(49)βS=Si+1(TB)-Si(TB)Si+1(TB)-Si+1(TR)-Si(TR)Si+1(TR).
This equation can be rewritten as follows:
(50)βS=1-Si(TB)Si+1(TB)-(1-Si(TR)Si+1(TR))=Si(TR)Si+1(TR)-Si(TB)Si+1(TB).
Each of the two fractions is limited to the interval [0,1], but the total value of βS is in the interval [-1,1].The weighted grade of a candidate prefix is defined asβ=bXβX+bYβY+bSβS. The candidate with the highest β is taken and added to the set of prefixes that form the block header.The complexity of the algorithm can be estimated as follows. Denote byN the number of products in the given D-polynomial. Unlike the fragmentation algorithm that deals with the partitions, the main decomposition algorithm considers only the values of the MOF. Since the main decomposition algorithm separates the N products by using a binary tree, its complexity is of order 𝒪(N). The complexity of the fragmentation algorithm is of order 𝒪(N2), since its main task is the generation of the set of secondary prefixes.


## 6.1. Fragmentation Algorithm

In each step, the fragmentation algorithm divides the set ofD-binomials (which is the set of products) into two subsets. One subset is called TB, and the second subset is called TR; TB consists of the products that determine the block D-polynomial—B, and TR contains the products that form the reminder D-polynomial—R. Formally,
(42)D^=B∘R=GITE(πh,D1,…Dj)∘R,
where the partition πh determines a common factor (block header) and Di’s (block fragments) of B. The block header is selected in such a way so as to provide a minimization of the resulting structure.Definition 22 (prefix).
LetP be a product in a block. Each product P′ covering the product P is called a prefix.The set of all prefixes associated with the products of the block defines the blockheader.The block header can be represented as a monolith whose internal nodes are associated with the prefix variables. The terminal nodes of the monolith correspond to the block fragments representing aD-polynomial with the remaining input variables. We call such fragments tails.In what follows we describe fragmentation algorithm.In each iteration the fragmentation algorithm chooses the prefixes for the current block. The prefixes that form the block header are chosen one by one. Each newly added prefix must be orthogonal to all prefixes accumulated so far. The algorithm is depicted in Figure5.Each iteration starts by preparing a list of candidate prefixes (see Section6.3). Then, the first (basic) prefix is chosen. The basic prefix defines the set of input variables that will determine the partition πh. Therefore it has special significance. The left hand side of Figure 5 shows the steps related to choosing the basic prefix. The set of criteria for ranking the candidate prefixes is described in Section 6.4. After choosing the prefix that is ranked the highest as the basic prefix, the algorithm constructs the block header by adding secondary prefixes. The right hand side of Figure 5 shows the algorithm that gathers all the prefixes that form the block header. The set of criteria for ranking the candidate secondary prefixes is described in Section 6.5. Let us start by presenting the notations.


## 6.2. Notations

(i)
T—the set of products for a given MOF.
(ii)
P—the prefix under consideration, that is, the basic prefix in the block header.
(iii)
P
s—a secondary prefix to be added to the block header.
(iv)
M—the number of variables in the prefix.
(v)
T
B
(
P
)—the set of products having prefix P. The set TB(P) is called the family of the prefix. When it is clear from the context we write TB instead of TB(P).
(vi)
T
R
(
P
)—the set of the products that do not depend on any of the prefix variables.
(vii)
T
U
(
P
)—the set of products depending on some of the prefix variables, TU=R∖(TP∪TR). Set TU is the “undecided” set, since these products are neither in the prefix family nor in its remainder.
(viii)
T
O
(
P
)—the set of products orthogonal to the prefix. Clearly, TO⊆TU.
(ix)
T
N
O
(
P
)—the set of products that are not orthogonal to the prefix, TNO=TU∖TO.
(x)
X
(
A
)—the set of variables in all the products in a set A.
(xi)
S
(
A
)—the number of literals in all the products in a set A.
(xii)
Y
(
A
)—the set of outputs corresponding to all the products in a set A.Example 23.
Consider the function specified in Table1. The function is specified by five products.
LetP=x-0x1 be a prefix under consideration. The number of variables in P is M=2. The family of P, that is, the set of products having prefix P, is TB={B1,B2}. There are two products in TB. Note that the set of variables in all the products of TB is X(TB)={x0,x1,x3}, the number of literals in all the products of TB is S(TB)=2·3=6, and the set of outputs corresponding to all the products of TB is Y(TB)={8,6}.
The set of the products that do not depend on any of the prefix variables isTR={B3,B4}, and the set of products depending on some of the prefix variables is TU={B5}. Note that B5 is orthogonal to the prefix; hence T0={B5}.


## 6.3. Preparing the List of Candidates

The prefix can be either a product or a product that covers it. A straightforward procedure is proposed below for constructing the list of the candidates from the products inTU(P).Letx,y be variables with values from {0,1,-}. Define an operator Ψ(x,y), that compares these two Boolean variables x and y, and returns the value of one of them if they are equal, and otherwise it returns a “−”. The function Common(T1,T2) accepts two products T1 and T2 and applies Ψ in a bitwise manner to each of the variables in the set X(T1)∪X(T2). The suggested procedure for constructing the list of candidates is presented in Algorithm 1.Algorithm 1:Constructing the list of candidates.
INPUT: List of productsTU.
OUTPUT: List of candidates.
O
u
t
p
u
t
←
I
n
p
u
t
T
e
m
p
1
←
O
u
t
p
u
t
REPEAT
Temp2←Φ
Compose common to every pair of
products fromTemp1.
If the result is not empty, add it toTemp2.
Output←Output∪Temp2
Temp1←Temp2
UNTIL|Temp1|=0


## 6.4.  Choosing the Basic Prefix

The basic prefix is the foundation of a block. It is chosen to simplify the representation of the block header. For this, the basic prefix has to attract the secondary prefixes “close” to it and repel those “far” from it.There are three main concerns to consider here: the input variables, the output functions, and the length of the prefix. In addition, since the secondary prefixes will be chosen from setTO, it is imperative to measure the orthogonality of TU. The four criteria are as follows.The first criterion fulfills the input requirement:(43)αX=1-|X(TB)∩X(TR)||(X(TB)∖X(P))∪X(TR)|.
It counts the variables common to the tail and the remainder corresponding to the prefix. The ratio must be reduced as much as possible to separate the block (with its tails) from the remainder. This criterion has values in the [0,1] interval, where 0 corresponds to the case, where all the remainder variables are present in the tail, and 1 to the opposite.The second criterion responds to the output requirement:(44)αY=1-|Y(TB)∩Y(TR)||Y(TB)∪Y(TR)|.
It counts the outputs common to the tail and the remainder corresponding to the prefix. The rationale here is the same as for the input requirement.The third criterion, calledPrefix Significance, measures the percentage of literals in the products of the prefix family:
(45)αP=M·|TB|S(TB).The reason for this is simple: the longer the basic prefix, the longer the list of candidates for the secondary prefixes.The last criterion, calledOrthogonality, responds to an additional requirement. It counts the number of literals in the products orthogonal to the prefix relative to the number of literals in all the candidates:
(46)αT=S(TO)S(TU).The weighted grade of a candidate prefix is defined asα=aXαX+aYαY+aPαP+aTαT. When choosing the basic prefix, the candidate with the highest α is taken. Note that the coefficients of the criteria should be chosen so as to reflect the relative significance/contribution of each criterion to the quality of the overall solution. In this paper (since it is conceptual) we assumed that all the criteria were equally significant; that is, the experimental results described in Section 7 were produced with aX=aY=aP=aT=1. Therefore, the results are suboptimal: they can be further improved. This however is left for future study.


## 6.5. Construction of the Block Header by Choosing the Secondary Prefixes

In the following equations, the superscript indicesi and i+1 stand for “current situation” and “after adding the target prefix,” respectively.The first criterion, calledAdditional Inputs, counts the number of variables common to the tail and to the remainder of the target prefix, but only those not yet present in the block,
(47)βX=1-|Xi+1(TB)∩Xi+1(TR)|-|Xi(TB)∩Xi(TR)||(Xi+1(TB)∖Xi+1(P))∪Xi+1(TR)|.The second criterion, calledAdditional Outputs, counts the number of output functions common to the tail and to the remainder of the prefix:
(48)βY=1-|Yi+1(TB)∩Yi+1(TR)|-|Yi(TB)∩Yi(TR)||Yi+1(TB)∪Yi+1(TR)|.
Here, as  in the previous criterion, only the newly added outputs are considered.The third criterion, calledOverhead, measures the literal overhead introduced to the block and removed from the remainder by selecting the target prefix,
(49)βS=Si+1(TB)-Si(TB)Si+1(TB)-Si+1(TR)-Si(TR)Si+1(TR).
This equation can be rewritten as follows:
(50)βS=1-Si(TB)Si+1(TB)-(1-Si(TR)Si+1(TR))=Si(TR)Si+1(TR)-Si(TB)Si+1(TB).
Each of the two fractions is limited to the interval [0,1], but the total value of βS is in the interval [-1,1].The weighted grade of a candidate prefix is defined asβ=bXβX+bYβY+bSβS. The candidate with the highest β is taken and added to the set of prefixes that form the block header.The complexity of the algorithm can be estimated as follows. Denote byN the number of products in the given D-polynomial. Unlike the fragmentation algorithm that deals with the partitions, the main decomposition algorithm considers only the values of the MOF. Since the main decomposition algorithm separates the N products by using a binary tree, its complexity is of order 𝒪(N). The complexity of the fragmentation algorithm is of order 𝒪(N2), since its main task is the generation of the set of secondary prefixes.


## 7. Experimental Results

The efficiency of the proposed approach was tested experimentally by applying the above decomposition algorithm to a number of benchmark functions. The effectiveness of the method was evaluated by comparing the compactness of a monolith MTBDD which corresponds to the given MOF with the compactness of the proposed decomposed network. In the experiments, PLA-like representations of the standard combinatorial-circuit benchmarks (LGSYNTH93) were used.The experiments demonstrate that the proposed decomposition, when successful, greatly reduces the size of the decision diagram as compared to the monolith solution.To analyze the experimental results, we defined ablock density—a specific parameter of a block. This parameter corresponds to the number of literals in the block’s products normalized by the maximal possible number of literals in this block. The success of the decomposition strongly depends on this defined density. Consequently, the effectiveness of the decomposition can be predicted quite reliably by making a preliminary study of the given MOF.The experimental results are shown in Tables2 and 3. Table 2 lists the benchmarks for which the decomposition network was simpler than the monolith MTBDD of the MOF. Table 3 shows the opposite cases. The columns in the tables are as follows: |X| is the number of inputs, D is the benchmark’s density D, and Nmon and Nnet are the number of nodes in the monolith MTBDD and in the decomposition network. The last column shows the ratio Nnet/Nmon. Both tables are arranged by ascending density.Table 2
Experimental results in which the decomposed network is simpler than the monolith MTBDD.
Title
|
X
|
D%
N
mon
N
net
Ratio
ALU1
12
18
982
25
0.02
B12
15
29
155
145
0.93
DK48
15
31
3428
58
0.02
DK27
9
34
79
22
0.28
CON1
7
37
16
15
0.94
ALU2
10
39
264
150
0.57
DUKE2
22
40
1435
326
0.23
ALU3
10
42
278
151
0.54
MISEX3C
14
43
10875
705
0.06
WIM
4
50
15
10
0.67
F51M
8
53
255
155
0.61
DK17
10
57
160
55
0.34
APLA
10
64
128
85
0.66
INC
7
79
39
35
0.90Table 3
Experimental results in which the monolith MTBDD is simpler than the decomposed network.
Title
|
X
|
D%
N
mon
N
net
Ratio
ADD6
12
52
504
731
1.45
RADD
8
57
90
143
1.59
CLIP
9
59
189
376
1.99
Z4
7
61
52
101
1.94
ROOT
8
65
72
134
1.86
SQR6
6
67
63
85
1.35
SQN
7
69
81
116
1.43
MLP4
8
73
240
345
1.44
SAO2
10
73
95
157
1.65
DIST
8
73
125
326
2.61
BW
5
80
25
58
2.32
RD53
5
90
15
53
3.53The results show that density is a consistent indicator of the success of the decomposition. The successful cases are mostly in the low-density area (density up to 45%), and the unsuccessful ones are mostly in the high-density area (density of at least 60%). The middle functions (density  40–60%) are divided more or less evenly between the successes and the failures. Moreover, there are several examples where the high-density functions are successfully decomposed and no examples where the method failed to work on low-density functions.The proposed decomposition, on the other hand, relies upon extracting dense blocks from the given MOF and treating the sparse remainders and tails separately. Therefore, a sparse MOF can be easily dealt with by splitting them into a network of component MTBDDs. With dense MOFs, choosing suitable blocks is difficult, and arbitrary choices lead to an ineffective resulting network.


## 8. Conclusions

Despite extensive research on building the fundamentals of logic design, some of its topics have yet to be examined. One of these topics relates to representation of systems of Boolean functions (multioutput functions) by decision diagrams. Specifically, the conceptual transition from the Boolean function domain to the multi-output functions is considered hard. Although introducing the If-Then-Else (ITE) operator on the Boolean domain makes it possible to construct the decision diagram of a logic function in a very clear way, the analogous procedure for multi-output functions was unknown. This work fills this gap. The main results can be summarized as follows.(i)
A GITE operator was introduced. The GITE operator is a generalization of the ITE operator on the Boolean domain.(ii)
Based on the GITE operator, an algebra of the GITE formula was developed and studied.(iii)
The concept ofD-polynomials as a compact analytical representation of the GITE formula was presented. The problem of the compact representation of multi-output functions was then formulated as a problem of decomposition of D-polynomials.(iv)
Finally, a solution to this problem, based on the GITE algebra and its properties, was introduced. Experimental results obtained on a number of benchmarks are promising. We believe that the present work will initiate future research on the GITE algebra and its possible applications in logic design.



---

*Source: 401616-2013-03-13.xml*