Conversion between Logic and Algebraic Expressions of Boolean

applied sciences
Article
Conversion between Logic and Algebraic Expressions of Boolean Control Networks
Cailu Wang 1 and Yuegang Tao 2,* 1 School of Automation, Beijing Institute of Technology, Beijing 100081, China; [email protected] 2 School of Artificial Intelligence, Hebei University of Technology, Tianjin 300130, China * Correspondence: [email protected]
Received: 12 September 2020; Accepted: 5 October 2020; Published: 15 October 2020
Abstract: The conversion between logic and algebraic expressions of Boolean control networks plays a worthy role in the analysis and design of digital circuits. In this paper, for a single Boolean function, a direct conversion between the minterm canonical form and the structure matrix is provided. For a Boolean control network consisting of systems of Boolean functions, two algorithms are developed to achieve the mutual conversion between the logic and algebraic expressions. The presented algorithms decrease exponentially the complexity of the semi-tensor product based method. Some numerical examples are given to demonstrate the algorithms and to compare our method with the existing ones.
Keywords: Boolean control network (BCN); logic expression; algebraic expression; canonical form; conversion algorithm; computational complexity

1. Introduction
Boolean control network (BCN) is a logical system pioneered by Kauffman in [1] for initially describing genetic regulatory networks, which provides useful modeling tools for dynamical systems whose state-variables take only two values (‘True’ or ‘False’). With the development of information technologies, BCNs have become an effective way to analyze and design circuits by algebraic means in terms of logic gates, and have served as a fundamental approach to digital circuit design, computer programming, and so on (see, e.g., [2–7]). With the development of digital circuit, the research on logic synthesis becomes particularly important. Recently, Rushdi and Ahmad [5] used a novel method for obtaining the parametric general solutions of the ‘big’ Boolean equation, which cover the most prominent type among basic problems of digital circuit design. Bandyopadhyay et al. [4] analyzed the effects of different graph-based intermediate representations, inclutding binary decision diagram, and-inverter graph and majority inverter graph, and their usability in making efficient circuit realisations. Wang and Tao [3] introduced the Karnaugh maps of logical systems and used in the analysis and design of clocked sequential circuits and in the simplification of multioutput gate circuits.
In addition to the traditional logical expression, there are some representations to describe dynamics and estimate performances of BCNs. For example, logic differential calculus [8] represents a mathematical methodology developed for analysis of Boolean functions, which enables us to consider the existing estimates of system importance, as well as some additional properties, of BCNs from the unique methodological standpoint (see, e.g., [9,10]).
The semi-tensor product (STP) of matrices is developed in [11] to convert a Boolean function into an algebraic function, and to model a BCN by a standard discrete-time linear system. A comparison of different representations of Boolean functions can be found in [12]. Describing a logical dynamic system as a linear system is useful for studying BCNs in a control-theoretic framework. Examples include the controllability and observability [13–16], periodicity and stability [17–22], optimal control [23,24],

Appl. Sci. 2020, 10, 7180; doi:10.3390/app10207180

www.mdpi.com/journal/applsci

Appl. Sci. 2020, 10, 7180

2 of 13

identification [25], etc. The computation complexity is a series problem in directly calculating the network transition matrix based on STP, which frames a limitation on the application of algebraic state-space approach. It has been calculated in [3] that the complexity of STP based method is O(26(m+n)n). Recently, Sarda et al. [26,27] proposed a Khatri-Rao product based method to transform the logical form of a BCN into a discrete time bilinear system, which has a complexity of O(2m+2n). In other words, the complexity of the STP based method is 25m+4nn times that of the Khatri-Rao product based method. This paper will provide a constructive and straightforward method with a complexity of O(2m+nn) to convert the logic expression to the algebraic expression of a BCN. More concretely, the complexity of the STP based method presented in [11] is 25(m+n) times that of the method given in this paper, and the Khatri-Rao product based method presented in [26,27] is 2n/n times that of ours.
For a BCN, converting the algebraic expression into the logic expression is an integral part for learning the logical meaning of the algebraic result from the algebraic expression. In [16], a mechanical procedure is provided to retrieve the logical network and logical dynamic equations from the network matrix of a BCN. The conversion formula given in [16] is an implicit equation, which converts the algebraic expression for a Boolean function into an irregular form of the logic expression. This paper will provide an explicit equation to directly convert the algebraic expression to a canonical form of the logic expression.
The remainder of this paper is organized as follows. Section 2 introduces some basic concepts about the logic and algebraic expressions of Boolean functions. Section 3 gives a conversion between the minterm canonical form and the structure matrix of a Boolean function. The algorithms for conversion between the logic and algebraic expressions of a BCN are presented in Section 4. The conclusions and future works are drawn in Section 5.

