# Robust Template Decomposition without Weight Restriction  for Cellular Neural Networks Implementing Arbitrary Boolean Functions Using Support Vector Classifiers

Authors: Yih-Lon Lin; Jer-Guang Hsieh; Jyh-Horng Jeng
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

If the given Boolean function is linearly separable, a robust uncoupled cellular neural network can be designed as a maximal margin classifier. On the other hand, if the given Boolean function is linearly separable but has a small geometric margin or it is not linearly separable, a popular approach is to find a sequence of robust uncoupled cellular neural networks implementing the given Boolean function. In the past research works using this approach, the control template parameters and thresholds are restricted to assume only a given finite set of integers, and this is certainly unnecessary for the template design. In this study, we try to remove this restriction. Minterm- and maxterm-based decomposition algorithms utilizing the soft margin and maximal margin support vector classifiers are proposed to design a sequence of robust templates implementing an arbitrary Boolean function. Several illustrative examples are simulated to demonstrate the efficiency of the proposed method by comparing our results with those produced by other decomposition methods with restricted weights.


---

## Body

## 1. Introduction

Cellular neural networks (CNNs) are large scale nonlinear circuits composed of locally connected cells, which was introduced in 1988 by Chua and Yang [1, 2].  CNN has a tremendous variety of applications in the fields of dynamic systems and signal processing [3–9].  The analysis of the dynamic behavior for the class of CNNs without feedback interconnections from neighboring cells, namely the uncoupled CNNs, is one of the popular research topics.  A main feature of the uncoupled CNNs is that the binary steady state output in terms of the binary input of the CNN can be represented by a linearly separable Boolean function (LSBF) [1, 2].In the study of uncoupled CNNs, most of the elementary applications can be derived and analyzed via Boolean functions, and this is directly related to the CNN template parameters.  For LSBFs, Chen et al. [10] developed an essential relationship among the template, offset levels, a basis of the binary input vector set, and a neat truth table of the corresponding Boolean functions.  In their work, they found a criterion for LSBFs and the criterion depends only on symbolic relations among the outputs of the Boolean functions.  In [11, 12], the authors proposed an efficient method for implementing an LSBF and successfully realized all the 1882 and 94572 LSBFs by designing the corresponding CNN templates of 4 and 5 input variables, respectively.  However, since the number of Boolean functions increases exponentially as the number of input variables increases, their method can be hardly extended.The robustness indicator of a CNN is a measure quantifying the degree by which the parameters of a CNN can be perturbed while still producing the desired output.  The definitions of robustness may be different in different contexts.  Rigorous definitions of absolute and relative robustness of CNNs were given in [13].  A theoretical upper bound for relative robustness was derived and the absolute robustness can be arbitrarily increased by template scaling.  CNN autoassociative memories were designed in [14, 15] using particle swarm optimization method with the robustness of designed memories taken into consideration.  The dynamic behavior of a class of third-order competitive CNNs depending on two parameters was investigated in [16].  In the special class of one-parameter family of symmetric CNNs, the authors discussed the robustness of the complete stability with respect to nonsymmetric perturbations on the neuron interconnections.  In the VLSI implementation of CNN-UM (CNN Universal Machine), the template values will usually deviate from the ideal template values due to numerous reasons.  Therefore robust design is crucial to guarantee correct outputs.  To make the chip react as an ideal CNN structure, adaptive simulated annealing (ASA) method, a chip-specific optimization method, was proposed in [17] to automatically tune the template values.  The result of the optimization process is the least sensitive template to the actual chip instance.Recently, some machine learning techniques are applied to CNN applications.  The recurrent fuzzy cellular neural network (RFCNN) was proposed for automatically constructing a multiple-CNN integrated neural system in [18–20].  The proposed RFCNN can automatically learn the network structure and the parameters simultaneously for uncoupled or coupled CNN.  In the sense of learning, this structure learning includes the creation of fuzzy rules of fuzzy neural network and CNNs with pattern clustering algorithms.  The parameter learning contains the tuning of fuzzy membership functions and CNN templates.For an arbitrarily given Boolean function, Chen et al. [21, 22] proposed a generalization of Rosenblatt’s perceptron model (universal perceptron) with DNA-like learning and decomposition algorithm.  Their papers considered all of the Boolean functions via single-layer perceptron using the DNA-like learning algorithm.  The proposed algorithms first train the DNA-like offset sequence and decompose the given linearly inseparable Boolean function into a sequence of LSBFs with logic XOR as conjunctions of the sequence of LSBFs.  On the other hand, the CFC decomposition method, proposed by Crounse et al. [23], can be used to find a sequence of uncoupled CNNs implementing the given Boolean function, whether linearly separable or inseparable.  In CFC method, the entries of the control templates of the required uncoupled CNNs are restricted to {0,±1} and the thresholds are some integers.  The conjunctions of the sequence of CNNs are traditional logic operators.  The method is a brute force one, yet it is simple and easy to implement.It was pointed out in [24] that the geometric margin of a linear classifier with respect to a training data set, a notion borrowed from the machine learning theory, can conveniently be used to define the robustness of an uncoupled CNN implementing a linearly separable Boolean function.  Larger geometric margin indicates better robustness against perturbations in both template parameters and the input data.  Consequently, the so-called maximal margin classifiers (MMCs) can be devised to provide the most robust template design for uncoupled CNNs implementing linearly separable Boolean functions.  An uncoupled CNN is said to be robust if it is a maximal margin classifier; that is, its template values are the solution of a maximal margin classification problem.The decomposition method proposed by Lin et al. [24], abbreviated as LHJ method in this study, extends the CFC method in the sense that the entries of the control templates are restricted to more general sets  {0,±1,±2}  or  {0,±1,±2,±3}, and all robust CNNs with template entries belonging to these weight-restricted constraint sets are characterized.  Hence, under essentially the same search mechanism in CFC method, a much simpler search space, consisting of all possible robust CNNs with template values belonging to the weight-restricted set, is focused.  The extension of the restricted weights above  {0,±1,±2,±3}  is computationally expensive because the number of searching templates will be an enormous number.We wish to point out that the entries of the control template of a robust CNN are not required to be restricted to the set of small magnitude.  For instance, the uncoupled CNN with the following control template and threshold:(1)w=(25222394125148),b=25,
is robust.  The purpose of this study is to find algorithms for robust template decomposition without weight restriction for CNNs implementing an arbitrary Boolean function via support vector classifiers (SVCs).


