Convergence and stability of the FSR CNN model

CNNA-94 Third IEEE International Workshop on Cdlular Neural Networks and their Applications Rome, Italy, December 18-21,1994 Convergence and StaWty of the FSR CNN Model S. Espejo, A. Rodriguez-Vtlzque&, R. Dominguez-Castro, and,R. Carmona Centro Nacional de Micraelectr6nica-Universidad de Sevilla Edificio CICA, W'Ida dn, 41012-&viila, SPAIN Phone: +34 - 5 - 423 99 23. Fax: +34 - 5 - 462 45 06. E-mail: [email protected] Abstract - Stability and convergency results are reported for a modified continuous-time CNN model. The signal range of the state variables is equal to the unitary interval, independently of the application. Stabiliiy and convergency properties are similar to those of the original model and, for given templates and offset cwflcients, the results are generally identical. In addition, robustness and area-efficiency of VLSI implementations are significantly advantageous. 1. Introduction From an implementation point of view, the signal-range of the state variables of CNNs is an important factor. In the Chua-Yang model [1],[2], this value (normalized to the signal range of the output variables) is usually in the range of 4 to 20, depending on the application. The difference between the two signal ranges results in increased error levels in CNN circuits. Furthermore, the dependency of the signal range of the state variables on the template coefficients represents an additional problem for the implementation of programmable CNN systems. A modified CNN model which exhibits identical signal ranges for the state and output variables, independently of the template coefficients, was proposed by the authors in [3]. This contributions demonstrates some stability and convergency properties of this model. Among them, the stability results reported by Chua and Yang in their first CNN proposal [1],[2] are extended here to the modified model, from now on called the Full Signal Range (FSR) model. For the purpose of mathematical demonstrations, we consider a parameterized family of CNN models, referred to as the Improved Signal Range (ISR) family, which includes the Chua- Yang and FSR models as particular cases. 2. The ISR model family in which each symbol is used with its usual meaning (see Annex at the end of the paper), The dynamic behavior of an ISR cell c is described by the following differential equation, 0-7803-207~.00 0 1994 IEEE 41 1 .- Note that the output and the state variables of each cell am related by the usual nonlinear relationship, while the loss term is modified introducing a nonlinear hction g(xc) parameterized by m E [ 1, .O ) . This function is depicted in Fig. 1. Note that if m P 1, then g(xc) = xc, thus resulting in the original CNN model. On the other hand, the FSR model is obtained when m + -. Although. compared to the original model, the implementation of an ISR cell according to Eq. 1, and the definitions in Eq. 2 nquircs a chitry of increased complexity, the situation becanes is inverted when the FSR model is c~nsid~d. In addition, the advantages of the ISR model become ophd wbn m+m. 3. Stabiuty and convergemcy of the ISR lrakl family This section contains a sequence of smments and proofs. We make here two definitions, 1 .-.- 1x . ..-- -1 7F .m F- 1. piece-wise ldar loss rem used in the ISR models. For simplicity, some statements below will be demonstrated assuming that ME 2 1, which is the most common case (for instance wheqcver a: 2 1). This assumption is not necessary. General demonstrations are available from the authors upon request [4]. Sruremenr 1: "The absolute value of the state variable of every cell c in an ISR CNN is bounded for any set of finite feedback, control and offset coefficients (including nonuniform CNNs), and for any set of finite initial conditions, input to the cells and boundary conditions." Proof: Using the definition of g(xc) into Eq. 1 we obtain adifferential equation from which the following expressions can be obtained by traditional methods, t which correspond, respectively, to the upper-saturated region (x'> 1) , the linear region (IxcI > 1) , and the lower-saturated region (xc c -1) . For these equations to be valid, the time variable must be shifted so as to make r = 0 at the instant in which the state variable entered a particular region, and the initial condition ~'(0) must be defined accordingly. Since the state variable will always be in one of (hese regions, we only need to demonstrate that the above three equations are bounded. Using Schwartz's inequality several times on Eq. 4, taking into account that the output variables are Iyc(r)l I 1, and that m 2 1, the following result is obtained (7) IxC(r)/ I - which is bounded. The same result can be obtained from Q. 6. Finally, within the linear region (Eq. 5) we have by definition that (xc(r)l s 1. Thus, state variables are globally bounded. Sruremenr 2: "For any cell c, the maximum possible absolute value of an equilibrium point is an absolute bound for the state variable at any time instant, assuming that it is true at r = o ." m 41 2 Pmofi In order to determine the paximum possible absolute value of an equilibrium point, we must look at the dynamic route of ISR cells, obtained from Eq. 1, -m(xC-l) -l+oy+rC ;Vxc>l (8) -m(xC+ I) + 1 +oy+ic ;VX'C-I where ic contains all the contributions on the right-hand side of Eq. 1 which do not directly depend on the state variable 2, Note that the summation extends to the reduced neighborhood N' (c) = N (c) - { c} of the cell. The value of the equilibrium points in each of the three regions in Eq. 8 can be obtained making the derivative equal to cero and using the definition of y (x) given in Eq. 2, where we include the condition required for the equilibrium points to be "real", otherwise being "virtual". Using lyc(r)l s 1 in Eq. 9 we obtain the maximum possible absolute value of ic (11) li'l I dc &(c) 14 + lkcl which used in Eq. 10 gives the maximum possible absolute value of a cell equilibrium point In order to calculate a global bound for the state variable, we must take into account that it can go in and out of the linear and saturated regions several times, defining intervals [rLi.r'Li), i=l, ..., Nand [rs.r'si).j=l,..., M within wbkh the state variable is in the linear region or in some saturated region, respectively. The union of these intervals contains the complete transient evolution of the cell. We consider different initial conditions f,{O) = xc(r'rfi), i=l, ..., N, and fs,{O) =f(t=rsi) ,j=l,..., M, and the componding time-shifts. This allows the use of one of Eq. 4 through Eq. 6 for each interval. Nate that in general lfL{O)I = lfs,{O)l = 1 with the possible exception of the real (unshifted he) initial condition 90(0). which afftcts either to f~l(0) or to fsl(0). If lfo(0)l-c 1, then Ixc~l(O)l= Wo(O)l< 1, and if lfo(O)l> 1 then L8~l(O)l= L8o(O)l> 1. In any case, Lrch{O)l S 1, V i=l, 2 ,..., N, and LXcsJI0)I 2 1, Vj=l, 2 ,.... M. From Eq. 7, which is valid for either saturated region, we can obtain a bound for the state variable in each interval [fsjs's$. We 4fim function &$) as the right hand side of Eq. 7, defined within the interval, where it can be seen to be bounded by one of the following limits, if then 413 Taking into account the possible values of LfsdO)l, the following result is obtained M The same procedure can be used for the linear region, or we can simply take into account (17) The right hand side of this equation coincides with that of Eq. 12 under the assumption made in the statement. Starement 3: “There is a hyper-rectangular region around the origin of the state space that is a global attracting region, this is, if the state vector of the network is outside, it evolves towards the region, and if it is inside, it neer scapes.” that Ix‘(r)l I; 1, Vr E [rLr, r’Li ) and for any i = 1. ..., N, which allows the extension of Eq. 16 to Ixc(r)l 5 max { m-l+MC - , Ix;(o)~ I vr 2 0 m Pro08 This hyper-rectangular region is defined by a set of intervals, one for each cell, From Eq. 13, if the state variable xC of some cell belongs to f at some time instant (which can be redefined as r = 0). then it will belong to f at any later instant. On the other hand, from Eq. 7 we have that, which shows that if the state variable of some cell is outside f at some time instant, the state variable will be either in rC or arbitrarily close to its borders after a sufficient amount of time. Statement 4: ‘The global attracting region approaches the [-1,11” hypercube as m + (FSR limit), regardless the particular template coefficients.” Pro08 Simply note that m- 1 +Mf lim - = 1 Statement 5: “ISR CNNs with central-feedback coefficients larger than unity (a:> I) have no stable equilibrium points within thc open hypercube (-1.1)“, this is, if it converges, its output is binary.” Proof: The slope of the dynamic route in the linear region is given by s = a: - 1, which is positive in the cases considered. Hence, any equilibrium point in the linear region is unstable. Statement 6: “ISR CNNs with reciprocal fedback templates are convergent.” Pmofi The demonstration is identic4 to that employed by Chua and Yang in [I]. A CNN * lim f = [-1,11 (20) m-s- m m+- is said to be reciprocal if a$ = a: ,Vce GD,Vde GD (21) We will use the same function that was proposed for the original CNN model: Sincethe output variables are restricted to the [-1,1] interval, this function is bounded for any set of finite CNN coefficients and inputs values. We will now demonstrate that this function is a continuously decreasing function of time. For this purpose, note that Then, taking the time derivative of Eq. 22, and after changing variables (c by d and vice-versa) 414 in one of the resulting sums, and using Q. 21, we obtain which, taking into account the following thrte facts can be transformed into 1x1 s 1 Since only the cells whose state variables an in the linear region are included in the sum, we can usc Eq. 1 with g(xc) = xc in the above equation, yielding Ixcl s I which demonstrates that E(r) is a monobnically decreasing function of time. Now, using Eq. 25 and Eq. 26, we can change Eq. 27 is follows, lxcls 1 lxcl s 1 Since E(t) is a bounded and monotonic decreasing function of time, its limit €or t + 00 exists, from where the limit of its derivative must be cero, where we have used Eq. 28 and the fact that if a sum of positive summands is cero, every summand is cero. The final result in Eq. 29 demonstrates that all output variables converge. We will show now that the state vatiables converge as well. Note that, after the output variables have converged, the state variables of the cells are confined in some region. We define The limit of f (f) for 1 + m exists because the limits of all output variables exist. Eq. 5, rewritten using the above definitions, which yields, If the state variable of a particular cell is in the linear region, we can obtain its limit using t t J rc(r) e'& (31) lim xc(r) = lim xC(0)e-'+ lim e-'Jrc(T)eThr = lim 0 = lim - = RC t+- t+- I+- t+- et t+- er where we have used the rule of L'Hopital. If the state variable is in the upper or lower saturated regions, we can use the same procedure starting from Eq. 4 or Eq. 6, respectively, which yields, rc& 0 m-l+RC 1-m+RC lim xC(t) = - or iim xc(r) = ~ also respectively I+- m I+- m 41 5 4. The FSR madel The statements in the previous section are valid (except statement 4) in the range m E [ 1, - ) which includes the Chua-Yang (m = 0) and the FSR (m + -) models. In addition, in the FSR model, statement 4 is valid, and haoce, the state vector never leaves the [-1,11“ hypercube, assuming that it is initially in it. Sithe state vector is confined in LMI”, where g(xc) = xC and yc = xc, the FSR model can be practically described by the following equation, c .‘.bid+ b>’+& ,Vlx”ll a$Vc#d 2‘ = { d6 N(c) da N(c) },wi& (33) ,vlxl = 1 -1,c=d 0 where the equilibrium points at lxcl = 1 arc stable or unstable depending on the sign of the derivative at the inner borders of interval 1-1.11, given by the upper expression in Eq. 33. In this manner, the implementation of the nonlinear operator y(x) in Eq. 2 is not required, neither that of the central segment ofthe dissipative term g(x). which is grouped with the self feedback coefficient U:. On the other htutd, the state variabk must be forced to remain in the unitary interval [-1.11 using a hard liter (external segments of g(x)). The result is a CNN model with signal range equal to the unitary interval, independently of the application, which requires less circuitry for its implementation, and with stability and convergency properties similar to those of the original model. Numerical simulation shows that, for a given templates and offset codiuients, the results obtained using the Chua-Yang model and those obtained using ISR model are gencdy identical. It can also be shown that uniform (proportional) variations of the templates and offset coefficients affect only to the time constant of the network This represent an incd robustness against global process parameter variations in VLSI implementations. Annex: notation c, d cell indexes state variable of cell c output variable of cell c normalized time. If t’ is the physical time, t = t’/i, where i is the time constant of the cells, assumed invariant through the network feedback coefficient. Weight of he conbibution from the output yd of cell d towards cell c. control coefficient. Weight of the contribution from the input ud of cell d towards cell c. offset term. Constant contribution to cell c N(C) neighborhood of cell c CD grid domain. Set of all inner cells in the network References [l J L.O. Chua and L. Yang: “Cellular Neural Networks: Theory”. IEEE Trans. Circuits and Systems, Vol. 35, pp 1257-1272, October 1988. [2] L.O. Chua and L. Yang: “Cellular Ne@ Networks: Applications”. IEEE Trans. Circuits and Systems, Vol. 35. pp 1273-1290, October 1988. [3] S. Espejo, A. Rodriguez-Vazquez, R. Dominguez-Castro, B. Linares and J.L. Huertas: “A Model for VLSI Implementation of c” Image Processing Chips Using Current-Mode Techniques”. Proc. 1993 IEEE Inc. Syntp. on Cimuits und Systems, Chicago, May 1993. 141 S. Espejo: “VLSI Design and Modeling of CNNs”. Ph. Dissertation, University of Sevilla, March 1994. 41 6