2. Preliminaries
This section reviews some basic concepts from Boolean functions and Boolean control networks (see, e.g., [6,7]).
A Boolean function is a function of the form

f : ∆n → ∆,

(1)

where ∆ = {True, False} is the logical domain and n is the arity of the function. Any logical function with n variables can be expressed as a propositional formula in variables x1, x2, . . . , xn. For simplicity, the logical disjunction x ∨ y, conjunction x ∧ y and negation ¬x are denoted by x + y, xy and x¯, respec- tively.
A truth table specifies the values of a Boolean function for every possible combination of values of the variables in the function. Label the rows of the truth table of Boolean function (1) by 0, 1, . . . , 2n − 1, respectively, and denote by si the function value in the row i of the truth table, where i ∈ {0, 1, . . . , 2n − 1}.
A minterm of n variables is a product of n literals in which each variable appears exactly once in either true or complemented form, but not both. The minterm which corresponds to the row i of truth table is designated as mi. Boolean function (1) can uniquely be written as a sum of minterms, i.e.,

f (x1, x2, . . . , xn) = mi1 + mi2 + · · · + mik := ∑ m(i1, i2, . . . , ik),

(2)

which is called the minterm canonical form of f .

Definition 1 ([11]). For A ∈ Rm×n and B ∈ Rp×q, the semi-tensor product (STP) of A and B is defined as
A B = (A ⊗ Iα/n) × (B ⊗ Iα/p), where α is the least common multiple of n and p, I is the identity matrix, ⊗ and × are the Kronecker product and conventional product of matrices, respectively.

Appl. Sci. 2020, 10, 7180

3 of 13

The STP has left-right dual forms. The STP mentioned in this paper is the left one. Using STP,

a

Boolean

function

can

be

converted

into

an

algebraic

form.

Denote

by

j
δn

the

j-th

column

of

identity

matrix In, where j ∈ {1, 2, . . . , n}. Represent the logical values “True” and “False” by

δ1 = 1 and δ2 = 0 ,

2

0

2

1

respectively. Then, Boolean function (1) can be equivalently represented as

f : {δ21, δ22}n → {δ21, δ22}. For the sake of brevity, a matrix of the form [δnj1 δnj2 . . . δnjk ] is briefly denoted by δn[j1, j2, . . . , jk]. Lemma 1 ([11]). For Boolean function (1), there exists a unique binary matrix M f ∈ {0, 1}2×2n such that

f (x1, x2, . . . , xn) = Mf x1 x2 · · · xn,

(3)

in which M f is called the structure matrix of f .

A Boolean network (BN) with n variables is described as

  x1(t + 1) = f1(x1(t), x2(t), . . . , xn(t)), 

  

x2(t + 1)

=

f2(x1(t), x2(t), . . . , xn(t)),

 ...

(4)





 

xn(t + 1)

=

fn(x1(t), x2(t), . . . , xn(t)),

where fj (j ∈ {1, 2, . . . , n}) are Boolean functions, and xj(·) ∈ {0, 1} (j ∈ {1, 2, . . . , n}) are states.
Lemma 2 ([11]). Let x(t) = nj=1xj(t) ∈ {0, 1}2n . Then, there exists a unique matrix L ∈ {0, 1}2n×2n such that BN (4) can be converted into a standard discrete-time dynamic system