## 2. Uncoupled CNN

Consider a standardM×N CNN.  In this study, we consider exclusively the most commonly used 3×3 neighborhood for each cell C(i,j).  Thus the CNN parameters may conveniently be represented by a triple (A,B,z), where A and B are 3×3 feedback and control templates, respectively, and z is the threshold value.  In this study, we consider the following uncoupled CNN written as
(2)
With the static binary inputs, the steady-state output yij(∞) of C(i,j) in this uncoupled CNN can be calculated explicitly as
(3)yij(∞)=sign[〈w,u〉+b],
where
(4)w:=[w1⋯w9]T,u:=[u1⋯u9]T,
and u1,…,u9 are inputs to the cell.  See Theorem 6.1 in [25].It is well known that a (local) Boolean functionh(u1,…,u9) of nine variables is realizable by every cell of an uncoupled CNN if and only if h(·) can be expressed by the formula
(5)h(u1,…,u9)=sign[a1u1+⋯+a9u9+b],
where ai,  i∈9_, b are real constants, and ui∈{1,-1},  i∈9_, is the ith Boolean variable.  See Theorem 6.2 in [25].  It is important to note that the discriminant function
(6)f(u):=a1u1+⋯+a9u9+b
is an affine-linear function of u∈ℜ9.  Thus implementing a Boolean function by an uncoupled CNN can be regarded as a linear classification problem.


