# Characterization of the Evolution of  Nonlinear Uniform Cellular Automata in  the Light of Deviant States

Authors: Pabitra Pal Choudhury; Sudhakar Sahoo; Mithun Chakraborty
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

Dynamics of a nonlinear cellular automaton (CA) is, in general asymmetric, irregular, and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable, primarily due to the presence of a matrix handle. In this paper, we present a novel technique of studying the properties of the State Transition Diagram of a nonlinear uniform one-dimensional cellular automaton in terms of its deviation from a suggested linear model. We have considered mainly elementary cellular automata with neighborhood of size three, and, in order to facilitate our analysis, we have classified the Boolean functions of three variables on the basis of number and position(s) of bit mismatch with linear rules. The concept of deviant and nondeviant states is introduced, and hence an algorithm is proposed for deducing the State Transition Diagram of a nonlinear CA rule from that of its nearest linear rule. A parameter called the proportion of deviant states is introduced, and its dependence on the length of the CA is studied for a particular class of nonlinear rules.


---

## Body

## 1. Introduction

The study of Boolean functions by G. Boole finds its application in various fields like electronics, computer hardware and software and is the base of digital electronics. On the other hand, the concept of Cellular Automata (CA) introduced by von Neumann [1] is a suitable tool for Complex Systems. CA rules have many real-life applications in almost all areas of science like physics, chemistry, mathematics, biology, engineering, and finance.  A connection can be made between CA rules in different dimensions with n-variable Boolean functions [2, 3]. Out of 22n Boolean functions of n variables, only 2n are linear and the rest are nonlinear [4]. In this way we get linear CAs and nonlinear CAs [2, 5, 6]. Likewise, we have uniformor hybrid CA, abbreviated as UCA and HCA, respectively, according to whether or not the same rule is applied to all the cells of the CA.Thedynamic behavior of any CA is visualized and studied in terms of either its space-time patternor its basin-of-attractionfield [7]. The latter is essentially a graph, which may or may not consist of disjoint subgraphs, and is commonly referred to as the State Transition Diagram or, in short, the STD of the CA. In the past, several attempts have been made [7–12] to study qualitatively and quantitatively the characteristics of UCA STDs in general (linear or nonlinear) in terms of parameters such as Z-parameter, λ-ratio, and λ-parameter. However, all these are techniques of absolute characterization of an STD (or, equivalently, a CA rule), that is, their main objective is to capture the graphical features of an STD as itis and they are not based on the comparison of a given STD with some known standard STD. Any linear UCA STD may be taken as a standard for comparison because all its essential features bear simple and well-known relationships with the fundamental properties such as rank, nullity, and determinant of the state transition matrixor transformation matrix, denoted by  T, of the corresponding linear CA rule. With this in mind, we have made an attempt at the relative characterizationof a particular set of nonlinear UCA STDs by first identifying the nearest linear rule of each such nonlinear rule, then considering the STD of the said nearest linear CA rule as a linear modelfor the nonlinear STD concerned and finally determining the nature and extent of departure of this nonlinear STD from the said linear model. But, first of all, we cluster the Boolean rules themselves into classes in order to separate out those rules that are readily amenable to the above analysis.The remainder of this paper is organized in the following manner. In Section2, some preliminary discussions on both Boolean functions and Cellular Automata are presented. In Section 3, some theoretical results are obtained using Hamming Distance (H.D) between Boolean functions.  In [5, 6] Boolean functions are classified and subclassified according to their degree of nonlinearity and also the position of bit mismatch. Some of these ideas are also included in this section. Using these ideas we introduce the concepts of deviant and nondeviant states in Section 4. Finally Section 5 concludes the paper.


## 2. Basic Concepts

### 2.1. Boolean Functions: Their Representations, Naming Conventions, and Types

ABoolean function or rulef(y1,y2,…,yp) of p independent binary variables is defined as a mapping from {0,1}p to {0,1}. Any Boolean function can be represented either by a Truth Table or by one of several alternative algebraic forms such as D.N.F. (“Disjunctive Normal Form”), C.N.F. (“Conjunctive Normal Form”), and A.N.F. (“Algebraic Normal Form”). A Boolean rule is often identified with the output column of its Truth Table, which is a binary string of length 2p for p independent variables. The decimal equivalent of this binary string, with the output of the first row being taken as the least significant bit, is called the Wolfram’s number(W) of the rule, and the rule is referred to as Rule W or fW. For example, the two-variable function f(y1,y2) satisfying  f(0,0)=0,  f(0,1)=1,  f(1,0)=1,  f(1,1)=1 is considered identical to the bitstring 1110 and is designated as Rule  14 of two variables or f14(y1,y2). Another naming scheme of Boolean functions is based on their Algebraic Normal Form which consists of AND and XOR operations only [4]. For one variable y1, the complete algebraic normal form is (y1⊕1) which is also the A.N.F. of f1(y1)=y̅1. Proceeding recursively, the complete A.N.F. of two variables y1,y2 is [{y2(y1⊕1)}⊕(y1⊕1)]=(y2y1⊕y2⊕y1⊕1)≡f1(y1,y2)=y̅1y̅2, and that of three variables is given by [{y3(y1y2⊕y2⊕y1⊕1)}⊕(y1y2⊕y2⊕y1⊕1)]=(y1y2y3⊕y2y3⊕y3y1⊕y3⊕y1y2⊕y2⊕y1⊕1)≡f1(y1,y2,y3)=y̅1y̅2y̅3 and so on. In general, there are 2p product terms in the complete A.N.F. of p-variables. The A.N.F. of any p-bit Boolean function can be generated by excluding one or more terms from the complete A.N.F. of p variables. If we denote presence of a term by 1 and absence by 0, we get a new binary string (of length 2p) corresponding to every Boolean rule and the decimal equivalent of this bitstring is called the A.N.F. number of the rule concerned, for example, consider the function f102(y1,y2,y3)=y̅1y̅2y3+y̅1y2y̅3+y1y̅2y3+y1y2y̅3=y2⊕y3; comparing with the complete A.N.F. of three variables, the binary string corresponding to the A.N.F. of  f102 is found to be 00010100, so its A.N.F. number must be 20. Throughout this paper, Boolean functions have always been represented by their A.N.F. but have been referred to by their Wolfram numbers [2]. It is also worthwhile to mention here that if the Wolfram’s number of a rule is even (odd), its ANF number is also even (odd), hence, without loss of generality, a rule may be referred to as “even-numbered” or “odd-numbered,” as the case may be. Thus Rule  10 is an even rule while Rule  57 is an odd rule.The generalized A.N.F. of a Boolean function ofp variables y1,y2,…,yp is given by(2.1)f(y1,y2,…,yp)=a0⊕(∑i=1paiyi)⊕(∑i=1i<jp∑j=1paijyiyj)⊕(∑i=1i<jp∑j=1j<kp∑k=1paijkyiyjyk)⊕⋯⊕a123⋯py1y2⋯yp,
where each of the coefficients a0,a1,a2,…,a12,a13,…,a123,…,a123⋯p may be either 0 or 1.The number of variables in the highest product term with non-zero coefficient in the A.N.F. of a Boolean function is the algebraic degree of the function. A function of degree at most one is called anaffine function. An affine function with the constant term equal to zero is called a linear function; all other functions are nonlinear functions. For p binary variables, there are 2p+1 affine functions of which 2p are linear and the remaining 2p are logical complements of these linear rules (they are nonlinear as each has its constant term equal to unity). For example, f0,f60,f90,f102,f150,f170,f204,f240 are the 8 linear functions of 3 variables; the remaining 248 functions are called nonlinear functions out of which the 8 functions f255,f195,f165,f153,f105,f85,f51,f15 are nonlinear affine functions.


### 2.2. Hamming Distance and Degree of Nonlinearity of a Boolean Rule