x(t + 1) = L x(t), t = 0, 1, · · · ,

(5)

where L is called the state transition matrix of BN (4).

A Boolean control network (BCN) with m inputs and p outputs is described as

 x1(t + 1) = f1(x1(t), . . . , xn(t), u1(t), . . . , um(t)),

    

...





 

xn(t + 1)

=

fn(x1(t), . . . , xn(t), u1(t), . . . , um(t)),

(6)

 y1(t) = g1(x1(t), . . . , xn(t)),



 ...



  yp(t) = gp(x1(t), . . . , xn(t)),

where fj (j ∈ {1, 2, . . . , n}) and gr (r ∈ {1, 2, . . . , p}) are Boolean functions, xj(·) (j ∈ {1, 2, . . . , n}) are states, uk(·) (k ∈ {1, 2, . . . , m}) are inputs and yr(·) (r ∈ {1, 2, . . . , p}) are outputs. Denote by Nin the network of states and inputs, and by Nout the network of states and outputs.
Since the dynamics of a BCN is composed of a set of Boolean functions, the STP can be used to
establish the algebraic expression of BCN (6) as follows:

x(t + 1) = L x(t) u(t), (7) y(t) = H x(t),

Appl. Sci. 2020, 10, 7180

4 of 13

where x(t) = nj=1xj(t) ∈ {0, 1}2n is state vector, u(t) = mk=1uk(t) ∈ {0, 1}2m and y(t) = rp=1yr(t) ∈ {0, 1}2p are input and output vectors, respectively, L ∈ {0, 1}2n×2m+n is the control-depending network transition matrix, H ∈ {0, 1}2p×2n is the transition matrix from x(t) to y(t) (see, e.g., [21–23]).
The STP based method has been presented in ([11], Theorem IV.6) for obtaining the algebraic expression of BCNs by introducing the swap matrix, dummy matrix and power reducing matrix, which has a very high computational complexity of O(26(m+n)n) (see [3], Theorem 1). Resently, Sarda et al. [26,27] proposed a Khatri-Rao product based method to obtain such an algebraic expression.
Definition 2 ([28]). For A ∈ Rm×p and B ∈ Rn×p, the Khatri-Rao product of A and B is defined to be a partitioned matrix of order mn × p as follows:
A ∗ B = [A1 ⊗ B1 A2 ⊗ B2 · · · Ap ⊗ Bp],
where Ar (resp. Br) (r ∈ {1, 2, . . . , p}) is the r-th column of A (resp. B), and ⊗ is the Kronecker product of matrices.

Lemma 3 ([26,27]). For BCN (6), the control-depending network transition matrix is L = ∗nj=1 Mijn, and the transition matrix from x(t) to y(t) is H = ∗rp=1 Mrout, where Mijn and Mrout are the structure matrices of fj and gr, respectively.

It is known that at most mnp multiplication operations are requited to compute the Khatri-Rao product of two matrices with sizes of m × p and n × p. Then, at most 2n2m+n = 2m+2n (resp. 2p2n = 2n+p) operations are requited to compute the transition matrix L (resp. H) by using the lemma above. Hence, the computational complexity of Lemma 3 is O(2m+2n), which decreases exponentially that of the STP based method. Quantitatively, the complexity of the STP based method is 25m+4nn times that of the Khatri-Rao product based method. This paper will provide a method with a much lower complexity.
3. Conversion of Expressions of Boolean Functions
This section presents a direct conversion between the minterm canonical form and the structure matrix of a Boolean function.
3.1. From Logic Expression to Algebraic Expression
There exists a one-to-one correspondence between the truth table and the structure matrix of a Boolean function.

Lemma 4 ([29]). If the truth table of Boolean function (1) is (s0 s1 . . . s2n−1) , then the structure matrix of f is

M f = s2n−1 . . . s1

s0 .

1 − s2n−1 . . . 1 − s1 1 − s0