## 3. Support Vector Classifiers

Since maximal margin and soft margin support vector classifiers will be utilized in our proposed decomposition methods, we briefly review the support vector classifiers in this section.  For more background materials, see, for instance, [26–28] and the references therein.LetX⊆ℜn and Y:={1,-1}.  Suppose we are given the training set
(7)S:={(xi,yi)}i=1l⊆X×Y.
The training set S in (7) is said to be linearly separable if there is a hyperplane Hw,b of the form
(8)fw,b(x):=〈w,x〉+b=0,w∈ℜn,b∈ℜ,
that correctly classifies all training data.  By treating the truth table of a given Boolean function as the training set with l=512 training data, this training set must be linearly separable in order for the Boolean function to be realizable by an uncoupled CNN.The geometric margin of the classifierfw,b(·) with respect to the training set S is defined by [28]
(9)ηS(w,b):=mini=1lyi·[〈∥w∥-1w,xi〉+∥w∥-1b].
This will be used as the robustness indicator of an uncoupled CNN implementing a linearly separable Boolean function [24].  Larger geometric margin indicates better robustness against perturbations in both template parameters and the input data.Let the Boolean function be linearly separable.  The maximal margin classifier (MMC) can be obtained by solving the following optimization problem:(10a)maximize∑i=1lzi-2-1∑i=1l∑j=1lzizjyiyj〈xi,xj〉(10b)subjectto∑i=1lziyi=0,zi≥0∀i∈l_.Suppose(z*,b*) solves the problem in  (10a) and (10b). Then the optimal weights are given by
(11)w*=∑i=1lzi*yixi.
The optimal discriminant function is thus given by
(12)f*(x)=〈w*,x〉+b*=∑i=1lzi*yi〈xi,x〉+b*.
Using the KKT conditions of the optimization problem (10a) and (10b), it can be shown that the corresponding margin is given by [28]
(13)γS=∥w*∥-1=(∑i=1lzi*)-1/2.
It is obvious that the maximal margin classification problem (10a) and (10b) has no solution if the training data of a Boolean function is linearly inseparable.  Note that as the maximal margin is obtained, the outputs of the optimal discriminant function will retain the same positive/negative signs even when the template parameters and the input data are perturbed.  Since the optimal separating hyperplane has the maximal geometric margin, the best robustness can be achieved for the designed CNN.To allow for misclassifications of training data, we now introduce the slack variables for classification problems.Letγ>0 be given.  The slack variable ξi of an example (xi,yi)  with respect to the hyperplane Hw,b and target margin γ is defined by [28]
(14)ξi:=max(0,γ-yi·[〈w,xi〉+b]).
See Figure 1 for illustration.  Clearly, ξi measures the amount by which the example (xi,yi) fails to have margin γ with respect to the hyperplane Hw,b.  Consequently, the quantity defined by
(15)∥ξ∥1:=∑i=1lξior∥ξ∥22:=∑i=1lξi2
measures the total amount by which the training set fails to have margin γ and takes into account any misclassifications of the training data.Figure 1
Slack variables for linear classification problems.The 2-norm soft margin classifiers (SVC2) will be used in this study.  The 1-norm soft margin classifiers (SVC1) may also be used.  In soft margin classification problems, the target marginγ is set to the canonical value of 1.The SVC2 can be obtained by solving the following optimization problem:(16a)maximize∑i=1lzi-12∑i=1l∑j=1lzizjyiyj〈xi,xj〉-12C∑i=1lzi2(16b)subjectto∑i=1lziyi=0,zi≥0∀i∈l_. Here, the regularization (or smoothing) parameter C>0 controls the tradeoff between the complexity of the machine and the number of nonseparable points.Suppose(z*,b*) solves the problem  in (16a) and (16b). Then the optimal weights and discriminant function are given by (11) and (12), respectively.  Moreover, the slack variables  ξi,  i∈l_, are given by
(17)ξi≔max(0,1-yi·[〈w*,xi〉+b*])=max(0,1-yi·[∑j=1lyjzj*〈xj,xi〉+b*]).


