Chua 1997
Chua 1997
10 (1997) 2219–2425
Visions of Nonlinear Science: Festschrift dedicated to Leon O. Chua
c World Scientific Publishing Company
LEON O. CHUA
Department of Electrical Engineering and Computer Sciences,
University of California at Berkeley, Berkeley, CA 94720, USA
CNN is an acronym for either Cellular Neural Network when used in the context of brain
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
science, or Cellular Nonlinear Network when used in the context of coupled dynamical systems.
A CNN is defined by two mathematical constructs:
1. A spatially discrete collection of continuous nonlinear dynamical systems called cells, where
information can be encrypted into each cell via three independent variables called input,
threshold, and initial state.
2. A coupling law relating one or more relevant variables of each cell Cij to all neighbor cells
Ckl located within a prescribed sphere of influence Sij (r) of radius r , centered at Cij .
In the special case where the CNN consists of a homogeneous array, and where its cells
have no inputs, no thresholds, and no outputs, and where the sphere of influence extends only
to the nearest neighbors (i.e. r = 1), the CNN reduces to the familiar concept of a nonlinear
lattice.
The bulk of this three-part exposition is devoted to the standard CNN equation
X X
ẋij = −xij + akl ykl + bkl ukl + zij
kl∈Sij (r) kl∈Sij (r)
1
yij = f (xij ) = (|xij + 1| − |xij − 1|)
2
i = 1, 2, . . . , M, j = 1, 2, . . . , N
where xij , yij , uij and zij are scalars called state, output, input, and threshold of cell Cij ; akl
and bkl are scalars called synaptic weights, and Sij (r) is the sphere of influence of radius r .
In the special case where r = 1, a standard CNN is uniquely defined by a string of “19” real
numbers (a uniform threshold zkl = z , nine feedback synaptic weights akl , and nine control
synaptic weights bkl ) called a CNN gene because it completely determines the properties of
the CNN. The universe of all CNN genes is called the CNN genome. Many applications from
image processing, pattern recognition, and brain science can be easily implemented by a CNN
“program” defined by a string of CNN genes called a CNN chromosome.
The first new result presented in this exposition asserts that every Boolean function of
the neighboring-cell inputs can be explicitly synthesized by a CNN chromosome. This general
theorem implies that every cellular automata (with binary states) is a CNN chromosome.
In particular, a constructive proof is given which shows that the game-of-life cellular au-
tomata can be realized by a CNN chromosome made of only three CNN genes. Consequently,
this “game-of-life” CNN chromosome is a universal Turing machine, and is capable of self-
replication in the Von Neumann sense [Berlekamp et al., 1982].
One of the new concepts presented in this exposition is that of a generalized cellular au-
tomata (GCA), which is outside the framework of classic cellular (Von Neumann) automata
2219
2220 L. O. Chua
because it cannot be defined by local rules: It is simply defined by iterating a CNN gene, or
chromosome, in a “CNN DO LOOP”. This new class of generalized cellular automata includes
not only global Boolean maps, but also continuum-state cellular automata where the initial
state configuration and its iterates are real numbers, not just a finite number of states as in
classical (von Neumann) cellular automata.
Another new result reported in this exposition is the successful implementation of an
analog input analog output CNN universal machine, called a CNN universal chip, on a single
silicon chip. This chip is a complete dynamic array stored-program computer where a CNN
chromosome (i.e. a CNN algorithm or flow chart) can be programmed and executed on the
chip at an extremely high speed of 1 Tera (1012 ) analog instructions per second (based on a
100 × 100 chip). The CNN universal chip is based entirely on nonlinear dynamics and therefore
differs from a digital computer in its fundamental operating principles.
Part II of this exposition is devoted to the important subclass of autonomous CNNs where
the cells have no inputs. This class of CNNs can exhibit a great variety of complex phenomena,
including pattern formation, Turing patterns, knots, auto waves, spiral waves, scroll waves, and
spatiotemporal chaos. It provides a unified paradigm for complexity, as well as an alternative
paradigm for simulating nonlinear partial differential equations (PDE’s). In this context, rather
than regarding the autonomous CNN as an approximation of nonlinear PDE’s, we advocate
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
the more provocative point of view that nonlinear PDE’s are merely idealizations of CNNs,
because while nonlinear PDE’s can be regarded as a limiting form of autonomous CNNs, only
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
1
For more details, see the following special issues and proceedings of workshops devoted exclusively to CNN:
• Special issue on cellular neural networks, International Journal of Circuit Theory and Applications, Vol. 20, Sept./Oct.
1992.
• Special issue on cellular neural networks, IEEE Transactions on Circuits and Systems I and II, Vol. 40, Mar. 1993 (in two
separate issues).
• Proceedings of the IEEE International Workshop on cellular neural networks and their applications, Budapest, Hungary,
Dec. 1990. IEEE Catalog Number No. 90TH0312-9 and ISBN 951-721-239-9.
• Proceedings of the IEEE International Workshop on cellular neural networks and their applications, Munich, Germany,
Oct. 1992. IEEE Catalog Number No. 92TH0498-6 and ISBN 0-7803-875-1.
• Proceedings of the IEEE International Workshop on cellular neural networks and their applications, Rome, Italy, Dec. 1994.
IEEE Catalog Number No. 94TH0693-2 and ISBN 0-7803-2070-0.
• Proceedings of the IEEE International Workshop on cellular neural networks and their applications, Seville, Spain, Jun.
1996. IEEE Catalog Number No. 96TH8180 and ISBN 0-7803-3261.
2
See also the special issue on “Nonlinear waves, patterns, and spatio-temporal chaos,” IEEE Transactions on Circuits and
Systems I and II, Vol. 42, Oct. 1995 (in 2 separate issues).
2222 L. O. Chua
patterns, auto-waves, spiral waves, scroll waves variables are functions of the continuous 4 time t.
and spatio-temporal chaos [Chua et al., 1996] with Given any initial state xij (t0 ) at t = t0 , any thresh-
diverse applications in image and video signal old zij (t), and any input uij (t), the state xij (t) of
processing [Roska & Vandewalle, 1994]. Since these each isolated cell Cij is assumed to evolve for all
latter applications are broader and not necessar- t ≥ t0 via a state equation
ily related to neural networks, it may be more ap-
propriate to decode CNN as Cellular Nonlinear ẋij = fij [xij , zij , uij ]
Networks in such applications. i = 1, 2, . . . , M ; j = 1, 2, . . . , N (1)
Definition. CNN.
where the “dot” denotes the time derivative and
A CNN is any spatial arrangement of locally-
fij [·] denotes a mathematical operator acting on
coupled cells, where each cell is a dynamical system
xij (t), zij (t) and uij (t). For example, Eq. (1) may
which has an input, an output, and a state evolving
be a nonlinear differential equation with a time de-
according to some prescribed dynamical laws [Chua
lay T , as in
& Roska, 1997].
Although neither the “cells”, nor the “cou- ẋij = fij [xij , zij , uij ]
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
pling laws”, are required to be spatially invariant = fij (xij (t − T ), zij (t), uij (t)) (2)
in the above definition, for the sake of concrete-
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
ness we will assume a translation-invariant (homo- It can also be a nonlinear integral of any complex-
geneous) three-dimensional lattice CNN architec- ity, e.g. Volterra and Wiener operators [Boyd et al.,
ture throughout this paper, as shown in Fig. 1, 1982; Boyd & Chua, 1985].
whose cutout view in Fig. 2 shows a typical cell Cijk In this paper we will assume for simplicity that
along with all neighboring cells Cαβγ lying inside a all cells are identical and fij [·] is an ordinary func-
sphere of influence Sijk . tion so that we can delete the subscripts and write
Mathematically, each cell Cijk at location Eq. (1) simply as a non-autonomous system of or-
(i, j, k) in the above lattice is a dynamical sys- dinary differential equations
tem whose states evolve according to some pre-
scribed state equations, or in the most abstract ẋij (t) = f (xij (t), zij (t), uij (t)) (3)
setting, as a semi-group, whose dynamics are cou-
pled only among the neighboring cells lying within In general, the output yij (t) may be any func-
some prescribed sphere of influence Sijk , centered tion of xij (t), zij (t) and yij (t), and possibly their
at (i, j, k). time derivatives of any order. In this paper, we will
assume that yij (t) depends only on xij (t); namely
A. Isolated Cell
yij (t) = gij (xij (t)) (4)
Except for some examples in Part II, we will con-
sider mostly the two-dimensional case and use a In fact, in many cases (see Part II), the output
double subscript system to present all results. The of interest often coincides with the state, yij (t) =
symbol and relevant variables for an isolated 3 cell xij (t), so that gij (·) is simply the identity function.
for a two-dimensional CNN are shown in Fig. 3(a). In this paper, an isolated CNN cell with a time-
Observe that in general four variables are associated varying input is defined by the non-autonomous
with each isolated cell: state equation (3) and the output equation (4), as
shown in Fig. 3(b).
1. input uij ∈ Ru
2. threshold zij ∈ Rz
Example. Standard Isolated CNN Cell.
3. state xij ∈ Rx
The standard isolated CNN cell [Chua & Yang,
4. output yij ∈ Ry
1988] used most widely in the literature, and which
In this paper, we will usually assume for sim- has been implemented in virtually all existing CNN
plicity that zij is a constant scalar, and all other silicon chips, is defined as follows:
3
A CNN cell is said to be isolated if it is not coupled to any other cell.
4
Although our “semi-group” definition of CNN includes discrete-time CNNs as a special case, only continuous-time CNNs are
considered in this paper.
CNN: A Vision of Complexity 2223
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 1. A three-dimensional CNN showing cells located at the lattice sites. The couplings between cells are not shown.
Fig. 2. A cutout view which exposes an inner cell Cijk and its sphere of influence Sijk .
2224 L. O. Chua
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 3. Symbol of an isolated CNN cell and its associated state and output equations.
State equation of standard isolated cell:5 Output equation of standard isolated cell:
5
We have abused our notation by using f (·) to denote both the “state equation” in Eq. (3), and the “output equation” in
Eq. (6). The content will make it clear which one it is intended for.
CNN: A Vision of Complexity 2225
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
(a)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 4. A CNN cell Cij with a 3 × 3 sphere of influence (a), and a 5 × 5 sphere of influence (b).
We will usually delete r from Sij (r) and simply shown in Fig. 4(b). Unless otherwise stated, we
write Sij to avoid clutter. will assume a 3 × 3 sphere of influence throughout
For the rectangular array, shown in Fig. 4(a), this paper.
Sij has a radius r = 1, and will usually be called a
neighborhood of radius 1, or a 3 × 3 sphere of influ- C. Local couplings
ence. In this case, Cij is coupled only to its eight
nearest neighbor cells Ckl as shown in Fig. 4(a), In the most general case, both the input ukl and
where (k, l) = (i + 1, j + 1), (i + 1, j), (i + 1, j − 1), the output ykl of all neighbor cells belonging to
(i, j + 1), (i, j − 1), (i − 1, j + 1), (i − 1, j), and Sij are coupled to cell Cij , as depicted schemat-
(i − 1, j − 1). ically in Figs. 5(a) and 5(b), respectively, where
A 5 × 5 sphere (corresponding to r = 2) of in- it is sometimes convenient to interpret each cell
fluence would enlarge the coupling to 24 cells, as in this figure as a neuron whose state dynamics
2226 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a) (b)
Fig. 5. The center cell Cij receives a weighted control (feedforward) signal bkl ukl in (a), and a weighted feedback signal akl ykl
in (b), from each neighbor cell Ckl .
1988] for an M × N CNN array with M rows and times be chosen to coincide with the gray-scale in-
N columns: tensity (normalized between “−1” for pure white
and “1” for pure black) of the corresponding dis-
State equations of standard CNN: cretized picture element — called a pixel — of the
X input image.
ẋij = −xij + zij + akl ykl
kl∈Sij
E. General CNN equations
X
+ bkl ukl (10) Together, Eqs. (10) and (11) will henceforth be re-
kl∈Sij ferred to as the standard CNN equation. There are
many applications, however, including many CNNs
Output equation of standard CNN: to be presented in Part II of this paper, where dif-
ferent cell dynamics and coupling laws are called
yij = f (xij ) (11) for. In all cases,
i = 1, 2, . . . , M , j = 1, 2, . . . , N, where f (·) is
An M × N CNN is defined by specifying:
usually defined by Eq. (6).
1. State equations of isolated cells
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
dynamics)
aij f (xij ) = aij yij and bij uij from Eq. (5) into the
summation signs in Eq. (10) so that unlike Eqs. (8) 2. Cell coupling laws
and (9), the indices kl under the summation signs (or CNN synaptic law when used in the
in Eq. (10) now include kl = ij. Consequently each context of neural networks)
summation term in Eq. (10) contains nine terms for 3. Boundary conditions
a 3 × 3 sphere of influence, and 25 terms for a 5 × 5 4. Initial conditions
sphere of influence, etc. For an M × N CNN ar-
ray, the indices i and j would each run from 1 to The complete system of M N nonlinear differen-
M and N , respectively, so that Eq. (10) consists tial equations for an M ×N CNN array obtained by
of a system of M N nonlinear ordinary differential combining the CNN “cell dynamics” and the “CNN
equations. coupling laws” assumes the following general form:
Observe that Eq. (10) is not completely defined
for cells whose sphere of influence Sij extends out- CNN state equation:
side of the boundary of the array. Consequently,
additional boundary conditions must be specified in ẋij = f (xij , zij ; ukl , ykl ) , kl ∈ Sij (r) (12)
order for Eq. (10) to be well defined. The three
most commonly chosen boundary conditions are: where ukl , ykl denote vectors whose components
(1) Fixed (Dirichlet) boundary condition ukl and ykl include all neighbor cells Ckl ∈ Sij (r).
Here, the state xkl of each cell Ckl in Eq. (10) which CNN output equation:
lies outside of the boundary is assigned a fixed con-
stant value. yij = g(xij ) (13)
(2) Zero flux (Neumann) boundary condition i = 1, 2, . . . , M ; j = 1, 2, . . . , N .
Here, the states xkl of corresponding neighbor cells
perpendicular to the boundaries are constrained to where zij , uij and yij denote as usual the threshold,
be equal to each other. input, and output of cell Cij . Assuming all cells
(3) Periodic (Toroidal) boundary condition are of nth order, i.e. xij ∈ Rn , then Eqs. (12) and
(13) constitute a system of nM N non-autonomous
Here, the first and last rows (resp., columns) of the
nonlinear equations
array are identified, thereby forming a torus.
Finally, before Eq. (10) can be simulated in a ẋij = f (xij , zij (t), ukl (t), g(xkl )) ,
computer, or implemented in a silicon chip, the ini-
kl ∈ Sij (r) (14)
tial state xij (0) for all cells must be specified. We
will see in Part I of this paper that for image pro- i = 1, 2, . . . , M ; j = 1, 2, . . . , N . In this paper, we
cessing applications, the initial states would some- will consider mainly the situation where both the
2228 L. O. Chua
threshold and the input of each cell are constants, Standard CNN :
i.e. zij (t) = zij and uij (t) = uij , in which case,
Eq. (14) becomes an autonomous system. For im- X
ẋij = −xij + zij + akl f (xkl )
age processing applications, it is usually more con-
kl∈Sij (r)
venient to recast this autonomous system of nM N X
differential equations into the matrix form + bkl ukl
kl∈Sij (r)
Ẋ = F (X) (15)
1
where yij = f (xij ) = (|xij + 1| − |xij − 1|)
2
x11 x12 ··· x1N i = 1, 2, . . . , M, j = 1, 2, . . . , N (16)
x21 x22 ··· x2N
· · ··· · For a space-invariant (homogeneous) CNN with
X=
,
a 3 × 3 sphere of influence (r = 1), Eq. (16) is
· · ··· ·
completely specified by 19 real numbers; namely,
· · ··· ·
one threshold zij , nine control (feed-forward) coef-
···
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Fig. 6. For a standard CNN with a 3 × 3 sphere of influence, only 19 real numbers are needed to specify its dynamics. These
19 numbers can be specified by z, B, A (top), henceforth called the CNN cloning template, or rearranged into a single
row (bottom), henceforth called a CNN gene.
x11 x12 ··· x15 x21 x22 ··· x25 x31 x32 ··· x35 x41 x42 ··· x45
⇓ ⇓ ··· ⇓ ⇓ ⇓ ··· ⇓ ⇓ ⇓ ··· ⇓ ⇓ ⇓ ··· ⇓
(20)
x1 x2 ··· x5 x6 x7 ··· x10 x11 x12 ··· x15 x16 x17 ··· x20
0 0 0
z= 0 , B= 0 b00 0 ,
0 0 0
(21)
0 0 0
A = a0,−1 a00 a0,1
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
0 0 0
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 8. Schematic diagram showing each cell is influenced only by the input ukl of its eight nearest neighbors via the B
template, and by the output ykl of the same eight nearest neighbors via the A template.
7
For the sake of clarity, we have included the boundary cells in counting the size of this CNN. In practice, as well as in the
following, the boundary cells are usually not included since they do not satisfy the same dynamics as the rest of the cells in
the array.
CNN: A Vision of Complexity 2231
(a)
(b)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 9. The 3 × 4 CNN in Fig. 9(a) with a fixed boundary condition has only 2 degrees of freedom, provided by the state
variables x1 and x2 of the two interior cells C22 and C23 , respectively. The dynamics (vector field) of this CNN can be
represented by the interactions of the directed graph in Fig. 9(b) where the two nodes represent y1 = f (x1 ) and y2 = f (x2 ),
respectively. The function f (·) is defined by Eq. (6).
Substituting template (21) and the boundary con- b00 plays only a non-dynamics role of “scaling” the
dition (22) into Eq. (16), we obtain the following inputs. On the other hand, the feedback coefficients
state equations for the above 3 × 4 CNN: {a0,−1 , a0,0 , a0,1 } play a decisive role in the non-
linear dynamical behaviors of Eq. (25). In par-
ẋ22 = −x22 + a00 f (x22 ) + a01 f (x23 ) + b00 u22 (t) ticular, observe that the “central” feedback coeffi-
ẋ23 = −x23 + a0,−1 f (x22 ) + a00 f (x23 ) + b00 u23 (t) cient a00 of the A template provides a self-feedback
(24) effect.8
To study the dynamical behaviors of Eq. (25),
where f (·) is defined by Eq. (6). let us consider two numerical examples.
In terms of our single-subscript notation,
Eq. (24) assumes the simpler form: Example 2.1.1.
ẋ1 = −x1 + a00 f (x1 ) + a01 f (x2 ) + b00 u1 (t) Choose a00 = 2, a0,−1 = −a01 = 2, and b00 = 0.
In this case, Eq. (24) reduces to the autonomous
ẋ2 = −x2 + a0,−1 f (x1 ) + a00 f (x2 ) + b00 u2 (t) system
(25a)
ẋ1 = −x1 + 2f (x1 ) − 2f (x2 )
y1 = f (x1 ) (26)
(25b) ẋ2 = −x2 + 2f (x2 ) + 2f (x1 )
y2 = f (x2 )
The right-hand side of the state equation of the One can prove that Eq. (26) has a unique limit
3×4 CNN in Fig. 9(a) can be represented by the di- cycle [Zou & Nossek, 1991a]. A typical pair of
rected graph shown in Fig. 9(b), which shows clearly waveforms (x1 (t), x2 (t)) corresponding to the ini-
the roles played by the coupling coefficients. Note tial state (x1 (0), x2 (0)) = (0.1, 0.1) is shown in
that since u1 (t) and u2 (t) are prescribed input func- Fig. 10(a). The associated trajectory and limit cy-
tions of time, the control (feedforward) coefficient cle is shown in Fig. 10(b).
8
In chemical reactions, the self-feedback term is said to be auto-catalytic if a00 > 0 and f 0 (x) > 0.
2232 L. O. Chua
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 10. The solutions x1 (t)(in red) and x2 (t)(in blue) of Example 2.1.1 corresponding to x1 (0) = 0.1 and x2 (0) = 0.1 are
shown in (a). The corresponding trajectory in (b) is seen to converge to a limit cycle.
Example 2.1.2. (x1 (0), x2 (0)) = (0.1, 0.1) are shown in Figs. 11(a),
Choose a00 = 2, a0,−1 = −a0,1 = 1.2, b00 = 1, and 11(b), respectively, along with their continu-
u1 (t) = 4.04 sin( π2 t), and u2 (t) = 0. In this case, ous broad power spectra. The corresponding tra-
Eq. (24) becomes jectory is given by the strange attractor shown in
Fig. 12(a). The associated Poincaré map obtained
ẋ1 = −x1 + 2f (x1 ) − 1.2f (x2 ) by sampling the attractor in Fig. 11(a) at the basic
π period T = 4 of the input signal u1 (t) is shown in
+ 4.04 sin t (27) Fig. 12(b) (called a “Lady’s shoe” attractor in [Zou
2
& Nossek, 1991b]).
ẋ2 = −x2 + 1.2f (x1 ) + 2f (x2 )
This second-order non-autonomous CNN has 2.3. Complete stability criteria for
been found numerically by [Zou & Nossek, 1991b] standard CNNs
to be chaotic. In particular, the waveforms of Virtually all image processing applications and sili-
(x1 (t), x2 (t)) corresponding to the initial state con chip implementations of standard CNNs to date
CNN: A Vision of Complexity 2233
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 11. (a) The solution x1 (t) of Example 2.1.2 and its power spectrum (in red). (b) The solution x2 (t) of Example 2.1.2
and its power spectrum (in blue).
are based on the assumption that neither the os- Since both zij (t) and ukl (t) are bounded by hy-
cillation nor the chaotic phenomenon exhibited by potheses, there exists finite constant K such that
the two simple CNN examples from the preceding
section can occur. In this section, we will present max |g(t)| < K (30)
0<t<∞
some mathematical criteria which guarantee such
complete stability properties. It follows from Eqs. (28) and (30) (via Gronwall’s
Lemma) that
Theorem 2.3.1. State-Boundedness Criterion.
If the function f (·) in the output equation (11) Z t
is continuous and bounded, then the state xij (t) |xij (t)| ≤ |xij (0)e−t | + | e−(t−τ ) g(τ )dτ |
0
of each cell of a standard CNN is bounded for all Z
bounded threshold and bounded inputs. t
−t
≤ |xij (0)|e + max |g(t)| e−(t−τ ) dτ
0<t<∞ 0
Proof. Equation (10) can be recast into the form
< |xij (0)| + K , for all t > 0 (31)
ẋij = −xij + g(t) (28)
where
∆ X X Theorem 2.3.2. Complete Stability Criterion.
g(t) = zij (t)+ akl f (xkl (t))+ bkl ukl (t) All trajectories of the standard CNN defined by
kl∈Sij kl∈Sij Eqs. (10) and (11) with constant thresholds, con-
(29) stant inputs, and a sphere of influence of arbitrary
2234 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
(b)
Fig. 12. (a) Strange attractor associated with the solution (x1 (t), x2 (t)) from Fig. 11(a). (b) The lady’s shoe attractor
extracted from a stroboscopic sampling of the strange attractor from (a) at the period T = 4 of the input signal u1 (t).
size, converge to an equilibrium state, which in gen- Eq. (11) is differentiable with positive slopes,
eral depends on the initial states, if the following and bounded.
three hypotheses are satisfied: (iii) All equilibrium points are isolated.
(i) The A template is symmetric with respect to Proof. Hypothesis (ii) implies that f (·) is injective
the center of the template; or equivalently, the and hence has an inverse function
associated matrix A in Eq. (19) is symmetric.
(ii) The scalar function f (·) in the output equation x = f −1(y) , ∀ y ∈ (ymin, ymax ) (32)
CNN: A Vision of Complexity 2235
where ymin = inf f (x) and ymax = sup f (x). Define It follows from Eq. (38) and hypothesis (ii) that
the following scalar function V : Rν → R: V (x) is a Lyapunov function, and V̇ (x) < 0 except
Z at the invariant set
1 T Xν yi
−1
V (x) = − y Ay + f (y)dy M = {x ∈ Rν : V̇ (x) = 0}
2 i=1 θ
= set of equilibrium points of Eq. (19) (39)
− yT Bu − yT z (33)
in view of Eq. (38) and f 0 (xi ) > 0 (hypothesis ii).
Now, since x(t) is bounded in view of Theo-
where θ is any real number chosen such that ymin <
rem 2.3.1, we can invoke LaSalle’s invariant princi-
θ < ymax , and ν = nM N , where n = 1 for Eq. (10).
ple [LaSalle, 1967] to conclude that all trajectories
The time derivative of V (x) along the trajectories
of Eq. (19) must converge to M . But M consists
of Eq. (19) is given by:
of only isolated equilibrium points [hypothesis (iii)],
1 and hence all trajectories must converge to an equi-
V̇ (x) = − (ẏT Ay + yT Aẏ) librium point.
2
X
ν Observe that although the nonlinear function
f −1 (yi )ẏi − ẏT Bu − ẏT z (34)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
and yij = −1, called the − saturation region (to be equilibrium, wij is a constant and the role it plays
coded in blue pseudo color in this paper), with the in Eq. (41) at equilibrium is simply to translate the
two distinct states of each cell. Observe that the two “curve” ẋij = g(xij ), as defined by Eq. (42), up (if
stable saturation regions are separated by a linear wij > 0) or down (if wij < 0) in a vertical direction.
region (coded in green), and that Consequently wij is called an offset level.
Since aij > 1, by hypothesis, the curve rep-
yij = −1, if and only if xij ≤ −1 resenting g(xij ) versus xij given by Eq. (42) is
(40)
yij = 1, if and only if xij ≥ 1 an odd symmetric three-segment piecewise-linear
curve whose inner segment (green) through the ori-
In terms of the above coding scheme, bistability gin has a positive slope equal to aij − 1. The slope
is achieved if all trajectories converge to an equi- of the two outer segments is equal to −1. Con-
librium point where the magnitude of each state xi sider first wij = 0 and an arbitrary initial state
is at least unity, i.e. |xij | ≥ 1. Our next theorem xij . Since ẋij > 0 when g(xij ) is in the upper half
asserts that this is indeed the case if the CNN cell is plane, and ẋij < 0 when g(xij ) is in the lower half
auto-catalytic in the sense that the “self-feedback” plane, starting from any point on this curve, the
synaptic coefficient aij , namely, the central element trajectory must tend to the right (resp. left) along
of the A template, is greater than unity. the direction indicated on the curve in the upper
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Theorem 2.4.1.
(resp., lower) half plane. The resulting curve in
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
The output yij of every cell at any stable equi- Fig. 13(a), along with its arrowheads, is called a
librium point of a completely stable standard CNN dynamic route [Chua, 1969] since it completely de-
defined by Eqs. (10) and (11) is equal to either plus termines the evolution of a trajectory originating
from any initial point on the curve.
1, or minus 1, if the center element aij of the A
When coupling is added, the resulting value
template satisfies aij > 1.
of wij introduces an offset which shifts the curve
Proof. Let us substitute Eq. (11) into Eq. (10) and from Fig. 13(a) upwards if wij > 0, or downwards
recast the result into the form if wij < 0, at equilibrium. Four such translated dy-
∆ namic routes are shown in Fig. 13(b) correspond-
ẋij = g(xij ) + wij = h(xij ; wij ) (41) ing to 4 values of wij which lead to 4 qualitatively
different translated curves. Although the dynamic
where
routes indicated on the curves in Fig. 13(b) are no
∆
g(xij ) = −xij + aij f (xij ) longer time invariant but shift up and down contin-
uously until equilibrium is reached, the location of
−xij + aij ,
xij ≥ 1 each stable equilibrium point is always to the left of
= (aij − 1)xij , |xij | < 1 (42) xij = −1, or to the right of xij = 1. It follows that
−xij − aij , xij ≤ −1 in all cases, yij = −1, or yij = 1.
9
DP plot is an acronym for driving-point plot. The concept of a DP plot and its associated dynamic route was first introduced
in [Chua, 1969] and has since been used extensively for studying first-order nonlinear circuits [Chua et al., 1985].
CNN: A Vision of Complexity 2237
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 13. (a) The dynamic route for an isolated cell (wij = 0) shows an unstable equilibrium point at xij = 0, a stable
equilibrium point Q− located at xij (Q− ) < −1 and a stable equilibrium point Q+ located at xij (Q+ ) > 1. (b) The dynamic
route associated with the shifted DP plot of a coupled cell corresponding to four different offset levels wij > aij > 0,
0 < wij < aij , −aij < wij < 0, and wij < −aij < 0. In each case, the stable equilibrium state is located at xij < −1, or at
xij > 1.
The family of DP plots Γ(t) in Fig. 13(b) consists of Referring to Fig. 13(b), akl 6= 0 implies that
translates of Γ whose offset level wij is defined by the DP plot Γ from Fig. 13(a) dances up and down
Eq. (43). For constant threshold z, and constant in a continuous motion until such time t = Ts ,
input u, the offset wij = wij (t) is time-varying if called the steady state time, where the states along
and only if akl 6= 0, kl 6= ij. The time variation the dynamic route of all cells had entered the
of wij (t) depends on the state xkl (t) of each neigh- + saturation, or the − saturation region. The
bor cell Ckl belonging to the sphere of influence Sij steady state time Ts for a standard CNN is, ex-
where akl 6= 0. Even in the time-varying case, wij (t) cept in degenerate cases, always a finite number
tends to a constant as soon as the magnitude of all since the state x(t) at t = Ts is not an equilib-
rium state. In general, x(t) will continue to vary
neighbor states xkl exceed unity because
with time until it reaches an equilibrium point as
( t → ∞. Only the output y(t) is constant at
−1, if xkl ≤ −1 t = Ts . The curve Γ(Ts ) obtained by translating
f (xkl ) = (44)
1, if xkl ≥ 1 Γ through the offset wij (Ts ) becomes stationary for
2238 L. O. Chua
all t ≥ Ts . Hence, the dynamics for t ≥ Ts is com- either a monochrome or a color image, and is
pletely determined by the dynamic route along the usually partitioned into an M × N array. Since
translated curve Γ(Ts ), henceforth called the steady any color image can be decomposed into three
state shifted DP plot. basic color components where each component is
If a CNN is oscillatory, or chaotic, then Γ(Ts ) processed separately and its outputs combined
does not exists. Hence, a standard CNN is com- subsequently, it suffices for us to consider only
pletely stable if, and only if, it has a steady state monochrome images. Real life images, such as those
shifted DP plot Γ(Ts ). registered on photographic films, are usually gray
The bistable property of a completely stable scale images because the intensity level of every
standard CNN is quite robust with respect to noise pixel in such images can vary over a continuous
and variations in the CNN parameters z , B and range of gray levels. Without loss of generality, we
will choose a numerical scale so that a pure white
A . This is easily seen in Fig. 13(b) where small
tone will be assigned the lowest normalized number
variations in the slope aij − 1 of the center segment,
−1, and a jet black tone will be assigned the high-
or in the offset level wij , will not change the bistable est normalized number +1. A number u ∈ (−1, 1)
outcome. The mechanism responsible for this ro- is associated therefore uniquely with a precise gray
bustness is in fact the same mechanism responsible intensity level. For visualization purposes in this
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
for the well-known reliability of digital computers. paper, the transient image evolutions from an ini-
In both cases, accuracy is restored by resetting the tial image to the final steady state image will usu-
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
output of each cell to one of two well-defined states ally be coded in “pseudo color” in accordance with
at steady state. the color code shown on top of Fig. 14 for the out-
In a typical bistable system, there are two put yij of cell Cij . In terms of this color code,
simultaneous stable states, and the outcome de- the discretized standard nonlinear output function
pends on which basin of attraction does the initial yij = f (xij ) in Eq. (6) will assume the pseudo-color
state belong. For example, a CNN with a steady code scale shown in Fig. 14. Hence, for most black-
state DP plot coinciding with one of the two in- and-white binary images to be presented in this
ner plots shown in Fig. 13(b) has two stable equi- paper, the white background will appear in blue
librium points. However, if wij (Ts ) > aij , or if pseudo-color, while the black objects will appear
wij (Ts ) < −aij , then the associated steady state DP in red.
plot would have only one globally asymptotically We will now demonstrate how the CNN cloning
stable equilibrium point, such as the top or bottom templates, A , B , z , henceforth repacked into
shifted DP plots in Fig. 13(b). In this case, a gen- a CNN gene defined by the single template
eralized form of bistability is achieved through the
application of an input u. This class of bistable phe- z , B , A , which uniquely defines a standard
nomenon is even more robust since its outcome is in- CNN can be chosen to perform many basic image
dependent of the initial conditions, and is therefore processing operations. In most of our examples, we
more immune to noise. In this case, the steady state will need only a 3 × 3 sphere of influence (r = 1) so
output y(∞) = limt→∞ y(t) is parameterized by the that only 19 real numbers need to be specified.
input image u only. Such CNNs are therefore par-
ticularly suited for performing pattern recognition 2.5.1. Edge detection CNN
and pattern generation tasks in image processing Among the many basic tasks routinely performed
applications. by sophisticated image processing systems, includ-
ing the human brain, the extraction of edges from
2.5. Coding the CNN gene a gray-scale image is perhaps the most important
because a lot of relevant information can be ex-
An image processor is any software or hardware sys- tracted from these edges, thereby achieving an im-
tem which transforms a class of input image U into mense amount of data compression. A simple CNN
an output image Y in accordance with some pre- that can perform this task reliably for binary input
scribed operations. This input image U can be images is defined by the template10
10
Although this CNN template can also extract edges from gray scale images, the results often contain noises which need to
be further filtered out by another CNN. A better gray-scale edge detector, called the Contour Extraction CNN, will be given
in Fig. 2.6.31 of Sec. 2.6.
CNN: A Vision of Complexity 2239
−1 −1 −1 0 0 0
z = −0.5 , B = −1 8 −1 , A= 0 2 0 (45a)
−1 −1 −1 0 0 0
which we can repack into the following CNN gene consisting of a string of 19 real numbers, following the
ordering scheme of Fig. 6.
G : −0.5 −1 −1 −1 −1 8 −1 −1 −1 −1 0 0 0 0 2 0 0 0 0 (45b)
naked eye.
To illustrate the continuous dynamical evolu-
tion in time of the Edge Detection CNN beginning
from a given binary input U and initial state X(t) at
t = 0, several “snap shots” of the Edge Detection
CNN output image Y(t) are shown in chronologi-
cal order in Fig. 16, henceforth called a CNN Flow
Pattern. The first image in the upper left hand
corner of a CNN flow pattern is always the input
image, usually printed in pseudo color. The next
image is the initial state X(0). The succeeding im-
ages are the snap shots of the output image Y(t)
arranged in chronological order, as in a movie strip.
Observe that since yij (t) = f (xij (t)) = xij (t) when-
ever |xij (t)| ≤ 1, and since the initial state xij (0) is
always normalized in this paper so the |xij (0)| ≤ 1,
it follows that the second image on the top of the
CNN flow pattern can be interpreted either as the
initial state X(0), or as the output image Y(t) seen
at t = 0 (since X(0) = Y(0)). In this CNN flow
Fig. 14. The pseudo color code for the standard CNN cell
pattern, as well as in all others to be shown later,
output function yij = f (xij ) to be used throughout this pa-
per. The adjective “pseudo” is used to emphasize that the the last image in the lower right hand corner will
color has no relation to the “real” color of the object in the always be chosen to be the steady state output im-
image or pattern. age, so that each pixel will be either black or white,
or in pseudo color, always red or blue.
For the above Edge Detection CNN, the input
Figure 15 presents two examples illustrating consists of any M × N image or pattern U where
the properties of the Edge Detection CNN. We will each pixel is either black or white (respectively, red
adopt this “CNN gene album page” format in pre- or blue in pseudo color), henceforth called a binary
senting other CNNs in Secs. 2.5–2.6. Each album image or pattern. The task to be performed by
page usually contains two examples: The first ex- this CNN is to produce a steady state output im-
ample in this format consists of an abstract pattern age Y consisting of only edges, i.e. boundaries, of
with a small array size so that each black (shown in the black (resp., red in pseudo color) objects in U .
red pseudo color) pixel is discernible as a small black In this CNN, an input cell uij ∈ U is defined to
2240 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 15. A CNN gene album page describing the Edge Detection CNN. The white pattern in the center of Examples 1 and 2
denotes zero initial state X(0).
be an edge cell if and only if it has at least one analytical approach for the Edge Detection CNN by
white (resp., blue in pseudo color) nearest neigh- proving the following proposition.
bor. It is important to realize that once a cloning
template, or equivalently, a CNN gene G, is speci- Proposition 2.5.1.
fied, the prescribed task (in this case, extracting the For any binary input image U, the correspond-
edges) will be implemented for any binary input im- ing steady state binary output image Y of the Edge
age, not just for the two illustrative examples. In Detection CNN consists of all edges of U. In par-
this sense, the CNN is imbued with certain predic- ticular, assuming xij (0) = 0, we have:
tive power, albeit a relatively modest one. In the (a) uij = 1 maps into yij = 1 if, and only if, there
jargon of neural network literatures, we can say that exists at least one nearest neighbor Ckl ∈ Sij
this CNN has some “generalization” power in the with ukl = −1.
sense that once the synaptic weights are chosen, ei- (b) uij = −1 maps into yij = −1 independent of its
ther by “learning” from a given set of input–output neighbors.
patterns, or by other methods, it will execute the
same prescribed task for all other patterns not in- Proof. Substituting the parameters from the
cluded in the original training set. For general neu- cloning template Eq. (45a) into Eqs. (41)–(43), we
ral networks, it is virtually impossible to guarantee obtain
that a prescribed task will be implemented reliably
ẋij = g(xij ) + wij (46a)
for all input images since this would normally re-
quire verifying the output image corresponding to where
all possible binary input images by brute force sim-
ulations. For standard CNNs, however, the precise g(xij ) = −xij + 2f (xij )
performance of a large class of cloning templates, −xij + aij ,
xij ≥ 1
including the above Edge Detection CNN, can be = xij , |xij | < 1 (46b)
derived rigorously. We will illustrate this rigorous −xij − aij , xij ≤ −1
CNN: A Vision of Complexity 2241
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 16. The CNN flow patterns showing a binary input image (top left) at t = 0, and the evolution of the corresponding
output image at t = 0, t1 , t2 , . . . , t8 . The black-and-white input image is coded in “red” and “blue” pseudo color where “red”
denotes the “black” object pixels and blue denotes the “white” background. Observe that the red edges in the steady state
image at t = t8 coincide with the boundary of the input image at t = 0. The red interior pixels enclosed within the boundary
at t = t8 have “melted” and turned to blue.
Fig. 18. Flow pattern of the corner detection CNN showing the input image (top left) at t = 0 and the evolution of the
corresponding output image at t = 0, t1 , t2 , . . . , t8 .
these two algorithmic operations into a single more (b) uij = −1 maps into yij = −1 independent of its
efficient continuous dynamical evolution. neighbors.
Our next proposition guarantees that the cor-
ner detection CNN will function as prescribed, for Proof [Chua & Shi, 1991]. Since A and B re-
all binary input patterns. main the same as in the Edge Detection CNN,
Eq. (47) is applicable also for the corner detec-
Proposition 2.5.2. tion CNN. Substituting z = −8.5 into Eq. (47), we
For any binary input image U, the correspond- obtain
ing steady state binary output image Y of the Cor-
ner Detection CNN consists of all convex corners of wij = −16.5 + 8uij + 2N−1 (50)
U. In particular, assuming xij (0) = 0, we have: where N−1 denotes as before the number of blue
(a) uij = 1 maps into yij = 1 if, and only if, there (i.e. ukl = −1) neighbors belonging to the sphere of
exist, at least 5 nearest neighbors with ukl = −1. influence Sij .
2244 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 19. Flow pattern of the corner detection CNN with input pattern adopted from a sketch by Escher.
sense that some entries in the CNN template (resp., form formula11 given in [Chua & Kang, 1977],
CNN gene) are not fixed real numbers, but are spec- namely,
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
11
Any scalar piecewise-linear function y = f (x) with a finite number of breakpoints at x = x1 , x2 , . . . , xn , and/or discontinuities
at x = x1 , x2 , . . . , xn has the closed form representation
y = a0 + a1 x + b1 |x − x1 | + b2 |x − x2 | + · · · + bn |x − xn |
+ c1 sgn(x − x1 ) + c2 sgn(x − x2 ) + · · · + cn sgn(x − xn ) (54a)
where
∆ 1, x>0
sgn(x) =
−1, x<0
This general result was first discovered and published in [Chua & Kang, 1977]. The coefficients aj , bj , and cj can be easily
calculated as follow:
1
a1 = (m0 + mn )
2
1
bj = (mj − mj−1 ), j = 1, 2, . . . , n
2
(
0, if f (·) is continuous at the breakpoint x = xj
cj = (54b)
1 −
[f (xj ) − f (xj )], otherwise, j = 1, 2, . . . , n
+
2
X
n
Here, mi denotes the slope f 0 (x) at segment i, i = 0, 1, 2, . . . , n, where the left-most segment is labeled segment 0 , and the
right-most segment is labeled segment n. All segments are labeled consecutively from left to right. A point x = xj is called
− −
a breakpoint of f (·) if f 0 (x+ 0
j ) 6= f (xj ), where xj and xj denote the right and left limit of f (xj ), respectively. If f (·) is
+
+ −
continuous at all breakpoints, i.e. f (xj ) = f (xj ), then cj = 0, j = 1, 2, . . . , n, and all terms involving sgn(x) are absent in
Eq. 54(a).
2246 L. O. Chua
kl∈Sij
X
+ aTkl ykl (t − T )
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
This cloning template is represented by a CNN gene (G, GT ) of twice the original length in the CNN
gallery as follow:
(60)
CNN: A Vision of Complexity 2247
Group 4 contains some CNN cloning tem- objects (e.g. defects on printed circuit boards) while
plates with a 5 × 5 sphere of influence (r = the main application of “point removal” is the fil-
2). Such templates are needed for fine-grain and tering of an impulse noise.
higher-resolution applications, especially in model-
2.6.7. Logic NOT Operation CNN
ing higher brain functions, such as illusions.
The following list contains all CNN genes ex- Task:
hibited in this gallery. Each CNN gene is listed Invert intensities of all binary image pixels —
under one of the four groups (group 1 is divided the foreground pixels become the background, and
into three subgroups, group 2 is divided into two vice versa. Logic NOT operation can be used as
subgroups, and group 3 is divided into two sub- an element of Boolean Logic algorithms which op-
groups) cited above, along with a brief description erate in parallel on data, represented in the form of
of its “genetic” properties, referred to in this gallery a two-dimensional array.
as a “task” because each CNN gene is designed to
implement a well-defined task. 2.6.8. Logic AND Operation CNN
2.6.9. Logic OR Operation CNN
Group 1: Standard (linear) 3 × 3 templates Task:
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Subgroup 1: Binary image processing by Perform a pixel-wise logic AND operation (logic
uncoupled CNNs (akl = 0, kl 6= ij)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2248 L. O. Chua
Fig. 2.6.2.
Fig. 2.6.1.
Album page for Threshold CNN.
Fig. 2.6.4.
Fig. 2.6.3.
Album page for Vertical Translation CNN.
2250 L. O. Chua
Fig. 2.6.5.
Fig. 2.6.6.
Album page for Point Removal CNN.
Album page for Point Extraction CNN.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 2.6.8.
Fig. 2.6.7.
Album page for Logic “Not” Operation CNN.
2252 L. O. Chua
Fig. 2.6.9.
Fig. 2.6.10.
Album page for Edge Detection CNN.
Album page for Logic “Or” Operation CNN.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 2.6.12.
Fig. 2.6.11.
Album page for Corner Detection CNN.
2254 L. O. Chua
Fig. 2.6.14.
Fig. 2.6.13.
Album page for Erosion CNN.
an important element of nonlinear image filtering objects containing pixels which coincide with the
methods. markers are extracted. Selected objects extraction
2.6.14. Dilation CNN is a useful element of the “divide-and-conquer” im-
age analysis strategy, since it provides a means for
Task: separate analysis of selected simpler objects.
Perform a “dilation” operation on a given bi-
nary image. Image dilation is a morphological com- 2.6.21. Filled Contour Extraction CNN
plement of the erosion operation. In the simple case, Task:
a dilation of a binary image can be seen as append- Take two binary images of the same size and
ing to image objects all those background pixels, extract from the former all those regions which
which can be reached by the chosen structuring ele- fill completely closed contours of the latter image.
ment moving along the objects’ boundary. For each This operation is useful in some pattern recognition
prescribed “dilation structuring element”, there is problems.
a corresponding dilation CNN gene.
2.6.22. Global Connectivity Detection CNN
Subgroup 2: Binary image processing by coupled
Task:
CNNs (akl 6= 0 for at least one kl 6= ij)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
2256 L. O. Chua
Fig. 2.6.16.
Fig. 2.6.15.
Album page for Shadow Projection CNN.
Fig. 2.6.18.
Fig. 2.6.17.
Album page for Vertical Hole Detection CNN.
2258 L. O. Chua
Fig. 2.6.20.
Fig. 2.6.19.
Album page for Diagonal Line Detection CNN.
2260 L. O. Chua
Fig. 2.6.24.
Fig. 2.6.23.
Album page for Hole-Filling CNN.
2262 L. O. Chua
Fig. 2.6.27.
Fig. 2.6.26.
Album page for Inverse-Half Toning CNN.
Fig. 2.6.29.
Fig. 2.6.28.
Album page for Histogram Generation CNN.
to the XOR function of nine Boolean variables, and 2.6.34. Image Difference Computation CNN
it is performed in parallel for all image pixels.
Task:
2.6.30. Row-Wise Parity Detection CNN Compute the logic difference of two binary im-
ages (e.g. consecutive frames of a video sequence)
Task:
and perform additional impulse noise filtering. As a
Determine whether the number of black pixels result of this operation only the moving image parts
in a row is even or odd. Parity detection is a simple are extracted. Therefore, the image difference com-
technique used for detecting errors which can occur putation can be viewed as a direction independent
during a binary data transfers. Row-wise parity motion detection.
detection CNN of size m rows by n columns, can
2.6.35. Speed Detection CNN
simultaneously check for errors in the form of a set
of m binary words, each of the length n bits. Task:
Detect binary image objects which are moving
Subgroup 2: Gray-scale image processing slower than some prescribed speed, in an arbitrary
2.6.31. Contour Extraction CNN direction. Speed detection is useful for performing
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Fig. 2.6.30.
Fig. 2.6.31.
Album page for Contour Extraction CNN.
Album page for Row-Wise Parity Detection CNN.
CNN: A Vision of Complexity 2265
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2266 L. O. Chua
Fig. 2.6.32.
Fig. 2.6.33.
Album page for Motion Detection CNN.
Album page for Gradient Detection CNN.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 2.6.34.
Fig. 2.6.35.
Album page for Speed Detection CNN.
Album page for Image Difference Computation CNN.
CNN: A Vision of Complexity 2267
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2268 L. O. Chua
Fig. 2.6.36.
Fig. 2.6.37.
Album page for De-Blurring CNN.
Album page for Herring-Grid Illusion CNN.
CNN: A Vision of Complexity 2269
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
thereby exhibiting exactly the same behavior as ob- or more disconnected components? An example
served by humans. of a geometric pattern whose global connectivity
is difficult to determine, even by humans, is the
labyrinth-like patterns highlighted on the cover of
2.7. Does there exist a CNN gene the classic monograph “Perceptrons” [Minsky &
for solving Minsky’s global Papert, 1969], which we reproduce in Fig. 22 since
connectivity problem? we will use this same pattern to test CNN’s capa-
bility. This is a serious challenge since the main
How much intelligence does a locally-connected neu- theorem proved in this highly influential book12
ral network posses? Would not the local connec- implies that perceptrons cannot tell whether the
tivity constraint severely limit its ability to recog- two labyrinth patterns on the cover are connected
nize global functions? Can it determine whether a or not.
given geometric pattern is “globally” connected in Consider the following CNN cloning template
one contiguous piece, or if it is composed of two [Zarandy, 1997], henceforth called the Global Con-
nectivity Detection CNN :
0 −0.5 0 0 0.5 0
z: −4.5 , B: −0.5 3 −0.5 , A: 0.5 3 0.5 (61a)
0 −0.5 0 0 0.5 0
12
So influential was this book that it had brought the highly visible and promising budding research area of perceptron to an
abrupt halt due to lack of further research fundings.
2270 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 22. Reproduction of the cover of M. Minsky and S. Papert, Perceptron: An introduction to computational geometry.
G : −4.5 0 −0.5 0 −0.5 3 −0.5 0 −0.5 0 0 0.5 0 0.5 3 0.5 0 0.5 0 (61b)
To determine whether a given binary pattern P nal black (red in pseudo color) pixels are changed
is globally connected or not, let us apply P as the to white (blue in pseudo color).
input of a CNN parameterized by the above tem-
plate. Let us assign next the following initial state Boundary condition: Assume a fixed (Dirichlet)
and boundary condition: boundary condition with the “state” xij and input
uij of all boundary cells set equal to −1; i.e. xi∗ j ∗ =
Initial state: Delete a few adjacent black (red in −1 and ui∗ j ∗ = −1, where the double index i∗ j ∗
pseudo-color) pixels from P and call the remain- denotes those cell indices corresponding to bound-
ing set P0 . Choose P0 as the initial state. Note ary cells.
that the initial state P0 is almost identical to the To obtain an intuitive idea on the dynamical
original pattern P, except for a few deleted pixels, mechanism of this CNN, it is useful to identify each
henceforth called triggering cells, where the origi- black (red in pseudo-color) pixel in P as an ignitable
CNN: A Vision of Complexity 2271
(combustible) object (e.g. trees, dry grass, chemical triggering cells have all changed to blue (all trees
coatings on a fuse wire for detonating dynamites) on the path had been burned).
on a white (blue in pseudo-color) field environment. Any remaining red pixels must necessarily
Let each triggering cell (red pixels from P which be disconnected from the path of the fire, and
had been converted to blue pixels) serve as an ig- therefore represents a disconnected component
niter (e.g. a lighted match). At t = 0, a fire is of P.
initiated at each triggering cell (ignition point) on Let us now apply the two labyrinth-like pat-
P and the ensuing dynamical evolution is akin to terns from Minsky and Papert as inputs to the
a uniform propagation (spreading) of the fire to all above CNN, as shown on the left side of Figs. 23(a)
parts of the field still covered with red pixels (un- and 23(b), respectively. The patterns on the right
burned trees). The steady state is reached when all side are the corresponding outputs. Using the
red pixels which formed a contiguous part with the above analogies, we can interpret the remaining red
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
(b)
Fig. 23. Two labyrinth-like patterns taken from [Minsky & Papert, 1969]. The input pattern in (a) is not connected since
the corresponding steady sate CNN output pattern had found a non-empty set of red pixels which is not connected to the rest
of the pattern. The input pattern in (b) is connected, since the corresponding CNN output shows an empty set.
2272 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 24. Flow pattern of the global connectivity detection CNN when the pattern in Fig. 23(a) is applied as the input
image.
pixels on the right hand side of Fig. 23(a) as belong- chronologically. Observe that each red pixel lying
ing to a different component of P which is discon- on a contiguous path with any triggering cell disap-
nected from the deleted component. Consequently, pears one-by-one as the propagation process contin-
the CNN outputs in Fig. 23 asserts that the lower ues until there were no more red pixels left on the
pattern is globally connected but the upper one contiguous path — they have all been burnt out
is not. and turned into blue (charred) pixels. The non-
The flow patterns in Fig. 24 shows the time empty red pixels in the last snap shot (lower right)
evolution when the CNN input image (upper left represent therefore another component which is not
corner) is chosen to be the pattern shown in connected to the burnt out component.
Fig. 23(a). The next pattern with some pixels (trig- The flow pattern in Fig. 25 shows the time
gering cells) on the leftmost “leg” deleted is the evolution when the CNN input (upper left corner)
initial state. All other snap shots are presented is chosen to be the pattern shown in Fig. 23(b).
CNN: A Vision of Complexity 2273
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 25. Flow pattern of the global connectivity detection CNN when the pattern in Fig. 23(b) is applied as the input
image.
Observe that in this case, the steady state CNN The CNN flow pattern associated with the input
output (lower right) contains no red pixels, imply- pattern of Fig. 26(a) is shown in Fig. 27.
ing that the input pattern is globally connected. It is sometimes useful to think of the nonlin-
To demonstrate that the task performed by the ear propagation phenomenon of the “global connec-
CNN is independent of the input image, let us con- tivity detection” CNN as an active nonlinear wave
sider another input pattern, also taken from [Min- which propagates or spreads an infectious disease,
sky & Papert, 1969], and shown in the upper part or a chemical agent, at uniform speed, to all con-
of Fig. 26. The resulting steady-state output in the tiguous parts of a living or active medium. This
bottom shows that the sub-pattern on the left is nonlinear wave is very different from ordinary linear
disconnected from the part that has been burned, waves (e.g. electro-magnetic waves, sound waves,
while the pattern on the right is globally connected. etc.) since when a wavefront hits a boundary, or
2274 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 26. Applying the two-component input pattern (top) to the global connectivity detection CNN yields a steady-state
output pattern (bottom) which shows that while the component on the right is connected, the one on left is not.
obstacle, or, when two wavefronts collide with each Three snap shots from the CNN output image
other, there is no reflection or scattering because the evolution are shown in Figs. 28(b)–28(d), where the
colliding pixels will simply annihilate (by changing last one represents the steady state output image.
states from red to blue) each other. To illustrate In the actual output images, England and Sicily will
this phenomenon, let us consider the hypothetical disappear since both they and the ocean will appear
example shown in Fig. 28(a) where a part of west- in blue.
ern Europe, England, Ireland, and northern Africa Let us now suppose that a narrow land bridge
is shown painted in red, and where an infectious connects England to Europe and another land
virus (encoded by a blue pixel) which plays the role bridge connects Sicily to the Italian mainland. Let
of a triggering cell was introduced simultaneously us repeat the same simulation as Fig. 28 by intro-
at Dover, England, and at Palermo, Sicily. The ducing an infecting pixel at Dover, England and at
surrounding ocean is shown in green. The entire Palermo, Sicily. Seven snap shots of the evolution
land mass shown in Fig. 28(a), i.e. all red pixels, of the corresponding CNN output images are shown
plus the blue triggering cells as well, is applied as in Figs. 29(a)–29(h), where the last one represents
inputs to the global connectivity detection CNN, the steady state output.
i.e. xij (0) = 1 for all land mass pixels. As for the The snap shot in Fig. 29(b) shows that the
initial state, the blue pixels (at Dover and Palermo) infecting virus has entered the European conti-
and the green pixels are assigned xij (0) = −1, nent through the land bridge, and continues to
whereas all red pixels are assigned xij (0) = 1. Note spread along a broad wavefront. The snap shot
that the blue and green pixels both represent the in Fig. 29(c) shows that the infecting virus from
background field in so far as the CNN is concerned. Palermo has also crossed into the Italian mainland.
We have manually recoded the ocean in green in This crossing occurs later in time because the ac-
Fig. 28 in order to separate the land mass from the tive CNN wave propagates at a uniform velocity
ocean. In the computer CNN output, green will of and Palermo is further from Italy than Dover is
course appear as blue. from Europe. Figure 29(d) shows the two traveling
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2275
Fig. 27.
Flow pattern of the global connectivity detection CNN when the pattern in the upper part of Fig. 26 is applied as the input image.
2276 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 28. An infectious virus originating simultaneously from Dover (England) and Palermo (Sicily) at t = 0 will eventually
spread and infect all of England and Sicily at t = Ts .
CNN: A Vision of Complexity 2277
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 29. Same as Fig. 28 except that a channel bridge now connects England with Europe and another bridge connects Sicily
with Italy mainland.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2278 L. O. Chua
Fig. 29.
(Continued )
CNN: A Vision of Complexity 2279
(the infecting agent) with the land mass represent- yij (∞) = white, independent of (ukl , xkl (0))
ing human organs!
of its neighbors.
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
P , each cell Cij at the initial time t = 0 can Proof. Substituting the 19 parameters from the
assume only one of three combinations of (in- CNN gene G in Eq. (61b) into Eqs. (41)–(43), we
put, initial state) = (uij , xij (0)); namely,14 (white, obtain the associated CNN state equation
∆ ∆
white) = (−1, −1), (black, white) = (1, 1), (black,
∆
black ) = (1, 1). Our next proposition provides an ẋij = g(xij ) + wij (t) (63)
explicit algorithm for tracking the evolution of each
where the output function
CNN cell Cij ∈ P , and for determining its final fate,
i.e. its steady state output yij = g(xij ) = −xij + aij f (xij )
∆
yij (∞) = lim yij (t) (62)
t−→∞ −xij + aij ,
xij ≥ 1
without numerically integrating the huge system of = 2xij , |xij | < 1 (64)
coupled nonlinear differential equations 10. −xij − aij , xij < −1
13
There are many other CNN cloning templates capable of extracting global features. For example, the horizontal, vertical, and
diagonal hole detection CNNs included in the template gallery in Sec. 2.6 all function by propagating a “wave-like” dynamics
over vast distances.
14
Recall a black (or red in pseudo color) input uij , output yij , or initial state xij (0) is assigned the value 1 in the standard
CNN Eqs. (10) and (11). Similarly, white (or blue in pseudo color) is assigned the value −1.
2280 L. O. Chua
is depicted by its associated DP plot Γ shown in Eq. (61a) has at most four nonzero off-central en-
Fig. 30(a) and the offset level 15 tries, it follows that
the 3 × 3 sphere of influence Sij . We know such a shifted DP plot Γ(Ts ) must lie below this curve, as
time Ts exists since all trajectories must eventually shown in Fig. 30(b). Since all trajectories along the
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
tend to an equilibrium point in view of the complete dynamic route indicated on Γ(Ts ) must tend to the
stability criterion (Theorem 2.3.2)16 only equilibrium point Q− on the left, it follows that
Let us investigate first the nature of the shifted yij (∞) = −1, which is Local Rule 1.
DP plot Γ(0) at t = 0. Recall that by prescription, Local Rule 2 : (uij , xij (0)) = (black , white) =
the initial state for a “global connectivity detection” (1, −1) ⇒ yij (∞) = −1.
CNN must satisfy Since uij = 1 in this case, Eq. (67) implies
xkl (0) = −1, if Ckl is a triggering cell wij (0) = −1.5 − n(Sij ) (70)
= ukl , if otherwise.
Hence wij (0) ≤ −2.5 if n(Sij ) ≥ 1 (i.e. at least
Consequently, one adjacent neighbor Ckl is a triggering cell). In
this case, the peak of the shifted DP plot lies below
ykl (0) − ukl = f (xkl (0)) − ukl the horizontal axis so that all trajectories xij (t) can
( only tend towards the only equilibrium Q− on the
−2, if Ckl is a triggering cell left and hence x0ij (t) < 0 at t = 0. Hence, it suffices
=
0, if otherwise to consider only the worst case where n(Sij ) = 0
(i.e. there are no triggering cells inside Sij .) where
(66)
Eq. (70) gives wij (0) = −1.5. The corresponding
It follows from Eqs. (65) and (66) that shifted DP plot Γmax in Fig. 30(c) has three equi-
librium points. But initially, since xij (0) = −1, we
have x0ij (t) < 0 so that yij (t) remains unchanged;
i.e. yij (∆t) = −1 for small ∆t > 0.
wij (0) = −4.5 + 3uij − n(Sij ) (67)
But the terms ykl (t) in Eq. (65) will change if
ykl (0) = 1. The state equation for the four ad-
jacent neighbor cells is obtained by changing the
where n(Sij ) denotes the number of off-central trig-
subscripts of Eqs. (63)–(65) from ij to kl and from
gering cells (i.e. those with ukl = 1 and xkl (0) =
kl to a new summation index k0 l0 :
−1) belonging to the 3 × 3 sphere of influence Sij ,
centered at cell Cij . Since the B template in ẋkl = g(xkl ) + wkl (t) (71)
15
Observe that unlike Eq. (46c) of the Edge Detection CNN, and Eq. (50) of the corner Detection CNN, where the offset level
is a constant for constant inputs, here wij is a function of time since ykl (t) = f (xkl (t)) depends on t until t = Ts where
|xkl (t)| ≥ 1 for t ≥ Ts .
16
To be precise, Eq. (64) must be substituted by an arbitrarily close C 1 approximating function.
CNN: A Vision of Complexity 2281
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
(b)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
Fig. 30. (a) DP plot of isolated cell Cij corresponding to wij = 0, (b) When uij = −1, the steady-state shifted DP plot
Γ(Ts ) (in red) must lie below the upper-limiting DP plot Γmax with wij = −3.5. (c) When uij = 1, and xij (0) = −1, the
steady-state shifted DP plot Γ(Ts ) (in red) must lie between Γmax and Γmin .
2282 L. O. Chua
X
wkl (t) = −4.5 + 0.5 (yk0 l0 (t) − uk0 l0 ) + 3ukl (72)
k 0 l0 ∈{(k,l−1), (k,l+1), (k−1,l), (k+1,l)}
wkl (0) = −1.5 − n(Skl ) (73) On the other hand, if Cij has at least one ad-
Now from the perspective of cell Ckl , cell Cij jacent triggering cell, then wij (0) ≤ −2.5 and the
is an adjacent triggering cell and hence n(Skl ) ≥ 1 peak of the shifted DP plot at t = 0 will in this case
in Eq. (73) so that the peak of the corresponding lie below the horizontal axis so that starting from
shifted DP plots must all lie below the horizontal xij (0) = 1, the dynamic route must flow towards
axis, forcing all trajectories of the 4 adjacent cells the left. Since xij (t) decreases below 1 after t = 0,
to move left, and hence ykl 0 (t) < 0 at t = 0. It fol- yij (t) = xij (t) must track with xij (t) and there-
lows from the decreasing behavior of ykl (t) that the fore must also decrease. From the perspectives of
offset level wij (t) given by Eq. (65) must decrease an adjacent cell Ckl , the decrease in yij (t) is seen
for t = ∆t > 0. This implies that in all cases, the as a decrease in a corresponding term yk0l0 (t) in its
shifted DP plot Γ(t) of cell Cij can only move in a associated state equation (72). In this case, the
downward direction, thereby precluding Γ(t) from same analysis as that for Local Rule 2 holds and
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
moving over and above Γmax , or eventually lying all trajectories must move towards Q− on the left.
completely on top of the horizontal axis. In other Consequently, yij (∞) = −1 in this case.
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
numbers (for 3 × 3 sphere of influence) as the CNN and any initial state
gene coding problem.
In this section, we address the inverse prob-
X(0) = {xij (0) ∈ R : i = 1, 2, . . . , M ;
lem; namely, given a CNN gene Gρ , defined by 19
real numbers, ρ ∈ R19 , find its input–output op- j = 1, 2, . . . , N } (76)
erator T (Gρ ) without solving its associated system
of coupled nonlinear differential equations. Trans-
For certain applications, the input image U
lated into less technical terms, the inverse problem
and/or the output image Y may be further re-
can be restated as follows: Given a CNN gene in
the form of an arbitrary set of 19 real numbers, find stricted to assume only binary values, in which case
the task performed by the associated CNN for any uij ∈ {−1, 1} and yij (∞) ∈ {−1, 1} in Eqs. (74)
input image. We will henceforth refer to this inverse and (75). Moreover, the initial state X(0) is usu-
problem as the CNN gene decoding problem. ally assumed to be fixed a-priori. An exception is
An input-output CNN operator T (Gρ ) is any set when X(0) is used to code a second image, as in the
of algorithms, rules, truth tables, etc., which can be Boolean AND, OR and NOT CNN genes exhibited
used to construct the output image in the CNN gallery in Sec. 2.6.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Y = {yij (∞) ∈ R : i = 1, 2, . . . , M ; j = 1, 2, . . . , N }
(74) 2.8.1. Examples of input–output
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Local Rule 1:
uij 7→ yij (∞) = −1, if uij = −1, independent of (ukl , xkl (0)) for arbitrary kl.
(77)
Local Rule 2:
uij 7→ yij (∞) = 1, ⇔ there exists kl ∈ Sij such that ukl = −1, independent of xkl (0).
Local Rule 1:
uij 7→ yij (∞) = −1, if uij = −1, independent of (ukl , xkl (0)) for arbitrary kl.
Local Rule 2: (78)
uij 7→ yij (∞) = 1, ⇔ there exist at least five nearest neighbors with ukl = −1,
independent of xkl (0).
17
A rule is said to be local if and only if the steady-state output yij (∞) of each pixel Cij can be uniquely determined by the
input ukl and initial state xkl (0) of only those pixels Ckl inside the sphere of influence Sij , centered at cell Cij . Otherwise,
the rule is said to be global.
2284 L. O. Chua
Local Rule 1:
uij 7→ yij (∞) = −1, if uij = −1 and xij (0) = −1, independent of (ukl , xkl (0)).
Local Rule 2:
uij 7→ yij (∞) = −1, if uij = 1 and xij (0) = 1, independent of (ukl , xkl (0)).
(79)
Global Rule 3 :
uij 7→ yij (∞) = −1, ⇔ there exists an adjacent cell Ckl ∈ Sij such that ukl = 1 and
xkl (0) < 0, or there exists a path of contiguous (adjacent) cells Ck1 l1 ,
Ck2 l2 , . . . , Ckt lt , such that uk1 l1 = 1, uk2 l2 = 1, . . . , ukt lt = 1, and xkt lt (0) < 0.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Observe that an input–output CNN operator put ukl and initial state xkl (0) of only the cells Ckl
T (G) is not well-defined unless it contains all infor- inside the sphere of influence Sij of cell Cij via the
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
mation necessary for decoding G. Take away any following explicit formulas (assuming |xij (0)| ≤ 1
one of the local or global rules from the preceding without loss of generality) for i = 1, 2, . . . , M and
examples will make the operator incompletely de- j = 1, 2, . . . , N :
fined. Deriving a well-defined input–output CNN
operator T (G) for an arbitrary CNN gene G will no Case 1. aij > 1, wij 6= |aij − 1|. In this case, the
doubt remain a major fundamental challenge for the steady state output is given by:
next century. This problem is analogous to that of yij (∞) = sgn[(aij − 1) xij (0) + wij ] (80)
decoding the functions of the hundreds of millions
X
of genes in the human genome. wij = z + bkl ukl (81)
kl∈Sij
2.8.2. Uncoupled CNN genes where wij is the offset level of cell Cij , z is the con-
Just like the human genome project, steady stant threshold, and bkl is the control (feedforward)
progress can be made, albeit slowly, by isolating synaptic coefficients from the B template.
various generic classes of genes whose secrets can In the limiting case where aij > 1 and wij =
be more easily uncovered. One such generic class |aij − 1|, the output is given by:
of more tractable CNN genes is clearly the class yij (∞) = 1, if xij (0) > −1
whose input–output CNN operators can be com-
pletely specified via local rules alone. The following and wij = aij − 1 > 0 or if xij (0) ≥ 1
theorem gives a complete characterization of an im- and wij = −(aij − 1) < 0 (82)
portant class of such CNN genes, called uncoupled
CNN genes for reasons that will soon be obvious. yij (∞) = −1, if xij (0) ≤ 1
Case 3. 0 < aij < 1. In this case, the steady state Since the shifted DP plot h(xij ; wij ) in Eq. (92)
output is given by: depends on only two parameters, namely, the self-
feedback coefficient aij and the offset level wij ,
yij (∞) = sgn[wij − (1 − aij )] , if |wij | > 1 − aij we can make an exhaustive analysis of all qualita-
(86) tively distinctive cases via the dynamic route tech-
niques illustrated earlier in our proofs of Proposi-
wij tions 2.5.1 and 2.5.2. We omit the details since they
yij (∞) = = xij (∞) , if |wij | < 1 − aij are straightforward though tedious.
1 − aij
(87) Observe that the above proof depends critically
on the assumption that akl = 0 for all kl ∈ Skl ,
yij (∞) = sgn[wij ] , if |wij | = 1 − aij (88) kl 6= ij. This assumption is essential for decoupling
Eq. (16) into a system of MN decoupled first-order
scalar differential equations. It is natural therefore
Case 4. aij < 0. In this case, the steady state for us to refer to these CNN templates with this
output is given by: property as uncoupled CNN genes.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Such CNNs operate only in the linear region of the Class 2. Gray-scale input Binary output genes.
output nonlinear function yij = f (xij ) [defined in This class corresponds to the remaining pa-
Eq. (6)] so that yij (t) = xij (t) for all t. rameter regions in Fig. 32 where uij ∈ [−1, 1]
The current image processing technology is and yij (∞) = +1 or yij (∞) = −1; i.e. yij (∞) ∈
based primarily on performing spatial convolutions {−1, 1}.
with appropriate two-dimensional kernels via digi- Let us now define another important tractable
tal signal processors (DSP) [Lim, 1990]. Such spa- class of CNN genes which includes all Class 2 un-
tial convolutions can be implemented with three or- coupled CNN genes as a proper subset provided the
ders of magnitude reduction in computing time via input is strictly binary; i.e. uij ∈ [−1, 1].
current CNN chips operating in the linear region,
such as the grayscale region (for 3 × 3 templates)
Definition 2.8.3. Boolean CNN gene.
in Fig. 32. Readers interested in the details of this
approach are refered to [Crounse & Chua, 1995]. A CNN gene G is said to be Boolean if, and
only if, given any binary input image U = {uij ∈
{−1, 1} : i = 1, 2, . . . , M, j = 1, 2, . . . , N }, the
2.8.3. Boolean CNN genes and truth tables steady-state output yij (∞) of each cell Cij is also
The input–output CNN operator T (G) associated binary, and can be uniquely determined from the
with any uncoupled CNN genes can be constructed input pattern of only the cells Ckl located inside
directly from the explicit algebraic formulas given in the sphere of influence Sij of Cij .
Theorem 2.8.1, without solving the associated dif-
ferential equations. Hence, the entire class of un- The class of Boolean CNN genes includes not
coupled standard CNN genes has been decoded by only the above class of uncoupled standard CNN
a single theorem. From the co-dimension-2 bifurca- as a proper subset, but also all uncoupled CNN
tion diagram shown in Fig. 32, an uncoupled CNN genes with binary outputs where one or more pa-
gene can be classified into two classes: rameters aij , bkl and z may be nonlinear functions
of ukl , xkl , and ykl as in Eq. (57), or where addi-
Class 1. Gray-scale input Gray-Scale output tional terms involving time delays are needed, as
genes. in various motion and speed detection CNN genes.
This class corresponds to all parameters For such CNN genes, the length of the “gene rib-
(aij , wij ) located inside the left triangular wedge bon” must be elongated accordingly to include the
(in blue color) where uij ∈ [−1, 1] and yij (∞) ∈ additional parameters needed to specify the nonlin-
[−1, 1]. earities and/or time delays. In all cases, the output
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2287
Fig. 32. Co-dimension-2 bifurcation diagram for uncoupled CNN genes. The steady-state output yij (∞) of an uncoupled CNN can be read-off directly from this
(aij − wij )-parameter bifurcation diagram which summarizes all results from Theorem 2.8.1.
2288 L. O. Chua
Fig. 33. Each 3×3 pattern within a bold frame on the left is a Boolean window pattern. There are 512 such distinct patterns.
The right-hand side shows four corresponding outputs calculated from the rules prescribed by the CNN game of life gene. The
output for the other pixels are left blank to avoid clutter.
yij (∞) can be determined uniquely from only the The 4 output pixels, y33 (∞) = 1, y38 (∞) = −1,
cells Ckl belonging to Sij . y83 (∞) = −1, and y88 (∞) = 1 shown in the right-
Any Boolean CNN gene G can be decoded by hand side of Fig. 33 are calculated from the CNN
simply constructing a “decoding book” as in cryp- game of life gene to be presented in Sec. 2.11. As
tography, where the output yij (∞) corresponding usual, the red pseudo color denotes +1 and the blue
to each distinct combination of binary input pat- pseudo color denotes −1.
terns, henceforth called a “Boolean window pat- A Boolean CNN gene is completely decoded if,
tern” B(i, j) centered at Cij , can be decoded by and only if, the output yij (∞) corresponding to
solving the associated system of nonlinear differen- each of the 512 distinct Boolean window patterns
tial equations, say Eq. (16) for standard CNN cells, is specified. As an illustrative example, the “de-
or from other more complicated differential equa- coding book” for the corner detection CNN gene
tions, maps, or algorithms defining more complex is displayed in Figs. 34(a)–34(p), in pseudo color
CNN cells. Note that this decoding process needs (red = 1, blue = −1). Figure 34 contains 32 dis-
to be done only once. Moreover, the size M × N tinct Boolean window patterns and labeled con-
of the CNN array need only to be chosen as large secutively from pattern “0” on the top left cor-
as the size of the sphere of influence Sij , excluding ner of Fig. 34(a) to pattern “511” in the bottom
the boundary cells. For an r = 1 neighborhood Sij , right corner of Fig. 34(p). The output correspond-
each Boolean window pattern consists of one of the ing to each pattern in Fig. 34 is shown as a sin-
29 = 512 distinct combinations of binary bits. Four gle pixel directly below the pattern; it can be de-
among these 512 distinct Boolean window patterns termined directly from Proposition 2.6.2, or from
are identified by four 3 × 3 bold frames in the in- Theorem 2.8.1.
put pattern shown on the left-hand side of Fig. 33. It is important to observe that the 512 Boolean
Depending on the prescription via the CNN gene, window patterns in Fig. 34 are invariant in the
each of these 4 patterns must map uniquely, by defi- CNN code book, regardless of the CNN gene G.
nition of a Boolean CNN gene, to either yij (∞) = 1, Only the “code” of the output pixel below each
or yij (∞) = −1, at cell Cij where the corresponding window pattern contains useful information. Hence,
pattern B(ij) is centered; namely, it should be possible to derive a much more com-
pact and efficient scheme to convey this informa-
B(ij) 7→ yij (∞) ∈ [−1, 1] . (94) tion. Let us begin by coding each of the 512
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 34.
Decoding book for specifying the input–output CNN operator T (G) of the corner detection CNN gene.
CNN: A Vision of Complexity 2289
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2290 L. O. Chua
Fig. 34.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 34.
(Continued )
CNN: A Vision of Complexity 2291
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2292 L. O. Chua
Fig. 34.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 34.
(Continued )
CNN: A Vision of Complexity 2293
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2294 L. O. Chua
Fig. 34.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 34.
(Continued )
CNN: A Vision of Complexity 2295
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2296 L. O. Chua
Fig. 34.
(Continued )
CNN: A Vision of Complexity 2297
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 35. Decoding card containing only the essential information from Fig. 34 for specifying the input–output CNN operator
T (G) of Boolean CNN genes. There are 16 rows, each with 32 columns, giving a total of 512 “cell” spaces, each one representing
one 3 × 3 Boolean window pattern via its binary location number.
19
The symbols ai in Eq. (95) are not related to the A templates.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2298
Fig. 36. The minimal CNN truth table, called a gene-decoding card, for specifying the input–output CNN operator T (G) of the corner detection CNN gene.
CNN: A Vision of Complexity 2299
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 37. The binary code for specifying the corner detection CNN gene has 512 symbols.
Boolean window patterns serves two purposes: as Finally, note that we can print the 512 binary
an “address” as well as a “code” for reconstructing bits in Fig. 37 into a single contiguous ribbon with
the pattern. Consequently, all 512 bits of infor- 512 bits (or 140 decimal digits if we print the deci-
mation represented by the “color” of the 512 sin- mal code instead) as shown in Fig. 39. The resem-
gle pixels below each pattern in Fig. 34 can now blance of this CNN gene ribbon to a strand of DNA
be cramped into a single code with 512 entries, as gene is striking, not only in form, but in content
shown in Fig. 35, where each cell is labeled con- as well.
secutively from left to right, and then from top to We close this section by asking the question:
bottom, as depicted in Fig. 36. The resulting one- How many distinct CNN Boolean genes (with
sheet CNN decoding card for the corner detection r = 1 neighborhoods or 3 × 3 sphere of influence)
CNN gene shown in Fig. 35 contains the same in- are there in the universe? Since every pair of CNN
formation as the 8-sheet CNN decoding book shown gene ribbons that differ by only one bit specifies
earlier in Fig. 34. Because it contains no extraneous two different input–output CNN operators T (G), it
9
information, the CNN decoding card for represent- follows that there are 22 ≈ 1.34078 × 10154 dis-
ing the input–output CNN operator T (G) of any tinct CNN Boolean genes (with r = 1 neighbor-
Boolean CNN gene G represents a minimal CNN hoods) in the universe. This gigantic number is
truth table.20 printed out in full in Fig. 40. It is an immense
The binary code for the corner detection CNN number greater than the volume of the known uni-
gene corresponding to the CNN decoding card in verse. We will see in Sec. 2.9 that every one of
9
Fig. 35 is shown in Fig. 37. The corresponding dec- these 22 Boolean CNN genes can be trivially pro-
imal number shown in Fig. 38 contains only 140 grammed into a general purpose CNN universal
digits, almost five times fewer symbols compared to chip capable of executing the program on any bi-
512 bits. nary input image of 100×100 pixels in less than one
20
The CNN decoding card in Fig. 35 is reminiscent of the ubiquitous IBM punch cards of yore, if one associates each red pixel
with a punch hole. The difference is in their information content: Each IBM punch card specifies one instruction, while each
CNN gene decoding card specifies an entire CNN “gene decoding” program!
2300 L. O. Chua
Fig. 38. The decimal code for specifying the same input–output corner detection CNN operator requires only 140 symbols.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 39. CNN gene decoding tape for specifying the input-output CNN operator T (G) of any Boolean CNN gene.
Fig. 40. The above number represents the total number of distinct Boolean CNN genes in the universe (with a 3 × 3 sphere
of influence).
CNN: A Vision of Complexity 2301
microsecond, based on the current 0.8 micron Conversely, all those patterns which must map
CMOS technology. to a blue pixel (i.e. yi,j (∞) = −1) must satisfy the
opposite inequality
2.9. What task can an uncoupled X
Boolean CNN gene perform? bkl ukl (t) + ẑij < 0 ⇒ yi,j (∞) = −1 (101)
kl∈Sij
We have already stressed the dominant role played
so far by uncoupled CNN genes, which alone ac- The class of Boolean functions satisfying the
counts for more than half of all CNN genes devel- above properties is said to be linearly separable. We
oped to date. Notwithstanding its importance as have therefore the following definitive answer to the
a workhorse for image processing and brain mod- question posed in the title of this section:
eling applications, we have also hinted in Sec. 2.7.
that not all Boolean CNN genes can be realized by Theorem 2.9.1.
uncoupled CNN’s, and that a completely general A Boolean CNN gene with a 3 × 3 neighborhood
realization must await the introduction of the all is realizable by an uncoupled standard CNN gene
powerful CNN universal machine to be presented in if, and only if, the associated 9-input Boolean truth
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Sec. 2.12. Our goal in this section is to find out ex- table is linearly separable.
actly how complex a task can an uncoupled Boolean
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2302
Fig. 41. Example illustrating the design of a one-dimensional uncoupled CNN: (a) The prescribed task to be performed, which in this case is to perform the logic “OR”
operation between each pixel and its right neighbor. (b) The corresponding CNN truth table. (c) A separating straight line. (d) Any straight line lying inside the green
region is a valid design.
CNN: A Vision of Complexity 2303
Fig. 41(c). From the intercepts of this optimized The corresponding state equation for this uncoupled
line, we obtain the equation CNN gene with a nonlinear B template is given
by:
1.5u1 + u2 + 1.3 = 0 (102)
ẋi (t) = −xi (t) + ai f (xi ) + αui
Comparing Eq. (102) with Eqs. (97)–(99) and as-
suming an initial state 21 xi (0) = 0, we readily ex- − |ui + ui+1 | + 1 , α ∈ [0, 1) (106)
tracts the following template coefficients 22 :
In the general case of a 9-Boolean input CNN
z = 1.3 , B: bi bi+1 = 1.5 1.0 , (with 3 × 3 Boolean window patterns), the pre-
scribed truth table can be represented abstractly by
A: ai ai+1 = 2 0 assigning each vertex of a nine-dimensional hyper-
The corresponding CNN gene in the one- cube with the corresponding “red” or “blue” color.
dimensional case is given by: Theorem 2.9.1 then asserts that such a Boolean
CNN gene can be realized by an uncoupled CNN
G : 1.3 1.5 1.0 2 0 (103) gene if and only if, there exists a hyperplane in R9
which separates all red pixels from the white pix-
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Boolean table to be performed and its associated Currently, there exist several versions of CNN algo-
CNN truth table are shown in Figs. 42(a) and 42(b), rithms embedded in softwares which will carry out
respectively. The corresponding “unit square” rep- this test automatically on any prescribed decoding
resentation in Fig. 42(c) clearly shows that it is im- card (CNN minimal truth table) defined in Fig. 35.
possible in this case to find a straight line capable If it is found to be linearly separable, an approx-
of separating the red pixels from the blue pixels. imately optimized hyperplane will be generated by
It follows from Theorem 2.9.1 that an uncoupled a computer program and the corresponding cloning
Boolean CNN gene defined by the standard CNN template will be printed in the computer output. If
state equation (16) (with constant template coeffi- it is not linearly separable, a realization via a CNN
cients) that can perform the above prescribed task universal machine to be described in Sec. 2.12 will
does not exist. be carried out automatically by the computer pro-
Observe, however, that there exist many non- gram [Nemes et al., 1998].
linear curves f (u1 , u2 ) = 0 which can easily sepa-
rate the “red” pixels in Fig. 42(c) from the “blue” 2.10. Bifurcation of CNN genes
pixels. One such nonlinear separating curve C is
shown in Fig. 42(c). The equation of the curve C is An examination of Example 2.9.1 shows that there
given by: are many distinct CNN genes capable of perform-
ing the same prescribed task, which in this case is
f (u1 , u2 ) = 1 − |u1 + u2 | + αu1 , to perform a logic “OR” operation between each
α ∈ [0, 1) (104) pixel Ci and its adjacent right neighbor Ci+1 . In
particular, every straight line
If we choose the threshold z = 1, ai = 2, ai+1 = 0,
bi = α, then the B template in this case has a L : b1 u1 + b2 u2 + ẑ = 0 (107)
coefficient bi+1 which is a nonlinear function of ui
and ui+1 , namely: which lies entirely inside the green region in
Fig. 41(d) represents a valid solution. An analy-
bi+1 (ui , ui+1 ) = −|ui + ui+1 | (105) sis of the geometry of the green region in Fig. 41(d)
21
It is convenient to choose xi (0) = 0 because such a choice will allow us to pick any convenient value ai which guarantees a
binary output. Here, we have chosen ai = 2.
22
Note that in terms of our standard template notation for 3 × 3 sphere of influence, the corresponding B and A templates
0 0 0 0 0 0
are: B: 0 bi bi+1 and A: 0 ai ai+1 .
0 0 0 0 0 0
2304 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 42. Example of a prescribed task which cannot be realized by a standard uncoupled CNN since no straight line can be
found to separate the two red pixels from the two blue pixels. An uncoupled CNN with a nonlinear B template endowed
with the nonlinear separating curve C in (c) can be designed to perform the prescribed task in (a).
shows that since ẑ = 1.3 > 0 for one possible choice Our goal is to find the region in the (b1 − b2 )-
of the separating straight line L, all other accept- parameter space such that Eq. (108) remains inside
able straight lines must also have the same sign; the green region in Fig. 41(d). Clearly, the follow-
namely ẑ > 0. We can therefore, without loss of ing two constraints are both necessary and sufficient
generality, divide both sides of Eq. (107) by ẑ to conditions for this condition to be true:
obtain the normalized equation23
Constraint 1
0
L : b1 u1 + b2 u2 + 1 = 0 (108) u1 = 1 ⇒ u2 < −1 (109)
23
Had the color of the pixels in Fig. 41(c) been reversed, the equation of the separating straight line would have to be changed
to −1.5u1 − u2 − 1.3 = 0 in order for Eq. (97) to give the correct answer. In this case, the normalized Eq. (108) must be
changed to b01 u1 + b02 u2 − 1 = 0.
CNN: A Vision of Complexity 2305
Substituting Eq. (109) into Eq. (108), we obtain If b2 < 0, Eqs. (111) and (112) imply b2 > b1 + 1,
b2 < b1 − 1, and b2 < −(b1 − 1) which cannot be
(b1 + 1) satisfied simultaneously.
u2 = − < −1 (111)
b2 The region in the (b1 −b2 )-parameter space cor-
Similarly, Eqs. (110) and (108) give responding to Eq. (113) with b2 > 0 is shown shaded
in Fig. 43. All CNN genes 1 b1 b2 2 0 with
(b1 − 1) two inputs such as Eq. (103), or its rescaled version
−1 < <1 (112)
b2 ẑ ẑb1 ẑb2 2 0 , where (b1 , b2 ) lies inside the
If b2 > 0, then Eqs. (111) and (112) can be com- shaded region K(0111) in Fig. 43, and for arbi-
bined as follow: trary ẑ > 0, will implement the same logic “OR”
operation, as that of Eq. (103). As soon as the
|b1 − 1| < b2 < b1 + 1 (113) parameter (b1 , b2 ) crosses the boundary ∂K(0111)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 43. Shaded region in the (b1 − b2 )-parameter space corresponds to “equivalent” CNN genes all implementing the same
Boolean function prescribed in Fig. 41(a), coded as (0111), following the same ordering scheme of Fig. 6.
Table 2.10.1. Boolean functions of two variables which are linearly separable via Eq. (107) for ẑ = 1 in (a), and ẑ = −1
in (b).
2306 L. O. Chua
of K(0111), which is an open set, the operation task upon crossing ∂K(0111). In both engineer-
changes abruptly to another Boolean function and ing and biology alike, such failures can have catas-
we say that the CNN gene has bifurcated from one trophic consequences. It is therefore of extreme im-
Boolean function into another. This phenomenon is portance to determine the failure boundary ∂K(G)
analogous to mutation in biological genes. Adopt- of a CNN gene so that its parameters may be re-
ing the language from bifurcation theory, ∂K(0111) located near the geometric center of K(G). For the
is called the bifurcation set, or failure boundary of 2-input Boolean CNN genes considered in this sec-
the Boolean function (0111) defined in Table 2.10.1, tion, the (b1 − b2 )-parameter plane is partitioned
since the CNN will fail to implement its designed into nine regions in Fig. 44(a) corresponding to
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a) (b)
(c)
Fig. 44. Bifurcation diagram for Boolean CNN genes with two input variables for (a) ẑ > 0 and (b) ẑ < 0. Each re-
gion is coded by 4 bits whose truth table is listed in Table 1. (c) three-dimensional cube depicting the distinct linearly-
separable Boolean functions of two variables in terms of the three parameters b1 , b2 , and ẑ defining the separating line in
Eq. (107).
CNN: A Vision of Complexity 2307
ẑ > 0, and another nine regions in Fig. 44(b) cor- OR, and NOT CNNs exhibited in the gallery in
responding to ẑ < 0. Observe that there are four Sec. 2.6.
common regions in Figs. 44(a) and 44(b). Together, Hence, the relevant bifurcation space for the
the 14 distinct regions in Fig. 44 correspond to standard CNN equation (16) has an immensely high
all 14 possible linear-separable Boolean functions dimension equal to 2M N + 19 (5019 parameters for
of two variables.24 All are realizable by an uncou- a modest sized 50×50 CNN array). The key concept
pled standard CNN gene in view of Theorem 2.9.1. of the input-image driven CNN is that bifurcation
In the three-dimensional (b1 − b2 − z)-parameter is allowed to take place only in a much smaller 19-
space, these 14 linearly separable Boolean functions dimensional subspace, R19 ⊂ R2M N +19 . The Venn
of two variables correspond to 14 pyramids which diagram depicting the relationship among the dif-
fit like zigsaw puzzles in a solid cube as shown in ferent subsets cited above is shown in Fig. 45.
Fig. 44(c).
For an arbitrary standard CNN gene, not nec- 2.11. The game-of-life CNN gene
essarily uncoupled or Boolean, the above analysis
can be generalized to a 19-parameter global bifurca- The game of life is one of the most widely-
tion problem (assuming a 3 × 3 sphere of influence) known discrete (finite-state) cellular automata
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
involving a system of MN coupled nonlinear differ- which evolves according to extremely simple local
ential equations for an M × N CNN. rules. Invented by John Conway as an abstraction
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Let Gρ denote any such CNN genes parameter- of real life [Berlekamp et al., 1982], it has attracted
ized by ρ ∈ R19 , and let T (Gρ ) denote its associated world-wide interests after Conway and his collabo-
input–output operator.25 Let Kρ ∈ R19 denote the rators have proved that not only is the game of life
largest open set such that all CNN genes chosen capable of universal computation as a Turing ma-
from Kρ execute the same input–output operator chine, but that it is also capable of self-replication,
T (Gρ ). Then the boundary set ∂(Kρ ) ∈ R19 of Kρ another essential condition for real life to be pos-
is the bifurcation set in the sense that the input– sible. In its original version, the game of life is
output operator T (Gρ ) changes abruptly as soon as played on an infinite grid of cells, like a checker
ρ crosses the “failure” boundary ∂(Kρ ). board. Each cell can assume one of two states, alive
For each prescribed task, it is desirable to (coded in red) or dead (coded in blue). The game
choose a CNN gene Gρ such that ρ is in the “ge- is initiated by assigning an initial state to each cell
ometric” center of Kρ . Observe that the above bi- on the checker board so that at t = 0, the board
furcation problem is actually more general in the looks like a mosaic of random juxtaposition of red
sense that given any parameter ρ ∈ R19 which and blue tiles. The game evolves in discrete times,
specifies uniquely a CNN gene Gρ , the associated t = 1, t = 2, . . . , etc. and is usually referred to in
input–output operator T (Gρ ) must remain invari- the game-of-life literature as generations 1, 2,. . . ,
ant (i.e. implements the same task) on all input etc., as an abstraction of real life events where each
images U ⊂ RM × RN . In other words, in addi- species in one generation evolves from its parents
tion to the 19 parameters (for a 3 × 3 sphere of in the previous generation, or from its parent’s par-
influence) specifying the CNN gene, there are M N ents in their previous generations, etc. From any
additional parameters uij ∈ U , i = 1, 2, . . . , M , given initial configuration of states (which corre-
j = 1, 2, . . . , N , each one specifying the gray- sponds to the input image of a CNN) at time t, each
level intensity of the input image. In fact, strictly cell Cij in the next generation t+1 evolves in accor-
speaking, there are M N more additional parame- dance with four simple local rules involving only the
ters needed to specifying the initial states xij (0), state of each of its eight nearest neighbors; i.e. the
i = 1, 2, . . . , M , j = 1, 2, . . . , N . In some CNNs, “fate” (alive or dead) of Cij at t + 1 is uniquely
this initial state is actually used to code the pixel determined by the “color” of only its eight nearest
intensity of a second image, as in the Boolean AND, neighbors Ckl ∈ Sij , where Sij denotes a 3×3 sphere
24
The two remaining Boolean functions of two variables which are not linearly separable correspond to the code (0110) and
(1001), respectively. These two Boolean CNN genes cannot be realized by an uncoupled standard CNN.
25
How to characterize and represent T (Gρ ) for arbitrary CNN genes which are neither uncoupled nor Boolean remains an
important unsolved problem.
2308 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 45. The bifurcation space R2MN+19 (shown in yellow ) associated with an M × N CNN described by the standard CNN
Eq. (16) has a dimension equal to 2MN + 19 for a 3 × 3 sphere of influence (r = 1). The bifurcation set lives inside of a
19-dimensional subspace R19 (shown in green). The point ρ ∈ R19 denotes the parameters specifying a particular CNN gene
Gρ . All CNN genes with nearby parameters K(Gρ ) ⊂ R19 , shown in blue executes the same task prescribed for Gρ . The bold
red contour is the failure boundary.
of influence as before. The four local rules are as Observe that we can define an “infinite” CNN
follow: array and identify one generation in the evolu-
tion of the game of life with the evolution of a
Local Rules For Game of Life:
CNN whose input–output gene operator T (G) co-
1. Birth: incides with the above four local rules [Chua et al.,
1993]. The corresponding pages of the CNN game-
A cell that is dead at time t becomes alive
of-life gene decoding book are shown in Figs. 46(a)–
at time t + 1 only if exactly three of its eight
46(p). The equivalent CNN game-of-life gene de-
neighbors were alive at time t.
coding card is shown in Fig. 47. Its associated gene
2. Death by overcrowding:
decoding tape is shown in Fig. 48(a) for a binary-
A cell that is alive at time t and has more than coded tape, or in Fig. 48(b) for a decimal-coded
three living neighbors at time t will be dead tape.
at time t + 1. It follows from the above equivalent decoding
3. Death by exposure: schemes that when translated into CNN language,
A cell that is alive at time t and has less than one generation of evolution in the “game of life”
two living neighbors at time t will be dead by can be duplicated exactly by applying the corre-
time t + 1. sponding initial state configuration as input image
4. Survival: of a Boolean CNN gene represented by the gene de-
A cell that was alive at time t will remain alive coding book in Fig. 46, or equivalently, by its gene
at time t + 1 if and only if it had exactly two decoding card in Fig. 47, or its gene decoding tape
or three alive neighbors at time t. in Fig. 48.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 46.
The CNN game-of-life gene decoding book.
CNN: A Vision of Complexity 2309
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2310 L. O. Chua
Fig. 46.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 46.
(Continued )
CNN: A Vision of Complexity 2311
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2312 L. O. Chua
Fig. 46.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 46.
(Continued )
CNN: A Vision of Complexity 2313
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2314 L. O. Chua
Fig. 46.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 46.
(Continued )
CNN: A Vision of Complexity 2315
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2316 L. O. Chua
Fig. 46.
(Continued )
CNN: A Vision of Complexity 2317
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
Fig. 48. The CNN game-of-life gene decoding tape. (a) Binary decoding tape. (b) Decimal decoding tape.
2318 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
(b)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
It can be proved that the CNN game-of-life CNN Cloning Template for G1 (game of life)
gene is not linearly separable and hence cannot
be implemented, even conceptually, by an uncou- −1 −1 −1 0 0 0
pled standard CNN gene. However, it is proved z: −1 , B: −1 0 −1 , A: 0 2 0
in [Crounse & Chua, 1996] that by applying the −1 −1 −1 0 0 0
initial state configuration U as the input image
U1 = U2 = U simultaneously to two uncoupled (114)
CNN genes G1 and G2 , and then feeding the respec-
tive steady-state outputs Y1 (∞) and Y2 (∞) into CNN Cloning Template for G2 (game of life)
a Logic AND CNN gene (exhibited in the CNN
gallery in Sec. 2.6), as shown in Fig. 49, the result- 1 1 1 0 0 0
ing composite binary output image Y (∞) is pre- z: 4 , B: 1 1 1 , A: 0 2 0
cisely that prescribed by the game-of-life gene. The 1 1 1 0 0 0
two component CNN genes G1 and G2 are defined (115)
as follow:
The corresponding CNN genes are given by:
G1 (game of life) : −1 −1 −1 −1 −1 0 −1 −1 −1 −1 0 0 0 0 2 0 0 0 0
(116)
G2 (game of life) : 4 1 1 1 1 1 1 1 1 1 0 0 0 0 2 0 0 0 0 (117)
Fig. 49. The CNN game-of-life gene can be realized by applying the CNN logic AND operation to two linearly-separable
CNN genes G1 (game of life) and G2 (game of life).
Fig. 50. (a) Decoding card for G1 (game of life). (b) Decoding card for G2 (game of life).
2320 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 51. A CNN program ribbon, called a CNN chromosome, containing the three CNN genes shown in the flow chart of
Fig. 49, as well as some “housekeeping” codes which play the role of “operating systems” in digital computers.
a CNN program ribbon, henceforth called a CNN in which each gene is to be activated, and where the
chromosome, which contains the information from respective inputs are located.
the three CNN genes specified in the flow chart, Clearly, these “housekeeping” codes are needed
plus some other “codes” labeled as “housekeeping” for the same reason that an “operating system”
codes which specify, among other things the order is needed in every digital computer in order for
CNN: A Vision of Complexity 2321
the computer to know how the instructions from a The game-of-life implementation in Fig. 49 pro-
user’s computer program is to be processed. vides an example illustrating how a complex task
It is possible to realize the game-of-life CNN which cannot be implemented by a single CNN gene
gene decoding book in Fig. 46 by a standard CNN may be realized by a combination of several CNN
with nonlinear template coefficients, as in Exam- genes, (called a CNN chromosome), each one spe-
ple 2.9.2. In this case, the game-of-life CNN gene cializing in a particular task, via a flow chart, or al-
will contain not only the usual constant template gorithm similar to that used for developing digital
coefficients, but additional parameters defining the computer programs. The only difference between
nonlinearities. Note that the resulting “ribbon” in the flow chart of Fig. 49 and a digital computer
this case still represents a CNN gene, and not a flow chart, is that the operations performed by the
CNN chromosome, because it pertains to only one CNN genes G1 (game of life) and G2 (game of life) in
CNN cell. Fig. 49 are continuous time (or analog operations
in electrical engineering jargons) whereas those per-
formed by digital computers are strictly “discrete”
2.12. The CNN universal machine in nature. Observe, however, that the CNN flow
chart in Fig. 49 calls for a logic AND operation
The original motivation which had led to the in-
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
neural network architecture to replace the theoret- values are irrelevant in so far as the AND operation
ically exciting Hopfield net [Hopfield, 1985], which is concerned: The output is uniquely determined
unfortunately cannot be built, even in modest array by the binary input signals Y1 (∞) and Y2 (∞). Im-
sizes, as VLSI (very-large-scale-integrated) circuits plicit in this flow chart is the assumption that the
— the technology responsible for the current revolu- outputs of the G1 (game of life) and G2 (game of
tion in micro-electronics. The reason why the glob- life) CNN are not applied to the logic “AND” CNN
ally connected Hopfield architecture is impractical until some minimum settling time (approximately
is because the number of wires and circuitry needed 250 nanoseconds (10−9 seconds) in current tech-
to electrically connect each cell to every other cell in nology) has elapsed in order to ensure that both
a fully-connected Hopfield network grows exponen- G1 and G2 have attained their steady states. Since
tially with the size of the array. The CNN was in- this flow chart involves both “analog” and “logic”
vented to circumvent this “curse of interconnecting operations, we will henceforth call the associated
wires” by decreeing that there should be no electri- program an analog-logic program, or simply an ana-
cal interconnections beyond a prescribed sphere of logic program.
influence [Chua & Yang, 1988]. Most brain functions in the human brain
The first CNN chip (based on a 3 × 3 neighbor- worked in a similar “analogic” mode: They are not
hood) was built and demonstrated to work robustly implemented in a single stroke via some highly in-
barely three years after the filing of the first of sev- telligent neurons, but instead each complex task is
eral CNN-related patents. The demonstration of decomposed into a serial and/or parallel sequence
this fully-working CNN chip had sparked visions of of relatively simple tasks via different groups of
mass-produced dedicated CNN chips as inexpensive neurons, called function specialization groups [Zeki,
off-the-shelf components, each one endowed with a 1994], each specialized in a particular task, such as
particular CNN gene. The advantage of using a detecting “edges” having a certain orientation, or
CNN chip to implement a gene’s prescribed task moving at a certain speed. Moreover, recent phys-
via its device physics, and not by programming via iological measurements [Salmelin et al., 1994] us-
a digital computer, is in the immense increase of the ing advanced instrumentation have revealed that it
computing speed S, typically three orders of magni- takes a certain amount of time (tenths of millisec-
tude faster than its closest competitor, a digital sig- onds) for various function-specialized neuron groups
nal processor (DSP) having the same silicon area. to complete their prescribed tasks, before other neu-
In addition, it consumes significantly less electrical ron groups higher up in the brain hierarchy (i.e.,
power P , and occupies much less silicon area A. further down the flow chart) can respond — just
This orders-of-magnitude superiority in combined like the game-of-life implementation in Fig. 49.
“SPA” measure is the raisin d’etre of the current Another physiological evidence which suggests
intense research activities on CNNs. that the human brain uses both analog and logic
2322 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
signal processing modes comes from the “Japanese (d) Some global unit with communication channel
brain” syndrome where Japanese car accident pa- to each cell and to communicate with the out-
tients suffering from injuries to their left brains can side world (similar to those performed by the
no longer interpret the Japanese Kana alphabets, “operating system” in digital computers).
whereas those suffering from injuries to their right
brains can no longer understand the Japanese Kanji A CNN whose cells are endowed with the above
characters.26 Since interpreting a word made up of modest set of programming features, or other equiv-
alphabets, or symbols, is essentially a serial logic alent capabilities, will make it possible to design
operation, whereas decoding a picture-like Chinese a von Neumann stored-program computer where
character is a “holistic” operation similar to paral- any flow chart or algorithm involving only logic
lel analog operations, one can infer that a part of operations (such as AND, OR, NOT, XOR, etc.),
the left brain is responsible for interpreting sequen- and CNN genes, can be programmed and executed
tial tasks via logic operations, whereas a part of the in the same way as in a digital computer. A
right brain is responsible for decoding parallel tasks working prototype of such a stored-program CNN
via analog operations. VLSI chip (fabricated in 0.8 micron CMOS tech-
We can mimic some of the “analogic” brain pro- nology) is shown in Fig. 52 [Cruz & Chua, 1997].
cessing algorithms by endowing upon each CNN cell The schematic diagram of a typical standard CNN
the following additional capabilities via electronic cell (excluding the routine programming circuitry,
circuitry (described formally in the CNN universal which is omitted to expose only the central core of
machine architecture [Roska & Chua, 1993]): the CNN cell) corresponding to the center cell in
(a) A local analog memory within each cell capable Fig. 5 [described by Eqs. (10) and (11)] is shown in
of storing continuous signals from either exter- Fig. 53. The circuit enclosed within the large yellow
nal or internal sources. box in Fig. 53 is the CMOS transistor circuit imple-
(b) A local logic memory within each cell capable mentation of the isolated standard cell [described by
of storing discrete-time signals from either ex- Eqs. (5) and (6) and depicted in Fig. 3]. The circuit
ternal or internal sources. shown in Fig. 54 implements the “control” (feedfor-
(c) Some local control and communication circuitry ward) synapse described by Eq. (8), and the “feed-
in each cell for “house keeping” tasks, and com- back” synapse described by Eq. (9). Two such CNN
munications with a global unit. synapses are therefore needed to couple the center
26
The Japanese language is made up of “serial” alphabets called Kana, and “picture-like” Chinese characters called Kanji.
CNN: A Vision of Complexity 2323
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 53. CMOS transistor circuit for implementing the central core of a standard CNN cell described by Eqs. (10) and (11),
where the nonlinear function f (·) is given by Eq. (6).
Fig. 54. A typical CMOS transistor circuit for implementing either Eq. (8) for a “feedforward” CNN synapse, or Eq. (9) for
a “feedback” CNN synapse.
2324 L. O. Chua
cell Cij in Fig. 5 to each neighbor cell Ckl located within its sphere of influence Sij (r), where r = 1
(3 × 3 neighborhood) in Fig. 5. The schematic diagram of a complete standard cell (excluding the routine
programming circuitry) for implementing any CNN gene
G: z b33 b32 b31 b23 b22 b21 b13 b12 b11 a33 a32 a31 a23 a22 a21 a13 a12 a11
Fig. 55. Schematic circuit diagram of a complete CNN cell, including circuitry for implementing the threshold, the nine feedfor-
ward synaptic weights {b11 , b12 , b13 , b21 , b22 , b23 , b31 , b32 , b33 } and the nine feedback synaptic weights {a11 , a12 , a13 , a21 , a22 ,
a23 , a31 , a32 , a33 }.
The prototype CNN universal chip shown in at a computing speed of 1 tera (1012 ) analog instruc-
Fig. 52 consists of an array of 16×16 identical cells, tions per second, for a 100 × 100 array. For many
each one endowed with a full repertoire of program- image processing applications, this immense speed
ming circuitry to make it a fully programmable dy- surpasses the computing power of some current su-
namic array computer in a chip. The entire chip percomputers, thereby making it a “supercomputer
contains approximately 60 000 CMOS transistors, on a chip”.
all crammed within a single silicon chip with an area In order to allow users to readily program any
of 5.5 mm × 4.7 mm. The chip consumes 0.3 watts CNN flow chart, or algorithm, such as that specified
of electrical power. The input is any gray-scale im- by a CNN chromosome, a user-friendly C-like high-
age, where the gray-level intensity of each pixel Cij level language, called the α-language, as well as a
in the image is scaled and converted into a voltage CNN operating system, and an α-language compiler,
vij ∈ [−1, 1]. The measured transient settling time have been developed at Professor T. Roska’s Ana-
for the entire chip is approximately 250 nanoseconds logical and Neural Computing Laboratory in Bu-
(0.25 × 10−6 seconds). dapest, Hungary [Roska & Chua, 1992, Zold, 1997;
Based on the performance of the above CNN Roska et al., 1993].
universal chip and the other operational prototype In a typical real-world application, a CNN prog-
with optical sensors in each cell [Dominguez-Castro ram for implementing a desired task, as pro-
et al., 1997], we can readily extrapolate it to arrive grammed by a CNN chromosome, will be written
CNN: A Vision of Complexity 2325
using the user-friendly α-language, as depicted in 6. Load the subroutine for the CNN gene
Fig. 56. This program is then downloaded into a called G2 (game of life).
personal computer, along with a library of CNN 7. Run G2 (game of life).
subroutines containing a collection of CNN genes, 8. Store the output Y2 (∞) of G2 (game of life)
such as those listed in the CNN gallery. With the in local logic memory location 3.
help of an α-language compiler, and a CNN oper-
9. Apply the logic AND operation to the con-
ating system, the high-level CNN program is trans-
lated automatically into a CNN machine language, tents of local logic memory locations 2 and
which contains the complete sequence of machine- 3 and call the output Y (∞).
level instructions for executing the CNN program. 10. Replace the content of local memory loca-
It is important to realize that all instructions are ex- tion 1 by the output Y (∞) from Step 9 and
ecuted automatically exactly like those taking place repeat Steps 2–10 a total of K times, where
inside conventional digital computers. However, un- K is the user prescribed “number of gen-
like a digital computer where the processing sig- erations” where the Game-of-Life Boolean
nals are continuously being routed from one sub- function is to be iterated.
unit (e.g. CPU) to another (e.g. memory), thereby
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
consuming valuable processing time, no signal ever Observe that the flow chart in Fig. 49, or
leaves the CNN universal chip until all processing is equivalently, the associated CNN chromosome in
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
completed. This is because the CNN is a complete Fig. 51, is implemented in its entirety in Steps 1
computing array equipped with all essential mem- to 9. Step 10 is not a part of the Game-of-
ory and programming subunits within every cell. It Life CNN chromosome but is included in this pro-
is therefore a completely self-contained supercom- gram in order to illustrate how the classic cellu-
puter on a chip. lar automata paradigm [Von Neumann, 1966; Wol-
fram, 1984; Toffoli & Margolis, 1987], of which
Example. Programming the Game-of-Life the game of life is a generic example, can be triv-
Chromosome. ially implemented by the CNN universal chip by
The game-of-life Boolean function, which is not adding just one more instruction, namely, a “CNN
linearly separable, can now be easily implemented DO LOOP”.
on the CNN universal chip by simply writing a CNN The above program also provides a simple way
program, via the high-level α-language, to execute to prove the following rather fundamental result.
the flow chart shown in Fig. 49, or equivalently, the
associated CNN chromosome shown in Fig. 51. In
Theorem 2.12.1. CNN Turing Machine Theorem
plain English, the pseudo code for the game-of-life
[Chua et al., 1993; Crounse et al., 1997].
Boolean function is as follows:
The CNN universal machine (implemented in a
chip) is a universal Turing machine.
GAME-OF-LIFE CNN PROGRAM
1. Store the user specified initial life configu- Proof. Since the above CNN program gives a con-
ration in local logic memory location 1 at structive way to execute the “game of life” on
each pixel. the CNN universal chip, and since the “game of
2. Load the subroutine for the CNN gene life” cellular automata has been proved by Conway
called G1 (game of life).27 [Berlekamp et al., 1982] to be a universal Turing
3. Copy the content of the local logic memory machine, it follows that the CNN universal chip is
location 1 and apply it as input of G1 (game also a universal Turing machine. Indeed our choice
of life). of the name “CNN universal chip” was inspired by
this theorem.
4. Run G1 (game of life).
5. Store the output Y1 (∞) of G1 (game of life)
in local logic memory location 2. We close this section by proving another fun-
damental theorem.
27
Each instruction for loading a CNN subroutine for a CNN gene includes the setting of the 19 template parameters, as well
as the associated boundary and initial conditions from the CNN library of subroutines.
2326 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 56. Schematic diagram depicting the typical steps in programming and executing a CNN program for implementing a
prescribed task.
Theorem 2.12.2. CNN Boolean Gene Realization It suffices for us to prove therefore that every
Theorem. “one-black-pixel” CNN min-term gene is linearly
9
Every member of the family of 22 = 2512 separable. Without loss of generality, pick an arbi-
Boolean functions of nine variables can be real- trary CNN min term gene, say the one where only
ized by a CNN chromosome containing at most the following 3 × 3 window pattern (correspond-
512 linearly separable CNN genes and logic OR ing to window pattern no. 58, where red pixels are
operations. coded by “1” and blue pixels by “0”) maps to a
black pixel (all other 3 × 3 window patterns must
Proof. Every Boolean function B of nine variables map to a white pixel, by definition):
is uniquely represented by a CNN decoding card window pattern 58
with 512 entries, as shown in Fig. 35. Let ρ(B)
denote the total number of “black” pixels in an 0 0 0
arbitrarily prescribed Boolean function B, where B= 1 1 1 7→ 1 (118)
0 ≤ ρ(B) ≤ 511. Define ρ(B) CNN genes, called 0 1 0
the “min-term genes”,28 each of which is defined
uniquely by a gene decoding card having exactly one In terms of our Binary Array Labeling Conven-
black pixel which coincides with one of the ρ(B) tion in Fig. 6, this window pattern has the following
black pixels in the gene decoding card for B. Con- binary code:
sequently, by performing a logic OR operation on all
[b9 b8 b7 b6 b5 b4 b3 b2 b1 ] = [000111010]
of the ρ(B) “one-black-pixel” CNN min-term genes,
we would recover the decoding card for B. = 58 (119)
28
Such a CNN gene is called a min-term gene because its associated Boolean truth table is called a min-term Boolean func-
tion in computer science. Such a function conveys the minimum amount of information; namely, only one out of 512 bits
represented the Truth (1). All other bits are False (0).
CNN: A Vision of Complexity 2327
where the lower-right corner corresponds to “b1 ”, For a linearly-separable uncoupled CNN (since
and the upper-left corner corresponds to “b9 ”, Let aij = 2 > 1, and akl = 0, kl 6= ij), the output of
us choose the following template: cell Cij is given by Eqs. (80) and (81):
" # " #
X
9 X
9
bˆ9 bˆ8 bˆ7 yij = sgn b̂i ui + z = sgn b̂i bi − 8
−1 −1 −1
i=1 I=1
z = −8 , B = bˆ6 bˆ5 ˆ
b4 = 1 1 1 ,
−1 1 −1 =1 if b̂i = bi for all i = 1, 2, . . . , 9
bˆ3 bˆ2 bˆ1
= −1 if b̂i = 0 for at least one
0 0 0 i ∈ {1, 2, . . . , 9} (122)
A= 0 2 0
0 0 0 Since the case b̂i = bi for all i = 1, 2, . . . , 9 cor-
(120) respond to the only min-term pattern specified by
the binary code in Eq. (119), the output of pixel
with initial state xij (0) = 0, where Cij is black only for this case. It follows that the
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
G : −8 b̂9 b̂8 b̂7 b̂6 b̂5 b̂4 b̂3 b̂2 b̂1 0 0 0 0 2 0 0 0 0 (123)
the inputs u1 , u2 , and u3 of 3 adjacent cells ci−1 , ci , to the 104 Boolean cubes identified by red deci-
and ci+1 , respectively, and by identifying xi (t + 1) mal numbers. Each of these 104 linearly-separable
with the steady state output y2 = limt→∞ yi (t) of Boolean functions of three variables can be imple-
cell ci . mented by a CNN by iterating a one-dimensional
3
Since there are only 22 = 256 distinct Boolean CNN with the template
functions of three variables, it is instructive to iden-
tify each of the 23 = 8 distinct 3-bit binary word z , B = b3 b2 b1 , A = a3 a2 a1
(xi−1 , xi , xi+1 ) = (b3 , b2 , b1 ) with a vertex in a
three-dimensional cube with its center located at (125)
the origin, as depicted in the lower left portion of
Fig. 57, and to code the Boolean function by color- or equivalently, by a CNN gene with seven real num-
ing each vector (b3 , b2 , b1 ) red if B(b3 , b2 , b1 ) = 1, ber entries; namely,
and blue if B(b3 , b2 , b1 ) = 0. In other words, in-
G: z b3 b2 b1 a3 a2 a1 (126)
stead of specifying a particular Boolean function of
three variables via a truth table
The corresponding CNN gene decoding card in this
case is a one-dimensional “tape” with 256 binary
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
u1 u2 u3 y2
number entries. This represents a data compres-
−1 −1 −1 γ7
sion of approximately 36 times.
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
−1 −1 1 γ6
Each of the 256 Boolean functions depicted in
· · · · Fig. 57 defines a one-dimensional 2-state cellular au-
1 1 1 γ0 tomata with an r = 1 neighborhood. Such a cellular
automata is equivalent to iterating a correspond-
where (γ7 , γ6 , . . . , γ0 ) denotes an 8-bit binary word, ing CNN gene (for the linearly-separable case), or a
we color the eight vertices of the “Boolean cube” in CNN chromosome (if the gene is not linearly sepa-
Fig. 57 as follows: rable) in a “CNN DO LOOP”, as in the “game-of-
vertex (u1 , u2 , u3 ) = red, if y2 (u1 , u2 , u3 ) = 1 life” cellular automata.
Similarly, a two-dimensional 2-state cellular au-
= blue, if y2 (u1 , u2 , u3 ) = 0 tomata with an r = 1 neighborhood is equivalent to
Each one of the 256 Boolean cubes in Fig. 57 is iden- iterating either a CNN gene (if the Boolean func-
tified by a decimal number 0 ≤ K10 ≤ 255, where tion is linearly separable), or a CNN chromosome
K10 = (γ7 , γ6 , . . . , γ0 )2 is the base-10 decimal in a CNN DO LOOP. Let us pause to look at an
equivalent of the binary number (γ7 , γ6 , . . . , γ0 ). illustration of a two-dimensional cellular automata
In other words, the decimal number below each simulated by a a CNN chromosome on the CNN
Boolean cube in Fig. 57 serves two purposes: (1) as universal chip.
an identification number, and (2) when converted
into a binary word, it specifies the output column Example. Two-Dimensional “Parity Rule” Cellu-
of the truth table as well. In addition, this dec- lar Automata
imal identification number is printed in red if the Consider the pixel-wise parity detection CNN
corresponding Boolean function is linearly separa- gene G from the CNN gallery in Sec. 2.6. For any
ble. Otherwise, it is printed in blue. For example, binary input pattern, this CNN gene maps each in-
the Boolean cube number “5” in Fig. 57(a) maps put pixel uij into an output pixel yij in accordance
into γ7 γ6 · · · γ1 γ0 = (0000101)2 = 510 where only with the following parity rules:
the vertices (1, 1, 1) and (1, −1, 1) are painted red.
Moreover, this Boolean function is linearly separa- (1) yij = 1, if the total number of black pixel Ckl
ble since the identification number five is printed (i.e. ukl = 1), kl ∈ Sij , including pixel Cij ,
in red. The Boolean cube number (000010)2 = 6 is an odd number, where Sij in this case is
has the two vertices (1, −1, 1) and (1, 1, −1) also assumed to be a von Neumann neighborhood
∆
printed red. However, since the number “6” in Sij = {Ci−1,j , Ci,j , Ci+1,j , Ci,j−1, Ci,j+1 } with
Fig. 57(a) is printed in blue, this Boolean function five neighbors, i.e. the two adjacent horizon-
is not linearly separable. tal and vertical cells, as well as the cell Cij
All together, there are 104 linearly separable itself.
Boolean functions of three variables, corresponding (2) yij = −1, if otherwise.
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 57. All Boolean functions of three variables can be represented by 256 Boolean cubes each of whose vertices is painted
in red if the corresponding Boolean function is “1” and painted in blue if the corresponding Boolean function is “0”.
2329
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 57.
2330
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
Fig. 57.
2331
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(d)
Fig. 57.
2332
(Continued )
CNN: A Vision of Complexity 2333
Fig. 58. The CNN chromosome for coding the pixel-wise parity rule. To conserve space, the “ribbon” is cut at two points
and joined. The logic OR and the logic AND CNN genes are not listed since they can be retrieved from the CNN gallery in
Sec. 2.6.
Observe that the above “parity rule” CNN gene ate of this CNN chromosome generated by feeding
requires a nonlinear template since its Boolean the CNN’s steady-state output back into its input
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
function is not linearly separable. Alternatively, is equivalent to one iteration of the corresponding
we can realize the above “parity rule” by a CNN cellular automata.
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
t=1 t=5
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
t = 50 t = 100
t = 200 t = 500
Fig. 59. Pattern generated by the “parity rule” CNN chromosome from 17 different generations: t = 1, 5, 50, 100, 200, 500,
10 000, 10 001, 10 002, 10 003, 10 004, 10 005, 80 001, 80 002, 80 003, 80 004, 80 005, and 80 006. The size of the CNN array is
101 × 101. The color code is: red pixel = 1, blue pixel = −1. The boundary condition is periodic.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
t = 10 004
t = 10 002
t = 10 000
Fig. 59.
2335
(Continued )
t = 10 005
t = 10 003
t = 10 001
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
2336 L. O. Chua
t = 80 005
t = 80 003
t = 80 001
Fig. 59.
(Continued )
t = 80 006
t = 80 004
t = 80 002
CNN: A Vision of Complexity 2337
t = 0.
Step 1
• If the B template is not identically zero,
apply initial cellular automata configuration
yij (t) from generation “t” as the CNN input
uij and set the initial state xij (0) prescribed
by the CNN gene G (resp., CNN chromosome
C) for i = 1, 2, . . . , M ; j = 1, 2, . . . , N .
Fig. 60. Venn diagram of the CNN genome with three
subclasses identified: Class C(A(0) ), class C(A(1) ) and class
If the B template is zero, apply yij (t) as the
C(A(2) ). The part of class C(A(0) ) which lies outside of class initial state xij (0).
C(A(1) ) corresponds to the class of uncoupled CNNs with non-
binary (grey-scale) steady-state outputs. The remaining yet
• Run the CNN universal chip until it settles
unidentified areas in the Venn diagram cover all other CNN to a constant output yij (∞) (approximately
chromosomes, including those containing CNN genes which 0.25 × 10−6 second with current CNN univer-
exhibit spatio-temporal chaos. sal chip).
• Read out the generalized cellular automata
output yij (t + 1) = yij (∞) for the next gener-
the perspective of classical cellular automata where ation t + 1.
a local rule or truth table is assumed to be given
a priori. Step 2. Apply yij (t + 1) in place of yij (t) in
From the perspective of a CNN universal chip, Step 1 and repeat Steps 1 and 2 (via CNN DO
however, since the propagation time grows only lin- LOOP instruction).
early with max(M, N ) for an M × N array, the
extreme speed (nanosecond time scale) of current Remarks
CNN universal chips will still make it computation-
ally efficient when operating in a cellular automata (1) Although the above 2-step GCA algorithm is
mode. We will henceforth refer to this much larger trivial to program, it can be easily incorporated
class of cellular automata as generalized cellular au- as “hardware” inside the CNN universal chip so
tomata, or by its acronym GCA. that a single instruction “Load and Run GCA”
29
Recall a CNN template is said to be completely stable if and only if all trajectories, starting from any initial state, tend to
an equilibrium state, for any constant input uij , i = 1, 2, . . . , M; j = 1, . . . , N.
2338 L. O. Chua
suffices to implement any generalized cellular usual scheme; namely, from the bottom-right corner
automata.30 (k = 0) to the upper-left corner k = M N − 1 = 19.
(2) If the B template is zero, the GCA will con- By assumption, each input pixel uk in Fig. 61(a)
verge to the same pattern after one iteration. is either black (uk = 1) or white (uk = 0). Con-
However, more complicated patterns can occur sequently, we can code each input pattern Ui by a
if the CNN gene is not completely stable. σ-bit binary number, where σ = M N = 20 in this
example; namely,
Observe that since the input uij , or the out-
put yij , of each cell in the CNN universal chip may Ui = α19 α18 α17 · · · α3 α2 α1 α0 , αk ∈ {0, 1}
be in gray-scale or binary value, depending on G
(resp. C), we can classify the universe of all Gen- By assumption, the corresponding output pat-
eralized Cellular Automata into the following four tern Yi is also binary and therefore can be similarly
operating modes: represented by a σ-bit binary number
GCA-4: Binary Input Binary Output GCA dition as prescribed by the CNN gene G, and nu-
merically integrate the associated system of M N
ordinary differential equations [Eq. (10)] to obtain
The first three operating modes are in general
a binary output Yi = B(Ui ) for each of the γ input
outside of the domain of classical 2-state cellular
automata. Since the term “gray-scale” includes “bi- patterns. In other words, we can in principle con-
nary” as a special case, the first three classes can struct a decoding book for any CNN gene G ∈ A(2)
be lumped into the class of non-classical generalized (resp., any CNN chromosome C ∈ C(A(2) )), which
cellular automata. operates in a GCA-4 mode as in Fig. 34 for the un-
Observe that classical 2-state cellular automata coupled case C ∈ C(A(0) ). In this case, however,
belongs to the relatively small subset of GCA-4. the decoding book will be much thicker as it will
Uncovering the properties and new phenomena ex- contain γ = 2σ = 220 distinct input patterns, each
hibited by the remaining classes of generalized cellu- one resulting in a binary output pattern determined
lar automata will no doubt pose a challenging prob- by solving Eq. (10). Consequently, each binary in-
lem for the next century. put vector Ui now maps to a binary output vec-
For those CNN genes and chromosomes belong- tor Yi , instead of a single black or white “bit” in
ing to the class C(A(2) ) in Fig. 60 which operate in Fig. 34.
a GCA-4 (binary-input binary-output) mode, it is Let us organize the decoding book as shown
possible to characterize their outputs by a global in Fig. 61(b), where each row contains a decimal
Boolean function. However, unlike Definition 2.8.3 identification number “n” at the left most column,
where the steady-state output yij (∞) of each cell where n = 0, 1, 2, . . . , γ − 1 (recall γ = 2σ = 220 is
Cij can be determined uniquely from the pattern of the total number of distinct M × N = 5 × 4 binary
only the cells Ckl located inside the sphere of in- input patterns). To the right of “n”, these corre-
fluence Sij of Cij , the output yij (∞) of each cell spond to a σ-bit (σ = M N = 20 in this example)
now depends in general on the input ukl from all binary number
cells in the array, as in the global connectivity de-
tection CNN. For example, consider the M × N = β̂n = [β]nσ−1 [β]nσ−2 [β]nσ−3
5 × 4 CNN array shown in Fig. 61(a) where the
· · · [β]n3 [β]n2 [β]n1 [β]n0 (127)
M ×N = 20 pixels are labeled consecutively via the
30
Readers who do not have access to a CNN universal chip can simulate Steps 1 and 2 on a digital computer by inte-
grating the associated system of ordinary differential equations. Several user-friendly software packages are available from
various sources, e.g. [Hänggi & Moschytz, 1997; Roska & Chua, 1992]. Consult also the following world wide web listings:
(1) http://www.isi.ee.ethz.ch/˜haenggi/CNNsim.html (2) http://lab.analogic.sztaki.hu/matcnn/index.html
(3) http://apx00.physik.uni-frankfurt.de/e ag rt/cnn/SCNN
CNN: A Vision of Complexity 2339
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
(a) (b)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
Fig. 61. (a) A 5 × 4 binary input pattern maps into a 5 × 4 binary output pattern. (b) A decoding book for CNN gene
G ∈ C(A(2) ) with binary input and binary outputs. (c) A CNN gene decoding ribbon associated with the decoding book in
Fig. 61(b).
where [β]nk ∈ {0, 1}, k = 0, 1, 2, . . . , σ − 1, which as a binary input pattern (when expressed in bi-
codes the output pattern determined by Eq. (10). nary form). Moreover, since the left column in the
Just as in Eq. (95), we will let the following decoding book of Fig. 61(b) remains invariant, only
binary equivalent of the decimal number “n” the σ-bit row vector contains the output pattern in-
formation, obtained by solving Eq. (10). Hence, we
n(10) = β19 (n)β18 (n)β17 (n) · · · β3 (n)β2 (n)β1 (n)β0 (n) , can further compress these information into a de-
coding tape with γ entries, as shown in Fig. 61(c),
βk (n) ∈ {0, 1} , k = 0, 1, 2, 3, . . . , 17, 18, 19 , where each entry contains a corresponding σ-bit bi-
nary number β̂n defined in Eq. (127). This gene de-
code a binary input pattern. In other words, as be- coding tape is uniquely defined for each CNN gene
fore, the number “n” serves two roles: (1) as a dec- G ∈ C(A(2) ) provided all input and output pat-
imal input pattern identification number, and (2) terns are binary. There are three basic differences
2340 L. O. Chua
between this decoding tape and that of Fig. 39 in- of mainly conceptual value as it is impractical to
troduced earlier for uncoupled CNN genes: (1) This numerically integrate Eq. (10) even for a small size
tape contains γ = 2M N entries, compared to only array, say M = N = 10.
29 = 512 entries in Fig. 39; (2) the content of each Let us consider next two specific CNN genes
entry in Fig. 61(c) is a σ-bit (σ = M N ) binary num- and choose a small CNN array size (2 × 3 in the fol-
ber, compared to a single binary bit in Fig. 39; and lowing examples) so that we can present the com-
(3) the content of each entry in Fig. 61(c) can only plete global Boolean map needed to define a gen-
be determined in general by integrating the associ- eralized cellular automata. Let us assume a peri-
ated system of M N nonlinear differential equations odic boundary condition and zero initial condition
[Eq. (10)] with the initial condition prescribed by xij (0) = 0. Observe that for periodic boundary
the CNN gene. In contrast, the content of each conditions some parameters in the following CNN
entry in Fig. 39 can be determined directly from genes are redundant.
explicit algebraic formulas given in Theorem 2.8.1.
Needless to say, the decoding tape in Fig. 61(c) is Example 1.
Consider the following CNN gene:
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
a = |yi,j−1 + yi−1,j − yij | − |yi,j+1 + yi−1,j − yij | + |yi,j+1 + yi+1,j − yij | − |yi+1,j + yi,j−1 − yij |
Fig. 62. (a) Global gene decoding book for the CNN gene G from Example 1 for a 2 × 3 array size. (b) The truth table
associated with the 64 distinct input patterns, listed in the same order as Fig. 62(a). The output pixels “yi ” are ordered from
the bottom-right corner (y0 ) to the upper-left corner (y5 ). (c) Corresponding gene decoding tape where the “64” binary output
patterns in Fig. 62(a) are listed in the same order along the tape. (d) Eight iterations (at t = 1, 5, 10, 15, 20, 25, 40, 41) of
the associated generalized cellular automata. The same pseudo-color code in Fig. 63(b) is used throughout.
2341
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2342 L. O. Chua
(b)
Fig. 62.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2343
(c)
Fig. 62.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(d)
2344 L. O. Chua
Fig. 62.
(Continued )
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 63. (a) Global gene decoding book for the CNN gene G for Example 2 for a 2 × 3 array size. (b) Corresponding gene
decoding tape. (c) Eight iterations (at t = 1, 5, 10, 15, 20, 25, 26, 27) of the associated generalized cellular automata. The
same pseudo-color code in Fig. 63(b) is used throughout. (d) Six output patterns from a more complex CNN gene. The size
of the array is 91 × 91.
2345
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2346
(b)
Fig. 63.
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
Fig. 63.
(Continued )
CNN: A Vision of Complexity 2347
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(d)
2348 L. O. Chua
Fig. 63.
(Continued )
CNN: A Vision of Complexity 2349
A great variety of GCA with virtually end- ing more complex CNN genes. For example, let us
less variations in gray-scale (or multiple pseudo col- change the threshold and the B template from the
ors) output patterns can be constructed by choos- above gene to obtain the following CNN gene:
G: 0 0 0 0 0 b 0 0 0 0 0 0 0 0 a 0 0 0 0
where “a” is as defined above, and where
b = f |ui,j−1 + ui,j+1 | + |ui,j+1 + ui−1,j | + |ui−1,j + ui+1,j | − ui,j − 4
Fig. 64. Snap shots showing the time evolution of the dynamics of the CNN image restoration “chromosome” program.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2350 L. O. Chua
Fig. 64.
(Continued )
CNN: A Vision of Complexity 2351
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 65. Flow chart for the CNN image restoration program.
the GCA-1 mode is in general much more complex much as possible. This problem is quite difficult
than a classical 2-state cellular automata. and cannot be solved using standard linear image
processing techniques. Nor can it be solved by using
2.14. A glimpse at some real-world a single standard CNN gene (i.e. a linear CNN tem-
CNN applications plate). However, by applying the flow chart shown
in Fig. 65 where only two standard CNN genes listed
We close Part I of this exposition with a few exam- in the CNN gallery in Sec. 2.6 are used; namely,
ples of real-world applications of the CNN universal the erosion CNN gene and the dilation CNN gene,
machine. a CNN program (i.e. a CNN chromosome) writ-
ten in α-language can be downloaded into the CNN
CNN Application 1 : Image Restoration universal chip to solve this problem in less than 1
Consider the image31 shown in Fig. 64(a) and its microsecond. Several “computer simulated” snap
corrupted version in Fig. 64(b), where both the shots of the time evolution of this CNN program
cracks and the “salt-and-pepper” noise had spoiled are shown in Figs. 64(c)–64(j). Observe that all
its artistic quality. Our goal is to repair this image of the cracks and pepper noise had been “eroded”
by “erasing” the “cracks”, the “salt” noise (extra- away after 2 erosions as shown in Figs. 64(c) and
neous white particles in black background), and the 64(d). Observe, however, that the erosion process
“pepper” noise (extraneous black particles in white had made the “salt” noise worse by peeling off the
background), while preserving the original image as black pixels surrounding the “white” particles. This
31
This abstract art image by Picasso is copied from the cover of the book, Image and Brain: The Resolution of the Imagery
Debate, by S. M. Kosslyn.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2352 L. O. Chua
Fig. 66.
Flow chart for the CNN skeletonization program.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 67.
Snap shots of one iteration of the CNN skeletonization chromosome defined by the flow chart in Fig. 66.
CNN: A Vision of Complexity 2353
2354 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
(b)
Fig. 68. The mammogram on top was processed by a CNN program for detecting spiculi, shown below as red radial threads
around the tumor kernel.
CNN: A Vision of Complexity 2355
degradation is subsequently corrected by applying genes, each one deleting one pixel along one of the
the dilation CNN gene which has the reverse effect eight compass directions. A time snapshot at the
of growing a layer of black pixels after each itera- output of each of these CNN genes corresponding to
tion to cover up the large white (salt) particles, as an input image (shown on top) is shown in Fig. 67.
shown in Figs. 64(e)–64(h). Observe that four “di-
lations” are used here. Since only two “erosions” CNN Application 3 : Detecting Cancer
have so far been applied, we must apply two more From Mammogram
erosions [Figs. 64(i)–64(j)] in order to preserve the Mammograms are x-ray images used for detecting
original features as much as possible. breast cancer. The two most common forms of
deadly breast cancer appear to the trained eyes of
CNN Application 2 : Extracting Skeleton a radiologist either as radiating patterns of short
From Images fibers, called spiculus, or as swarms of lumped
Skeletonization is one of the standard preprocess- particles called microcalcifications. Two CNN
ing tasks called for in many image processing and programs have been developed to automatically
pattern recognition applications, such as handwrit- identify these two forms of breast cancer [Liszka
ing character recognition, chromosome classifica- et al., 1995].
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
tion, etc. The problem is to replace the lines, Both programs have been implemented on
curves, strokes, etc., of varying thickness in a bi- PC’s, enhanced with a CNN hardware accelerator
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
nary pattern with one-pixel wide skeletons located [Roska et al., 1992b] and were presently being field
approximated at their geometric centers. This pre- tested at several hospitals in Budapest. Figure 68
processing step preserves all relevant information of shows the input and output images of a mammo-
the input pattern while reducing greatly the stor- gram with spiculi (shown in red). The flow chart de-
age and processing times. The flow chart, from the picting various stages of the CNN program is shown
CNN software library [Roska et al., 1997] for solving in Fig. 69. The result from a mammogram with mi-
this problem is shown in Fig. 66. It is composed of crocalcifications (in blue) extracted from the second
a sequential application of eight pixel-peeling CNN CNN program is shown in Fig. 70.
Fig. 69. Flow chart of CNN program for detecting spiculi in mammograms.
2356 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
(b)
Fig. 70. The mammogram in (a) was processed by a CNN program for detecting microcalcifications, shown in (b) as blue
particles of varying sizes.
CNN: A Vision of Complexity 2357
(a)
(a)
(b)
Fig. 71. (a) A girl’s face with distinctly red lips. (b)
A red pepper whose dark red region near the center re-
sembles closely the girl’s lips above (courtesy of Prof.
Fujita).
where bkl = 0. In particular, Sec. 3.1 is devoted model is discussed. First, some aspects of the pos-
exclusively to CNNs described by sible stable equilibria of the autonomous CNN are
characterized for the purpose of explaining what
X types of stable patterns are possible. Second, the
ẋij = −xij + zij + akl ykl (130)
kl∈Sij (r)
process of spontaneous pattern formation within
the CNN from random initial conditions is inves-
yij = f (xij ) i = 1, 2, . . . , M , tigated. Finally, it is shown that the CNN can ex-
hibit many pattern forming phenomena which are
j = 1, 2, . . . , N (131)
found in nature.
ẋαβγ = f (xαβγ ) + D ∇2 xαβγ (132) an autonomous CNN must satisfy [Thiran et al.,
1995]
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
!
α, β, γ = 1, 2, . . . , N , where xαβγ ∈ Rn denotes X
the state of cell Cαβγ located at the grid point with
?
yi,j ?
ak−i,l−j yk,l > 1 if |x?i,j | > 1 (134)
integer coordinates (α, β, γ) of a three-dimensional k,l∈Sij (r)
N × N × N cube, D denotes an n × n diagonal X
matrix whose diagonal elements Di , i = 1, 2, . . . , n
?
ak−i,l−j yk,l = x?i,j if |x?i,j | ≤ 1 .(135)
are called the diffusion coefficients associated with k,l∈Sij (r)
32
To avoid clutter, we formulate the reaction diffusion CNN equation only in 2 or 3 spatial dimensions in this paper. The
same form applies, mutatis mutandis to any dimensions. Observe that if Dk = 0, then the kth equation in Eq. (132) reduces
to (ẋαβγ )k = fk (xαβγ ), where the discrete Laplacian operator is suppressed.
2360 L. O. Chua
33
Mosaic is the name used in [Chow & Mallet–Paret, 1995] for patterns which are restricted to output state values in
{−1, 0, +1}. Motif was used in [Thiran et al., 1995] for a regular pattern of any output values which is at least regionally
stable.
CNN: A Vision of Complexity 2361
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 74. Some examples of stable configurations in the symmetric one-dimensional autonomous CNN for various values of the
center template element p, when s = 1/2. When 0 < p < 2, the unique length B of the boundary strings between saturated
regions is found according to Eq. (138).
Fig. 75. A CNN template for which constant patches are the dominant motif. An initial random state pattern (labeled as
input pattern) will give rise to large constant patches of saturated cells.
2362 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 76. A CNN template for which checkerboard patterns are the dominant motifs. An initial random state “input” pattern
will give rise to large checkerboard patterns of saturated cells.
Fig. 77. A CNN template for which horizontal or vertical stripes are the dominant motifs. An initial random state “input”
pattern will give rise to large striped patches of saturated cells.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
2363
Fig. 78. Bifurcation diagram for the stability of the elementary motifs of the 3 × 3 template as a function of the template values. (a) p > 1. (b) p < 1.
2364 L. O. Chua
how patterns can arise, evolve and eventually con- initial conditions evolve independently in time. It
verge to such stable equilibrium in the standard au- has the elementary solution:
tonomous (zero-input) CNN system. In all of the
autonomous, zero-threshold pattern forming CNN x̃[ω1 , ω2 ](t) = x̃[ω1 , ω2 ](0)eλ̃[ω1 ,ω2 ]t .
systems, the zero-state image is an unstable equilib-
rium. Perturbing this equilibrium by a small, ran- If all λ̃[ω1 , ω2 ] are non-positive, the origin remains
dom displacement excites the instability and pat- stable and nothing interesting happens. However, if
terns develop, which is the mechanism for morpho- for any spatial mode ω1 , ω2 the gain λ̃[ω1 , ω2 ] is pos-
genesis first proposed in [Turing, 1952]. This type itive, the origin becomes unstable and we say that
of pattern is important because it is unbiased by the CNN system has the pattern forming property.
any input or correlated initial condition and there- When the initial condition is a pixel-wise indepen-
fore produces an “inherent” pattern of a given gene dent random perturbation about zero, x̃[ω1 , ω2 ](0)
(template). will be expected on average to have the same spec-
Very complex patterns can be obtained by this tral power for all ω1 , ω2 . Let t1 be the time at which
technique of breaking the symmetry of the unstable the first cell enters saturation. Then, if λ̃[ω1 , ω2 ]
equilibrium. To understand this, consider an initial is negative, exp(λ̃[ω1 , ω2 ]t1 ) will be a quantity less
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
condition which is a very small pertubation from than one, so the magnitude of spatial frequency ω1 ,
the unstable zero image: ω2 will have decreased from its already small orig-
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 79. A CNN template for which stripes of any orientation are motifs. An initial random state “input” pattern will give
rise to a squiggle pattern as stripes of various orientations merge and connect. This template has a bandpass instability which
is characteristic of many reaction-diffusion processes.
• Linear System leading to noise shaping. Here 3.1.3. CNN pattern formation in
the CNN primarily operates in the linear region, biology and physics
i.e. most cells have xi,j < 1. During this time
the initial state “noise” is filtered and begins to Many interesting patterns in nature have been mod-
exhibit some coherency. eled by partial differential equations, cellular au-
• Local Separation of Modes leading to regional tomata, and other locally active systems. The CNN
meta-stability of motifs. During this epoch, most provides a convenient framework for studying such
cells enter saturation and, at least locally, have basic mechanisms of pattern formation by allow-
settled to a particular motif. ing the control of the critical instabilities needed
• Boundary Negotiation leading to a globally sta- for pattern formation, without obfuscating param-
ble pattern. Once most cells have reached sat- eterizations, complex nonlinearities, or high-order
uration and have locally settled to a motif, cell states. In fact, many of the natural phenomena
the boundaries between them are adjusted un- which have been emulated by complex mathemati-
til the array is stable. This may take a very cal models can also be demonstrated by the CNN.
long time.
Example 3.1.1. Synergetics.
The three epochs can be easily observed in the
CNN transient of Fig. 80. Although the transition The study of the spontaneous self-organizing
time between these epochs will not be exactly de- behavior of collections of locally-coupled systems is
fined and may not apply to the whole array simulta- sometimes known as synergetics. The name comes
neously, the classification has proved useful for the from the idea that cooperation between simple sys-
intuitive understanding of the CNN pattern forma- tems can produce a large-scale order [Haken, 1978].
tion process and its application to image processing Synergetic mechanisms have been found to be useful
problems [Crounse & Chua, 1996]. for explaining phenomena in physics, chemistry, and
2366 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 80. A CNN pattern forming transient. The linear system can be observed to operate from approximately t = 0 to t = 3.
Once the cells begin entering saturation the local separation into motifs occurs (checkerboards and squiggles), concluding at
about t = 8. Finally, for t > 8 a long and tedious negotiation process takes place. Apparently, the boundaries between the two
types of motifs are not stable and are adjusted at the expense of the squiggle pattern. Eventually the checkerboard regions
meet up. If they are of the same parity, they merge; otherwise a narrow band at the lower characteristic spatial frequency is
formed. Eventually, the checkerboard dominates the whole array.
biology, and have also been applied to problems in pattern-forming behavior. Stripes and spots are
computer recognition of human faces [Haken, 1994]. easily formed in such systems, and can be shown
A well-known example of synergetics due to to be a consequence of a local excitation and lateral
Haken [1994] is the phenomena of competing con- inhibition in the dynamics.
vection rolls in a heated fluid. When a single strong Such stripes and spots can be generated by
convection roll is initiated in a quiescent fluid, it the bandpass CNN template of Fig. 79, since such
has been shown through simulation that other rolls a template has the necessary excitation-inhibition
develop along the same orientation, as shown in pattern. As shown in Fig. 79, stripes are the inher-
Fig. 81. However, when two rolls of differing ori- ent pattern of such a CNN. To generate spots, the
entation and strength are initiated, they compete bistable state symmetry must be broken in some
until all rolls align with the strongest orientation, a way. The easiest way to accomplish this is to add a
strongly nonlinear behavior. This phenomenon has simple constant to the cell dynamics through either
been reproduced in the CNN by using the bandpass the CNN threshold or input. An example is given
template of Fig. 79. The initial rolls strongly excite in Fig. 82 which demonstrates a narrow stripe/spot
the unstable modes of the bandpass CNN system. transition band over which stripes break up into
As in the convection simulation, the array eventu- spots until finally the output nonlinearity will no
ally only sympathizes with the strongest feature. longer support stripes due to the strong biasing.
2367
Fig. 81. (a) Haken’s example of synergy in the convection of a heated fluid, from [Haken, 1994]. (b) Synergy in the CNN bandpass template. The three columns of each
example show the time-evolution for which the unstable equilibrium was broken by features which strongly excite the unstable modes. The third column demonstrates
that the superposition principle does not apply — instead, the strongest feature wins the competition and eventually dominates the array.
2368 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 82. The reaction-diffusion (bandpass) CNN was supplied with a space-varying threshold, or simply “bias”, increasing
from “zero” on the left to “one” on the right.
etc. [Murray, 1989; Meinhardt, 1995], e.g. those CNN exhibits dendritic growth or “fingering” which
found on mammalian fur, fishes, and sea shells. is a type of curvature dependent penetration of one
These models typically employ a reaction-diffusion of the bistable states into the other, as seen in
mechanism. But, to get realistic appearances, con- Fig. 85. Such patterns can be found in viscous fin-
straining the shape of the domain over which the gering and the growth of lichens.
equations act is necessary. That is, the manner
in which the evolving patterns interact with the Example 3.1.5. Hallucinations.
boundary is critical. It has been proposed that hallucinations and
The stripe-to-spot transition typical of feline other spontaneous visual disturbances may be
tails has been demonstrated in the CNN by using caused by self-organizing phenomena within the
a narrowing array size (triangular in shape) [Setti visual cortex [Oster, 1970]. Chemical agents
& Thiran, 1996], which follows the approach of or the lack of external stimuli, for instance,
Murray [1989], as shown in Fig. 83. may cause a type of pattern formation within
Another frequently studied example are the the visual cortex due to coupling among cells.
patterns on fish. Here both shape and growth of Since there is a spatial transformation between
the fish seem important to the final pattern which the retina and the cortex, the visual percep-
develops [Kondo & Asai, 1995]. A CNN simulation tion due to these cortical patterns is the retinal
of the markings of a zebrafish relative are shown in pattern which would have given rise to the in-
Fig. 84. duced cortical pattern. Using simple neural net-
work models to generate cortical patterns followed
Example 3.1.4. Dendritic Growth. by a cortico-retinal transformation have shown re-
A qualitatively different behavior than develop- markable similarities to subjective drawings of hal-
ment of stripes and spots can arise in a bandpass lucinatory experiences [Markus, 1992].
reaction-diffusion system when the uniform (con- Following the methods of [Markus, 1992], a sim-
stant image) binary (+1, −1) states become stable. ple CNN model for the interactions among cells
This can be achieved in the CNN by increasing the of the visual cortex was designed by using a tem-
center element of the bandpass CNN template to plate with a local activation and lateral inhibition.
slightly above the point where the zero-frequency The CNN with this template was then used to
mode becomes unstable (a0,0 > −22). Then, the spontaneously generate a labyrinthine pattern from
CNN: A Vision of Complexity 2369
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 83. (a) Simulations and drawings of the marking on feline tail coats from Murray [1989]. (b) Results of a spatially
homogeneous CNN simulation on a triangular domain. The morphology of the array induces the stripe-to-spot transition.
Fig. 84. (a) A typical zebrafish marking from [Kondo & Asai, 1995]. (b) The results of a CNN simulation. The spot-to-stripe
transition was produced by a space-varying threshold.
2370 L. O. Chua
(a)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 85. When the self-feedback is increased until the zero-frequency mode just becomes unstable, here a0,0 = −21.9 was
chosen, a qualitatively different behavior can be observed. In this example, the array is initiated with a small cross-shaped
seed. Unlike the previous example, growth proceeds dendritically through a type of curvature flow.
CNN: A Vision of Complexity 2371
(c)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 86. Starting with small, random initial conditions the given CNN template produces patterns similar to those that might
be formed in the visual cortex under certain conditions (left). The spatial transformation of Eq. (144) was then applied to
produce the virtual (perceived) image on the retina (right). This is most easily done by choosing each desired point (r, θ) on
the retina image and finding the corresponding point (x, y) on the cortex according to Eq. (144). In practice, the exact scale
of the spatial indexing must be chosen carefully. Specifically, since the retinal image must be periodic in θ, so must the y-axis
of the cortical image. This was accomplished by using periodic boundary conditions during the CNN simulation and then by
scaling θ to range across the complete cortex image vertically. Since the units for the radius from the center of the retinal
image, r, are arbitrary, they can be selected so that the region for which log r < 0 is of a desired size. This region corresponds
to a circle in the center of the output image, for which the values can be specified arbitrarily, since they are mapped from off
the edge of the cortex image. Here, this region was assigned the brightest intensity values. Then log r can be scaled so that
the positive part of it spans the entire cortex image horizontally.
∂ 2 xi ∂ 2 xi ∂ 2 xi i = 1, 2, . . . , nx . (149)
(∇ xαβγ )i → (∇ x)i =
2 2
+ +
∂x2 ∂y 2 ∂z 2
(148) With some important exceptions (e.g. the prop-
agation failure phenomenon, which can occur in
where (x, y, z) denotes here the continuous spatial Eq. (147) but not in its limiting PDE version
(x, y, z)-coordinates, then Eq. (147) becomes the [Perez–Munuzuri et al., 1992] extensive numeri-
standard Reaction-Diffusion PDE: cal simulations have shown that the qualitative
CNN: A Vision of Complexity 2373
Table 3.2.1. Some CNN Reaction-Diffusion Equations and their associated PDEs.
αu2ij 2
u̇ij = − βuij + D1 [ui+1,j + ui−1,j ∂u αu2 ∂ u ∂2u
vij = − βu + D1 + 2
∂t v ∂x2 ∂y
+ ui,j+1 + ui,j−1 − 4uij ] 2
∂v ∂ v ∂2v
= αu2 − γv + D2 +
v̇ij = αu2ij − γvij + D2 [vi+1,j + vi−1,j ∂t ∂x2 ∂y 2
+ vi,j+1 + vi,j−1 − 4vij ]
behaviors of Eqs. (147) and (149) are similar. assumed xαβγ ∈ R3 and denoted the components
Since it is computationally more efficient to solve of xαβγ by uijk , vijk and wijk , i.e.
Eq. (147) than Eq. (149), specially when Eq. (147) is
implemented in a dedicated silicon chip, it is desir- xαβγ = [x1 (αβγ) x2 (αβγ) x3 (αβγ)]T
able to study the CNN Reaction-Diffusion Equation ∆
= [uijk vijk wijk ]T
associated with various standard reaction-diffusion
PDE’s. For future reference, Table 3.2.1 contains a It is obvious from Table 3.2.1 that given
list of some CNN reaction-diffusion equations and any Reaction-Diffusion PDE, one can trivially
their associated PDE’s, where to avoid clutter, we generate a corresponding Reaction-Diffusion CNN
2374 L. O. Chua
34
To avoid clutter, we change notations and use (u, v, w) instead of (x1 , x2 , x3 ). In addition, we use (i, j, k) instead of
(α, β, γ).
CNN: A Vision of Complexity 2375
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 87. The three-segment piece-wise linear function of Chua’s oscillator. All parameters of Eq. (152) are identified here.
The different slopes are depicted with different colors.
for wi,j,k (t) in the second equation in Eq. (153) from Eq. (155) will be virtually identical to those
to obtain the following “reduced” second order computed from Eq. (153). For large array sizes,
equation: Eq. (155) will result in significant savings in compu-
tation time without compromising accuracy. More-
Reduced Chua’s Reaction-Diffusion CNN over, being a second-order differential equation,
Equation: Eq. (155) allows us to apply several well-known bi-
furcation results for two state variables in the liter-
u̇i,j,k = f (ui,j,k , vi,j,k ) ature [Murray, 1989].
+ Du [ui+1,j,k + ui−1,j,k + ui,j+1,k We end this section by presenting some com-
puter simulation results using the above reduced
+ ui,j−1,k + ui,j,k+1 + ui,j,k−1 − 6ui,j,k ] Chua’s Reaction-Diffusion Equation.
v̇i,j,k = g(ui,j,k , vi,j,k )
+ Dv [vi+1,j,k + vi−1,j,k + vi,j+1,k Example 3.2.1. Turing Patterns from Chua’s
Reaction-Diffusion Equations [Muñuzuri et al.,
+ vi,j−1,k + vi,j,k+1 + vi,j,k−1 − 6vi,j,k ] 1995].
(155) Turing patterns are those stationary structures
that appear spontaneously upon breaking the sym-
where metry of the medium [Turing, 1952], and are caused
∆ by the coupling between the reaction and the dif-
f (ui,j,k , vi,j,k ) = α[vi,j,k − h(ui,j,k )]
fusion processes. (In the absence of diffusion, these
∆ systems tend to a stable uniform steady state.) Tur-
g(ui,j,k , vi,j,k ) = ui,j,k − νvi,j,k
ing structures have been suggested as a possible
∆ β mechanism for morphogenesis in large-scale biolog-
ν =1+ .
γ ical systems [Murray, 1989].
It follows from the well-known singular per- Once Turing patterns arise, they remain stable
turbation theory that, under rather mild condi- until some external perturbation destroys them. (If
tions, the solutions ui,j,k (t) and vi,j,k (t) computed we suppress the perturbation, the Turing structures
2376 L. O. Chua
will reappear and reorganize themselves again.) in accordance with the mechanism proposed by
They are characterized by an intrinsic wavelength [Murray, 1989]:
that does not depend on the geometric parameters
of the medium, it depends only on the macroscopic fu + gv < 0
parameters, namely, the diffusion coefficients and
the initial and boundary conditions. fu gv − fv gu > 0
It is possible to derive analytically the follow- fu Dv + gv Du > 0
ing conditions necessary for the generation of these
spatial patterns in the system given by Eq. (155) {fu Dv + gv Du }2 − 4Du Dv {fu gv − fv gu } > 0 .
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 88. Temporal spontaneous formation of hexagonal Turing patterns. The initial values of the system variables [Eq. (155)]
are set equal to the equilibrium values plus some small random noise. As time evolves the following configurations are seen:
(a) t = 20 time units (t.u.), (b) t = 70 t.u., (c) t = 120 t.u. and (d) t = 2000 t.u. Note that the final configuration is a
hexagonal lattice with some defects. (Size of the array, 101 × 101; different colors correspond with different values of the
u-variable, blue is the minimum value and red is the maximum; Neumann boundary conditions were chosen.)
CNN: A Vision of Complexity 2377
The above inequalities constrain the formation Example 3.2.3. Three-Dimensional Knots
of Turing patterns to some ranges of the system from Chua’s Reaction-Diffusion CNN Equation.
parameters. For the example presented here we [Muñuzuri & Chua, 1997].
used the following parameters: α = −10, ν = 2, The two previous examples were devoted to sta-
m0 = −1, m1 = m2 = 0.2, ε = 2, Du = 1 and tionary structures in monostable systems. Here, a
Dv = 40, which satisfy the above four conditions. bistable system (with two different stable equilib-
Figure 88 shows the temporal spontaneous for- rium points that we call P+ and P− ) is considered,
mation of hexagonal lattices in a two-dimensional subject to the same type of diffusion-driven insta-
system. The final state is characterized by mul- bilities given by Eqs. (155). Under these conditions,
tiple domains each containing groups of hexagons stationary tubular structures may appear in a three-
with different orientations. Observe that the differ- dimensional medium whose diameter is determined
ent domains are separated by “penta-hepta” defects. by the system parameters. All points in the inte-
Once these defects are created in the system they rior of the tubular structure are in one of the equi-
remain stable and motionless [Fig. 88(d)]. librium states (P+ ) while all others are in the other
equilibrium state (P− ). The final three-dimensional
“steady state” structure is determined (decisively)
Example 3.2.2. Turing Patterns with Side-Wall
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
1995a].
of many systems in nature, e.g. the dynamics of
Pattern formation and stability in a two- membranes as well as some liquid crystals [Roux,
dimensional system are strongly affected by exter- 1993; Goldstein et al., 1993], knotted circular DNA
nally imposed modulations [Pismen, 1987], a phe- [Wasserman et al., 1985; Sumners, 1990], linked and
nomenon that can be clearly observed by imposing a knotted filaments of phase.
periodic sidewall forcing on Turing structures. This Below are some examples of the different pat-
is achieved by adding the term terns, knots, that can be obtained for different
sets of initial conditions. The model parameters
Ap cos(ωt) δ(i − 1) were set equal to: α = −5, ν = 2, m0 = 1,
m1 = m2 = 0.1, ε = −0.1, Du = 5 and Dv = 15.
to Eq. (155) for the u-variable, where Ap and ω are
Figure 90(a) shows a Hopf-link pattern in such a
the amplitude and the frequency of the forcing, re-
three-dimensional medium. The initial conditions
spectively, and δ(·) is the Dirac delta function which
were chosen as close as possible to the desired fi-
is equal to one when i = 1 for any j ∈ [1, N ], and nal structure. Figure 90(b) shows a three-knot
zero otherwise. pattern and in Figs. 90(c)–90(e) stationary helices
When a periodic sidewall forcing is applied to are presented.
the system with the same initial conditions as in
the previous example and the same set of param-
eters (α = −10, ν = 2, m0 = −1, m1 = m2 = 3.3. Nonlinear waves in
0.2, ε = 2 and Du = 1), perfect organization reaction-diffusion CNNs
into a rhombic array can be obtained. This per- By setting the diffusion coefficient Dv = 0 in the
fect rhombic organization only occurs for specific, Chua’s Reaction-Diffusion Equation [Eq. (153) or
resonant, values of Du , Dv and the forcing fre- (155)] and by choosing appropriate values for the
quency, ω. parameters α, ν, m0 , m1 , m2 and ε, we can obtain
Figure 89 shows this effect; first for the res- “dynamic” patterns in the form of autowaves, spiral
onant case (Dv = 40) and, then, for the non- waves and scroll waves [Muñuzuri et al., 1995] as
resonant case (Dv = 43). Only in the first case is illustrated in the following examples.
perfect rhombic arrangement achieved without de-
fects. In Fig. 89(b) a hexagonal array is observed Example 3.3.1. Traveling Triggered Waves
with “penta-hepta” defects in the upper-right hand from Chua’s Reaction-Diffusion CNN Equation.
corner of the figure. The forcing affects the sys- [Muñuzuri et al., 1995b].
tem from the beginning of the simulation. Once Nerve propagation of a stimuli is one of the
a stationary structure is achieved, it remains sta- most important and complex spatial patterning pro-
tionary even after the external forcing is removed. cesses. Under stimulation, nerve cells trigger a
2378 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 89. Sidewall forcing of hexagonal Turing patterns. (a) Resonant case, a perfect rhombic arrangement is achieved.
(b) Non-resonant case, normal hexagonal arrangement with defects. The simplest configuration was considered for this
simulation — a continuous forcing in time and amplitude (Ap = 1, ω = 0). (Same initial and boundary conditions, parameters
and color codes as in Fig. 88; array size, 50 × 50.)
CNN: A Vision of Complexity 2379
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 90. Three-dimensional knots from Chua’s reaction-diffusion CNN equation. (a) Stationary Hopf-link (t = 19 time
units (t.u.) after the beginning of the experiment; array size: 201 × 201 × 201). (b) Three-knot (t = 116 t.u.; array size:
201 × 201 × 201). (c) Stationary single helix (t = 78 t.u.; array size: 301 × 301 × 91). (d) Stationary double helix (t = 78 t.u.;
array size: 301 × 301 × 91). (e) Triple helix (t = 78 t.u.; array size: 301 × 301 × 91). The surface plotted in all these figures
separates the set of cells in the equilibrium state P+ (inside the tubes) from the set of cells in the equilibrium state P− (outside
the tubes). Colors were artistically chosen to stress the interface geometry. (Neumann boundary conditions were chosen.)
2380 L. O. Chua
rapid but brief pulse-like voltage called the “action mechanisms in nature, such as nerve pulse prop-
potential” which carries the information along a agation [Scott, 1975], combustion waves [Murray,
nerve fiber [Scott, 1975]. This type of behavior can 1989], excitation waves in cardiac muscles [Alle-
be modeled by solving the set of Eq. (155) for the sie et al., 1973, 1977], etc. On the basis of
one-dimensional case and the appropriate set of pa- the fundamental properties of these waves, it has
rameters (α = −5, ν = 2, m0 = 1, m1 = m2 = 0.1, been possible to use them for some image pro-
ε = 0.1, Du = 0.5 and Dv = 0). Such a system cessing operations [Krinsky et al., 1991; Kuhnert
is bistable (it has two stable equilibrium points, P+ et al., 1989; Mikhailov, 1989; Pérez–Muñuzuri
and P− ) and can initiate a traveling triggered wave, et al., 1993a; Steinbock et al., 1995], such as find-
also called a “transition wave”, between two sta- ing the shortest path in a two-dimensional labyrinth
ble states, that moves with constant velocity along connecting two points.
the array. The direction of propagation is deter- The labyrinth is implemented in a two-
mined by the “sign” of the following integral [Pérez– dimensional CNN by modulating the diffusion coef-
Muñuzuri et al., 1995], ficient of each cell. Figure 93(a) shows the labyrinth
Z u+ (a maze photographed from a garden in England
h(u) du [Fisher, 1990]) chosen to demonstrate the mecha-
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Fig. 91. Traveling triggered wave propagating in a Chua’s reaction-diffusion CNN equation. (Array size: 50; colors are
proportional to the u-variable values; Neumann boundary conditions were chosen.)
Fig. 92. Propagation failure phenomenon. (Same initial and boundary conditions as for Fig. 93; Du = 0.334; array size: 50;
colors are proportional to the u-variable values.)
2382 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(a)
(b)
Fig. 93. The different snapshots show the evolution of the traveling waves through the labyrinth: (a) t = 60 time units (t.u.),
(b) t = 940 t.u., (c) t = 2260 t.u. and (d) t = 3140 t.u. The starting point, P1 , where the traveling wave was triggered is
marked with the number 1 surrounded by a yellow spot and the final destination, P2 , by the number 2. Green color marks the
points of no propagation, red denotes the points in the more stable state, P+ , and blue points in the state P− . The black line
with arrows shows the part of the shortest path already covered. (Model parameters for the three-variable set of Eqs. (148):
α = 9, β = 30, γ = 0, m0 = −0.14, m1 = m2 = 0.14, ε = −0.1, Du = 1 and Dv = 0; array size: 851 × 411 cells; Neumann
boundary conditions were chosen.)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 93.
(c)
(d)
(Continued )
CNN: A Vision of Complexity 2383
2384 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(e)
In order to obtain this spatio-temporal pattern There are different mechanisms for creating
in our two-dimensional system, we set the parame- a spiral wave in a two-dimensional monostable
ters of Eq. (153) to α = 10, β = 0.3, γ = 0.008, medium and all of them are contrived to produce
m0 = −0.55, m1 = 1.18, m2 = 6.89, ε = 0.1, a break in the front of a propagating autowave
Du = 1 and Dv = 0. The values of the en- [Gómez–Gesteira et al., 1994a, 1994b]. An effec-
tire system variables are set at the stable equilib- tive way to initiate spiral waves [Jahnke & Winfree,
rium point values, except for the central cell of 1991] consists of setting all cells at the equilibrium
the medium (called a pacemaker) whose value for state except for a front of excited circuits in the u-
the u-variable is set periodically equal to u = −3. and v-variables, and followed by a smoothly declin-
Figure 94(a) shows such an initial state for the u- ing circular gradient in the w-variable [Muñuzuri
variable, as time evolves [Figs. 94(b)–94(d)] concen- et al., 1993]. This is the initial state shown in
tric waves appear, then vanish at the boundaries as Fig. 96(a) (all points inside the wedge-like region
new concentric waves are being created at the cen- correspond to the excited value of the u-variable,
ter. Figure 95 shows a three-dimensional view of u = −3, and all other points correspond to the
this spatio-temporal structure. equilibrium value). As the system evolves, the free-
end (also called the tip) starts curling [Fig. 96(b)]
Example 3.3.5. Spiral Waves from Chua’s while increasing its curvature. The whole structure
Reaction-Diffusion CNN Equation [Muñuzuri et al., rotates [Figs. 96(b)–96(d)] until a constant wave-
1995b]. length is achieved [Fig. 96(e)]. This stationary
Rotating spiral waves are another type of structure continues rotating steadily [Fig. 96(f)].
spatio-temporal structures that may appear after Figure 97 shows a three-dimensional view of this
reorganization of autowaves during propagation. spatio-temporal structure.
Those waves are responsible for some pathological
diseases (e.g. arrythmias [Allesie et al., 1973, 1977], Example 3.3.6. Scroll Waves from Chua’s
in the chickens’ eye retina [Bures et al., 1984], etc.) Reaction-Diffusion CNN Equation [Muñuzuri et al.,
as well as in many other roles in different systems 1995].
[Cohen & Robertson, 1971; Jakubith et al., 1990; An extension of the previous example to a
Zhabotinsky & Zaikin, 1973]. three-dimensional medium makes it possible to
CNN: A Vision of Complexity 2385
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 94. Concentric waves from Chua’s reaction-diffusion CNN equation. Figures (a)–(d) correspond to times t = 0 t.u.,
30 t.u., 60 t.u. and 90 t.u. where “t.u.” denotes “time units.” (In all figures the values of the u-variable are plotted, blue color
corresponds to the minimum value — excitation state value — while red corresponds to the maximum value — equilibrium
state value — array size: 251 × 251; Neumann boundary conditions were chosen.)
generate three-dimensional waves called scroll wave fill an entire line in space, which is called a vor-
waves. If we take a two-dimensional rotating spiral tex filament (which, in this case is a straight line).
wave and extend it vertically upwards, we obtain a Depending on the particular geometry of the fila-
three-dimensional wave called a straight scroll vor- ment different types of scroll waves can be obtained
tex [Mikhailov, 1990]. The properties of the scrolls (Fig. 98).
are analogous to those of spirals. In the case of Let us simulate Eq. (153) with the set of pa-
spirals, they rotate around some point in the plane rameters α = 10, β = 0.3, γ = 0.008, m0 = 0.44,
called the tip, while the rotation centers of a scroll m1 = 2.2, m2 = 8, ε = 0, Du = 0.4 and Dv = 0.
2386 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 95. Three-dimensional view of concentric waves. (The vertical axis represents the u-variable while the horizontal axes
are the spatial coordinates (i, j); same parameters and color codes as in Fig. 96.)
Figure 98(a) shows a straight scroll vortex ori- Remark. Many other spatio-temporal patterns, in-
ented along the k-direction (its filament is a straight cluding spatio-temporal chaos, from CNNs with
vertical line). We chose the same initial conditions Chua’s circuit cells have been investigated both nu-
as in the previous example but for all planes in the merically and analytically [Nekorkin & Chua, 1993;
k-direction. Zheleznyak & Chua, 1995; Pivka, 1995a; Pivka,
Figure 98(b) shows a straight twisted scroll 1995b; Pérez–Mariño et al., 1995; Pivka, 1995a;
wave (the filament is now an open non-straight Gómez-Gesteira et al., 1995; Osipov et al., 1995a;
line). We chose the same initial conditions as for Ogorzalek et al., 1995].
a two-dimensional spiral wave but now the set of
free-ends or tips combine to form a helicoidal verti-
3.4. Simulating nonlinear PDEs via
cal line.
autonomous CNNs
Figure 98(c) shows a scroll ring wave (the fila-
ment is no longer an open line but rather a circle). Reaction-diffusion PDE’s is an important albeit rel-
As initial conditions, the whole system was set at atively small subset of the universe of all nonlin-
the equilibrium point except for a disc of excited ear PDE’s. For any other nonlinear PDE, the
cells (u = −3) in the middle of the system, with spatial derivative (of any order) of any state vari-
another disk of cells immediately over the surface able ui (t; x, y, z) at time t and spatial location35
of the previous disc with inhibited cells (w = 2.5). (x, y, z) ∈ R3 can be approximated to any
In this way, the disc of excited cells starts propagat- desired accuracy [Kantorovich & Krylov, 1964;
ing in all directions except upwards, where it starts Milne–Thomson, 1960] by finite differences in-
curling giving rise to a scroll ring wave. volving only the values of the state variable
35
To avoid clutter we restrict our discussion to the three-dimensional Euclidean space R3 . The same formulation is valid for
any dimension.
CNN: A Vision of Complexity 2387
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 96. Spiral waves from Chua’s reaction-diffusion CNN equation. Figures (a)–(f) correspond to times t = 0 t.u., 10 t.u.,
20 t.u., 50 t.u., 200 t.u. and 1000 t.u. where “t.u.” denotes “time units.” (Same parameters and color codes as for Fig. 96;
array size: 101 × 101; Neumann boundary conditions were chosen.)
2388 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 97. Three-dimensional view of a steadily-rotating spiral wave. (The vertical axis represents the u-variable while the
horizontal axes are the spatial coordinates (i, j); same parameters and color codes as in Fig. 98.)
CNN: A Vision of Complexity 2389
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
Fig. 98. Scroll waves from Chua’s reaction-diffusion CNN equation. Points on the surface corresponds to those circuits
whose value of the u-variable is minimum. Colors were artistically chosen to stress the surface geometry. (Array size:
(a) 51 × 51 × 51, (b) 61 × 61 × 61 and (c) 121 × 121 × 81; Neumann boundary conditions were chosen.)
ui (t; α0 , β 0 , γ 0 ) located at a finite number of lat- PDE, we can generate many (depending on the
tice points (x, y, z) = (α0 , β 0 , γ 0 ) ∈ Sαβγ (r), desired accuracy) approximate discretized systems
where (αβγ) ∈ Z3 denotes the “discrete” co- of ODE’s in terms of a three-dimensional array
ordinates of a three-dimensional lattice Z3 and of state variables xi (t; α, β, γ), α = 1, 2, . . . , M ,
Sαβγ (r) denotes a neighborhood of radius r, cen- β = 1, 2, . . . , N , γ = 1, 2, . . . , P . Moreover, since
tered at (α, β, γ). Hence, given any nonlinear all finite-difference operations involve only variables
2390 L. O. Chua
located within a local neighborhood, we can always obtain the following associated KdV CNN equation:
decompose the discretized system into a component
(the isolated cell), which involves only ui (t; α, β, γ) dui (t) 1
= 3 [ui−2 (t) − 2ui−1 (t) + 2ui+1 (t)
at the lattice site (α, β, γ) and another component dt 2h
(the cell coupling) which involves all neighboring 3 2
cells (α0 , β 0 , γ 0 ) ∈ Sαβγ (r).36 In other words, given − ui+2 (t)] − [u (t) − u2i−1 (t)] ,
2h i+1
any nonlinear PDE, we can induce many associ-
ated CNN equations — the example given in Ta- i = 1, 2, . . . , M (159)
ble 3.2.1 represents the simplest one. Although it
∆ ∆
is not true that the qualitative behaviors of a non- where ui (t) = u(t; xi ) and h = xi − xi−1 .
linear PDE and its associated CNN equation are Figure 99 shows six snap shots of the computer
always the same — the propagation failure phe- simulation of Eq. (159) with h = 0.5 and N = 300
nomenon [Perez–Muñuzuri et al., 1992] is a case cells at t = 0, 1, 2, 5, 10, and 30 for Gaussian ini-
in point — extensive computer experiments have tial condition ui (t = 0) = 4 exp[−(1/20)(ih)2 ] and
shown that for the vast majority of cases, the re- periodic boundary condition. Another simulation
spective solutions can be made virtually indistin- using a sine wave ui (t = 0) sin(i 2π
64 h) as the initial
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
guishable by choosing a sufficiently large array size condition leads to the six snap shots (at t = 0, 10,
and by optimizing the CNN cell and coupling pa- 15, 20, 30 and 60) shown in Fig. 100. To verify
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
rameters [Roska et al., 1995; Kozek et al., 1995; that the respective shapes of colliding solitons re-
Tetzlaff & Wolf, 1996; Puffer et al., 1996]. We close main unchanged, Fig. 101 shows six snap shots for
this section with a glimpse of some PDE-induced the initial condition
CNN examples.37
4ψi1 ψi2 +(4ψi1 +ψi2 )(1+1/9ψi1 ψi2 )
ui (t = 0) = 2
Example 3.4.1. One-Dimensional KdV (Korteweg- (1+ψi1 +ψi2 +1/9ψi1 ψi2 )2
de Vries) CNN Equation.
with ψi1 = exp[2ih−9] and ψi2 = exp[ih] during the
Consider the one-dimensional KdV (Korteweg-
time interval [0, 50] where the two solitons collided
de Vries) equation [Drazin & Johnson, 1989]:
with each other. The result (Fig. 101) simulated
from the KdV CNN equation is virtually identical
∂u(t; x) ∂[u(t; x)]2 ∂ 3 u(t; x) to the corresponding results obtained from the ex-
= −3 − (156)
∂t ∂x ∂x3 act solution of Eq. (156) [Hirota, 1971; Drazin &
Johnson, 1989], which was obtained with the above
Let us approximate the two spatial derivatives special choice of initial condition.
∂[u(t; x)]2 3
∂x and ∂ u(t;
∂x3
x)
as follows:
Example 3.4.2. Two-Dimensional Sine–Gordon
CNN Equation.
∂[u(t; x)]2 1 2
≈ [u (t; x + h) − u2 (t; x − h)] , Consider the two-dimensional Sine–Cordon
∂x 2h Equation [Hirota, 1973]:
(157)
∂ 2 u(t; x, y)
= − sin[u(t; x, y)] + ∇2 u(t; x, y)
∂ 3 u(t; x) 1 ∂t2
3
≈ − 3 [u(t; x − 2h) − 2u(t; x − h) (160)
∂x 2h
+ 2u(t; x + h) − u(t; x + 2h)] . (158) where
∂ 2 u(t; x, y) ∂ 2 u(t; x, y)
Substituting Eqs. (157) and (158) into Eq. (156) ∇2 u(t; x, y) = + .
and changing the spatial coordinate into the cor- ∂x2 ∂y 2
responding one-dimensional CNN coordinate, we (161)
36
In most cases, the decomposition consists of just the superposition of these two components. However, more complex
decompositions (e.g. nonlinear functional compositions) may be required for some nonlinear PDE’s.
37
All simulation results in this section were obtained by Dr. R. Tetzlaff and his colleagues from the University of Frankfurt.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 99.
Time evolution of the KdV CNN equation for periodic boundary condition and Gaussian initial condition.
CNN: A Vision of Complexity 2391
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 100.
2392 L. O. Chua
Time evolution of the KdV CNN equation for periodic boundary condition and sine-wave initial condition.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 101. Time evolution showing the collision of two solitons. The soliton on the left with the larger amplitude is faster and
collides with the smaller soliton on the right which is traversing in the same direction at a slower speed.
2393
2394 L. O. Chua
Let us approximate the two-dimensional Lapla- recast Eq. (163) into the standard state equation
cian operator in Eq. (161) as follows: form by introducing the velocity variable
1
∇2 u(t; x, y) ≈ [u(t; x + h, y)] + u(t; x − h, y) vij (t) =
∆ duij (t)
(164)
h2 dt
+ u(t; x, y + h) + u(t; x, y − h)
and rewriting Eqs. (163) and (164) as follows:
− 4u(t; x, y)] . (162)
duij (t)
Substituting Eq. (162) into Eq. (160) and chang- = vij (t)
dt
ing the spatial coordinates into corresponding two-
dimensional CNN coordinates, we obtain dvij (t) 1
= − sin[uij (t)]+ 2 {ui+1,j (t)+ui−1,j (t)
dt h
d2 uij (t) 1
=− sin[uij (t)]+ 2 {ui+1,j (t)+ui−1,j (t) +ui,j+1(t)+ui,j−1 (t)−4ui,j (t)} (165)
dt2 h
+ui,j+1 (t)+ui,j−1(t)−4ui,j (t)} (163) i = 1, 2, . . . , M , j = 1, 2, . . . , N . Figure 102 shows
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
∆
u(t; xi , yi ) and h = xi − xi−1 = yj − yj−1. We can and M = N = 1024 cells at t = 0, 8, and 16, re-
spectively. The initial condition is given by
X
X
3 Y
3 3
exp{φl (i, j)} + A(n, l) exp φl (i, j)
l=1
l,n=1,n<l l=1
uij (t = 0) = 4 arctan ,
X3
1+ A(n, l) exp{φ (i, j) + φ (i, j)}
n l
l,n=1,n<l
(a)
2395
Fig. 102. Time evolution of the uij (t) (top) and vij (t) (bottom) of the sine-Gordon CNN equation at (a) t = 0, (b) t = 8
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(b)
Fig. 102.
2396
(Continued )
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c)
Fig. 102.
2397
(Continued )
2398 L. O. Chua
(a) (b)
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
(c) (d)
(e)
4
Fig. 103. Solution of the Klein–Gordon (φ )-CNN equation for 5 different velocities: (a) vk = 0.190, (b) vk = 0.191,
(c) vk = 0.192, (d) vk = 0.195, and (e) vk = 0.204.
CNN: A Vision of Complexity 2399
we can recast Eqs. (168) and (169) into the follow- Prigogine, 1989] can be simulated by CNNs with
ing state equation form: relatively simple cells and coupling laws. These
“complexity” phenomena have been reported from
dui (t) many disciplines (e.g. biology, chemistry, ecol-
= vi (t)
dt ogy, physics, sociology, etc.) and analyzed from
dvi (t) various perspectives, such as order from dis-
= [u3i (t) − ui (t)] order [Schrödinger, 1948], dissipative structure
dt
[Prigogine, 1980], self-organization [Nicolis &
1 Prigogine, 1977], synergetics [Haken, 1983], slaving
+ {ui+1 (t) + ui−1 (t) − 2ui (t)} ,
h2 principle [Haken, 1983], cooperative phenomenon
(170) [Haken, 1975], far-from-thermodynamic equilibrium
[Prigogine, 1980], edge of chaos [Langton, 1990],
Figure 103 shows the kink-antikink solution ui (t) etc. While intuitively appealing and instructive, the
at xi = (i − 1)h − 16 of the Klein–Gordon (φ4 )- above cited analyses are based primarily on exam-
CNN equation (with M = 4096 cells) obtained by ples, metaphors, physical reasonings, etc., and are
1
simulating Eq. (170) with h = 128 for 5 different therefore imprecise. Moreover, since none of the
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
for resorting to nonlinear circuits even for readers where we have changed the state variable notation
who are not interested in nonlinear circuit theory. from lower case x to upper case V (the usual no-
First, given any nonlinear function f (xαβγ ) and tation for “voltages”), and the spatial coordinates
any diffusion matrix D, it is always possible, in fact from the triple subscript αβγ in Eq. (132) into
quite easy, to synthesize a nonlinear circuit whose the triple index (j, k, l) as part of the argument
state equations are given exactly by Eq. (147) [Chua of V(t; j, k, l). We have also inserted the time
et al., 1996]. “t” into the arguments of V(t; j, k, l) to emphasize
Secondly, the theory of nonlinear circuits that V(t; j, k, l) depends not only on the spatial
[Chua, 1969; Chua et al., 1985; Brayton et al., coordinates (i, j, k), but also on time “t”. Since
1978] is a well-developed scientific discipline en- the variable V(t; j, k, l) in Eq. (171) always refers
dowed with many deep theorems on the fundamen- to the same “time” t, and the same point (j, k, l)
tal properties and physical realizability of differ- in “space”, we can abbreviate Eq. (171) as follows:
ent classes of linear and nonlinear circuits. Since
the theory of nonlinear circuits is based entirely on V̇ = f (V) + D ∇2 V . (172)
the Kirchhoff Current Law (KCL) and the Kirch- In component form, Eq. (171) becomes
hoff Voltage Law (KVL), which are special cases of
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Fig. 104. An isolated cell C(j) at location j and its coupling circuit S(j). Each node number is enclosed by a ellipse. All
voltages V1s (j − 1), V1s (j), V1s (j + 1), V1 (j − 1), V1 (j), and V1 (j + 1) represent node-to-datum voltages. All currents I1s (j − 1),
I1s (j), and I1s (j + 1) are defined with an associated reference direction [Chua et al., 1985] entering the coupling circuit S(j). All
currents I1 (j − 1), I1 (j), and I1 (j + 1) are defined with an associated reference direction entering the cells. The conductance
of each linear resistor in S(j) is equal to D1 .
Fig. 105. Nonlinear circuit model for a one-dimensional Reaction-Diffusion CNN having one nonzero diffusion coefficients
(D1 > 0). (a) Zero-flux (Neumann) boundary condition. (b) Periodic (toroidal) boundary condition.
all cells outside of the sphere of the influence of Equation defined by Eqs. (174)–(176) can be ex-
cell C(j). actly simulated by cascading the circuit building
Each cell C(j) is completely defined by a state blocks shown in Fig. 104.
equation via Eq. (177), and is associated with a pair For a zero-flux (Neumann) boundary condition,
of variables (I1 (j), V1 (j)) whose product the resulting circuit model for the above FitzHugh-
Nagumo Equation is shown in Fig. 105(a). For
∆
P1 (j) = I1 (j)V1 (j) (181) a periodic (toroidal) boundary condition, the cor-
responding circuit model is a ring, as shown in
at any time t is equal to the instantaneous power Fig. 105(b).
entering cell C(j) at t [Chua, 1969].39 Although the above presentation was based on
Observe that if we connect the corresponding the FitzHugh-Nagumo Equation, the alert reader
nodes in Fig. 104 into a single node j , and ap- will notice that so far, we have never made use of
ply Kirchhoff Current Law at j , we would ob- the definitions of f1 (V1 , V2 ) and f2 (V1 , V2 ) given in
tain Eq. (178). Similarly, Kirchhoff Voltage Law Eq. (175). Moreover, the same results would fol-
implies Eq. (179). Observe next that if we ap- low if there are more than two state variables, i.e. if
ply the two Kirchhoff Laws to the coupling circuit n > 2 in Eq. (173), or if there are more than one
S(j), we would obtain Eq. (180). In other words, spatial variables. The only essential requirement for
the cell coupling laws defined by Eqs. (178)–(180) the circuit models in Fig. 105 to hold is that all but
are exactly realized by the resistive coupling circuit one diffusion coefficients are zero. In other words,
S(j). It follows that the FitzHugh-Nagumo CNN every Reaction-Diffusion CNN having only one
39
For the associated reference direction shown in Fig. 104, P (j) > 0 at time t means power is delivered to cell C(j) at time t.
CNN: A Vision of Complexity 2403
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 106. Nonlinear circuit model for a two-dimensional Reaction-Diffusion CNN having one nonzero diffusion coefficients
(D1 6= 0) and zero-flux (Neumann) boundary conditions. All linear resistors are identical with conductances equal to D1 .
spatial dimension and only one nonzero diffusion following cell dynamics:
coefficient can be modeled by a one-dimensional
V̇1 (j, k) = f1 (V1 (j, k), V2 (j, k), . . . , Vn (j, k))
nonlinear circuit model, as shown in Fig. 105, by
simply defining the associated cell dynamics and + I1 (j, k)
cell coupling laws.
V̇2 (j, k) = f2 (V1 (j, k), V2 (j, k), . . . , Vn (j, k))
The above procedure can be easily generalized
to higher spatial dimensions. For a two-dimensional ..
.
Reaction-Diffusion CNN with n state variables and
one nonzero diffusion coefficient, say D1 6= 0, V̇n (j, k) = fn (V1 (j, k), V2 (j, k), . . . , Vn (j, k))
Eq. (173) assumes the form (184)
V̇1 (j, k) = f1 (V1 (j, k), V2 (j, k), . . . , Vn (j, k)) For a two-dimensional Reaction-Diffusion CNN
with n state variables and two nonzero diffu-
+ D1 ∇2 V1 (j, k) sion coefficients, say D1 6= 0 and D2 6= 0, the
above equations remain valid upon adding the term
V̇2 (j, k) = f2 (V1 (j, k), V2 (j, k), . . . , Vn (j, k)) D2 ∇2 V2 (j, k) to the second equation in Eq. (182),
.. and the term I2 (j, k) to the second equation in
. Eq. (184). The corresponding nonlinear circuit
V̇n (j, k) = fn (V1 (j, k), V2 (j, k), . . . , Vn (j, k)) model shown in Fig. 107 requires a second linear
(182) resistive grid layer where all resistors have identical
conductances equal to D2 6= 0, and where each cell
where C(j, k) has two external terminals having currents
I1 (j, k) and I2 (j, k), as shown in Fig. 108(a).
∆
∇2 V1 (j, k) = V1 (j + 1, k) + V1 (j − 1, k) The generalization to the case where there
are m nonzero coefficients is obvious. Each
+ V1 (j, k + 1) + V1 (j, k − 1) cell C(j, k) now has “m” external terminals
− 4V1 (j, k) . (183) with node-to-datum voltages V1 (j, k), V2 (j, k), . . . ,
Vm (j, k), and currents I1 (j, k), I2 (j, k), . . . ,
The corresponding nonlinear circuit model shown Im (j, k), as shown in Fig. 108(b). For each nonzero
in Fig. 106 is a direct generalization of Fig. 105(a). diffusion coefficient Di 6= 0, we have a resistive
Each cell C(j, k) in this figure is described by the grid having identical conductances equal to Di
2404 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 107. Nonlinear circuit model for a two-dimensional Reaction-Diffusion CNN having two nonzero diffusion coefficients
(D1 6= 0 and D2 6= 0) and zero-flux (Neumann) boundary condition. All resistors in the upper layer have identical conductances
equal to D1 . All resistors in the lower layer have identical conductances equal to D2 . Each cell has two external input ports
where energy can flow in or out, via the coupling circuit, to the neighboring cells.
Fig. 108. Symbol of a CNN cell C(j, k). Each terminal current Ii (j, k) is associated with node ji , ki (the rectangle here
is denoted by ellipses in the figure) of the ith resistive grid layer, where i = 1, 2 in (a) for the case D1 6= 0, D2 6= 0, and
i = 1, 2, . . . , m in (b) for the case D1 6= 0, D2 6= 0, . . . , and Dm 6= 0. Each terminal voltage Vi (j, k) denotes the node-to-datum
voltage from node ji , ki of the ith resistive grid with respect to the datum (ground) node. All resistors in the ith resistive
grid layer have identical conductances equal to Di .
and whose node (ji , ki ) is connected to terminal in the circuit theory literature [Chua, 1969]. We
(ji , ki ) of cell C(j, k), as shown in Fig. 109. will borrow this terminology and henceforth refer
Since electrical energy can flow in or out of each to each external terminal of a CNN cell as a cou-
cell C(j, k) in Fig. 108 only through its external ter- pling port since it is only through the coupling ports
minals, these terminals are sometimes called ports that energy from each cell can flow into, or from,
CNN: A Vision of Complexity 2405
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 109. Nonlinear circuit model for a two-dimensional Reaction-Diffusion CNN having “m” nonzero diffusion coefficients
(Di 6= 0, i = 1, 2, . . . , m) and zero-flux (Neumann) boundary condition. Only one m-port cell is shown to avoid clutter.
The subscript “i” attached to (ji , ki ) denotes the node in the ith resistive grid layer which is connected to a terminal of cell
C(j, k).
its neighboring cells, via the coupling circuit. In the to [Chua, 1969; Chua et al., 1985]:
case of Reaction-Diffusion CNNs with “m” nonzero
diffusion coefficients, the coupling circuit consists X
m
P (t; j, k) = Ii (t; j, k)Vi (t; j, k) (185)
of “m” layers of linear resistive grids, one layer for i=1
each nonzero diffusion coefficient. Similarly, we will
call the cell in Figs. 104, 108(a), and 108(b) a one- where we have re-inserted the time t into the argu-
port CNN cell, a two-port CNN cell, and an m-port ments of Ii (j, k) and Vi (j, k) to emphasize that they
CNN cell, respectively. must be evaluated in Eq. (185) at time t. The signif-
Since each port current Ii (j, k) of Cell C(j, k) icance for choosing the very convenient though arbi-
in Fig. 108(b) is assigned an associated reference trary Associated Reference Convention [Chua et al.,
direction (i.e. entering the cell) relative to its as- 1985] shown in Fig. 108 is to simplify the book-
sociated node-to-datum voltage, the total power keeping of energy flows, or power,40 in and out
P (t; j, k) entering cell C(j, k) at time t is equal of each CNN cell: It can be shown via Maxwell’s
40
Although strictly speaking power is defined as the rate of change of energy, we will often use “energy flow” and “power flow”
synonymously in this chapter.
2406 L. O. Chua
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
Fig. 110. Nonlinear circuit model of the three-dimensional Reaction-Diffusion CNN for Example 3.2.2. There are two three-
dimensional resistive lattices corresponding to the two diffusion coefficients Du (on the left) and Dv (on the right). Each node
(ji , ki , li ) of each lattice is connected to six identical linear resistors with a conductance equal to Du on the left, and Dv on
the right, respectively. The circuit inside the shaded two-port (bottom right) is the Chua’s oscillator whose state equation is
given by Eq. (151). The nonlinear v − i curve is for a typical Chua’s diode [Madan, 1993]. The actual characteristic is shown
in Fig. 87.
Equations that under this convention, P (t; j, k) > operations, in contrast to the much slower numer-
0 at time t1 means that there is a net amount of ical simulations via computers. Such hardware re-
power equal to P (t1 ; j, k) flowing into cell C(j, k) alizations are called for in applications where many
at time t = t1 . Conversely, P (t; j, k) < 0 at experiments and measurements must be carried out
time t2 means that a net amount of power equal in real-time [Perez–Muñuzuri et al., 1993b]. For
to |P (t2 ; j, k)| is flowing out of cell C(j, k) at time such applications we must synthesize a circuit cell,
t = t2 . in contrast to a mathematical cell, having the pre-
In all nonlinear circuit models for Reaction- scribed state equations. This can always be done
Diffusion CNNs shown in Figs. 105–109, the CNN [Chua et al., 1995; Chua, 1975] but is not needed for
cells are described mathematically via a state equa- understanding and analyzing local activity, which
tion, such as Eqs. (177) and (184). This mathemat- is the sole purpose of this chapter. We will close
ical characterization of CNN cells is all that we need this section, however, by presenting one such ex-
to carry out a complete mathematical, numerical, or ample for illustrative purposes. Figure 110 shows
circuit-theoretic analysis of the associated Reaction- the nonlinear circuit model of the three-dimensional
Diffusion CNN, including the local activity property Reaction-Diffusion CNN described earlier in Exam-
to be defined in the next section. It is not neces- ple 3.2.3 of Sec. 3.2, where each CNN cell is defined
sary to find a circuit realization of the CNN cells in by a “Chua’s oscillator” circuit.
terms of elementary circuit elements, such as linear
and nonlinear resistors, inductors, capacitors, bat-
teries, controlled sources, diodes, transistors, etc., 4.3. What is local activity?
unless we are interested to build the CNN in hard-
ware (via discrete off-the-shelf components), or to Although the concept of local activity is extremely
fabricate a VLSI chip, in order to obtain high-speed general, and can be easily translated into other
CNN: A Vision of Complexity 2407
Anderson & Vongpanitlerd, 1973; Brayton et al., pattern is possible in Fig. 105(a) if the cells are
1978]. Secondly, if a theory is ever needed to help made of only batteries and nonlinear resistors char-
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
resolve any paradox or dilemma that might be trig- acterized by strictly-monotone increasing constitu-
gered by this paper, one can always revert to the tive relations (i.e. voltage-current characteristics),
well-established local activity theory of the ubiq-
in addition to linear positive resistors, inductors,
uitous transistor, the workhorse of microelectronic
and capacitors. Some more subtle property than
chips and undoubtedly, the most intensely stud-
just “nonlinearity” is essential for the circuit model
ied and best understood of all local-active devices
in Fig. 105 to exhibit a static or dynamic pattern,
to date.
For the sake of clarity, we will sacrifice gen- and this illusive condition to be uncovered below is
erality in this section and choose the simple one- what we call local activity.
dimensional FitzHugh-Nagumo Reaction-Diffusion
CNN in Fig. 105(a), and defined by Eqs. (174)– 4.3.1. Cell equilibrium points
(176) as our vehicle for presentation. Now recall
To define the concept of local activity for a CNN
that a CNN is completely defined by only two pieces
cell, such as the one-port shown in Fig. 104, the two-
of information: Cell dynamics and cell coupling
port shown in Fig. 108(a), and the m-port shown
laws. For the Reaction-Diffusion CNNs shown in
Figs. 105–109, the cells are modeled by “m-ports” in Fig. 108(b), we must derive first its associated
(where “m” is the number of external ports, which static driving-point characteristic, henceforth ab-
is equal to the number of nonzero diffusion coeffi- breviated as DP characteristic,41 which relates the
cients) and the coupling laws are modeled by a cou- port current and the port voltage variables of the
pling circuit (made of “m” resistor lines, grids, or CNN cell at equilibrium, i.e. when V̇i (j, k, l) = 0,
lattices for CNNs with one-, two-, or three-spatial i = 1, 2, . . . , m. For the one-port CNN cell defined
dimensions). in Eq. (177), the first step to derive its static DP
If we impose the usual physical assumption characteristic is to set V̇1 (j) = 0 and V̇2 (j) = 0. (We
that the diffusion coefficients are non-negative, then will henceforth delete the argument “j” to avoid
the coupling circuit is just a “box” of intercon- clutter):
nected positive linear resistors, and is therefore
purely dissipative in the sense that all energies f1 (V1 , V2 ) + I1 = 0 (186a)
flowing into the coupling circuit are dissipated as f2 (V1 , V2 ) = 0 (186b)
heat. Since the coupling circuit is a heat sink,
it is intuitively reasonable to expect that in order Since there is only one port current I1 and only one
for the node voltages Vj , j = 1, 2, . . . , N , in the port voltage V1 in a one-port CNN cell, its static DP
41
The term “driving point” is a circuit-theoretic jargon for stressing the condition that energy can enter the cell only by
driving an input signal though its external ports.
2408 L. O. Chua
∆
G1 (V1 , V2 , . . . , Vm , I1 ) = f1 (V1 , V2 , . . . , Vm , g1 (·), g2 (·), . . . , gn−m (·)) + I1 = 0
∆
G2 (V1 , V2 , . . . , Vm , I2 ) = f2 (V1 , V2 , . . . , Vm , g1 (·), g2 (·), . . . , gn−m (·)) + I2 = 0
(194)
..
.
∆
Gm (V1 , V2 , . . . , Vm , Im ) = fm (V1 , V2 , . . . , Vm , g1 (·), g2 (·), . . . , gn−m (·)) + Im = 0
CNN: A Vision of Complexity 2409
and
∆
I1 = F1 (V1 , V2 , . . . , Vm ) = −f1 (V1 , V2 , . . . , Vm , g1 (·), g2 (·), . . . , gn−m (·))
∆
I2 = F2 (V1 , V2 , . . . , Vm ) = −f2 (V1 , V2 , . . . , Vm , g1 (·), g2 (·), . . . , gn−m (·))
(195)
..
.
∆
Im = Fm (V1 , V2 , . . . , Vm ) = −fm (V1 , V2 , . . . , Vm , g1 (·), g2 (·), . . . , gn−m (·))
(198)
dV2 (t)
= f2 (V 1 , V 2 ) + a21 (V1 (t) − V 1 )
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
coefficients calculated from Eq. (175) are given by: CNN cell, and a corresponding continuum of local
cell coefficients.
2
a11 = −(V 1 − 1) , a12 = −1 Consider next the local state equation at any
(201) cell equilibrium point (V 1 , I 1 ). Let v1 (t) denote the
a21 = − , a22 = b
solution of Eq. (200) corresponding to any given
where (V 1 , I 1 ) is the cell equilibrium point deter- time function i1 (t), subject to zero initial states
mined from the last equation in Eq. (191). To be v1 (0) = 0 and v2 (0) = 0. Let us define
more concrete, let us assume a = 0 and I1 = I 1 = 0 ∆
p(t) = v1 (t)i1 (t) , t≥0 (207)
so that the resulting equation
henceforth called the local power flow at time t at
1 3 1 1 1
V + − 1 V1 = V1 V12 + −1 =0 cell equilibrium point (V 1 , I 1 ). It is sometimes con-
3 1 b 3 b venient to interpret p(t) as the instantaneous power
(202) flowing into a CNN cell at time t whose state equa-
tion is given by Eq. (200), and whose current refer-
can be solved analytically; namely, ence direction is as shown in Fig. 104. Recall that
if b ≤ 1 this Associated Reference Conversion implies that
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
V1 = V 1 = 0 , (203)
if p(t) < 0 at t = t1 , then the cell is actually acting
as a source of power at time t = t1 , where power
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
and
flows out of the cell into the “outside world”, which
V1 = V 1 = 0 , in this case consists of the resistive coupling circuit
s s and the other cells.
1 1 1 1 (204)
1− , − 1− , if b > 1 . Observe that unless the CNN cell is endowed
3 b 3 b with an innate ability to act as a source of “local”
power under passive terminations (namely, the dis-
Hence, a11 = 1, a12 = −1, a21 = − and a22 = b sipative coupling box in Reaction-Diffusion Equa-
are uniquely determined if b ≤ 1, but can assume tions) at least over some periods of time, no local
three sets of values if b > 1, one for each of the above power gain is possible and entropy in the CNN will
three distinct cell equilibrium points, namely, keep increasing as heat is dissipated, even if the cells
s ! are continually supplied with energy by batteries.
1 1
(V 1 , I 1 ) = (0, 0) , 1− ,0 , Generalizing Eq. (196) to an “m-port” cell hav-
3 b ing “n” state equations and m ≤ n nonzero diffusion
s ! (205)
coefficients, we obtain
1 1
− 1− ,0 . dV1 (t)
3 b = f1 (V1 (t), V2 (t), . . . , Vn (t)) + I1 (t)
dt
The corresponding local cell coefficients in this case
dV2 (t)
are given respectively by42 : = f2 (V1 (t), V2 (t), . . . , Vn (t)) + I2 (t)
dt
" # " #
a11 a12 1 −1 ..
= , .
a21 a22 − b
(206) dVm (t)
2 1 2 1 = fm (V1 (t), V2 (t), . . . , Vn (t)) + Im (t)
3 + 3b −1 3 + 3b −1 dt
, .
dVm+1 (t)
− b − b = fm+1 (V1 (t), V2 (t), . . . , Vn (t))
dt
Observe that the above sets of local cell coef- ..
ficients are calculated by assuming I 1 = 0 for sim- .
plicity. Since I1 in Eq. (191) may assume any real dVn (t)
number, there are actually a continuum of distinct = fn (V1 (t), V2 (t), . . . , Vn (t))
dt
cell equilibrium points for the FitzHugh-Nagumo (208)
42
The last two matrices are identical in this case in view of the odd symmetry of I1 = F(V1 ) in Eq. (191) when a = 0.
CNN: A Vision of Complexity 2411
∆
The associated Local State Equation at a cell equilibrium point Q = (V 1 , V 2 , . . . , V m , I 1 , I 2 , . . . , I m ),
defined by Eq. (194), or Eq. (195), and subject to zero initial state v1 (0) = v2 (0) = · · · = vn (0) is given by:
aij = (210)
∂Vj Q
a locally-active CNN cell must behave exactly like
a transistor operating at an active operating point
are the local cell coefficients at the cell equilibrium whereby a “small” (low-power) input signal can be
point Q. Using vector notations, we can recast converted into a “large” (high-power) output sig-
Eq. (209) into a form similar to Eq. (200); namely, nal at the expense of an energy supply43; namely,
a battery in this case. In other words, we will say
an m-port CNN cell is locally active at a cell equi-
v̇a = Aaa va + Aab vb + ia ∆
(211) librium point Q = (Va , Ia ) if it is possible to find
v̇b = Aba va + Abb vb a local (i.e. infinitesimal) input port current signal
ia (t) such that by applying the global input port
current Ia (t) = Ia + ia (t), we can extract more “in-
where va = [V1 , V2 , . . . , Vm ]T , ia = [i1 , i2 , . . . , im ]T , finitesimal” signal energy δE(Q) at Q over some
vb = [Vm+1 , Vm+2 , . . . , Vn ]T , and where Aaa , time interval 0 < t ≤ T than what the cell has taken
Aab , Aba , and Abb are appropriately partitioned from its external environment (which consists of the
submatrices. coupling circuit and all other cells). In this case, the
Finally, the local power flow entering the “m- net local (infinitesimal) energy gain is supplied by
port” CNN cell in Fig. 108(b) at a cell equilibrium the energy derived from the large constant input
point Q is defined, analogously to Eq. (207), by port current Ia . We are now ready to define local
activity in a mathematically precise form.
∆ X
m
p(t) = vj (t)ij (t) , t≥0 (212) Definition 4.3.2. Locally-Active Reaction-Diffu-
j=1 sion CNN Cell.
The m-port CNN cell shown in Fig. 108(b)
and described by Eq. (208) is said to be lo-
4.3.3. Local activity in cally active at a cell equilibrium point Q =
∆
reaction-diffusion CNN cells (V 1 , V 2 , . . . , V m , I 1 , I 2 , . . . , I m ) if, and only if,
In general, the “sign” of the local power flow p(t) there exists a local port current ia (t) such that
into an m-port CNN cell does not remain constant, Z T
∆
but can change back and forth over the course of δE(Q) = p(t)dt < 0 (213)
0
43
In circuit theory, the word signal usually means a small information-bearing (hence time-varying) component x(t) of a
composite time function X(t) = X + x(t) where |X| |x(t)| is a constant called the dc (for direct current) component. In
this section, we will refer to X(t), X, and x(t) as the global time function, cell equilibrium point and local signal, respectively.
2412 L. O. Chua
for some time T > 0, where p(t) denotes the local local cell coefficients aij from Eq. (210), which
power flow at Q, defined by Eq. (212), and vi (t) is depends on the local equilibrium point Q.
computed from the associated Local State Equation (4) Definition 4.3.2, like most definitions, is not
at Q, defined by Eq. (209), with zero initial states constructive in the sense that the reader is left
vj (0) = 0, j = 1, 2, . . . , n. with the burden of finding an appropriate port
current ia (t) which makes δE(Q) negative. This
Remarks task is like fishing a needle in a haystack and
(1) Since p(t) represents the power flow into a CNN is clearly impractical. In fact, in many cases,
cell at time t, δE(Q) can be interpreted as the no such port current ia (t) exists but it is never-
net energy entering the cell from t = 0 to t = T . theless necessary to exhaust all possible port
Since δE(Q) < 0 in Eq. (213), a net amount currents before one is entitled to condemn a
of energy equal to |δE(Q)| is actually extracted particular CNN cell as not locally active at a
from the CNN cell during the time interval, particular local cell equilibrium point Q. Such
0 < t ≤ T , i.e. in a small neighborhood of a CNN cell will henceforth be called locally
Q, the CNN cell is acting like an energy source passive44 at Q. A CNN cell is said to be not
for any input port current ia (t) which makes locally active, or simply local passive, if there
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
stant of time T . In fact, there is no loss of (5) Much of the classic circuit theory literature
generality to let T = ∞ in Eq. (213) because if is devoted to deriving practical procedures for
ia (t) = g(t) is a local port current signal which testing whether a linear m-port is passive, and
makes δE(Q) < 0 at T = T1 , we can always several equivalent sets of necessary and suffi-
define a truncated signal cient conditions are available for this purpose
( [Guillemin, 1957; Tuttle, 1958; Anderson &
∆ g(t), t ≤ T1 Vongpanitlerd, 1973]. For an m-port CNN cell
îa (t) = (214)
0, t > T1 to be locally active at Q, the associated linear
m-port must violate at least one of these neces-
which gives the same property δE(Q) < 0 at
sary conditions. It is possible therefore to derive
T = ∞.
many equivalent criteria for testing whether an
(3) Since the local state equation (209) is a system
m-port CNN cell is locally active, some of them
of linear differential equations, if va (t) and p(t)
will be presented in the next section.
denote the solution and the local power flow
due to a local port current ia (t), then kva (t) and
k2 p(t) are the corresponding solution and power 4.4. Testing for local activity
flow (under zero initial states) when the input
is changed to kia (t). In other words, scaling There exist many equivalent passivity criteria in the
the input port current kia (t) in Eq. (211) does literature for testing when a linear m-port is pas-
not affect the sign of δE(Q). It follows therefore sive. Since the local activity of an m-port CNN
∆
that in so far as testing Eq. (209) for local activ- cell at a cell equilibrium point Q = (Va , Ia ) of
ity is concerned, there is no need to restrict the Eq. (208) is defined in terms of a linear state
variables va (t), ia (t) and vb (t) in Eq. (211) to equation, namely, Eq. (209), we can associate
small signals. It is often convenient therefore the local state equation with that of a linear m-
to think of the Local State Equation (209) at port and then simply apply any convenient pas-
Q as the global state equation of an associated sivity criteria to Eq. (209) directly. Since most
linear m-port CNN cell which inherits the local passivity criteria in the literature are formulated
activity property from its “parent”. The only in the complex s-domain, where s is a complex
time when locality is crucial is in calculating the variable associated with the Laplace Transform45
44
Passivity is a classic circuit-theoretic property exhibited by any m-port made of only passive circuit elements, such as linear
positive resistors, inductors and capacitors [Guillemin, 1957].
45
Throughout this section, variables with a “hat” are Laplace Transform variables. Hence, v̂k (s) is the Laplace transform of
vk (t), and îk (s) is the Laplace transform of ik (t).
CNN: A Vision of Complexity 2413
it is necessary that we transform Eq. (209) from If we choose 0 < b ≤ 1, then it follows from
the time domain to the s-domain first. We will Eq. (203) that (V 1 , I 1 ) = (0, 0) is the only cell
illustrate this standard procedure in the following equilibrium point when I 1 = 0. In this special case,
subsections. Eq. (219) reduces further to
(s − b)
4.4.1. Testing one-port CNN cells for ZQ (s) = , 0<b≤1
s2 − (1 + b)s + (b − 1)
local activity
(220)
Consider first the one-port CNN cell defined by
Eq. (196), which is a special case of Eq. (208) with We can easily extend Eq. (218) for a general
∆ one-port CNN cell having “n” state variables. In
m = 1 and n = 2. Let Q = (V 1 , I 1 ) be a cell equilib-
this general case, n > 2 and the associated local
rium point of Eq. (196) and consider the associated
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Observe that ZQ (s) in Eq. (223) is a scalar is either a complex number, or a negative real
function of s even though the expression on the right number.
contains the three matrices Aab , Aba , and Abb de- (4) ZQ (s) has a multiple pole on the imaginary axis.
fined in Eq. (222). Indeed, for the special case where
n = 2, the submatrices Aab = a12 , Aba = a21 , and
Abb = a22 are all scalars and Eq. (223) reduces to Proof. This theorem is a direct translation of a
Eq. (218), as it should. The reader is encouraged to classic result from circuit theory which asserts that
carry out this straightforward reduction and by do- a linear time-invariant one-port with impedance
ing so, verify that the impedance ZQ (s) in Eq. (223) Z(s) is passive if, and only if, Z(s) is a positive
can always be recast into the following standard real function. A rational function Z(s) is called a
form of a rational function of s, namely, a ratio of positive real function if Z(s) is analytic in Re[s] > 0
two polynomials p(s) and q(s) of degree α and β, (i.e. Z(s) has no poles in the open right half plane)
respectively, where α and β are integers, and where and if Z ∗ (s) + Z(s) ≥ 0 for all Re[s] = σ > 0.
the coefficients ak and bk depend only on the local The following well-known necessary and sufficient
cell coefficients ajk at Q: conditions for Z(s) to be passive can be found in
any text on linear circuit synthesis [Guillemin, 1957;
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
(s − a22 )
ZQ (s) = (227) is always a complex number if a22 6= 0. Hence,
s2 − Ts + ∆
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
[Eq. (153)] also belongs to this class with m = 2 and Substituting Eq. (232) for v̂b (s) in the first equation
∆ of Eq. (231), and solving for v̂a (s), we obtain
n = 3. Let Q = (V 1 , V 2 , I 1 , I 2 ) be a Cell Equilib-
rium Point of the corresponding two-port CNN cell
[Fig. 108(a)]. The associated local state equation at v̂a (s) = ZQ (s)îa (s) (233)
Q is given by Eq. (209) or Eq. (211) with m = 2.
where48
The four matrices in Eq. (211) are given by
" #
ZQ (s) = [(s1 − Aaa ) − Aab (s1 − Abb )−1 Aba ]−1
∆
a11 a12
Aaa = ,
a21 a22 (234)
" #
a13 a14 ··· a1n
Aab = is a 2 × 2 matrix function of s, henceforth called the
a23 a24 ··· a2n CNN cell impedance matrix at Q.
a31 a32 In contrast to the scalar cell impedance ZQ (s)
for one-port CNN cells, the local state equation of a
a41 a42
two-port CNN cell is characterized by a 2×2 matrix
Aba = . .. , (230)
.. . function of s:
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
" #
an1 an2 Z11 (s) Z12 (s)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
ZQ (s) = . (235)
a33 a34 ··· a3n Z21 (s) Z22 (s)
a43 a44 ··· a4n
It can be shown that each element Zij (s) in
Abb = . ..
.. .
Eq. (235) is always a rational function of s,
an3 an4 ··· ann i.e. Zij (s) = pij (s)/qij (s) where pij (s) and qij (s) are
polynomials in s, just like the scalar cell impedance
where Aaa , Aab , Aba , and Abb are 2 × 2, 2 × (n − 2), ZQ (s) in Eq. (223). We are now ready to state the
(n − 2) × 2, and (n − 2) × (n − 2) matrices, respec- necessary and sufficient conditions for a two-port
tively. Taking the Laplace transformation of both Reaction-Diffusion CNN cell to be locally active at
sides of Eq. (211), we obtain Q(V 1 , V 2 , I 1 , I 2 ).
sv̂a (s) = Aaa v̂a (s) + Aab v̂b (s) + îa (s) Theorem 4.4.2. Local Activity Criteria for Two-
(231) Port Reaction-Diffusion CNN Cell.
sv̂b (s) = Aba v̂a (s) + Abb v̂b (s) .
A two-port Reaction-Diffusion CNN cell is lo-
∆
Solving for v̂b (s) from the second equation in cally active at a cell equilibrium point Q = (V 1 ,
Eq. (231) we obtain V 2 , I 1 , I 2 ) if, and only if, its cell impedance matrix
ZQ (s) at Q satisfies at least one of the following
v̂b (s) = (s1 − Abb )−1 Aba v̂a (s) . (232) four conditions 49 :
48
Observe that 1 is a 2 × 2 unit matrix in the first term, but an (n − 2) × (n − 2) unit matrix in the second term, on the right
side of Eq. (234).
49
We say ZQ (s) has a pole s = sp if at least one element of Zij (s) of ZQ (s) has a pole at s = sp . If an element Zij (s) has
a pole s = sp , there is no loss of generality to assume that all other elements also have a pole at s = sp since we can always
multiply both the numerator and the denominator of Zkl (s) by the factor (s − sp ).
We use the dagger † to denote the Hermitian operator, i.e. Z†Q (s) is constructed by taking first the transpose of ZQ (iω),
√
and then followed by the complex conjugate operation, i.e. change i = −1 to −i in all terms. A matrix A is said to be a
Hermitian matrix if A = A† . Observe that ZH Q (iω) in condition (2) is a Hermitian matrix, since
∗ ∗
Z11 (iω) Z21 (iω) Z11 (iω) Z12 (iω)
ZH
Q (iω) = ∗ ∗
+
Z12 (iω) Z22 (iω) Z21 (iω) Z22 (iω)
∗ ∗
Z11 (iω) + Z11 (iω) Z21 (iω) + Z12 (iω)
= ∗ ∗
Z12 (iω) + Z21 (iω) Z22 (iω) + Z22 (iω)
†
= [ZH
Q (iω)]
CNN: A Vision of Complexity 2417
(236)
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
diffusion coefficients and two state variables, matrix, condition (2) is equivalent to the simpler
2418 L. O. Chua
condition that the constant matrix GQ should not not locally active at all possible cell equilibrium
be a positive semi-definite matrix. states, then, except for certain singular and de-
generate cases which do not concern us here (since
Remarks they cannot give rise to “robust” patterns) it can
1. The above local activity criteria are construc- be proved [Chua, 1980] that each isolated m-port
tive because each condition can be tested CNN cell in this case must have a unique cell equi-
systematically. librium state with unique port voltages V i (j, k, l),
2. All results in this section can be generalized, mu- i = 1, 2, . . . , m, for each set of port currents
tatis mutandis, to any Reaction-Diffusion CNN I i (j, k, l) ∈ (−∞, ∞), i = 1, 2, . . . , m, where
with any m > 2 nonzero diffusion coefficients, Eq. (194) has a solution.
∆
any number of spatial coordinates, and any num- Now recall that a cell equilibrium state Q =
ber n ≥ m of state variables. In fact, all con- (V i , I i ), i = 1, 2, . . . , m, pertains only to individ-
ditions remain unchanged except that there are ual isolated cells, each one driven separately by
now n2 coefficients aij from the n × n Jacobian the same port current I i , i = 1, 2, . . . , m. Ob-
matrix of f (·). serve, however, that after the interconnections are
3. A Reaction-Diffusion CNN with m = n (i.e. made, via the resistive coupling layers, the result-
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
when the number of nonzero diffusion coeffi- ing circuit array becomes a CNN, which is uniquely
cients is equal to the number of state variables defined mathematically by a very large system of
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
in the “kinetic” part ẋαβγ = f (xαβγ ) of the ordinary nonlinear Reaction-Diffusion Equations,
equation.) is locally active at Q if, and only namely, Eq. (133). Each solution xαβγ of this sys-
∆ tem’s equilibrium equation
if, the systematic part Js = JT + J of the
∆
Jacobian matrix J = ∂f (x)/∂x of f (xαβγ ) =
f (xαβγ ) + D∇2 xαβγ = 0 (243)
−f (xαβγ ) is not positive semi-definite. Hence,
the local activity criteria for the Brusselator is an equilibrium state of the CNN. One such equi-
PDE, the Meinhardt-Gierer PDE, and the Oreg- librium state is clearly a uniform distribution of
onator PDE listed in Table 3.2.1 can all be the above port voltage V i (j, k, l) of the isolated-
tested by examining a real matrix Js . Ob- cell C(j, k, l) at all nodes within the “ith” resistive
serve that the resulting criteria contain only pa-
coupling layer, i = 1, 2, . . . , m. This follows from
rameters from the “kinetic” part, and not the
the observation that in this case, the two node-to-
diffusion coefficients, which are assumed to be
datum voltages at each pair of resistor terminals
non-negative.
are equal to each other and hence the current in
4. The above discourse on local activity could have
each resistor is zero in view of Ohm’s law. Conse-
been formulated mathematically in an axiomatic
quently, the port currents Iis (j, k, l) entering each
way without mentioning any circuit. However,
the physical intuition and motivation behind this node j, k, l of each resistive coupling layer “i” is
subtle concept would be lost. also zero in view of Kirchhoff current law. Hence, in
this case, even though the composite circuit is phys-
ically connected, from an electrical point of view,
4.5. Why is local activity necessary the circuit behaves as if all cells have been discon-
for pattern formation?
nected so that the same cell equilibrium state volt-
We have shown in Sec. 4.2 that every Reaction- ages V i (j, k, l) remain unchanged even after the
Diffusion CNN Equation, such as those listed in Ta- interconnection has been made (see Fig. 104 for a
ble 3.2.1, has an exact circuit model consisting of concrete case). The above conclusion can in fact be
interconnections of identical m-port CNN cells50 via easily derived directly from Eq. (176) (for the “one”
“m” resistive lines, grids, or lattices (for one, two or spatial dimension case) or Eqs. (132) and (133) (for
three spatial dimensions, respectively), henceforth CNNs with three spatial dimensions) upon observ-
s
simply referred to as resistive coupling layers, made ing that I i (j, k, l) = −∇2 V i (j, k, l) = 0 if V i (j −
of linear positive coupling conductances. If the m- 1, k − 1, l − 1) = V i (j, k, l) = V i (j + 1, k + 1, l + 1),
port CNN cells are locally passive, i.e. if they are i = 1, 2, . . . , m.
50
Recall the integer “m” is equal to the number of nonzero diffusion coefficients in the Reaction-Diffusion Equation.
CNN: A Vision of Complexity 2419
Now assuming the cells are locally passive not analytically, from Theorem 4.4.1 (or Corol-
(i.e. not locally active) and assuming Di > 0, lary 4.4.1) for Reaction Diffusion Equations with
i = 1, 2, . . . , m, then it follows from well-known one diffusion coefficient, from Theorem 4.4.2 (or
results from the qualitative theory of nonlinear cir- Corollary 4.4.2) for Reaction-Diffusion Equations
cuits [Chua & Green, 1976a, 1976b, 1976c] that, with two nonzero diffusion coefficients, and from
except for certain singular cases of no concern here, mth order versions of Theorem 4.4.2 [they are iden-
the entire composite system of equilibrium equa- tical to Theorem 4.4.2 and Corollary 4.4.2 except
tions in Eq. (227) must also have a unique solution. that there are now n2 coefficients aij from the n × n
Since no other solutions in addition to the above Jacobian matrix of f (·).] for m nonzero diffusion
homogeneous solution can exist, it follows that no coefficients.
non-homogeneous static, let alone dynamic, volt- Any set of CNN parameters which satisfies one
age distributions within each resistive coupling layer of the “local activity” conditions in these theo-
can exist in this case. rems will make the CNN cell locally active. Con-
The above analysis shows that the cells must sequently, the union A of all such parameter sets
be locally active at least at some equilibrium state constitutes the CNN’s local activity parameter do-
in order for a Reaction-Diffusion CNN to exhibit main. We will henceforth call the set A as the
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
a non-uniform static or dynamic pattern.51 It is locally-active cell parameter domain, or simply local
now clear that locally-passive CNN cells are quite activity domain, of the CNN.
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
dull since they can only dissipate power, resulting It follows from the definition of “local activity”
in a net power loss. In thermodynamic parlance, that if A1 and A2 denote the local activity domain
this means that entropy in locally-passive CNNs of two identical CNN cells but with m1 and m2 ex-
must always increase with time even in open sys- ternal ports (equivalently, non-zero diffusion coeffi-
tems where energy is continuously supplied from cients), respectively, then A1 ⊂ A2 if m1 < m2 . In
batteries. In economics parlance, locally passive particular, the largest local activity domain occurs
CNNs are a drain on the economy. In biological
when the number of diffusion coefficients is equal to
parlance, locally passive CNNs are lifeless, they are
the number of state variables.
dead as door nails.
Given any Reaction-Diffusion CNN, we have a
constructive method for determining its associated
4.6. How to choose locally-active locally-active cell parameter domain A. For ex-
CNN parameters? ample, the local activity domain of the FitzHugh–
Every CNN has parameters which must be tuned to Nagumo Equation is easily derived from Corollary
achieve certain functions. For the standard CNNs 4.4.1 [Dogaru & Chua, 1998]. A CNN cell having its
considered in Parts I and II, these parameters de- parameters lying outside of A is locally passive and
termined the CNN genes. Mutations in a CNN gene hence cannot exhibit patterns when interconnected
can be defined as the migration of certain CNN pa- via any resistive coupling circuit with positive
rameters outside of its failure boundary, thereby conductances.
resulting in trajectories escaping from the desired
basin of attraction into other attractors. 4.7. Local activity and stability are
For Reaction-Diffusion CNN Equations, the different concepts
CNN parameters must be chosen so as to make
its cells locally active in order for complex phe- Readers familiar with the standard methods
nomena, such as pattern formation, to be possible. for deriving parameters from Reaction-Diffusion
These parameters can be derived, numerically if Equations in order to produce Turing patterns
51
For CNNs with more complicated coupling circuits, such as those found in standard CNNs, non-homogeneous patterns can
develop even with locally-passive CNN cells, provided the basic coupling units, such as the coupling box labeled S(j) in
Fig. 104, are locally active. In such cases, the coupling unit can be treated as a p-port, where p may depend on the spatial
dimension as well as on the number m of the CNN cells. In this case, the same procedure presented above for CNN cells
remains applicable, mutatis mutandis. In particular, analogous test for local activity of the coupling units can be similarly
formulated.
In view of the above observation, we will henceforth say a CNN is locally active if the cells or the coupling units or both
are locally active at least at one equilibrium point.
2420 L. O. Chua
[e.g. Eq. (151)] might be tempted to conjecture that tain sufficient conditions, we must clearly embed
making a cell locally active is equivalent to desta- the coupling circuits. The fundamental new con-
bilizing an isolated cell’s equilibrium point. Un- cept here is that if the cells are not locally active,
fortunately, this conjecture is incorrect because the no passive coupling circuits (the diffusion-based re-
“locally-active cell parameter domain” A of a CNN sistive grid is only a special case) of any complex-
cell does not contain the diffusion coefficients as pa- ity can be found to create patterns in the resulting
rameters. This is because the concept of local ac- CNN.
tivity is defined for isolated cells whereas the classic Finally, observe that it would be impossible to
concept of “stability” is defined for a system made derive a mathematically precise and universal mea-
of interconnected cells. Local activity is a physical sure of complexity based on system concepts alone
concept, whereas stability is a system concept. because such a theory must depend on the system
If a cell is not locally active, then it would be model being used. In contrast, our concept of local
impossible to destabilize an interconnected system’s activity is universal because the law of conservation
equilibrium point so long as the coupling circuit is of energy is universal and local activity is based only
locally passive, namely, so long as the diffusion co- on this law. The universality of the concept of local
efficients in the Reaction-Diffusion CNN are non- activity is manifested clearly by its local activity
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
negative. Local activity is based on the physical no- criteria (Theorems 4.4.1 and 4.4.2) which are in-
tion that the universal law of conservation of energy dependent of the nature of the CNN cells. Only
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
must impose certain fundamental limits on perfor- a function of a complex variable called local cell
mance, whereas stability is based on the mathemat- impedance ZQ (s), or local cell admittance YQ (s),
ical notion that the dynamics near an equilibrium is needed.
point is determined by its eigenvalues.
Readers familiar with dissipative structures 4.8. The local activity dogma
[Nicolis & Prigogine, 1977; Prigogine, 1980], syner-
getics [Haken, 1983], and other complexity related Although Part III has been couched almost entirely
dynamical analysis will recall the common condi- on Reaction-Diffusion CNN Equations, the local ac-
tion that at least one eigenvalue of the Jacobian tivity concept is universal and does not depend on
matrix of f (·) (associated with the kinetic laws in the choice of the CNN models. The only assump-
Reaction-Diffusion Equations) must have a positive tion we demand in this lengthy discourse is that
real part for patterns to exist. This condition is any system exhibiting complexity be represented by
exactly condition (1) of Theorems 4.4.1 and 4.4.2, a mathematical model which can be decomposed
and their corollaries. Observe, however, that this is into cells and coupling laws. The standard CNNs
only one out of four independent conditions each of and the Reaction-diffusion CNNs represent only
which is sufficient for local activity. In particular, two such models. A mathematical model is essen-
condition (2) can be satisfied with all eigenvalues tial because any theory on complexity which is not
having negative real parts! In fact, this is the stan- based on a mathematical model will forever be fuzzy
dard operating mode of most useful transistor cir- and its conclusions are suspect at best. Even the
cuits (except oscillators), and the basic problem in complexity of “real” life in biology must be formu-
designing transistor amplifiers is precisely to keep lated via realistic mathematical models before any
the eigenvalues in the open left half plane while ex- theory being advocated can be seriously endorsed
tracting local power gain! Indeed, the somewhat or challenged on firm grounds.
fuzzy notion of “edge of chaos” described in [Lang- It is hoped that this essay represents only the
ton, 1990] would correspond to operating a CNN in beginning of a new perspective and a new approach
this locally stable but potentially unstable parameter to the subject of complexity. We shall close there-
domain. fore by summarizing our conclusions with a dogma
It is important to observe that local activity is whose truth for all non-conservative systems (not
only a necessary condition for complexity. To ob- just for CNNs) must await the test of time.52
52
We assume that any future refinement that may be made in the definition of local activity in order to apply to more compli-
cated mathematical models will be based on the fundamental ideas introduced in Sec. 4.3. In each case, the associated CNN
“cell ” or “coupling” must be locally active. Finally, we remark that the local activity dogma applies only to “robust” complex
phenomena since it is easy to find CNNs which are not locally active but can exhibit a continuum of non-isolated patterns
depending on the initial condition. Such CNNs include mathematical models of conservative systems, systems endowed with
a non-trivial null space, etc.
CNN: A Vision of Complexity 2421
THE LOCAL ACTIVITY DOGMA with Volterra series,” IEEE Trans. Circuits Syst. 32,
A HOMOGENEOUS MEDIUM CANNOT EXHIBIT 1150–1161.
COMPLEXITY UNLESS IT IS LOCALLY ACTIVE Brayton, R. K., Chua, L. O., Rhodes, J. D. & Spence,
R. [1978] Modern Network Theory: An Introduc-
tion, guest lectures of the 1978 European Conference
on Circuit Theory and Design (Georgi Publishing,
Acknowledgment Switzerland).
Bures, J., Koroleva, V. I. & Gorelova, N. A. [1984]
I would like to thank the following colleagues and “Leao’s spreading depression, an example of diffusion-
research scholars from my laboratory for their in- mediated propagation of excitation in the central
valuable assistance in the preparation of this paper: nervous system,” in Autowaves and Structures Far
K. Crounse, R. Dogaru, M. Hasler, A. S. Huang, from Equilibrium, ed. Krinsky, V. I. (Springer-Verlag),
T. Kozek, G. Moschytz, J. Nossek, A. Perez– pp. 180–183.
Muñuzuri, T. Roska, G. Setti, B. Shi, K. Slot, Carina, R. F., Dietrich-Buchecker, C. & Sauvage, J.-P.
I. Szatmari, P. Thiran, R. Tetzlaff, T. Yang, [1996] “Molecular composite knots,” J. Am. Chem.
C. W. Wu and A. Zarandy. This work is partially Soc. 118, 9110–9116.
Chow, S.-N. & Mallet-Paret, J. [1995] “Pattern forma-
supported by the Office of Naval Research under
tion and spatial chaos in lattice dynamical systems,”
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
S78, a special grant from the Alexander Hum- Theory (McGraw Hill, New York).
boldt foundation, the Ecole Polytechnique Federale Chua, L. O. [1980] “Device modeling via basic nonlinear
de Lausanne (EPFL), the Eidgenossiche Technis- circuit elements,” IEEE Trans. Circuits Syst. 27(11),
che Hochschule (ETH) Zurich, and the Technische 1014–1044.
Universitat München. Chua, L. O. [1980] “Dynamic nonlinear networks: State
of the art,” IEEE Trans. Circuits Syst. 27(11),
1059–1087.
References Chua, L. O. & Green, D. N. [1976a] “Graph-theoretic
Allesie, M. A., Bonke, F. I. M. & Schopman, F. J. C. properties of dynamic nonlinear networks,” IEEE
[1973] “Circus movement in rabbit atrial muscle as a Trans. Circuits Syst. 23(5), 292–312.
mechanism in tachycardia,” Circ. Res. 33, 54–62. Chua, L. O. & Green, D. N. [1976b] “A qualitative anal-
Allesie, M. A., Bonke, F. I. M. & Schopman, F. J. C. ysis of the behavior of dynamic nonlinear networks:
[1977] “Circus movement in rabbit atrial muscle as Stability of autonomous networks,” IEEE Trans.
a mechanism of tachycardia. III. The ‘leading circle’ Circuits Syst. 23(6), 292–312.
concept: A new model of circus movement in car- Chua, L. O. & Green, D. N. [1976c] “A qualitative anal-
diac tissue without the involvement of an anatomical ysis of the behavior of dynamic nonlinear networks:
obstacle,” Circ. Res. 41, 9–18. Steady state solutions of non-autonomous networks,”
IEEE Trans. Circuits Syst. 23(9), 530–550.
Anderson, B. D. O. & Vongpanitlerd, S. [1973] Network
Chua, L. O. & Kang, S. M. [1977] “Section-
Analysis and Synthesis (Prentice Hall, Englewood,
wise piecewise-linear functions: Canonical representa-
Cliffs, New Jersey).
tion, properties and applications,” Proc. IEEE 65,
Balbach, J., Forge, V., Lau, W. S., van Nuland, N.
915–929.
A. J., Brew, K. & Dobson, C. M. [1996] “Pro- Chua, L. O. & Lin, P. M. [1975] Computer-Aided Anal-
tein folding monitored at individual residues during ysis of Electronic Circuits: Algorithms and Compu-
a two-dimensional NMR experiment,” Science 274, tational Techniques (Prentice-Hall, Englewood Cliff,
1161–1163. New Jersey).
Berlekamp, E. R., Conway, J. H. & Guy, H. K. [1982] Chua, L. O. & Roska, T. [1990] “Stability of a class of
Winning Ways for your Mathematical Plays (Aca- nonreciprocal cellular neural networks,” IEEE Trans.
demic Press, New York). Circuits Syst. 37, 1520–1527.
Bishop, A. R., Krumhansl, J. A. & Trullinger, S. E. [1980] Chua, L. O. & Roska, T. [1993] “The CNN paradigm,”
“Solitons in condensed matter: A paradigm,” Physica IEEE Trans. Circuits Syst. I 40, 147–156.
D, 1D(1), 1–44. Chua, L. O. & Roska, T. [1997] Cellular Neural Networks
Boyd, S., Chua, L. O. & Desoer, C. A. [1984] “Analytical — Foundations and Primer, Lecture Notes/EE129,
foundation of Volterra series,” IMA J. Math. Control University of California, Berkeley.
Info. 1, 243–282. Chua, L. O. & Shi, B. E. [1991] “Multiple layer cellu-
Boyd, S. & Chua, L. O. [1985] “Fading memory and lar neural networks: A tutorial,” in Algorithms and
the problem of approximating nonlinear operators Parallel VLSI Architecture. Vol. A: Turtorials, eds.
2422 L. O. Chua
Deprettere, E. F. & Van der Veen, A. (Elsevier Sci- array processor with on-chip binary imaging and in-
ence, Amsterdam), pp. 137–168. structions storage,” IEEE J. Solid-State Circuits 32,
Chua, L. O. & Wu, C. W. [1992] “On the universe of 1013–1026.
stable cellular neural networks,” Int. J. Circuit Theor. Drazin, P. G. & Johnson, R. S. [1989] Solitons: An In-
Appl. 20, 497–517. troduction (Cambridge University Press, New York).
Chua, L. O. & Yang, L. [1988] “Cellular neural networks: Fisher, A. [1990] Labyrinth: Solving the Riddle of the
Theory and applications,” IEEE Trans. Circuits Syst. Maze (Harmony Books, New York).
35, 1257–1290. Fujita, I., Tanaka, K., Ito, M. & Cheng, K. [1992]
Chua, L. O., Hasler, M., Moschytz, G. S. & Neirynck, “Columns for visual features of objects in monkey in-
J. [1995] “Autonomous cellular neural networks: A ferotemporal cortex,” Nature 360(6402), 343–346.
unified paradigm for pattern formation and active Gilli, M. [1994] “Stability of cellular neural networks
wave propagation,” IEEE Trans. Circuits Syst. I 42, and delayed cellular neural networks with nonpositive
559–577. templates and nonmonotonic output functions,” IEEE
Chua, L. O., Dessor, C. A. & Kuh, E. A. [1985] Linear Trans. Circuits Syst. I: Fundamental Theor. Appl. 41,
and Nonlinear Circuits (McGraw Hill, New York). 518–528.
Chua, L. O., Roska, T. & Venetianer, P. L. [1993] Goldstein, R. E., Pesci, A. I. & Shelley, M. J. [1993]
“The CNN is universal as the Turing machine,” IEEE “Topology transitions and singularities in viscous
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Trans. Circuits Syst. I 40, 289–291. flows,” Phys. Rev. Lett. 70(20), 3043–3046.
Cohen, M. H. & Robertson, A. [1971] “Chemotaxis and Gómez-Gesteira, M., Fernández-García, G., Muñuzuri,
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.
early stages of aggregation in cellular slime molds,” J. A. P., Pérez-Muñuzuri, V., Krinsky, V. I., Starmer,
Theor. Biol. 31, 119–130. C. F. & Pérez-Villar, V. [1994a] “Vulnerability in ex-
Crounse, K. R. & Chua, L. O. [1995] “Methods for im- citable Belousov-Zhabotinsky medium: From 1D to
age processing and pattern formation in cellular neu- 2D,” Physica D76, 359–368.
ral networks: A tutorial,” IEEE Trans. Circuits Syst. Gómez-Gesteira, M., del Castillo, J. L., Vázquez-Iglesias,
42(10), 583–601. M. E., Pérez-Muñuzuri, V. & Pérez-Villar, V. [1994b]
Crounse, K. R. & Chua, L. O. [1996a] “The CNN univer- “Influence of the critical curvature on spiral initia-
sal machine is as universal as Turing machine,” IEEE tion in an excitable medium,” Phys. Rev. E50(6),
Trans. Circuits Syst. 43(4), 353–355. 4646–4649.
Crounse, K. R. & Chua, L. O. [1996b] “A synergetics Grekova, M. T. [1981] Autowave: Processes in Systems
approach to image processing in Cellular Neural Net- with Diffusion (Acad. Sci. USSR, Gorky).
works,” in Proc. 1996 IEEE Int. Symp. Circuits and Guckenheimer, J. & Holmes, P. [1983] Nonlinear Oscilla-
Syst., Vol. 3, pp. 134–137. tions, Dynamical Systems, and Bifurcations of Vector
Crounse, K. R., Fung, E. L. & Chua, L. O. [1997] “Effi- Fields (Springer-Verlag, New York).
cient implementation of neighborhood logic for cellu- Guillemin, E. A. [1957] Synthesis of Passive Networks
lar automata via the cellular neural network universal (John Wiley & Sons, New York).
machine,” IEEE Trans. Circuits Syst. I: Fundamental Haken, H. [1975] “Cooperative phenomena in systems
Theor. Appl. 44, 355–361. far from thermal equilibrium and in nonphysical sys-
Crounse, K. R., Chua, L. O., Thiran, P. & Setti, G. [1996] tems,” Rev. Mod. Phys. 47(1), 67–121.
“Characterization and dynamics of pattern formation Haken, H. [1978] Synergetics, An Introduction (Springer-
in cellular neural networks,” Int. J. Bifurcation and Verlag, Berlin).
Chaos 6(9), 1703–1724. Haken, H. [1983] Synergetics, 3rd edition (Springer-
Cruz, J. M. & Chua, L. O. [1991] “A CNN chip for con- Verlag, New York).
nected component detection, ” IEEE Trans. Circuits Haken, H. [1994] “Synergetics: From pattern formation
Syst. 38, 812–817. to pattern analysis and pattern recognition,” Int. J.
Cruz, J. M. & Chua, L. O. [1998] “A 16×16 cellular neu- Bifurcation and Chaos 4(5), 1069–1083.
ral network universal chip: The first complete single- Hänggi, M. & Moschytz [1997] “Visualization of CNN
chip dynamic computer array with distributed mem- dynamics,” Electron. Lett. 33(20), 1714–1716.
ory and with gray-scale input-output,” Analog Integr. Henze, C. & Winfree, A. T. [1991] “A stable knotted sin-
Circuits Sig. Process. J., 15(3), 227–238. gularity in an excitable medium,” Int. J. Bifurcation
Dogaru, R. & Chua, L. O. [1998] “Edge of chaos and lo- and Chaos 1(4), 891–922.
cal activity domain of FitzHugh-Nagumo Equation,” Hirota, R. [1971] “Exact solution of the Korteweg-de
Int. J. Bifurcation and Chaos 8(2), (to appear). Vries equation for multiple collisions of solitons,”
Dominguez-Castro, R., Espejo, S., Rodriguez-Vazquez, Phys. Rev. Lett. 27(18), 1192.
A., Carmona, R. A., Zarandy, A., Szolgay, P., Hirota, R. [1973] “Three-soliton solution of the two-
Sziranyi, T. & Roska, T. [1997] “A 0.8-µm CMOS two- dimensional Sine-Gordon equation,” J. Phys. Soc.
dimensional programmable mixed-signal focal-plane Japan 35(5), 1566.
CNN: A Vision of Complexity 2423
Hirsch, M. W. & Smale, S. [1974] Differential Equations, Markus, M. [1992] “Numerical modelling of hallu-
Dynamical systems, and Linear Algebra (Academic cinations,” in World of Consciousness, 1st Int.
Press, New York). Congr. European College for the Study of Conscious-
Hopfield, J. J. [1985] “Neural networks and physical sys- ness (ECSC), eds. Schlichting, M. & Leuner, H.,
tems with emergent computational abilities,” Proc. pp. 131–140.
National Acad. Sci. USA 79, 2554–2558. Meinhardt, H. [1995] The Algorithmic Beauty of Sea
Jakubith, S., Rotermund, H. H., Engel, W., van Shells (Springer-Verlag, Berlin).
Oertzen, A. & Ertl, G. [1990] “Spatiotempo- Mikhailov, A. S. [1990] Foundations of Synergetics I
ral concentration patterns in a surface reaction: (Springer-Verlag, Berlin).
Propagating and standing waves, rotating spirals and Milne-Thomson, L. M. [1960] The Calculus of Finite Dif-
turbulence,” Phys. Rev. Lett. 65, 3013–3016. ferences (MacMillan, London).
Jahnke, W. & Winfree, A. T. [1991] “A survey of spiral- Minsky, M. & Papert, S. [1969] Perceptrons: An In-
wave behaviors in the oregonator model,” Int. J. Bi- troduction to Computational Geometry (MIT Press,
furcation and Chaos 2, 445–466. Cambridge, MA).
Juang, J. & Lin, S. S. [1997a] “Cellular neural networks Moylan, P. J., Chua, L. O. & Szeto, E. W. [1982] “When
I: Mosaic pattern and spatial chaos,” preprint. is a device passive?” Int. J. Circuit Theor. Appl. 10,
Juang, J. & Lin, S. S. [1997b] “Cellular neural networks 151–165.
Muñuzuri, A. P., Pérez-Muñuzuri, V., Pérez-Villar, V.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
one-dimensional array of Chua’s circuits,” J. Circuit Roska, T., Hamori, J., Labos, E., Lotz, K., Orzo, L.,
Syst. Comput. 3(1), 215–229. Takacs, J., Venetianer, P. L., Vidnyanszky, Z. &
Pérez-Muñuzuri, V., Pérez-Villar, V. & Chua, L. O. Zarandy, A. [1993] “The use of CNN models in the
[1993b] “Autowaves for image processing on a two- subcortical visual pathway,” IEEE Trans. Circuits
dimensional CNN array of excitable nonlinear circuits: Syst. I : Fundamental Theor. Appl. 40, 182–195.
Flat and wrinkled labyrinths,” IEEE Trans. Circuit Roska, T., Kek, L., Nemes, L. & Zarandy, A. [1997]
Syst. I 40, 174–181. “CNN software library (templates and algorithms),”
Perez-Munuzuri, V., Gomez-Gesteira, M., Munuzuri, A. version 7.0 (DNS-1-1997). Analogical and Neural
P., Chua, L. O. & Perez-Villar, V. [1995a] “Sidewall Computing Laboratory, Computer Automation In-
forcing of hexagonal turing patterns: Rhombic pat- stitute, Hungarian Academy of Sciences, Budapest,
terns,” Physica D82, 195–204. Hungary.
Pérez-Muñuzuri, A. P., Gómez-Gesteira, M., Pérez- Roska, T. & Vandewalle, J. [1994] Cellular Neural Net-
Villar, V., Pivka, L. & Chua, L. O. [1995b] “Nonlinear works (Wiley, New York).
waves, patterns and spatio-temporal chaos in cellular Roux, D. [1993] “Sponge phases: An example of random
neural networks,” Phil. Trans. Roy. Soc. London, Se- surfaces,” Physica A213(1, 2), 168–172.
ries A. 353, 101–113. Salmelin, R., Hari, R., Lounasmaa, O. V. & Sams, M.
Petrich, D. M. & Goldstein, R. E. [1994] “Nonlocal [1994] “Dynamics of brain activation during picture
naming,” Nature (London) 368(6470), 463–465.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
Wasserman, S. A., Dungan, J. M. & Cozzarelli, N. R. Zeki, S. [1994] A Vision of the Brain (Blackwell Scientific
[1985] “Discovery of a predicted DNA knot substanti- Publications, Oxford).
ates a model for site-specific recombination,” Science Zhabotinsky, A. M. & Zaikin, A. N. [1973] “Autowave
229, 171–174. processes in a distributed chemical system,” J. Theor.
Werblin, F., Roska, T. & Chua, L. O. [1994] “The Biol. 40, 45–61.
analogic cellular neural network as a bionic eye,” Int. Zold, S. [1997] “The ALPHA language and compiler
J. Circuit Theor. Appl. 23, 541–569. for CNN algorithms,” Tech. Rep. DNS-10-1997, Ana-
Werblin, F., Jacobs, A. & Teeters, J. [1996] “The logical and Neural Computing Systems Laboratory,
computational eye,” IEEE Spectrum, May, 30–37. Hungarian Academy of Sciences, Budapest.
Winfree, A. T. [1995] “Persistent tangles of vortex rings Zou, F. & Nossek, J. A. [1991a] “Stability of cellular
in excitable media,” Physica D84(1, 2), 126–147. neural networks with opposite-sign templates,” IEEE
Wolfram, S. [1984] “Universality and complexity in Trans. Circuits Syst. 38, 811–812.
cellular automata,” Physica D10, 1–35.
Zou, F. & Nossek, J. A. [1991b] “A chaotic attractor with
Wu, C. W. & Chua, L. O. [1997] “A more rigorous proof
cellular neural networks,” IEEE Trans. Circuits Syst.
of complete stability of cellular neural networks,”
38, 675–677.
IEEE Trans. Circuits Syst. 44(4), 370–371.
Zarandy, A. [1998] “The art of CNN template design,”
Int. J. Circuit Theor. Appl. 26, to appear.
Int. J. Bifurcation Chaos 1997.07:2219-2425. Downloaded from www.worldscientific.com
by UNIVERSITY OF QUEENSLAND on 09/30/15. For personal use only.