TheHamming distance (abbreviated as H.D. throughout this paper) between any two bit sequences of equal length is defined as the number of positions at which the bits differ in the two sequences.The H.D. between two Boolean functions ofp variables is defined as the H.D. between the binary sequences formed by the output columns of their Truth Tables (i.e., the p-bit binary equivalents of the rule numbers according to Wolfram’s labeling convention). For example, let us take two Boolean functions of three variables namely Rule  34 and Rule  225. Their 8-bit binary representations are 00100010 and 11100001, respectively. Clearly, these two strings differ from each other at 4 bit positions. Hence, the H.D. of Rule  34 from Rule  225 is 4. Equivalently, the H.D. between two rules f1 and f2 is given by the weightof the sum mod 2 (XOR) of these two rules; in other words, it is the number of “1”s in the output column of the Truth Table of f1⊕f2.Thedegree of nonlinearity of a p-variable Boolean function f is defined as the minimum H.D. of f from the set of all affine functions of p variables.


### 2.3. Terminology and Notation Pertaining to One-Dimensional Cellular Automata

In this paper, we will restrict ourselves to the study of a one-dimensional, binary cellular automaton (CA) ofn cells (i.e., nbits) x1,x2,…,xn, with local architecture [7]. The global state or simply state of a CA at any time instant t is represented as a vector Xt=(x1t,x2t,…,xnt) where xit denotes the bit in the ith cell xi at time instant t. However, instead of expressing a state as a bitstring, we will frequently represent it by the decimal equivalent of the n-bit string with x1 as the Most Significant Bit; for example, for a 4-bit CA, the state 1011may be referred to as state 11(=1×20+1×21+0×22+1×23).The bit in theith cell at the “next” time instant t+1 is given by alocal mappingdenoted by fi, say, which takes as its argument a vector of the bits    (in proper order) at time instant  t in the cells of a certain predefined neighborhood(of size p, say) of the ith cell. Thus, the size of the neighborhood is taken to be the same for each cell and may also be called the “number of variables” (which fi takes as inputs).Null Boundary (NB)
The left neighbor ofx1 and the right neighbor of xn are taken as 0 each.Periodic Boundary (PB)
xn is taken as the left neighbor of x1 and x1 as the right neighbor of xn.A CA may be represented as a string of the rules applied to the cells in proper order, along with a specification of the boundary conditions. For example,〈103,234,90,0〉NB refers to the CA (x1,x2,x3,x4), where x1t+1=f103(0,x1t,x2t), x2t+1=f234(x1t,x2t,x3t), x3t+1=f90(x2t,x3t,x4t), x4t+1=f0(x3t,x4t,0).If the “present state” of ann-bit CA (at time t) is Xt, its “next state” (at time t+1), denoted by Xt+1, is in general given by the global mappingF(Xt)=(f1(lbt,x1t,x2t),f2(x1t,x2t,x3t),…,fn(xn-1t,xnt,rbt)), where lb and rb denote, respectively, the left boundary of x1 and right boundary of xn.If the rule applied to each cell of a CA is a linear Boolean function, the CA will be called aLinear Cellular Automaton, otherwise a Nonlinear Cellular Automaton, for example, 〈0,60,60,204〉NB is a linear CA while 〈31,31,31,31〉NB and 〈60,90,87,123〉PB are nonlinear CAs.If the same Boolean function (rule) determines the “next” bit in each cell of a CA, the CA will be called aUniform Cellular Automaton (UCA), otherwise it will be called a Hybrid Cellular Automaton (HCA), for example, 〈135,135,135,135〉PB is a UCA, 〈0,60,72,72〉NB is a HCA.For a UCA, the Boolean function applied to each cell will be called therule of the CA. So for a UCA, we can obviously drop the superscript “i” from the local mapping fi and simply denote it as f. for example. for the 4-bit CA〈230,230,230,230〉PB, the rule of the CA is Rule  230 and the CA will be called the “Rule  230 CA” of 4 bits with periodic boundary conditions.  Henceforth, we will use the following notation UCAnNB, UCAnPB, HCAnNB, and HCAnPB for an n-bit CA. For our purpose, we will be mostly interested in elementary CA defined by Wolfram [2] to be one-dimensional binary CA with a symmetrical neighborhood of size p=3 for each cell so that xit+1=fi(xi-1t,xit,xi+1t),i=2,3,…,n-1.


## 2.1. Boolean Functions: Their Representations, Naming Conventions, and Types

ABoolean function or rulef(y1,y2,…,yp) of p independent binary variables is defined as a mapping from {0,1}p to {0,1}. Any Boolean function can be represented either by a Truth Table or by one of several alternative algebraic forms such as D.N.F. (“Disjunctive Normal Form”), C.N.F. (“Conjunctive Normal Form”), and A.N.F. (“Algebraic Normal Form”). A Boolean rule is often identified with the output column of its Truth Table, which is a binary string of length 2p for p independent variables. The decimal equivalent of this binary string, with the output of the first row being taken as the least significant bit, is called the Wolfram’s number(W) of the rule, and the rule is referred to as Rule W or fW. For example, the two-variable function f(y1,y2) satisfying  f(0,0)=0,  f(0,1)=1,  f(1,0)=1,  f(1,1)=1 is considered identical to the bitstring 1110 and is designated as Rule  14 of two variables or f14(y1,y2). Another naming scheme of Boolean functions is based on their Algebraic Normal Form which consists of AND and XOR operations only [4]. For one variable y1, the complete algebraic normal form is (y1⊕1) which is also the A.N.F. of f1(y1)=y̅1. Proceeding recursively, the complete A.N.F. of two variables y1,y2 is [{y2(y1⊕1)}⊕(y1⊕1)]=(y2y1⊕y2⊕y1⊕1)≡f1(y1,y2)=y̅1y̅2, and that of three variables is given by [{y3(y1y2⊕y2⊕y1⊕1)}⊕(y1y2⊕y2⊕y1⊕1)]=(y1y2y3⊕y2y3⊕y3y1⊕y3⊕y1y2⊕y2⊕y1⊕1)≡f1(y1,y2,y3)=y̅1y̅2y̅3 and so on. In general, there are 2p product terms in the complete A.N.F. of p-variables. The A.N.F. of any p-bit Boolean function can be generated by excluding one or more terms from the complete A.N.F. of p variables. If we denote presence of a term by 1 and absence by 0, we get a new binary string (of length 2p) corresponding to every Boolean rule and the decimal equivalent of this bitstring is called the A.N.F. number of the rule concerned, for example, consider the function f102(y1,y2,y3)=y̅1y̅2y3+y̅1y2y̅3+y1y̅2y3+y1y2y̅3=y2⊕y3; comparing with the complete A.N.F. of three variables, the binary string corresponding to the A.N.F. of  f102 is found to be 00010100, so its A.N.F. number must be 20. Throughout this paper, Boolean functions have always been represented by their A.N.F. but have been referred to by their Wolfram numbers [2]. It is also worthwhile to mention here that if the Wolfram’s number of a rule is even (odd), its ANF number is also even (odd), hence, without loss of generality, a rule may be referred to as “even-numbered” or “odd-numbered,” as the case may be. Thus Rule  10 is an even rule while Rule  57 is an odd rule.The generalized A.N.F. of a Boolean function ofp variables y1,y2,…,yp is given by(2.1)f(y1,y2,…,yp)=a0⊕(∑i=1paiyi)⊕(∑i=1i<jp∑j=1paijyiyj)⊕(∑i=1i<jp∑j=1j<kp∑k=1paijkyiyjyk)⊕⋯⊕a123⋯py1y2⋯yp,
where each of the coefficients a0,a1,a2,…,a12,a13,…,a123,…,a123⋯p may be either 0 or 1.The number of variables in the highest product term with non-zero coefficient in the A.N.F. of a Boolean function is the algebraic degree of the function. A function of degree at most one is called anaffine function. An affine function with the constant term equal to zero is called a linear function; all other functions are nonlinear functions. For p binary variables, there are 2p+1 affine functions of which 2p are linear and the remaining 2p are logical complements of these linear rules (they are nonlinear as each has its constant term equal to unity). For example, f0,f60,f90,f102,f150,f170,f204,f240 are the 8 linear functions of 3 variables; the remaining 248 functions are called nonlinear functions out of which the 8 functions f255,f195,f165,f153,f105,f85,f51,f15 are nonlinear affine functions.