## 4. Minterm and Maxterm CNNs

To understand our proposed decomposition algorithm, we first introduce the minterm and maxterm Boolean functions [24].Definition 1.
A Boolean functionβ(u1,…,un) of n variables is said to be a minterm (resp., maxterm) if its output column in the truth table consists of all “−1”s (resp., “1”s) except for one entry having a “1” (resp., “−1”).
Since there are2n  rows in a truth table of  n  Boolean variables, for the usual case with n=9 variables, there are 29=512 distinct minterm (or maxterm) Boolean functions.
Every minterm (or maxterm) Boolean function is linearly separable [25].  In the truth table of a minterm (resp., maxterm) Boolean function, let  ujmin (resp., ujmax),  j∈n_, be the values (−1 or 1) of the input variables corresponding to the row with output 1 (resp., −1).  Then the optimal discriminant function with maximum (geometric) margin 1/n is given by
(18)fmin(u)=sign(u1min)u1+⋯+sign(unmin)un-(n-1)(resp.,fmax(u)=-sign(u1max)u1-⋯-sign(unmax)un+(n-1)).
For the usual case of n=9, the optimal discriminant function with maximum (geometric) margin 1/9 is given by
(19)fmin(u)=sign(u1min)u1+⋯+sign(u9min)u9-8(resp.,fmax(u)=-sign(u1max)u1-⋯-sign(u9max)u9+8fmax(u)).
A CNN which implements a minterm (resp., maxterm) Boolean function in each cell is called a minterm (resp., maxterm) CNN.  Our proposed algorithm is based on the following realization theorem [25].Theorem 2.
Every local Boolean function ofn variables can be realized by ORing (in minterm decomposition) or ANDing (in maxterm decomposition) at most 2n uncoupled CNNs.Let us consider for instance the Boolean functionβ with n=3 given  in the truth table shown in Table 1,  where u1, u2, and u3 are input variables and y is the output variable.Table 1
Simple Boolean function.
u
1
u
2
u
3
y
1
-
1
-
1
-
1
-
1
2
-
1
-
1
1
1
3
-
1
1
-
1
-
1
4
-
1
1
1
1
5
1
-
1
-
1
1
6
1
-
1
1
1
7
1
1
-
1
1
8
1
1
1
-
1Table1 can also be conveniently represented by the following figure by listing only the output values, where black and white dots represent logic values 1 and −1, respectively:Since there are five 1 s in the output, according to the realization theorem, the Boolean functionβ can be decomposed by ORing 5 minterm CNNs:
(20)β=β2∨β4∨β5∨β6∨β7,
where βj is a minterm Boolean function, having a “1” in the jth output and “−1”s elsewhere, and “∨” is the OR logic operator.  It is desirable to shorten the length of the minterm decomposition.  A natural idea is to group some minterms so that the resulting Boolean function is still linearly separable.  Furthermore, we require that the uncoupled CNN realizing the resulting Boolean function is robust in the sense that it is a maximal margin classifier.  For instance, the following decomposition produces exactly the same Boolean function:
(21)β=β1min∨β2min=(β5∨β6∨β7)∨(β2∨β4).
The first and second combined Boolean functions β1min and β2min are both linearly separable, which can be realized by the following robust uncoupled CNNs with control templates and thresholds, respectively:
(22)w=(2-1-1),b=-1,w=(-101),b=-1.
The problem is how we group appropriate minterms.


## 5. Decomposition Algorithms