The structure matrix of a Boolean function can be constructed from the minterm canonical form.

Theorem 1. If the minterm canonical form of Boolean function (1) is shown in (2), then the structure matrix of

f is

M f = δ2[c2n−1, . . . , c1, c0],

(8)

where

ci = 12,, ii ∈∈ {{0i1,,1i,2., .. .. ,. 2, ink}−, 1}\{i1, i2, . . . , ik}.

Appl. Sci. 2020, 10, 7180

5 of 13

Proof. The minterms presented in (2) are in one-to-one correspondence with the logical value 1 in the truth table. Suppose that the truth table of f is (s0 s1 . . . s2n−1) . Then si = 1 if and only if mi is a minterm of f , i.e., i ∈ {i1, i2, . . . , ik}. It follows from Lemma 4 that ci = 1 if and only if si = 1. Hence, ci = 1 if and only if i ∈ {i1, i2, . . . , ik}.
Let us compute the structure matrix of the Boolean function given in ([29], Example 2.5) using Theorem 1.

Example 1. Consider the Boolean function

f (x1, x2, x3) = (x1 ↔ ¬x2) ∧ (x2 ↔ ¬x3) ∧ (x3 ↔ ¬x1 ∧ ¬x2). The minterm canonical form of f is m2(= x¯1x2x¯3). Then, in (8),

ci = 1, i = 2, 2, i ∈ {1, 3, 4, 5, 6, 7, 8}.

Hence, the structure matrix of f is M f = δ2[2, 2, 2, 2, 2, 1, 2, 2].

Comparing the above example with ([29], Example 2.5), the method based on the minterm canonical form can avoid the complex calculations of STP.
3.2. From Algebraic Expression to Logic Expression
After studying a logical dynamic system in the algebraic state space, it is necessary to convert the algebraic expression back to the logic expression in order to design digital circuits to implement the desired control functions (see, e.g., [3,5]). For a Boolean function, it is claimed in [16] that ‘converting an algebraic form back to logical form is not an easy job’, and a ‘mechanical procedure’ is provided for converting the algebraic expression back to the logic expression as below.

Lemma 5 ([16]). If Boolean function (1) has an algebraic expression as (3), then

f (x1, x2, . . . , xn) = [x1 ∧ f1(x2, . . . , xn)] ∨ [¬x1 ∧ f2(x2, . . . , xn)],

(9)

where M f = (M f1 | M f2 ), i.e., the structure matrices of f1 and f2 are the first and last half of M f , respectively.

It can be seen that Equation (9) is implicit, which converts the algebraic expression of a Boolean function into an irregular form of the logic expression. In fact, the minterm canonical form of a Boolean function can directly be obtained from the structure matrix.

Theorem 2. If the structure matrix of Boolean function (1) is shown in (8), then the minterm canonical form of

f is

f (x1, x2, . . . , xn) = ∑ mi,

(10)

i∈S

where S = {i ∈ {0, 1, . . . , 2n − 1} | ci = 1}.

Proof. Suppose that the truth table of f is (s0 s1 . . . s2n−1) . By Lemma 4, S = {i | ci = 1} = {i | si = 1} = {i | mi is a minterm of f }.

Then, the minterm canonical form of f is (10).
In contrast to the implicit Equation (9) given in Lemma 5, Equation (10) presented in Theorem 2 is explicit, by which the algebraic expression is directly converted into a canonical form of the logic

Appl. Sci. 2020, 10, 7180

6 of 13

expression. Let us compute the minterm canonical form of the Boolean function whose structure matrix is given in ([16], Example 6) using Theorem 2.

Example 2. Consider the Boolean function f with structure matrix

M f = δ2[1, 2, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 1, 2]. In (8), c1 = c2 = c6 = c7 = c8 = c10 = c12 = c15 = 1. By (10), the minterm canonical form of f is
f (x1, x2, x3, x4) = ∑ m(1, 2, 6, 7, 8, 10, 12, 15).
Furthermore, the minimization form of f is