## 2.2. Hamming Distance and Degree of Nonlinearity of a Boolean Rule

TheHamming distance (abbreviated as H.D. throughout this paper) between any two bit sequences of equal length is defined as the number of positions at which the bits differ in the two sequences.The H.D. between two Boolean functions ofp variables is defined as the H.D. between the binary sequences formed by the output columns of their Truth Tables (i.e., the p-bit binary equivalents of the rule numbers according to Wolfram’s labeling convention). For example, let us take two Boolean functions of three variables namely Rule  34 and Rule  225. Their 8-bit binary representations are 00100010 and 11100001, respectively. Clearly, these two strings differ from each other at 4 bit positions. Hence, the H.D. of Rule  34 from Rule  225 is 4. Equivalently, the H.D. between two rules f1 and f2 is given by the weightof the sum mod 2 (XOR) of these two rules; in other words, it is the number of “1”s in the output column of the Truth Table of f1⊕f2.Thedegree of nonlinearity of a p-variable Boolean function f is defined as the minimum H.D. of f from the set of all affine functions of p variables.


## 2.3. Terminology and Notation Pertaining to One-Dimensional Cellular Automata

In this paper, we will restrict ourselves to the study of a one-dimensional, binary cellular automaton (CA) ofn cells (i.e., nbits) x1,x2,…,xn, with local architecture [7]. The global state or simply state of a CA at any time instant t is represented as a vector Xt=(x1t,x2t,…,xnt) where xit denotes the bit in the ith cell xi at time instant t. However, instead of expressing a state as a bitstring, we will frequently represent it by the decimal equivalent of the n-bit string with x1 as the Most Significant Bit; for example, for a 4-bit CA, the state 1011may be referred to as state 11(=1×20+1×21+0×22+1×23).The bit in theith cell at the “next” time instant t+1 is given by alocal mappingdenoted by fi, say, which takes as its argument a vector of the bits    (in proper order) at time instant  t in the cells of a certain predefined neighborhood(of size p, say) of the ith cell. Thus, the size of the neighborhood is taken to be the same for each cell and may also be called the “number of variables” (which fi takes as inputs).Null Boundary (NB)
The left neighbor ofx1 and the right neighbor of xn are taken as 0 each.Periodic Boundary (PB)
xn is taken as the left neighbor of x1 and x1 as the right neighbor of xn.A CA may be represented as a string of the rules applied to the cells in proper order, along with a specification of the boundary conditions. For example,〈103,234,90,0〉NB refers to the CA (x1,x2,x3,x4), where x1t+1=f103(0,x1t,x2t), x2t+1=f234(x1t,x2t,x3t), x3t+1=f90(x2t,x3t,x4t), x4t+1=f0(x3t,x4t,0).If the “present state” of ann-bit CA (at time t) is Xt, its “next state” (at time t+1), denoted by Xt+1, is in general given by the global mappingF(Xt)=(f1(lbt,x1t,x2t),f2(x1t,x2t,x3t),…,fn(xn-1t,xnt,rbt)), where lb and rb denote, respectively, the left boundary of x1 and right boundary of xn.If the rule applied to each cell of a CA is a linear Boolean function, the CA will be called aLinear Cellular Automaton, otherwise a Nonlinear Cellular Automaton, for example, 〈0,60,60,204〉NB is a linear CA while 〈31,31,31,31〉NB and 〈60,90,87,123〉PB are nonlinear CAs.If the same Boolean function (rule) determines the “next” bit in each cell of a CA, the CA will be called aUniform Cellular Automaton (UCA), otherwise it will be called a Hybrid Cellular Automaton (HCA), for example, 〈135,135,135,135〉PB is a UCA, 〈0,60,72,72〉NB is a HCA.For a UCA, the Boolean function applied to each cell will be called therule of the CA. So for a UCA, we can obviously drop the superscript “i” from the local mapping fi and simply denote it as f. for example. for the 4-bit CA〈230,230,230,230〉PB, the rule of the CA is Rule  230 and the CA will be called the “Rule  230 CA” of 4 bits with periodic boundary conditions.  Henceforth, we will use the following notation UCAnNB, UCAnPB, HCAnNB, and HCAnPB for an n-bit CA. For our purpose, we will be mostly interested in elementary CA defined by Wolfram [2] to be one-dimensional binary CA with a symmetrical neighborhood of size p=3 for each cell so that xit+1=fi(xi-1t,xit,xi+1t),i=2,3,…,n-1.


## 3. Studies on the Hamming Distances between Boolean Functions and Their Classification

In our paper [5], we proposed and proved a few theorems (and their corollaries) on the H.D.s between Boolean functions of any number of variables  n. Next, we presented a chart of the H.D.s of all the 256 Boolean rules of three variables from the set of the 8 linear rules of three variables and, based on these observations, suggested a classification of three-variable Boolean functions. Here, we have a quick recapitulation.


### 3.1. Theorems on the H.D.s between Boolean Functions

Theorem 3.1.
If the H.D. of an n- variable Boolean function f  from another rule g  is m,  then the H.D. of the complement of f  from the same rule g  is(2n-m).Corollary 3.2.
For any nonlinear rule of n  variables, there exists at least one affine rule of n  variables such that the H.D. between the two is smaller than or equal to2n-1.


### 3.2. Classification of Boolean Rules of Three Variables Based on H.D.s from the Set of Linear Rules