In this section, we describe our proposed minterm- and maxterm-based decomposition methods.  Before proceeding, we give some motivation for the minterm-based decomposition algorithm.  First notice that the maximal margin classification problem (10a) and (10b) has no solution if the training data of a Boolean function is not linearly separable.  Suppose now we are given a general Boolean function.  To find the first template in our proposed algorithm, we may start from the working Boolean function which is the given Boolean function β, now thought of as the minterm decomposition.  Since we do not know whether the Boolean function β is linearly separable or not, we may solve (16a) and (16b) for an SVC2 with a guaranteed solution.  This results in an optimal separating hyperplane but some data may be misclassified.  Let Iremain be the set of all indices of data with output value 1 in the working Boolean truth table.  If there are no misclassified data, then the algorithm stops because the working Boolean function is linearly separable and we may find the corresponding robust CNN by solving the maximal margin classification problem  (10a) and (10b).  Otherwise suppose that there are misclassified data, and the jth data with j∈Iremain achieves the maximal value of slack variables among all data with indices in Iremain.  The key idea is that this data might represent the point which is rather difficult to be correctly classified by the current hyperplane.  In this case, the minterm with output value 1 in the jth data will be dropped from the working Boolean function.  This process is repeated until we find a linearly separable working Boolean function or end up with a minterm which is certainly linearly separable.The preceding discussion can be summarized as the following top-down (or pruning) algorithm which is based on the minterm realization theorem.  Note that the entries of the Boolean truth table are either +1 or −1.Algorithm
1 (minterm-based decomposition)Data. A Boolean truth table consisting of l=2n training data S:={(xi,yi)}i=1l⊆{+1,-1}n×{+1,-1} with n predictors and one output.Goal.  A sequence of robust templates implementing the given Boolean truth table.Step 1.
Choose the regularization parameterC>0 and the desired upper bound α, 0≤α≤1, for the slack variables ξi.Step 2.
Define(23)D:={yi}i=1l,Iremain⟵Iindex,m⟵0.Step 3.
Define(24)Iindex:={i∈l_:yi=1}.Step 4.
IfIindex=⌀, go to Step 9, else go to Step 5.Step 5.
If#(Iremain)=1, say j∈Iremain, set m←m+1.  Then the mth robust template is a minterm.Step
5.1. Form the new target set D by setting yj=-1.Step
5.2.
I
index
←
I
index
∖
I
remain, Iremain←Iindex, and go to Step 3.Step 6.
If#(Iremain)>1, from the current l training data with target set D, solve the soft margin classification problem.  Define
(25)Imiss:={i∈l_:ξi≥α}ifα=1;Imiss:={i∈l_:ξi>α}ifα≠1.Step 7.
IfImiss=⌀, set m←m+1.  Then the mth robust template is obtained by solving the maximal margin classification problem with target set D.Step
7.1. Form the new target set D by setting yj=-1 for all j∈Iremain.Step
7.2.
I
index
←
I
index
∖
I
remain, Iremain←Iindex, and go to Step 3.Step 8.
IfImiss≠⌀, find
(26)Itemp=argmaxi∈Iremain{ξi}.Step
8.1. If #(Itemp)<#(Iremain), set Idelete=Itemp; else choose any j∈Itemp and set Idelete=Itemp∖{j}.Step
8.2. Form the new target set D by setting yj=-1 for all j∈Idelete.Step
8.3. Iremain←Iremain∖Idelete and go to Step 3.Step 9.
STOP!The given Boolean function is realized by ORing the Boolean functions corresponding to the robust templates generated by the algorithm.  In the worst case, the algorithm yields templates being all minterms.Note that in Step6 if α=1, the points with ξi≥α=1 (including the case ξi=1 corresponding to the points on the separating hyperplane) must be included in the set Imiss.  However, if α=0, the points with ξi=α=0 (corresponding to the points achieving the target functional margin of value 1) must not be included in the set Imiss.  In Step 8.1, the indices to be deleted from Iremain are all indices (possibly all indices except one) in the set Itemp.It is true that different values of the regularization parameterC and the desired upper bound α in Step 1 will affect the length and margins of the decomposition.  In general, the choice of both parameters is problem-dependent.  According to our experience, the choice of C≥1 and α=1 in Step 1 works well in most cases we have encountered.  However, the algorithm may result in a long sequence of robust templates or poor robustness in some templates if C and α are small.Notice that we may also state a similar algorithm based on maxterm realization theorem, namely, the maxterm-based decomposition algorithm.  In this algorithm, we simply changeyj=-1 to yj=1 in Steps 3, 5.1, 7.1, and 8.2 of the minterm-based decomposition algorithm.