f (x1, x2, x3, x4) = x1x¯3x¯4 + x2x3x4 + x¯1x3x¯4 + x¯2x3x¯4 + x¯1x¯2x¯3x4.

Comparing the above example with ([16], Example 6), the explicit equation makes the conversion straightforward. Moreover, given the truth table of a Boolean function, it is possible to write the function as various propositional formulas with irregular forms, while the minterm canonical form is unique up to the order of minterms.
4. Conversion of Expressions of Boolean Control Networks This section extends the presented approach to Boolean control networks to achieve the mutual
conversion between logic and algebraic expressions.
4.1. From Logic Expression to Algebraic Expression A method for computing the next state of BN (4) is provided in [3] based on the algebraic
expression as below.
Lemma 6 ([3]). For BN (5), if x(t) = δ22nn−i, then x(t + 1) = L δ22nn−i = δ22nn−ci , where
∑n
ci = si(j) × 2n−j, i = 0, 1, · · · , 2n − 1,
j=1
and si(j) is the function value in the row i of the truth table of fj.
The lemma above can be extend to BCNs for converting the logic expression into the algebraic expression.

Theorem 3. For BCN (6), let ci be defined by

∑n

ci = si(j) × 2n−j, i = 0, 1, . . . , 2m+n − 1,

(11)

j=1

where si(j) is the function value in the row i of the truth table of fj. Then, the transition matrix of Nin is

L = δ2n [2n − c2m+n−1, . . . , 2n − c1, 2n − c0].

(12)

In the theorem above, it can be seen that ci is the decimal representation of the n-bit binary number whose jth bit code is si(j).

Appl. Sci. 2020, 10, 7180

7 of 13

Proof. Let L be the transition matrix of Nin and x(t) u(t) = δ22nn−i. It can be inferred from (7) and

Lemma 6 that

x(t + 1) = L x(t) u(t) = L δ22nn−i = δ22nn−ci .

This implies that the (i + 1)th column of L from right is δ22nn−ci , i.e., L is equal to (12).

The following lemma for constructing the transition matrix of Nout can be obtained in almost the same way.

Theorem 4. For BCN (6), let c˜i be defined by

p

c˜i = ∑ s˜i(r) × 2p−r, i = 0, 1, . . . , 2n − 1,

(13)

r=1

where s˜i(r) is the function value in the row i of the truth table of gr. Then, the transition matrix of Nout is

H = δ2p [2p − c˜2n−1, . . . , 2p − c˜1, 2p − c˜0].

(14)

The following algorithm for converting the logic expression to the algebraic expression of a BCN can then be developed.
Next, let us consider the computational complexity of Algorithm 1 starting from the minterm canonical form.

Algorithm 1 Algorithm for converting the logic expression to the algebraic expression of BCN (6). Input: Logic expression of Nin (resp. Nout). Output: Transition matrix L (resp. H). Setp 1. For Nin, construct the truth table of fj for each j ∈ {1, 2, . . . , n}, which is denoted by
(s0(j) s1(j) . . . s2(jm)+n−1) .
Setp 2. Compute ci by Formula (11). Setp 3. The control-depending network transition matrix is given in (12). Setp 4. For Nout, construct the truth table of gr for each r ∈ {1, 2, . . . , p}, which is denoted by
(s˜0(r) s˜1(r) . . . s˜2(rn)−1) .
Setp 5. Compute c˜i by Formula (13). Setp 6. The transition matrix from x(t) to y(t) is given in (14).