In Table1, we provide an incomplete chart of the H.D.s of three-variable Boolean functions from the set of linear rules and hence enlist a few interesting observations thereof.Table 1
H.D.s of three-variable Boolean Functions from linear rules.
Rule no.H.D. from Rule nos.06090102150170204240004444444115555555215333355326444466413533535524644646624422446735533557813355335⋮⋮⋮⋮⋮⋮⋮⋮⋮2485335533124964466442250642442422517535535325262444422253735555332547333333325584444444Observations
(1)
H.D. between any two linear rules of 3 variables is4=23-1.(2)
For any nonlinear rule of 3 variables, there exists at least one linear rule of 3 variables such that the H.D. between the two is smaller than or equal to 4.(3)
If H.D. of a nonlinear rule of 3 variables from one of the 8 linear rules is even (odd), that from any other linear rule is also even (odd); for example, Rules  3 and 255 shown in Table1.(4)
If the H.D. of a nonlinear rule of 3 variables from a linear rule of 3 variables is m, say, then the H.D. of the complement of the said nonlinear rule from that linear rule is (8-m); for example, Rule  2 and Rule  253.(5)
If the H.D. of a nonlinear rule of 3 variables from a linear rule of 3 variables is 8, then its H.D. from every other linear rule is 4. There are 8 such nonlinear rules, each of which is, evidently, the complement of one of the 8 linear rules.(6)
In case the H.D. of a nonlinear rule of 3 variables from a linear rule is even and the said nonlinear rule is not the complement of a linear rule, we have either only one or exactly three linear rule(s) at an H.D. of 2 from the nonlinear rule under consideration. In that case, we have exactly three or only one linear rule(s), respectively, each at an H.D. of 6 from the nonlinear rule under consideration. The H.D. of the nonlinear rule in question from each of the remaining four linear rules is 4.A Boolean rule of 3 variables is said to belong to Classm if m is the minimum possible H.D. of the nonlinear rule from any linear rule of 3 variables, that is, there exists at least one linear rule such that the H.D. of the rule under consideration from this linear rule is m and, if  m′  is the H.D. of the said rule from any other linear rule, then m′ is larger than or equal to  m. The classification is presented in Table 2.Table 2
Classification of three-variable Boolean rules.
Name of the classRules in the classNumber of rules in the classClass 00,60,90,102,150,170,204,2408Class 11,2,4,8,16,22,26,28,32,38,42,44,52,56,61, 62,64,70,74,76,82,88,91,94,98,100,103, 110,112,118,122,124,128,134,138,140, 146,148,151,158,162,168,171,174,176, 182,186,188,196,200,205,206,208,214, 218,220,224,230,234,236,241,242,244,24864Class 23,5,6,9,10,12,17,18,20,23,24,27,29,30,33, 34,36,39,40,43,45,46,48,53,54,57,58,63, 65,66,68,71,72,75,77,78,80,83,86,89,92, 95,96,99,101,106,108,111,113,114,116, 119,120,123,125,126,129,130,132,135, 136,139,141,142,144,147,149,154,156, 159,160,163,166,169,172,175,177,178, 180,183,184,187,189,190,192,197,198, 201,202,207,209,210,212,215,216,219, 221,222,225,226,228,231,232,235,237, 238,243,245,246, 249,250,252112Class 37,11,13,14,19,21,25,31,35,37,41,47,49,50, 55,59,67,69,73,79,81,84,87,93,97,104,107, 109,115,117,121,127,131,133,137,143, 145,152,155,157,161,164,167,173,179, 181,185,191,193,194,199,203,211,213, 217,223,227,229,233,239,247,251,253,25464Class 415,51,85,105,153,165,195,2558Comments
(1)
The rules in Class 0 and Class 4 are the affine Boolean functions of 3 variables, Class 0 rules being linear rules and Class 4 rules being the logical complements of the linear rules. The degree of nonlinearity of each of these rules is 0.(2)
Each rule in Class 3 has its complement in Class 1 (in the order in which the rules are arranged in Table3, the ith rule in Class 3 is the complement of the (65-i)th rule in Class 1, (i=1,2,…,64); the degree of nonlinearity of each of the Class 1 and Class 3 rules is 1.(3)
In the order in which the rules are presented in Table3, the ith rule in Class 2 is the complement of the (113-i)th rule in Class 2, i=1,2,…,56; the degree of nonlinearity of each Class 2 rule is 2.Table 3
Classification of three-variable Boolean rules.
2726252423222120220001011015010010110


### 3.3. Subclassification of the Classes of Three-Variable Boolean Rules Based on Position of Bit- Mismatch with the Nearest Linear Rule

Each Class 1 rule has exactly one linear rule at an H.D. of 1 from itself; that linear rule will be called itsnearest linear rule. We express the Wolfram’s number of every Class 1 rule in its 8-bit binary form and compare it with the binary equivalent of the nearest linear rule. If mismatch occurs at bit position 2q, q=0,1,2,…,7, the rule is said to belong to Subclass q of Class 1, denoted by 1 : q; for example, nearest linear rule of Rule  22 is 150 as shown in Table 3.Therefore, Rule  22 belongs to Subclass 7 of Class 1. Thus, there are 8 subclasses of Class 1, as shown in Table4.Table 4
Subclassification of Class 1 Rules.
Subclass of Class 1Wolfram’s numbers of the rules included in the subclass1 : 722, 42, 76, 112, 128, 188, 218, 2301 : 626, 38, 64, 124, 140, 176, 214, 2341 : 528, 32, 70, 122, 138, 182, 208, 2361 : 416, 44, 74, 118, 134, 186, 220, 2241 : 38, 52, 82, 110, 158, 162, 196, 2481 : 24, 56, 94, 98, 146, 174, 200, 2441 : 12, 62, 88, 100, 148, 172, 206, 2421 : 01, 61, 91, 103, 151, 171, 205, 241We observed that each Class 3 rule has exactlythreenearest linear rules; so, it is not possible to subclassify them by the method adopted for Class 1 rules for there remains a confusion as to which of the three nearest linear rules to choose. But, since each rule in Class 3 has its complement in Class 1, the 64 rules in Class 3 can be subclassified into 8 subclasses of 8 rules each in the following manner.If the complement of a Class 3 rule belongs to Subclassq of Class 1, then that Class 3 rule is said to belong to Subclass q* of Class 3, denoted by 3 : q*. The details are presented in Table 5.Table 5
Subclassification of Class 3 Rules.
Subclass of Class 3Wolfram’s numbers of the rules included in the subclass3 : 7*233,213,179,143,127,67,37,253 : 6*229,217,191,131,115,79,41,213 : 5*227,223,185,133,117,73,47,193 : 4*239,211,181,137,121,69,35,313 : 3*247,203,173,145,97,93,59,73 : 2*251,199,161,157,109,81,55,113 : 1*253,193,167,155,107,83,49,133 : 0*254,194,164,152,104,84,50,14For Class 2 rules, we observe the following.(1)
Each of the 56 even-numbered rules in Class 2 is the complement of one of the 56 odd-numbered rules in Class 2.(2)
Every odd rule in Class 2 is at Hamming distance of 2 from exactly one linear rule (and at an H.D. 6 from exactly three linear rules); this single linear rule may be called thenearest linear ruleof the odd-numbered rule concerned; naturally, each even rule in Class 2 is at an H.D. of 2 from exactly three linear rules and at an H.D. of 6 from exactly one linear rule, and, hence, for an even Class 2 rule, the nearest linear rule is not unique, for example, rule  6 (Table 2).(3)
As a linear rule is necessarily even numbered, the binary representation of any odd rule in Class 2 will definitely differ from that of its nearest linear rule at the bit position 20 (i.e., at the LSB) which is always 1 for an odd rule and 0 for an even rule. The bit position of the second mismatch will naturally not be the same for all odd-numbered rules.Thus, the subclassification of the odd-numbered Class 2 rules could be based on the aforesaid bit-position of the second mismatch with the nearest linear rule and, the even-numbered Class 2 rules being the complements of these odd rules, their subclassification could be done in a manner similar to that in which the Class 3 rules have been sub-classified. For example. The nearest linear rule of Rule  3 is 0. Therefore, Rule  3 belongs to Subclass 1 of Class 2, denoted by 2 : 1 and complement of Rule 3=255-3=252. Thus, Rule  252 belongs to Subclass 1* of Class 2, denoted by 2 : 1* as shown in Table 6.Table 6
Subclassification of Class 2 Rules.
Subclass of Class 2Wolfram’s numbers of the rules included in the subclass2 : 723,43,77,113,129,189,219,2312 : 627,39,65,125,141,177,215,2352 : 529,33,71,123,139,183,209,2372 : 417,45,75,119,135,187,221,2252 : 39,53,83,111,159,163,197,2492 : 25,57,95,99,147,175,201,2452 : 13,63,89,101,149,169,207,2432 : 7*232,212,178,142,126,66,36,242 : 6*228,216,190,130,114,78,40,202 : 5*226,222,184,132,116,72,46,182 : 4*238,210,180,136,120,68,34,302 : 3*246,202,172,144,96,92,58,62 : 2*250,198,160,156,108,80,54,102 : 1*252,192,166,154,106,86,48,12


## 3.1. Theorems on the H.D.s between Boolean Functions

Theorem 3.1.
If the H.D. of an n- variable Boolean function f  from another rule g  is m,  then the H.D. of the complement of f  from the same rule g  is(2n-m).Corollary 3.2.
For any nonlinear rule of n  variables, there exists at least one affine rule of n  variables such that the H.D. between the two is smaller than or equal to2n-1.


## 3.2. Classification of Boolean Rules of Three Variables Based on H.D.s from the Set of Linear Rules

In Table1, we provide an incomplete chart of the H.D.s of three-variable Boolean functions from the set of linear rules and hence enlist a few interesting observations thereof.Table 1
H.D.s of three-variable Boolean Functions from linear rules.
Rule no.H.D. from Rule nos.06090102150170204240004444444115555555215333355326444466413533535524644646624422446735533557813355335⋮⋮⋮⋮⋮⋮⋮⋮⋮2485335533124964466442250642442422517535535325262444422253735555332547333333325584444444Observations
(1)
H.D. between any two linear rules of 3 variables is4=23-1.(2)
For any nonlinear rule of 3 variables, there exists at least one linear rule of 3 variables such that the H.D. between the two is smaller than or equal to 4.(3)
If H.D. of a nonlinear rule of 3 variables from one of the 8 linear rules is even (odd), that from any other linear rule is also even (odd); for example, Rules  3 and 255 shown in Table1.(4)
If the H.D. of a nonlinear rule of 3 variables from a linear rule of 3 variables is m, say, then the H.D. of the complement of the said nonlinear rule from that linear rule is (8-m); for example, Rule  2 and Rule  253.(5)
If the H.D. of a nonlinear rule of 3 variables from a linear rule of 3 variables is 8, then its H.D. from every other linear rule is 4. There are 8 such nonlinear rules, each of which is, evidently, the complement of one of the 8 linear rules.(6)
In case the H.D. of a nonlinear rule of 3 variables from a linear rule is even and the said nonlinear rule is not the complement of a linear rule, we have either only one or exactly three linear rule(s) at an H.D. of 2 from the nonlinear rule under consideration. In that case, we have exactly three or only one linear rule(s), respectively, each at an H.D. of 6 from the nonlinear rule under consideration. The H.D. of the nonlinear rule in question from each of the remaining four linear rules is 4.A Boolean rule of 3 variables is said to belong to Classm if m is the minimum possible H.D. of the nonlinear rule from any linear rule of 3 variables, that is, there exists at least one linear rule such that the H.D. of the rule under consideration from this linear rule is m and, if  m′  is the H.D. of the said rule from any other linear rule, then m′ is larger than or equal to  m. The classification is presented in Table 2.Table 2
Classification of three-variable Boolean rules.
Name of the classRules in the classNumber of rules in the classClass 00,60,90,102,150,170,204,2408Class 11,2,4,8,16,22,26,28,32,38,42,44,52,56,61, 62,64,70,74,76,82,88,91,94,98,100,103, 110,112,118,122,124,128,134,138,140, 146,148,151,158,162,168,171,174,176, 182,186,188,196,200,205,206,208,214, 218,220,224,230,234,236,241,242,244,24864Class 23,5,6,9,10,12,17,18,20,23,24,27,29,30,33, 34,36,39,40,43,45,46,48,53,54,57,58,63, 65,66,68,71,72,75,77,78,80,83,86,89,92, 95,96,99,101,106,108,111,113,114,116, 119,120,123,125,126,129,130,132,135, 136,139,141,142,144,147,149,154,156, 159,160,163,166,169,172,175,177,178, 180,183,184,187,189,190,192,197,198, 201,202,207,209,210,212,215,216,219, 221,222,225,226,228,231,232,235,237, 238,243,245,246, 249,250,252112Class 37,11,13,14,19,21,25,31,35,37,41,47,49,50, 55,59,67,69,73,79,81,84,87,93,97,104,107, 109,115,117,121,127,131,133,137,143, 145,152,155,157,161,164,167,173,179, 181,185,191,193,194,199,203,211,213, 217,223,227,229,233,239,247,251,253,25464Class 415,51,85,105,153,165,195,2558Comments
(1)
The rules in Class 0 and Class 4 are the affine Boolean functions of 3 variables, Class 0 rules being linear rules and Class 4 rules being the logical complements of the linear rules. The degree of nonlinearity of each of these rules is 0.(2)
Each rule in Class 3 has its complement in Class 1 (in the order in which the rules are arranged in Table3, the ith rule in Class 3 is the complement of the (65-i)th rule in Class 1, (i=1,2,…,64); the degree of nonlinearity of each of the Class 1 and Class 3 rules is 1.(3)
In the order in which the rules are presented in Table3, the ith rule in Class 2 is the complement of the (113-i)th rule in Class 2, i=1,2,…,56; the degree of nonlinearity of each Class 2 rule is 2.Table 3
Classification of three-variable Boolean rules.
2726252423222120220001011015010010110


## 3.3. Subclassification of the Classes of Three-Variable Boolean Rules Based on Position of Bit- Mismatch with the Nearest Linear Rule

Each Class 1 rule has exactly one linear rule at an H.D. of 1 from itself; that linear rule will be called itsnearest linear rule. We express the Wolfram’s number of every Class 1 rule in its 8-bit binary form and compare it with the binary equivalent of the nearest linear rule. If mismatch occurs at bit position 2q, q=0,1,2,…,7, the rule is said to belong to Subclass q of Class 1, denoted by 1 : q; for example, nearest linear rule of Rule  22 is 150 as shown in Table 3.Therefore, Rule  22 belongs to Subclass 7 of Class 1. Thus, there are 8 subclasses of Class 1, as shown in Table4.Table 4
Subclassification of Class 1 Rules.
Subclass of Class 1Wolfram’s numbers of the rules included in the subclass1 : 722, 42, 76, 112, 128, 188, 218, 2301 : 626, 38, 64, 124, 140, 176, 214, 2341 : 528, 32, 70, 122, 138, 182, 208, 2361 : 416, 44, 74, 118, 134, 186, 220, 2241 : 38, 52, 82, 110, 158, 162, 196, 2481 : 24, 56, 94, 98, 146, 174, 200, 2441 : 12, 62, 88, 100, 148, 172, 206, 2421 : 01, 61, 91, 103, 151, 171, 205, 241We observed that each Class 3 rule has exactlythreenearest linear rules; so, it is not possible to subclassify them by the method adopted for Class 1 rules for there remains a confusion as to which of the three nearest linear rules to choose. But, since each rule in Class 3 has its complement in Class 1, the 64 rules in Class 3 can be subclassified into 8 subclasses of 8 rules each in the following manner.If the complement of a Class 3 rule belongs to Subclassq of Class 1, then that Class 3 rule is said to belong to Subclass q* of Class 3, denoted by 3 : q*. The details are presented in Table 5.Table 5
Subclassification of Class 3 Rules.
Subclass of Class 3Wolfram’s numbers of the rules included in the subclass3 : 7*233,213,179,143,127,67,37,253 : 6*229,217,191,131,115,79,41,213 : 5*227,223,185,133,117,73,47,193 : 4*239,211,181,137,121,69,35,313 : 3*247,203,173,145,97,93,59,73 : 2*251,199,161,157,109,81,55,113 : 1*253,193,167,155,107,83,49,133 : 0*254,194,164,152,104,84,50,14For Class 2 rules, we observe the following.(1)
Each of the 56 even-numbered rules in Class 2 is the complement of one of the 56 odd-numbered rules in Class 2.(2)
Every odd rule in Class 2 is at Hamming distance of 2 from exactly one linear rule (and at an H.D. 6 from exactly three linear rules); this single linear rule may be called thenearest linear ruleof the odd-numbered rule concerned; naturally, each even rule in Class 2 is at an H.D. of 2 from exactly three linear rules and at an H.D. of 6 from exactly one linear rule, and, hence, for an even Class 2 rule, the nearest linear rule is not unique, for example, rule  6 (Table 2).(3)
As a linear rule is necessarily even numbered, the binary representation of any odd rule in Class 2 will definitely differ from that of its nearest linear rule at the bit position 20 (i.e., at the LSB) which is always 1 for an odd rule and 0 for an even rule. The bit position of the second mismatch will naturally not be the same for all odd-numbered rules.Thus, the subclassification of the odd-numbered Class 2 rules could be based on the aforesaid bit-position of the second mismatch with the nearest linear rule and, the even-numbered Class 2 rules being the complements of these odd rules, their subclassification could be done in a manner similar to that in which the Class 3 rules have been sub-classified. For example. The nearest linear rule of Rule  3 is 0. Therefore, Rule  3 belongs to Subclass 1 of Class 2, denoted by 2 : 1 and complement of Rule 3=255-3=252. Thus, Rule  252 belongs to Subclass 1* of Class 2, denoted by 2 : 1* as shown in Table 6.Table 6
Subclassification of Class 2 Rules.
Subclass of Class 2Wolfram’s numbers of the rules included in the subclass2 : 723,43,77,113,129,189,219,2312 : 627,39,65,125,141,177,215,2352 : 529,33,71,123,139,183,209,2372 : 417,45,75,119,135,187,221,2252 : 39,53,83,111,159,163,197,2492 : 25,57,95,99,147,175,201,2452 : 13,63,89,101,149,169,207,2432 : 7*232,212,178,142,126,66,36,242 : 6*228,216,190,130,114,78,40,202 : 5*226,222,184,132,116,72,46,182 : 4*238,210,180,136,120,68,34,302 : 3*246,202,172,144,96,92,58,62 : 2*250,198,160,156,108,80,54,102 : 1*252,192,166,154,106,86,48,12


## 4. Characterization of Nonlinear UCA STDs in Terms of Deviation from Linearity

### 4.1. The State Transition Diagram of a UCA

The evolution of a CA can be completely described by a diagram in which each state is connected to its successor by a properlydirected line  segment. This diagram is called the State Transition Diagram (abbreviated as STD) of the CA. In other words, the STD of a CA is essentially a directed graph where each node represents one of the states of the CA and the edges signify transitions from one state to another. The STD of the UCA Rule  170 NB is shown in Figure 1.Figure 1
S.T.D. of〈170,170,170,170〉NB.As already mentioned the structure of a linear CA STD is very well behaved and has been exhaustively studied. But, unfortunately, even for a moderate number of input variables, the linear rules constitute practically a microscopic fraction of the great multitude of Boolean functions. The nonlinear rules are, however, at various degrees of nonlinearity. So the idea that those nonlinear rules that arenot so distant from linear rulesmay be studied in terms of their similarity (or, equivalently, dissimilarity) with their closest linear rules appears quite appealing and viable, and we have tried to work on it.Before we proceed, we would like to draw attention to the biological analogy of the relationship between a rule table and the corresponding UCA STD that has been suggested in the literature [7]. Any Boolean rule (or, more correctly, the output column of a Boolean rule table) is comparable to a genotype of an organism so that a change (complementation) of one or more bits of the rule may be viewed as a genetic mutation in this context. Consequently, the change in the topology of the corresponding CA STD brought about by such a bit complementation is analogous to the change in morphology introduced by genetic mutation. As such, the new rule (offspring) obtained from another rule (parent) is called a mutant of the latter. Thus, in our classification, Class 1 rules may be regarded as one-bit mutants of linear rules, Class 2 rules as two-bit mutants of linear, rules and so on. Of these, the one-bit mutants are of utmost importance because, quite understandably, they can be expected to exhibit a greater similarity with linear rules than any other rule. This is found to be true in practice, as will be elaborated in the subsequent sections.


### 4.2. The Concept of Deviant States

If we compare the STD of a UCA with a Class 1 nonlinear rule (all subclasses) or an odd-numbered nonlinear rule from Class 2 with that of a same-sized UCA with its nearest linear rule, we observe that a considerable number of states have identical successors in both the STDs while the successors of other states differ in the two STDs. For a given size (n) of CA, we define a state of a nonlinear UCA, to which a Class 1 rule or an odd Class 2 rule has been applied, as a deviant state for that nonlinear rule if the successor of the state under consideration in the S.T.D. of the nonlinear UCA taken is different from its successor in the STD of the nearest linear rule UCA (of the same size). For example, Rule  128 belongs to Class 1 : 7 and its nearest linear rule is 240. Comparison of their STDs for a UCA4NBreveals that only the states 7, 14, 15have different successors in the two STDs, so for Rule  128 UCA4NB, the deviant states are 7, 14, 15.It is evident from this discussion that the deviant states have been defined with respect to thenearest linear ruleonly (and not just any linear rule) because we can expect maximum similarity of the STD of a nonlinear rule with the STD of its nearest linear rule. For this same reason, deviant states have been defined for the above subclasses only; for other subclasses, the nearest linear rule is not uniquely defined.


### 4.3. An Algorithm for Deducing the Set of Deviant States

For a Class 1 rule, the deviant states for a given size of CA can be easily determined and, hence, the STD of such a nonlinear rule, sayf, can be easily deduced from that of its nearest linear rulefL by  Algorithm 1.Algorithm 1:
(1) Locate the position of bit-mismatch in the Truth Table output column betweenf and fL(which is identical to the subclass number off).(2) Write down the 3-bit input combination, saya*b*c* corresponding to that row of the TruthTable where the said mismatch occurs (which is nothing but the 3-bit binary  representation ofthe subclass number off);  evidently, it is only for this  input sequence a*b*c* that f and fL givedifferent (i.e., complementary)  outputs, their output for every other 3-bit input combination beingidentical. Consequently,  a state of a three-neighborhood UCA of any lengthn will give differentsuccessors when acted upon byf and fL if and only if the state contains the sequence a*b*c*.(3) Search the space of all 2n possible states of the UCA for states each of which contains  thesequence (neighborhood)a*b*c* at least once. However,  while looking for the neighborhood,a*b*c*we must properly take into account the boundary values for the two terminal bits of the CA.(4) In each deviant state, mark the position of that bit which, along with its immediate left  andright neighbours, forms the sequencea*b*c*. As the same sequence may occur more than  oncein state, we may get more than one such bit-positions in a state.  Let these marked positions beþ1, þ2 and so forth.(5) In the STD of the nearest linear rule, locate the successors of thedeviant states; in the binaryrepresentation of each such successor state, mark the bit-positionsþ1, þ2 and so forth. (whichwere marked in the binary representation of each deviant state in step (4)) and toggle  the bitsat these positions; the resulting bit string will give us the successor of the deviant  state in theSTD of the nonlinear rule in question.  Accordingly, make necessary changes in the diagram.(6) Leave the successors of the nondeviant states unchanged.Illustration
Let us take Rule  22 UCA4NB. Rule  22 belongs to Class 1 : 7 with Rule  150 as its nearest linear rule. The deduction of the deviant states and their successors and, hence, the derivation of the STD of〈22,22,22,22〉NB from that of 〈150,150,150,150〉NB are shown with the help of Tables 7 and 8 and Figures 2 and 3.Table 7
Comparison of Truth Tables of Rules  150 and 22.
RowabcRule  150Rule  22000000100111201011301100410011510100611000711110Table 8
Determination of deviant states and their successors for Rule  22 UCA4NB.
Deviant statesSuccessor in Rule  150 UCA4NBSuccessor in Rule  22 UCA4NBBinaryDecimalDecimalBinaryDecimalBinary0 11 17101 01 01 00 0811 1 014501 0 100 0 11111 1156011 0000 00Figure 2
STD of〈150,150,150,150〉NB.Figure 3
STD of〈22,22,22,22〉NB.


### 4.4. Comments on Deviant States

(1)
Since the sequence to be searched may occur more than once in the same state and, in case of multiple occurrences, the repeating sequences may or may not overlap, it is clear that the task of identifying the deviant states and deducing their successors by the bit-toggling method becomes increasingly difficult with increasing length of CA.(2)
Determination of the deviant states for odd Class 2 rules can be similarly accomplished by first locating the two positions of bit-mismatch and then searching forat least one of the two corresponding 3-bit combinations in the CA state. We could also proceed in two steps by considering one mismatch at a time. Obviously, the task is more difficult than that for the Class 1 case.(3)
The set of deviant states for a givenf depends strongly on the number of bits in the CA as well as on the boundary conditions (null/periodic); for example, for 〈22,22,22,22〉NB, the set of deviant states is {7,14,15} whereas that for 〈22,22,22,22〉PB is {7,11,13,14,15}.(4)
For given CA length and boundary conditions, all the rules in a subclass have identicaldeviant states because bit-mismatch with the respective nearest linear rules occurs at the same bit-position but the set of deviant states, in general, varies from one subclass to another.(5)
For the periodic boundary case, the bits in any state may be supposed to be arranged in a ring or circle so that it is somewhat less difficult to identify the deviant states because such states will occur inrotationally equivalent sets [7]; for example, for 〈22,22,22,22〉PB, (7)10≡(011̲1)2 is clearly a deviant state and  (14)10≡(11̲10)2, (13)10≡(1̲101)2, (11)10≡(1011̲)2 are rotationally equivalent to 7, so we can immediately declare them deviant states. It is also interesting to note that it is sufficient to deduce the successor of any one state from this set by the bit-toggling method because their successors are also rotationally equivalent and hence occupy equivalent positions in the STD.


### 4.5. The Significance of the Proportion of Deviant States in an STD

Let us define a quantityPds, called the proportion of deviant states for an n-bit nonlinear UCA, as Pds=Nds/2n, where Nds = number of deviant states of the UCA considered and  2n  is the total number of states of the UCA.The rationale underlying the introduction of the concept of deviant states is that the behavior of the deviant states embodies the effect of the bit-mismatch (es) between f andfL  (or, in other words, the nature and extent of nonlinearity of f) on the topology of the STD of the UCA of f—if, for the type of nonlinear UCA considered (Class 1 and Class 2 odd), we start from a seed which is a nondeviant state, the system evolution follows the path of the nearest linear rule until and unless a deviant state is encountered; when a deviant state is actually reached, the evolution deviates from the linear path, reaches some state, and henceforward resumes the linear path till the next deviant state is reached. As such, the proportion of deviant statesin a CA may provide us with some measure of the deviation from linearity of a nonlinear rule (with respect to CA state transitions). This discussion reveals that it is not just the number of bit-mismatches (i.e., degree of nonlinearity) but also the actual positions of bit-mismatch, which determine how much a nonlinear UCA STD differs both qualitatively and quantitatively from the closest linear STD. With this in mind, we investigated the dependence of Pds on the length of the CA for all Class 1 subclasses for the periodic boundary (PB) case, and the results are presented in Table 9 and Figure 4.Table 9
Table showing the variation in the number of deviant states for a 1 : 7 rule with CA length.
No. of cells in the CA(n)No. of states (2n)No. of deviant states416553211664257128578256125951227110102458111204812331240962597138192543514163841131315327682344116655364838117131072995191826214420410919524288417545201048576852245212097152173604322419430435301212383886087166985241677721614530301253355443229421711266710886459507605Figure 4
Plot of proportion of deviant states versus length of CA (periodic bound) for various subclasses of Class 1.Comments on Figure4
(1)
For any given length of CA (PB),Pds(1:7)=Pds(1:0) as the neighborhoods 111 and 000exhibit complementary symmetry[7], Pds(1:5)=Pds(1:2) as the neighborhoods 101 and 010 also exhibit complementary symmetry, Pds(1:6)=Pds(1:3)=Pds(1:4)=Pds(1:1) as the neighborhoods 110 and 011exhibit reflection symmetry [7], 011 and 100show complementary   symmetry,and 100 and 001 show reflection symmetryagain.(2)
As the length of CA (PB) increases, the proportion of deviant states, sayPds, tends towards unity for any subclass of Class 1, which means that the effect of nonlinearity becomes more pronounced but following inequality is always maintained: Pds(1:7,1:0)<Pds(1:5,1:2)<Pds(1:6,1:3,1:4,1:1) with the difference between the last two becoming significantly smaller than that between the first two.


## 4.1. The State Transition Diagram of a UCA

The evolution of a CA can be completely described by a diagram in which each state is connected to its successor by a properlydirected line  segment. This diagram is called the State Transition Diagram (abbreviated as STD) of the CA. In other words, the STD of a CA is essentially a directed graph where each node represents one of the states of the CA and the edges signify transitions from one state to another. The STD of the UCA Rule  170 NB is shown in Figure 1.Figure 1
S.T.D. of〈170,170,170,170〉NB.As already mentioned the structure of a linear CA STD is very well behaved and has been exhaustively studied. But, unfortunately, even for a moderate number of input variables, the linear rules constitute practically a microscopic fraction of the great multitude of Boolean functions. The nonlinear rules are, however, at various degrees of nonlinearity. So the idea that those nonlinear rules that arenot so distant from linear rulesmay be studied in terms of their similarity (or, equivalently, dissimilarity) with their closest linear rules appears quite appealing and viable, and we have tried to work on it.Before we proceed, we would like to draw attention to the biological analogy of the relationship between a rule table and the corresponding UCA STD that has been suggested in the literature [7]. Any Boolean rule (or, more correctly, the output column of a Boolean rule table) is comparable to a genotype of an organism so that a change (complementation) of one or more bits of the rule may be viewed as a genetic mutation in this context. Consequently, the change in the topology of the corresponding CA STD brought about by such a bit complementation is analogous to the change in morphology introduced by genetic mutation. As such, the new rule (offspring) obtained from another rule (parent) is called a mutant of the latter. Thus, in our classification, Class 1 rules may be regarded as one-bit mutants of linear rules, Class 2 rules as two-bit mutants of linear, rules and so on. Of these, the one-bit mutants are of utmost importance because, quite understandably, they can be expected to exhibit a greater similarity with linear rules than any other rule. This is found to be true in practice, as will be elaborated in the subsequent sections.


## 4.2. The Concept of Deviant States

If we compare the STD of a UCA with a Class 1 nonlinear rule (all subclasses) or an odd-numbered nonlinear rule from Class 2 with that of a same-sized UCA with its nearest linear rule, we observe that a considerable number of states have identical successors in both the STDs while the successors of other states differ in the two STDs. For a given size (n) of CA, we define a state of a nonlinear UCA, to which a Class 1 rule or an odd Class 2 rule has been applied, as a deviant state for that nonlinear rule if the successor of the state under consideration in the S.T.D. of the nonlinear UCA taken is different from its successor in the STD of the nearest linear rule UCA (of the same size). For example, Rule  128 belongs to Class 1 : 7 and its nearest linear rule is 240. Comparison of their STDs for a UCA4NBreveals that only the states 7, 14, 15have different successors in the two STDs, so for Rule  128 UCA4NB, the deviant states are 7, 14, 15.It is evident from this discussion that the deviant states have been defined with respect to thenearest linear ruleonly (and not just any linear rule) because we can expect maximum similarity of the STD of a nonlinear rule with the STD of its nearest linear rule. For this same reason, deviant states have been defined for the above subclasses only; for other subclasses, the nearest linear rule is not uniquely defined.


## 4.3. An Algorithm for Deducing the Set of Deviant States

For a Class 1 rule, the deviant states for a given size of CA can be easily determined and, hence, the STD of such a nonlinear rule, sayf, can be easily deduced from that of its nearest linear rulefL by  Algorithm 1.Algorithm 1:
(1) Locate the position of bit-mismatch in the Truth Table output column betweenf and fL(which is identical to the subclass number off).(2) Write down the 3-bit input combination, saya*b*c* corresponding to that row of the TruthTable where the said mismatch occurs (which is nothing but the 3-bit binary  representation ofthe subclass number off);  evidently, it is only for this  input sequence a*b*c* that f and fL givedifferent (i.e., complementary)  outputs, their output for every other 3-bit input combination beingidentical. Consequently,  a state of a three-neighborhood UCA of any lengthn will give differentsuccessors when acted upon byf and fL if and only if the state contains the sequence a*b*c*.(3) Search the space of all 2n possible states of the UCA for states each of which contains  thesequence (neighborhood)a*b*c* at least once. However,  while looking for the neighborhood,a*b*c*we must properly take into account the boundary values for the two terminal bits of the CA.(4) In each deviant state, mark the position of that bit which, along with its immediate left  andright neighbours, forms the sequencea*b*c*. As the same sequence may occur more than  oncein state, we may get more than one such bit-positions in a state.  Let these marked positions beþ1, þ2 and so forth.(5) In the STD of the nearest linear rule, locate the successors of thedeviant states; in the binaryrepresentation of each such successor state, mark the bit-positionsþ1, þ2 and so forth. (whichwere marked in the binary representation of each deviant state in step (4)) and toggle  the bitsat these positions; the resulting bit string will give us the successor of the deviant  state in theSTD of the nonlinear rule in question.  Accordingly, make necessary changes in the diagram.(6) Leave the successors of the nondeviant states unchanged.Illustration
Let us take Rule  22 UCA4NB. Rule  22 belongs to Class 1 : 7 with Rule  150 as its nearest linear rule. The deduction of the deviant states and their successors and, hence, the derivation of the STD of〈22,22,22,22〉NB from that of 〈150,150,150,150〉NB are shown with the help of Tables 7 and 8 and Figures 2 and 3.Table 7
Comparison of Truth Tables of Rules  150 and 22.
RowabcRule  150Rule  22000000100111201011301100410011510100611000711110Table 8
Determination of deviant states and their successors for Rule  22 UCA4NB.
Deviant statesSuccessor in Rule  150 UCA4NBSuccessor in Rule  22 UCA4NBBinaryDecimalDecimalBinaryDecimalBinary0 11 17101 01 01 00 0811 1 014501 0 100 0 11111 1156011 0000 00Figure 2
STD of〈150,150,150,150〉NB.Figure 3
STD of〈22,22,22,22〉NB.


## 4.4. Comments on Deviant States

(1)
Since the sequence to be searched may occur more than once in the same state and, in case of multiple occurrences, the repeating sequences may or may not overlap, it is clear that the task of identifying the deviant states and deducing their successors by the bit-toggling method becomes increasingly difficult with increasing length of CA.(2)
Determination of the deviant states for odd Class 2 rules can be similarly accomplished by first locating the two positions of bit-mismatch and then searching forat least one of the two corresponding 3-bit combinations in the CA state. We could also proceed in two steps by considering one mismatch at a time. Obviously, the task is more difficult than that for the Class 1 case.(3)
The set of deviant states for a givenf depends strongly on the number of bits in the CA as well as on the boundary conditions (null/periodic); for example, for 〈22,22,22,22〉NB, the set of deviant states is {7,14,15} whereas that for 〈22,22,22,22〉PB is {7,11,13,14,15}.(4)
For given CA length and boundary conditions, all the rules in a subclass have identicaldeviant states because bit-mismatch with the respective nearest linear rules occurs at the same bit-position but the set of deviant states, in general, varies from one subclass to another.(5)
For the periodic boundary case, the bits in any state may be supposed to be arranged in a ring or circle so that it is somewhat less difficult to identify the deviant states because such states will occur inrotationally equivalent sets [7]; for example, for 〈22,22,22,22〉PB, (7)10≡(011̲1)2 is clearly a deviant state and  (14)10≡(11̲10)2, (13)10≡(1̲101)2, (11)10≡(1011̲)2 are rotationally equivalent to 7, so we can immediately declare them deviant states. It is also interesting to note that it is sufficient to deduce the successor of any one state from this set by the bit-toggling method because their successors are also rotationally equivalent and hence occupy equivalent positions in the STD.


## 4.5. The Significance of the Proportion of Deviant States in an STD

Let us define a quantityPds, called the proportion of deviant states for an n-bit nonlinear UCA, as Pds=Nds/2n, where Nds = number of deviant states of the UCA considered and  2n  is the total number of states of the UCA.The rationale underlying the introduction of the concept of deviant states is that the behavior of the deviant states embodies the effect of the bit-mismatch (es) between f andfL  (or, in other words, the nature and extent of nonlinearity of f) on the topology of the STD of the UCA of f—if, for the type of nonlinear UCA considered (Class 1 and Class 2 odd), we start from a seed which is a nondeviant state, the system evolution follows the path of the nearest linear rule until and unless a deviant state is encountered; when a deviant state is actually reached, the evolution deviates from the linear path, reaches some state, and henceforward resumes the linear path till the next deviant state is reached. As such, the proportion of deviant statesin a CA may provide us with some measure of the deviation from linearity of a nonlinear rule (with respect to CA state transitions). This discussion reveals that it is not just the number of bit-mismatches (i.e., degree of nonlinearity) but also the actual positions of bit-mismatch, which determine how much a nonlinear UCA STD differs both qualitatively and quantitatively from the closest linear STD. With this in mind, we investigated the dependence of Pds on the length of the CA for all Class 1 subclasses for the periodic boundary (PB) case, and the results are presented in Table 9 and Figure 4.Table 9
Table showing the variation in the number of deviant states for a 1 : 7 rule with CA length.
No. of cells in the CA(n)No. of states (2n)No. of deviant states416553211664257128578256125951227110102458111204812331240962597138192543514163841131315327682344116655364838117131072995191826214420410919524288417545201048576852245212097152173604322419430435301212383886087166985241677721614530301253355443229421711266710886459507605Figure 4
Plot of proportion of deviant states versus length of CA (periodic bound) for various subclasses of Class 1.Comments on Figure4
(1)
For any given length of CA (PB),Pds(1:7)=Pds(1:0) as the neighborhoods 111 and 000exhibit complementary symmetry[7], Pds(1:5)=Pds(1:2) as the neighborhoods 101 and 010 also exhibit complementary symmetry, Pds(1:6)=Pds(1:3)=Pds(1:4)=Pds(1:1) as the neighborhoods 110 and 011exhibit reflection symmetry [7], 011 and 100show complementary   symmetry,and 100 and 001 show reflection symmetryagain.(2)
As the length of CA (PB) increases, the proportion of deviant states, sayPds, tends towards unity for any subclass of Class 1, which means that the effect of nonlinearity becomes more pronounced but following inequality is always maintained: Pds(1:7,1:0)<Pds(1:5,1:2)<Pds(1:6,1:3,1:4,1:1) with the difference between the last two becoming significantly smaller than that between the first two.


## 5. Conclusion and Future Research Directions

In this paper, we have identified a group of elementary nonlinear uniform cellular automata (Class 1 and Class 2 odd), which can be studied in terms of deviation from linearity with relative ease, and have suggested a new way of looking at their STDs by introducing the concept of deviant states. Of the remaining Boolean rules, Class 3 is the complement of Class 1 whereas even Class 2 rules are complements of odd Class 2 rules. Hence the last two sets of Boolean rules (Class 3 and Class 2 even) may be expected to bear the same relationship with nonlinear affine rules (Class 4) as do the aforesaid two sets (Class 1 and Class 2 odd) with the linear rules. As such, it would apparently be wiser to classify Boolean functions on the basis of distance from the set of affine rules (i.e., degree of nonlinearity) rather than the set of linear rules and, in that case, the entire set of affine rules (linear rules and their complements) must be taken as the standard. We are exploring this possibility. Although the idea is still in an incipient state, it appears quite promising.Another of our current efforts is aimed at deducing a possible formula for the number of deviant states in terms of the lengthn of the CA for a given nonlinear rule and given boundary conditions.Moreover, we have considered only 3-neighborhood 1D UCA. We are investigating how far this idea could be carried forward to the cases with larger neighborhoods. From the study presented in this paper, it appears that even if the neighborhood size (number of independent variables) increases, we can still possibly isolate a set ofmutants of linear rules, which can be characterized in terms of deviant states. It is germane to mention here that, as already pointed out in [7], one-bit mutation amounts to (1/23× 100)% = 12.5% change for a 3-variable function, to (1/25× 100)% = 3.125% for a 5-variable function, and so on. In other words, the effect of mutation of a CA rule on a CA evolution (and thus the deviation of the CA STD from linearity) decreases as the size of the neighborhood increases. So, for a given length of CA and a given nonlinear rule, the proportion of deviant states must decrease with increasing size of neighborhood.



---

*Source: 605098-2011-05-05.xml*