## 6. Illustrative Examples

In this section, we provide six illustrative examples.  In Example1, the Boolean function is generated from the so-called Game of Life, and those in Examples 2–6 will be given by the (minimal CNN) truth tables [25], where black and white dots represent logic values 1 and −1, respectively.  In the following simulations, the maxterm-based decomposition algorithm using SVC2 with α=1 and C=1 is implemented in Examples 1–3 and the minterm-based decomposition algorithm using SVC2 with α=1 and C=2 is implemented in Examples 4–6.  We wish to point out that the template values in the following simulations are rounded to integers.  All the simulated results obtained from the proposed decomposition algorithms are compared to those obtained from the LHJ algorithms with I3.Example 1.
Consider a two-dimensional matrix of cells.  The Boolean function for the Game of Life, which is not linearly separable, is generated from the following local rules.(a)
If there are two neighbors whose state values are 1, then set the state value to 1.(b)
If there are three neighbors whose state values are 1, then retain the state value.(c)
For situations apart from (a) and (b), set the state value to −1.
The LHJ and maxterm-based decompositions are shown in Tables2 and 3, respectively.  As can be seen, we obtain essentially the same results including the length and margins of the decompositions by both algorithms.Table 2
LHJ decomposition in Example1.
Template values
Logic operator
Margin
1
w
=
(
-
1
,
-
1
,
-
1
,
-
1
,
0
,
-
1
,
-
1
,
-
1
,
1
)
,
-
b
=
-
1
0.3536
2
w
=
(
-
1
,
-
1
,
-
1
,
-
1
,
-
1
,
-
1
,
-
1
,
-
1
,
-
1
)
,
b
=
-
4
XOR
0.3333Table 3
Maxterm-based decomposition in Example1.
Template values
Logic operator
Margin
1
w
=
(
-
1
,
-
1
,
-
1
,
-
1
,
0
,
-
1
,
-
1
,
-
1
,
-
1
)
,
b
=
-
1
0.3536
2
w
=
(
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
,
1
)
,
b
=
4
AND
0.3333Example 2.
Consider the Boolean function given by the truth table of Figure2.  The LHJ and maxterm-based decompositions are shown in Tables 4 and 5, respectively.  It is seen that the maxterm-based decomposition has little shorter length but with smaller margins.Table 4
LHJ decomposition in Example2.
Template values
Logic operator
Margin
1
w
=
(
-
1
,
2
,
0
,
-
1
,
0
,
0
,
0
,
0
,
0
)
,
b
=
-
1
0.4083
2
w
=
(
-
2
,
0
,
-
2
,
1
,
1
,
0
,
0
,
0
,
0
)
,
b
=
-
3
OR
0.3162
3
w
=
(
1
,
0
,
1
,
-
1
,
0
,
0
,
0
,
0
,
0
)
,
b
=
-
2
OR
0.5774Table 5
Maxterm-based decomposition in Example2.
Template values
Logic operator
Margin
1
w
=
(
-
3
,
1
,
1
,
-
2
,
0
,
0
,
0
,
0
,
0
)
,
b
=
2
0.2581
2
w
=
(
3
,
3
,
-
2
,
1
,
1
,
0
,
0
,
0
,
0
)
,
b
=
5
AND
0.2041Figure 2
Boolean function of Example2.Example 3.
Let the Boolean function be given by the truth table shown in Figure3.  The LHJ decomposition is shown in Table 6 and the maxterm-based decomposition is given in Table 7.  It is observed that the length of the maxterm-based decomposition is much shorter than that of LHJ decomposition, but the minimal margin of the templates by the maxterm-based algorithm is a little bit smaller.Table 6
LHJ decomposition in Example3.
Template values
Logic operator
Margin
1
w
=
(
3
,
2
,
2
,
2
,
3
,
1
,
2
,
1
,
2
,
1
)
,
b
=
1
0.1581
2
w
=
(
1
,
1
,
2
,
1
,
2
,
0
,
1
,
1
,
1
)
,
b
=
1
AND
0.2673
3
w
=
(
2
,
1
,
0
,
1
,
0
,
1
,
1
,
0
,
1
)
,
b
=
-
4
OR
0.3333
4
w
=
(
0
,
1
,
2
,
1
,
2
,
0
,
1
,
1
,
1
)
,
b
=
-
2
OR
0.3333
5
w
=
(
1
,
1
,
0
,
0
,
0
,
1
,
0
,
1
,
1
)
,
b
=
4
AND
0.4472Table 7
Maxterm-based decomposition in Example3.
Template values
Logic operator
Margin
1
w
=
(
4
,
3
,
4
,
3
,
5
,
1
,
3
,
2
,
3
)
,
b
=
1
0.1010
2
w
=
(
1
,
1
,
-
1
,
-
1
,
-
1
,
1
,
-
1
,
1
,
1
)
,
b
=
8
AND
0.3333Figure 3
Boolean function of Example3.Example 4.
Consider the Boolean function given by the truth table of Figure4.  The resulting decomposition by LHJ algorithm is given in Table 8.  As shown in Table 9, the length and the minimal margin of the minterm-based decomposition are the same as those of the LHJ decomposition.Table 8
LHJ decomposition in Example4.
Template values
Logic operator
Margin
1
w
=
(
3
,
1
,
-
1
,
1
,
3
,
2
,
1
,
3
,
2
)
,
b
=
2
0.1601
2
w
=
(
0
,
0
,
1
,
-
1
,
0
,
1
,
1
,
1
,
0
)
,
b
=
-
4
NAND
0.4472Table 9
Minterm-based decomposition in Example4.
Template values
Logic operator
Margin
1
w
=
(
3
,
1
,
-
1
,
1
,
3
,
2
,
1
,
3
,
2
)
,
b
=
2
0.1601
2
w
=
(
-
1
,
0
,
1
,
-
1
,
-
1
,
1
,
1
,
1
,
-
1
)
,
b
=
-
7
OR
0.3536Figure 4
Boolean function of Example4.Example 5.
Let the Boolean function be given by the truth table shown in Figure5.  The LHJ and minterm-based decompositions are shown in Tables 10 and 11, respectively.  Note that the length of the minterm-based decomposition is shorter than that of the LHJ decomposition.  Note that the first templates in both decompositions have small margins.Table 10
LHJ decomposition in Example5.
Template values
Logic operator
Margin
1
w
=
(
1
,
-
2
,
1
,
-
2
,
2
,
3
,
3
,
3
,
2
)
,
b
=
2
0.1490
2
w
=
(
0
,
-
1
,
1
,
-
1
,
1
,
1
,
1
,
1
,
1
)
,
b
=
1
AND
0.3535
3
w
=
(
0
,
-
1
,
1
,
-
1
,
0
,
1
,
1
,
0
,
0
)
,
b
=
-
2
OR
0.4472
4
w
=
(
1
,
0
,
0
,
0
,
0
,
1
,
1
,
1
,
0
)
,
b
=
-
3
OR
0.5000Table 11
Minterm-based decomposition in Example5.
Template values
Logic operator
Margin
1
w
=
(
1
,
-
3
,
2
,
-
3
,
3
,
4
,
4
,
4
,
3
)
,
b
=
9
0.1060
2
w
=
(
-
1
,
-
1
,
1
,
-
1
,
-
1
,
-
1
,
1
,
-
1
,
-
1
)
,
b
=
-
8
OR
0.3333
3
w
=
(
-
1
,
-
1
,
1
,
-
1
,
-
1
,
1
,
-
1
,
-
1
,
-
1
)
,
b
=
-
8
OR
0.3333Figure 5
Boolean function of Example5.Example 6.
Let the Boolean function be given by the truth table shown in Figure6.  The resulting decompositions by the LHJ and minterm-based algorithms are given in Tables 12 and 13, respectively.  Again, the minterm-based decomposition has shorter length but with smaller margins.  In Table 13, it is seen that the first Boolean function has a smaller margin than other Boolean functions in the minterm-based decomposition.Table 12
LHJ Decomposition in Example6.
Template values
Logic operator
Margin
1
w
=
(
2
,
-
2
,
-
1
,
1
,
3
,
-
2
,
0
,
0
,
0
)
,
b
=
1
0.2085
2
w
=
(
1
,
-
1
,
1
,
2
,
1
,
-
1
,
0
,
0
,
0
)
,
b
=
-
3
XOR
0.3780
3
w
=
(
-
1
,
1
,
0
,
0
,
0
,
-
1
,
0
,
0
,
0
)
,
b
=
-
2
OR
0.5774
4
w
=
(
-
1
,
-
2
,
1
,
2
,
1
,
-
1
,
0
,
0
,
0
)
,
b
=
3
AND
0.2887
5
w
=
(
1
,
1
,
0
,
1
,
0
,
1
,
0
,
0
,
0
)
,
b
=
-
3
OR
0.5000
6
w
=
(
-
1
,
0
,
0
,
0
,
1
,
-
1
,
0
,
0
,
0
)
,
b
=
-
2
OR
0.5774
7
w
=
(
1
,
1
,
0
,
0
,
1
,
0
,
0
,
0
,
0
)
,
b
=
2
AND
0.5774
8
w
=
(
1
,
-
1
,
1
,
-
1
,
0
,
0
,
0
,
0
,
0
)
,
b
=
-
3
OR
0.5000Table 13
Minterm-based decomposition in Example6.
Template values
Logic operator
Margin
1
w
=
(
-
5
,
-
2
,
-
1
,
1
,
5
,
-
3
,
0
,
0
,
0
)
,
b
=
-
8
0.1240
2
w
=
(
3
,
1
,
-
3
,
3
,
-
1
,
1
,
0
,
0
,
0
)
,
b
=
-
7
OR
0.1826
3
w
=
(
3
,
-
2
,
1
,
-
3
,
1
,
-
1
,
0
,
0
,
0
)
,
b
=
-
6
OR
0.2000
4
w
=
(
-
2
,
2
,
1
,
1
,
-
2
,
-
2
,
0
,
0
,
0
)
,
b
=
-
7
OR
0.2357
5
w
=
(
1
,
1
,
1
,
1
,
0
,
1
,
0
,
0
,
0
)
,
b
=
-
4
OR
0.4472Figure 6
Boolean function of Example6.


## 7. Conclusion

In this study, simple minterm- and maxterm-based decomposition algorithms utilizing soft margin and maximal margin classifiers have been proposed to design a sequence of robust templates implementing an arbitrary Boolean function.  In contrast to the past research works, the control template parameters and thresholds in our approach are not restricted to assume only a given finite set of integers.  Several numerical examples have been provided to illustrate the use of the proposed method.  CFC and LHJ decomposition methods are in general faster than the proposed minterm- and maxterm-based decomposition methods.  However, in many cases, the minterm- and maxterm-based decomposition methods produce a sequence of robust templates with shorter length.  To further speed up the decomposition algorithm, a natural idea is to make use of more logic functions as conjunctions for the sequence of robust templates, instead of OR operator in minterm-based decomposition or AND operator in maxterm-based decomposition.  This constitutes an interesting future research topic.  Furthermore, it is worthwhile to investigate if one can devise a decomposition algorithm such that each resulting robust template in the decomposition has a margin greater than or equal to a pre-specified value.  This constitutes another interesting future research topic.



---

*Source: 614543-2013-07-17.xml*