Theorem 5. Algorithm 1 has a complexity of O(2m+nn).
Proof. In Step 1 (resp. Step 4), the truth tables of fj (resp. gr) can be obtained directly from their minterm canonical forms without any calculation. In Step 2, the computation cost of ci is one exponent and n multiplication together with n − 1 addition. Hence, the number of operations of Step 2 is at most 2n × 2m+n = 2m+n+1n. Step 3 requires 2m+n subtraction operations to compute the transition matrix L. Hence, the computation cost of Nin is 2m+n+1n + 2m+n = 2m+n(2n + 1). Similarly, the computation cost of c˜i is 2p, and hence the number of operations of Step 5 is at most 2p × 2n = 2n+1 p. Step 6 requires 2n subtraction operations to compute the transition matrix H. Hence, the computation cost of Nout is 2n+1 p + 2n = 2n(2p + 1). Therefore, the computational complexity of Algorithm 1 is O(2m+nn).
The STP based method presented in ([11], Theorem IV.6) and the Khatri-Rao product based method stated in Lemma 3 convert the logic expression into the algebraic expression of BCN (6) starting from the structure matrices, while Algorithm 1 starting from the minterm canonical form. It can be seen

Appl. Sci. 2020, 10, 7180

8 of 13

from Theorems 1 and 2 that the conversion between the minterm canonical form and the structure matrix of a logical function does not need any calculation. This implies that Algorithm 1, Lemma 3 and ([11], Theorem IV.6) can be viewed as starting from the same point. Then, the computational complexity of the STP and Khatri-Rao product based methods are 25(m+n) and 2n/n times that of Algorithm 1, respectively.
Let us illustrate Algorithm 1 with the following example.

Example 3. For the BCN depicted in Figure 1, the logical dynamic equations are

  x1(t + 1) = x2(t)u1(t), 

 

x2(t + 1)

=

u¯2(t),

(15)

 x3(t + 1) = x1(t) + x2(t),



 

y1(t) = x¯3(t).

Let us give the algebraic expression of such a BCN using Algorithm 1.

Step 1. Step 2. Step 3.

For Nin, the truth table of fj for each j ∈ {1, 2, 3} is listed in Table 1. By (11), ci (i ∈ {0, 1, . . . , 31}) is presented in the last column of Table 1. By (12), the control-depending network transition matrix is

L = δ8[3, 1, 7, 5, 3, 1, 7, 5, 7, 5, 7, 5, 7, 5, 7, 5, 3, 1, 7, 5, 3, 1, 7, 5, 8, 6, 8, 6, 8, 6, 8, 6]. (16)

Step 4. Step 5. Step 6.

For Nout, the truth table of g1 is given in Table 2. By (13), c˜i (i ∈ {0, 1, . . . , 7}) is presented in the last column of Table 2. By (14), the transition matrix from x(t) to y(t) is

H = δ2[2, 1, 2, 1, 2, 1, 2, 1].

(17)

Hence, the algebraic expression of BCN (15) is x(t + 1) = L x(t) u(t), (18) y(t) = H x(t),
where transition matrices L and H are given in (16) and (17), respectively.

Figure 1. Boolean control network.

Appl. Sci. 2020, 10, 7180

9 of 13

Table 1. Truth table relative to Nin (The indexed parameters a and b given together with other parameters are needed only further for Algorithm 2).
f1 f2 f3 ci i x1 x2 x3 u1 u2
b1i b2i b3i ai
000000 0 1 0 2 100001 0 0 0 0 200010 0 1 0 2 300011 0 0 0 0 400100 0 1 0 2 500101 0 0 0 0 600110 0 1 0 2 700111 0 0 0 0 801000 0 1 1 3 901001 0 0 1 1 10 0 1 0 1 0 1 1 1 7 11 0 1 0 1 1 1 0 1 5 12 0 1 1 0 0 0 1 1 3 13 0 1 1 0 1 0 0 1 1 14 0 1 1 1 0 1 1 1 7 15 0 1 1 1 1 1 0 1 5 16 1 0 0 0 0 0 1 1 3 17 1 0 0 0 1 0 0 1 1 18 1 0 0 1 0 0 1 1 3 19 1 0 0 1 1 0 0 1 1 20 1 0 1 0 0 0 1 1 3 21 1 0 1 0 1 0 0 1 1 22 1 0 1 1 0 0 1 1 3 23 1 0 1 1 1 0 0 1 1 24 1 1 0 0 0 0 1 1 3 25 1 1 0 0 1 0 0 1 1 26 1 1 0 1 0 1 1 1 7 27 1 1 0 1 1 1 0 1 5 28 1 1 1 0 0 0 1 1 3 29 1 1 1 0 1 0 0 1 1 30 1 1 1 1 0 1 1 1 7 31 1 1 1 1 1 1 0 1 5
Table 2. Truth table relative to Nout (The indexed parameters a˜ and b˜ given together with other parameters are needed only further for Algorithm 2).
g1 c˜i i x1 x2 x3 b˜ 1i a˜ i
00 0 0 1 1 10 0 1 0 0 20 1 0 1 1 30 1 1 0 0 41 0 0 1 1 51 0 1 0 0 61 1 0 1 1 71 1 1 0 0

Appl. Sci. 2020, 10, 7180

10 of 13

Algorithm 2 Algorithm for converting the algebraic expression back to the logic expression of BCN (7).
Input: Transition matrix L (resp. H). Output: Logic expression of Nin (resp. Nout).

Step 1. For Nin, let L = δ2n [l1, l2, . . . , l2m+n ], where lv ∈ {1, 2, . . . , 2n} represents the vth column of transition matrix L and v ∈ {1, 2, . . . , 2m+n}. Let ai be defined by

ai = 2n − l2m+n−i, i = 0, 1, . . . , 2m+n − 1.

(19)

In fact, ai is constructed by conversely applying (12), which has the same value as ci.
Step 2. Denote by bji the jth bit code of the binary representation of decimal number ai, where i ∈ {0, 1, . . . , 2m+n − 1} and j ∈ {1, 2, . . . , n}. In fact, bji is obtained by conversely applying (11), which has the same value as si(j).
Step 3. Construct the minterm canonical form of fj for each j ∈ {1, 2, . . . , n} as follows:

fj(x1, . . . , xn, u1, . . . , um) = ∑ mi, i∈Sj

where Sj = {i ∈ {0, 1, . . . , 2m+n − 1} | bji = 1}. Step 4. For Nout, let H = δ2p [h1, h2, . . . , h2n ], where hv ∈ {1, 2, . . . , 2n} represents the vth column of
transition matrix H and v ∈ {1, 2, . . . , 2n}. Let a˜i be defined by

a˜i = 2p − h2n−i, i = 0, 1, . . . , 2n − 1.

(20)

Step 5. Step 6.

In fact, a˜i is constructed by conversely applying (14), which has the same value as c˜i.
Denote by b˜ri the rth bit code of the binary representation of decimal number a˜i, where i ∈ {0, 1, . . . , 2n − 1} and r ∈ {1, 2, . . . , p}. In fact, b˜ri is obtained by conversely applying (13), which has the same value as s˜i(r).
Construct the minterm canonical form of gr for each r ∈ {1, 2, . . . , p} as follows:

∑ gr(x1, x2, . . . , xn) = mi, i∈S˜r

where S˜r = {i ∈ {0, 1, . . . , 2n − 1} | b˜ri = 1}.

4.2. From Algebraic Expression to Logic Expression The logical networks Nin and Nout can be reconstructed from the algebraic expression (7) through
conversely applying Algorithm 1. Let us illustrate the algorithm above with the following example.
Example 4. Reconstruct the logic network of BCN (18).
Step 1. Calculate ai for each i ∈ {0, 1, . . . , 31} by (19), which is presented in the last column of Table 1. Step 2. Through the decimal-binary conversion, one can calculate bji for each i ∈ {0, 1, . . . , 31} and j ∈
{1, 2, 3}, which is presented in Table 1. Step 3. Let
S1 = {i ∈ {0, 1, . . . , 31} | b1i = 1} = {10, 11, 14, 15, 26, 27, 30, 31}, S2 = {i ∈ {0, 1, . . . , 31} | b2i = 1} = {0, 2, 4, . . . , 30}, S3 = {i ∈ {0, 1, . . . , 31} | b3i = 1} = {8, 9, 10, . . . , 31}.