INTERNATIONAL JOURNAL OF CIRCUIT THEORY AND APPLICATIONS, VOL. 24,145-164 (1996) ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA-KEY ALGORITHMS AND LAY-OUT DESIGN? PETER L. VENETIANER AND PETER SZOLGAY Analogical and Neural Computing Laboratory, Hungarian Academy of Sciences, Pf.63,H-I518 Budapest, Hungary KENNETH R . CROUNSE Department of Electrical Engineering and Computer Sciences, and the Electronics Research Laboratory, University of California at Berkeley, Berkeley, CA 94720, U.S.A. TAMAS ROSKA Analogical and Neural Computing Laboratory, Hungarian Academy of Sciences, Pf,63,H-IS18 Budapest. Hungary and The Electronics Research Laboratory, University of California at Berkeley, Berkeley. CA 94720, U.S.A. AND LEON 0. CHUA Department of Electrical Engineering and Computer Sciences, and the Electronics Research Laboratory, University of California at Berkeley, Berkeley, CA 94720, U.S.A. SUMMARY This paper demonstrates how certain logic and combinatorial tasks can be solved using CNNs. A design method is proposed for solving combinatorial tasks on a CNN. It can be used to simulate cellular automata on a CNN, to prove the self-reproducing capability of the CNNUM and for sorting, histogram calculation, parity analysis and minimum Hamming distance computation. These solutions are especially useful since they can serve as subroutines of more complex CNNUM algorithms. As an important real-life application the lay-out of printed circuit boards is designed with the CNNUM at an extremely high speed. 1. INTRODUCTION The cellular neural network (CNN)'-3 is a paradigm for locally connected, nonlinear, analogue, dynamic computing arrays. In a recent paper4 it was shown that the game-of-life algorithm can be realized by appropriate analogue templates (locally interactive weight patterns). Therefore any Turing machine can be realized by a CNN. The enormous implied capability has been evidenced by the development of many applications (see e.g. Reference 3 and references cited therein). Here we will show some interesting examples of CNN templates which perform logical operations. We show theoretically how simple analogue templates can generate the logic functions needed to calculate the next states in the time evolution of arbitrary cellular automata. As a practical application we describe the use of the analogue CNN universal machine5 (CNNUM, a stored programme analogic microprocessor) to perform certain logic and combinatorial tasks as opposed to the standard analogue ones. Some of these applications, especially the lay-out design, outperform traditional solutions, while others can serve as subroutines of complex analogic algorithms. t Part of this research has been reported in the Proceedings of the 1994 IEEE International Workshop on Cellular Neural Networks and Their Applications held in Rome. CCC 0098 -9886/96/010 145-20 0 1996 by John Wiley & Sons, Ltd. Received 15 January 1995 Revised 6 April I995 I46 P.L. VENETIANER ET AL. In many CNN applications the two saturation values (e.g. + 1 and - 1) are sufficient for detection tasks. However, in other cases the two states corresponding to the saturation regions I v , I 3 1 of the CNN might not be sufficient to represent the different states of a model. In such cases it is straightforward to map some states to values or regions in the (-1, +1) interval of the dynamics. However, if simulating a multistep procedure, it is also important that the different cells of the network reach their new states at the same time. A possible solution to this problem is to discretize time in the state equation of the CNN. If the time step is set to unity, the following equations are obtained when using a forward Euler formula: +1 ifx,, 2 +1 y,, = f ( x , , ) = x,, if -1 s x,, s +1 -1 ifx,, 6 -1 [ where we have used the standard notations.'-3 We shall call the network described by these equations a piecewise-linear unity-gain discrete-time cellular neural network (pwuDTCNN, not to be confused with the original DTCNN6 which has a threshold-type output equation). This type of network was first used in Reference 4: the game of life was realized on a pwuDTCNN too, using the values in the interval (- 1, + 1) to code information about the actual state of the cells of the life pattern. The basic idea in Reference 4, namely coding information in the grey-scale values in one step and decoding it using non-linear functions in a second step, is further generalized in Section2 to realize arbitrary cellular automata. Section3 demonstrates the self-reproducing capability of the CNNUM. In Section4 some interesting and important combinatorial tasks such as sorting, counting parity, etc. are solved using a pwuDTCNN. In Section5 we show an interesting application of the pwuDTCNN in the field of information theory, namely we show how to find a code with minimum Hamming distance. Finally, Section6 describes how a classical lay-out design algorithm is implemented and used for printed circuit board design with the CNNUM. 2. REALIZATION OF CELLULAR AUTOMATA Here we explain how arbitrary cellular automata can be implemented using a pwuDTCNN. The general first-order case is demonstrated constructively and several interesting special cases are given. Finally, it is shown how a particular cellular automaton with higher-order dynamics can be implemented. The design method demonstrated here can be used to solve complex combinatorial tasks with a CNN. Cellular automata (see e.g Reference 7 for an excellent introduction) are a class of dynamical systems which are discrete in space, state and time. We will speak of an array of cells. Each cell (i, j ) holds a state ~ , , ~ at ( ktime ) k. The state can only take on a value from a finite set. There is no input. Rather, starting from an initial state condition, the state values evolve in time according to a state transition rule, which gives the next state as a function of the current states of a cell and its neighbours. For our purposes we assume that rhe state transition rule is space-invariant, i.e. it is the same for every cell. The neighbourhood is usually defined by a radius r , so that any cell inside this radius is in the neighbourhood. 2.1, First-order cellular automata If the set of possible states for a cell is binary and the neighbourhood is r = 1, we will call the cellular automaton first-order. 2.1.1. General case. The two-step approach used in Reference 4 can be used to show that the pwuDTCNN with arbitrary template non-linearities can be used to implement any first-order cellular automaton. ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA 147 The generalized two-step method on the pwuDTCNN can be considered as an implementation of the following algorithm for determining the evolution of a cellular automaton. In the first step the binary current states in every cell neighbourhood of the cellular automaton are encoded into a single unique integer using powers of two in the standard way. In the second step these integers are used to index into a truth table to determine the next state of the cellular automaton at each cell. Since any binary function can be represented by a truth table, this allows any binary function of the neighbourhood to be implemented. This algorithm to implement cellular automata can be performed with a single pwuDTCNN template. To show how, we will use y, = - 1 to represent s, = 0 and y , = 1 to represent s,,,= 1. The rest of the CNN cell's state space is used to index the truth table. In our example we use the region [ -0.8,0.8] for this purpose. The input, bias and B,,,,,, template functions are not used. Figure I shows the A,,,,, template functions for the construction of binary cellular automata with the pwuDTCNN, where the functions a and a, are arranged in the template as follows: To understand the operation of the network, first assume that at time zero all outputs y i j ( 0 )are in states representing the initial conditions of the cellular automaton, i.e. y i j ( 0 )E ( - 1, + 1 ). Then the template functions shown will cause the next state of each cell of the pwuDTCNN to be a unique encoding of the current neighbourhood. More precisely, we will get Y i , j ( l >= (2' x Yt-l,j- I(0) + 2' x Yi,j-i(O)+ 22 x Y i + i , j - I(0) + 2* x + 24 x Y , + , , j ( o >+ 25 x ~ i - ,1/ + I Yi-l,j(O) (0) + 2 6 ~ ~ i , j + i+( 20' )~ ~ i + I , j + l ( O ) x+~2i ,~j ( 0 ) > / 3 2 0 + 0 . 8 which is the standard power-of-two encoding of a binary number scaled to fit in the range [-043,0.8 1. After this step all y , , ] ( l )are guaranteed to be in this range. Now, at a particular cell ( i , j ) the next state ~ , , ~ (is2 )solely determined by the value of the function ~ ( y , , ~ ( lsince ) ) , the functions a , are zero in the [-0.8,0.8] region of the state space. Therefore, if the truth table for the state transition rule of the cellular automaton is put in this region of the function a , the 2 ) be identical with the cellular automaton output. Once accomplished, the system is ready output ~ , , ~ (will to repeat the whole procedure. 2.1.2. One-dimensional cellular automata. To demonstrate the application of the above technique, we will apply it to a one-dimensional, or line, cellular automaton. In this simpler case the next state only depends on the left and right neighbours. The template in our example is where the template functions are as shown in Figure 2. The template function a implements the truth table for the cellular automaton rule left CB right. 148 P.L. VENETIANER ET AL , 6 -1 .o I I I , I I 1 __ -- - 0.2 I I I I I I L I 1.o - i yu -1.0 -0.n Ynaighbor -1.0 -0.06 Figure 2. Template functions for one-dimensional cellular automata An additional function c is used so that the results from the previous time step scroll up the twodimensional array. In order for all of this to work properly, all initial states of the pwuDTCNN array must be set to zero, except for the initial cellular automaton state condition which should be placed in the bottom row of the array. 2.1.3. Totalistic cellular automata. In some cases the state transition function of the desired cellular automaton rule may be of a special form which is easier to implement than by the direct, yet unwieldy, truth table method. This is true of the class of cellular automata with totalistic rules. For this class the cellular automaton state transition rule depends only on the sum of neighbours and possibly on the state of the cell itself. The game of life is an example of such a system. Some other interesting examples of totalistic rules are given in Figure 3. The template of functions for totalistic rules is of the form (::I: Aj-m,j-n = d a d The encoding function is simply an unweighted sum of the neighbour states. The next state is encoded in a sum look-up table. The parity rule is the famous self-replicating cellular automaton attributed to Edwin Fredkin (Reference 7 , p. 32). A small initial pattern in the centre of the array will replicate itself outwards after each successive power-of-two number of time steps, while interesting mosaic patterns are generated during the intermediate stages. The majority and anneal rules are examples of voting rules (Reference 7, p. 41). In the majority rule each cell will choose its next state in accordance with the majority of its neighbours. When starting with a random array, major regions are consolidated with one state eventually dominating the array. 149 ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA a PdtY a 1.1 -L sum41234 -1 .o majority 6789 - + - -0,s -0.4 1.o Yi,i -1 .o a d anneal 1.0 --c sum 4 1 2 3 4 ‘i6 7 8 9 t-+--.t ; ; ; ; ; : ; -1 .o -0.4 1.- : 3 .0 Yi,i Yncighbor -1 .o 0.95 1.0 -1.0 Figure 3. Template functions for some interesting totalistic cellular automaton rules The anneal rule is similar to the majority rule except that when the tally is close, an inverted decision is made. The effect is much more interesting and tends to support stable boundaries. 2.2. Higher-order cellular automata 2.2.1. General case. In general, cellular automata can have more than two allowed states per cell. It may be possible to make an argument similar to the first-order case for the implementation of higher-order cellular automata with pwuDTCNNs, but the size of the state table increases exponentially with the number of states making it quite impractical. However, if the high-order cellular automaton is of a special form, e.g. totalistic, it may be possible to easily design a simple non-linearity. 2.2.2. Tube-worms. As an example of implementing higher-order cellular automata, we introduce a slight variant of the tube-worm rule (Reference 7 , p. 82). The rule is presented as a stylization of tube-worn feeding and other competitive/co-operative phenomena. Our example is a cellular automaton with six possible states per cell. The state transition diagram for a single cell is shown in Figure 4 (bottom). The cell will stay in the ‘active’ state A unless a critical number of its neighbours are or have recently been in the active state. In this case the cell ‘hides’ for a fixed number of time steps. Once this time has expired, the cell becomes active and the same decisions have to be made once again. To implement this on the pwuDTCNN, the same two-step trick is used. The rule’s ‘special form’ which we can exploit is the timer, which is a cascade of states for which transitions are automatically made I50 P. L. VENETIANER ET AL in alataa A, 8, w C. I = thmhold v d r (2) t = sum of lulplbon Figure 4. State transitions for timer cellular automata (top). State transitions for a single equivalent pwuDTCNN cell (bottom) without any decision criteria. The state transition diagram for a given cell of the pwuDTCNN implementation shows that the cellular automaton is simulated with every other state of the pwuDTCNN, as shown in Figure 4 (top). If all the initial states are set to valid CA initial states, the system will work properly. Figure 5 shows the non-linearities necessary to perform these state transitions. Running this system, one can observe the self-organization of spiral waves. Of course, variations in the rules could be made by changing the number of states which provoke a response, the threshold values necessary to set the timer or the length of the timer, each of which will change the form of the spatiotemporal dynamics. 3. SELF-REPRODUCTION WITH CNNS In Reference 4 it was shown how the game of lifeRcan be implemented on a CNN either by a pwuDTCNN template or with two continuous-time CNN templates. The rules of the game are very simple: given an arbitrary pattern of black (living) or white (dead) cells on an infinite squared board at time t , then at time t + 1 one of the following happens: (a) birth-a white cell becomes black if it has exactly three black neighbours (b) survival-a black cell remains black if it has two or three black neighbours (c) death-in all other cases the cell becomes white. Gosper's ingenious glider gun (see Figure 6), emitting a new glider (walking diagonally) every 30 generations, is the main building block for demonstrating the universality and self-reproducing property of the game. It follows from the main statement of Reference 4 that the CNNUM is also capable of selfreproduction. 15 1 ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA f -0.95 -0.85 tube worms timer 1.0 0.02 D c’ -- -0.05 -1 .o -1 C 1 .o L -- -0.28 J- -- -0.35 -- -0.58 -0.58 -- -0.9 T -1 .o -1.0 -- -0.65 -0.65 d A F d -1 .o 1.o Figure 5. Template functions for timer cellular automata I I I I I I I I I I I I I I I I I I I I I I I I I I I I I 1 1 1 1 1 1 1 1 1 1 1 1 Figure 6. Gosper’s glider gun (black pixels), emitting diagonally translating gliders (grey pixels) every 30 iterations 152 P. L. VENETIANER ET AL. 4. ANALOGUE COMBINATORICS In this section pwuDTCNN templates are used to solve some interesting image-processing and combinatorial tasks such as drawing the histogram of a black-and-white image, adding binary numbers, sorting values in the [ - 1,1] interval, determining panty and comparing the number of black and white pixels. In most cases global features are extracted using propagating templates. Most algorithms use ID templates operating on just one row (column) of the image. Processing just one line is usually no faster than a conventional digital solution, but there are two reasons why these algorithms are important 1 . A CNN array can process several lines in parallel; 2. These problems might come up as subroutines in complex analogic algorithms, and by being able to solve them on a CNN, we do not lose time by A/D and D/A conversions. 4.1. Adding binary numbers The three templates of Figure 7 are capable of adding n m-bit binary numbers in n + m + 1 steps. The operation is executed in three phases. At the beginning the initial state should be set to 0, while the input image contains the operands, each row corresponding to a binary number, where black (+1) codes the binary 1 (true) and white (- 1) the binary 0 (false) (see Figure 8). In the first phase of the algorithm, using the template of Figure 7(a) for n steps, the 1s are added column-wise. This means that each cell will d: carry fmm right neighbor --- 0.15 0.05 p.05 0.15 0.5 (b) binary I A=[e] Figure 7. The add template: (a) column-wise addition of bits; (b) converting n-ary numbers to binary; (c) converting to +I/-1 representation ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA - INPUT 153 - OUTPUT 9 = 0010011 1 = 0001011 + 8 = 0010010 -+ 0 = 0010100 -+ 9 = 0001001 --j 0010011 = 1 + 0011110 = 3 t 0110000 = 4 c 1000100 = 6 t- 1001101 = 7 Figure 8. Example for the add template contain a grey-scale value corresponding to the number of 1s above it. (This means 0.05 x number of 1s.) As there are n operands, these values can be interpreted as n-ary numbers. In the second phase (Figure 7(b) for rn iterations) the n-ary values are converted to binary, but unlike the input, here 0.05 corresponds to true and 0 to false. The original black-and-white representation of the binary numbers is restored in one step with the template of Figure 7(c). Note that in the second step we converted an n-ary number to a binary using the template of Figure 7(b). This template can be used on its own for conversion tasks and can be extended to be able to convert between arbitrary bases. 4 . 2 . Majority vote-taker template The goal of the one-dimensional majority vote-taker template is to decide, whether a row of the input image contains more black or white pixels or whether their number is equal. The effect is realized in two phases. The template of Figure 9(a) (setting the initial state to 0) gives rise to an image where the sign of the rightmost pixel corresponds to the dominant colour, namely it is positive if there are more black pixels than white ones, negative in the opposite case and 0 in the case of equality. Using the template of Figure 9(b), this information can be extracted, driving the .whole network to black or white, depending on the dominant colour, or leaving the rightmost pixel unchanged otherwise (Figure 10). The method can easily be extended to two or even three dimensions. A=[ 1 0 0 1 A=[Oa2] B=[ 0.05 ] (b) (a) Figure 9. The majority vote-taker template: (a) setting the sign of the rightmost pixel to that of the dominant colour; (b) extracting the encoded information of the first step input more BLACK< more WHITE- black white pixels 6 5 4 3 2 1 2 3 4 5 Figure 10. Example for the majority vote-taker template output 154 P.L.VENETIANER ET AL. 4.3. Counting parity The template of Figure 11 determines the parity of a row of the input image, i.e. it determines whether the number of black pixels in a row is even or odd. As a result, in the output image the leftmost pixel will correspond to the parity of the row, namely black representing odd and white even parity. It is also true that each pixel codes the parity of the pixels right of it, together with the pixel itself (see Figure 12). Naturally, the parity of a column or a diagonal can be counted in the same manner. The parity of an array can also be determined if column-wise parity is counted on the result of the row-wise parity operation. The idea behind the template is as follows. The computation propagates from right to left. The initial state should be set to -0.5, and as long as the output of the right neighbour of a cell does not leave the (-0.7, -0.1) interval, the cell itself remains inside this interval as well. However, as soon as the right neighbour is not in this interval any more, which means that it contains a value corresponding to its parity, the actual cell will also take a value according to its parity and in the next iteration step the pixel becomes black or white and will not change its value any more. A = [ O a bJ B=[0.1] 0.2 I -0.7 I I I I I I Y I -+ - I I I -0.1 0.1 -0.1 b- keepstate around -0.5 . ) I 0.7 4- 0.1 -- donotallow changes any more I -0:l 0.1 0.3 -2 -0:7 I 0.7 0.3 b Y -0.7 even odd parityarity even parity Figure 11. The panty template do not allow changes any more ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA input number of black pixels even odd 155 output Figure 12. Example for the parity template 4.4. Sorting The task of sorting a one-dimensional array of n values in the [- 1, + 1] interval in descending order can be solved using the time- and space-varying template of Figure 13. The core of the algorithm is to compare two neighbouring cells and swap them if necessary, just like in bubble-sort. However, thanks to the parallel architecture, n/2 compare-and-swap operations can be executed simultaneously, which means that the sorting is completed in n steps. The two feedback templates are shown in Figure 13. Template L compares the actual cell value with that of its left neighbour and replaces the cell by the neighbour if the neighbour is smaller. Template R is quite similar, except that the comparison is made with the right neighbour and the replacement is done if the neighbour is greater than the actual cell value. Using these two templates simultaneously, i.e. feeding R to a cell and L to its right neighbour, the two cells will be swapped if they are not in descending order. Using the RLRLRL ... space-varying template pattern on a one-dimensional grey-scale image will compare and swap if necessary the first pixel (from the left) with the second, the third with the fourth and so on. In the next iteration, using the LRLRLR ... pattern (note that now the Ltemplate is used on the leftmost pixel), the second pixel is compared and swapped with the third, the fourth with the fifth and so on. With this algorithm, applying the RLRLRL ... pattern in every odd and the LRLRLR.. . pattern in every even step and setting the leftmost boundary to + 1 and the rightmost to - 1 (to suppress side effects), the grey-scale values will be in descending order after n steps (see Figure 14). left neighbor is smaller: don’t do anything T‘ left neighbor is greater: copy it to actual cell tb Yij-Ykl R=[O 1 b] right neighbor is smaller: copy it to actual cell right neighbor is greater: don’t do anything I56 P.L. VENETIANER ETAL. (b) Figure 14. Example lor the sort template: (a) input and (b) output values in descending order 4.5.Histogrum When the image contains only black and white pixels instead of grey-scale values, sorting turns into the task of separating the different values, e.g. moving all black pixels to the left and white ones to the right. In the case of a two-dimensional image this function gives rise to the histogram of the picture. The task can of course be solved by the sorting algorithm of the previous subsection, but there are other possibilities as well. A solution of this problem was given in Reference 9 using a three-layer continuous-time CNN. Here we present an even simpler, single-layer solution (see Figure 15). It drives a black cell to white if its left neighbour is white (function a ) and drives a white cell to black if its right neighbour is black (function b). This template works on a DTCNN as well. An example is given in Figure 16. 1 'actual cell is black, drivc cell 10 black Figure 15. The histogram template Figure 16. Example for the histogram template 157 ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA 5 . COMPUTING MINIMUM HAMMING DISTANCE In the theory of information processes it is a common problem that given a code received on a noisy channel and the set of legal code words, we have to determine the code word nearest in some metric to the received one. In the case of binary codes the Hamming distance is the most common choice to measure the distance. The Hamming distance of two binary strings is the number of differing bits, e.g. d(01001,11011) = 2. In this section we will show a pwuDTCNN algorithm solving this problem. Other metrics could also be applied, e.g. the Hausdorff distance. Its non-linear version, the so-called 'autowave' distance, has already been implemented on a CNN." It can be used in OCR programmes, for instance. 5.1. The algorithm Our algorithm consists of four steps. In the first one the input is compared with all legal code words, then the number of differences is counted, afterwards the minimum of these differences is computed and finally the legal code word(s) having this minimum distance is (are) selected. 5.1.1. Comparison step. Let us assume that there are m legal code words, each of them of length n. The binary values are represented by black (+ 1) and white (- 1) in the CNN. At the beginning, two m x n arrays are created, one of them containing all legal code words, each row being a different code word, and the other containing the input code m times, once in each row. In this first comparison step the exclusive OR (XOR)logic function should be applied to these two arrays, extracting the differences between the legal and the received code words. 5.1.2. Counting diferences. The previous step explored all differences between the input code and the legal code words. Now the number of these differences has to be counted row-wise, i.e. for each legal code word. This can be done by feeding the output of the previous step to the input, setting the initial state to zero and using the template of Figure 17(a). This propagating template starts from the right and copies the value of the right neighbour to the actual cell, incrementing it if a difference (coded by -0.8) is found. This means that after this step the leftmost cell of each row will contain a value corresponding to the distance between the input code and the appropriate legal code word. 5.1.3. Computing the minimum distance. By now we already know for each legal code word how far it is from the input, so in this step we have to find the minimum of these values, which can be done by a oneDiferences: Min. distance: A, = B, = [ u ] A2= (4 Best matching: (b) B, =[-'I I=0.02 (c) Figure 17. Templates of computing the Hamming distance: (a) counting differences; (b) computing the minimum distance; (c) selecting the legal code word 158 P.L. VENETIANER ET AL. legal codes input code Hamming distances best match 4 1 2 3 Figure 18. Example for computing the Hamming distance dimensional variant of the global minimum searching template of Reference 11. Use the template of Figure 17(b), applying the output of the previous step to the initial state. This template sets all cells in a column to the minimum value of the column. For us only the leftmost column is of importance. The resulting value of this column corresponds to the minimum distance between the input and the legal code words. 5.1.4. Selecting the legal code words. Only one step remains, namely to select the code word(s) that is (are) at the minimum distance computed in the previous step from the input. For this the outputs of the last two steps have to be compared, i.e. all Hamming distances with the minimum Hamming distance, and if two are equal, the corresponding legal code word is at minimum distance from the input. Feed the output of the previous step (minimum distance) to the initial state and that of the step before (Hamming distances) to the input and apply the template of Figure 17(c). In the output, black pixels in the leftmost column correspond to the rows of the legal code words at minimum distance from the input, while all other cells in the leftmost column are white. (See Figure 18 for an example.) 5.2. Time requirements Recall that we have m legal code words, each of length n. The logic comparison (step 5.1.1) takes only one step. Counting the differences (step 5.1.2) is executed by a propagating template which requires n steps to settle. Computing the minimum value of a column (step 5.1.3), also using a propagating template, is done in m steps, while the final selection (step 5.1.4) can be performed in a few steps. All this means that the task can be solved in m + n + const. steps. 6. LAY-OUT DESIGN WITH CNNS In this section it will be shown how the lay-out of a printed circuit board (PCB) can be designed using a cellular neural network universal machine. A two-layer model is assumed, where one layer contains only vertical and the other only horizontal wires. The algorithm terminates after a time of approximately 6 x wire length x t,where t is the settling time of the analogue transient (around 100 ns, depending on the underlying CNNUM chip). After a brief introduction to lay-out design, the Lee model will be explained, which is the most well-known lay-out design algorithm. Then the outline of our algorithm, also based on the Lee model, is given, followed by the description of the key element of the algorithm, namely interconnecting equipotential nodes using the shortest path. Finally, this shortest path algorithm will be generalized to the problem of lay-out design with the CNNUM. 6.1. Overview of lay-out design The lay-out design is usually decomposed into two consecutive steps, namely (i) the placement of the components on the carrier (on printed circuit board, ceramic or silicon) and (ii) the routing. The placement phase also includes assigning co-ordinates to sets of equipotential points. In the routing phase these sets of equipotential points have to be interconnected to meet the criteria of the lay-out production technology. In this paper we will apply the CNNUM to solve the second problem. Our method is based on the Lee 159 ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA model,” which is perhaps the most well-known lay-out design algorithm. The Lee model not only provides a solid, theorem-based solution but the different technological requirements can also be taken into account with the help of a cost function. 6.2. The Lee model The Lee model is defined in the complex cell space C = (C, S,N , r,M ) on the lay-out design area,12.13 where C the set of cells; in the case of a multilayer technology the cell space is quasi-three-dimensional S state of the cell: free or used N neighbourhood of the cell; four adjacent cells r cell-symbol configuration; a mapping r:C +C x S; a symbol is assigned to each cell in the design area distinguishing the cells to be connected; the cell-symbol configuration has to be updated after each completed interconnection M allowed path function; the path p between two cells c,, and c, is defined by a sequence of cells called chain co-ordinates: p ( C 0 , c,) = Cg, c , , c2,..., c,; the path function is equal to one if the path is allowed, zero otherwise; a path is allowed if all elementary paths p ( c i ,c, I ) are allowed. An elementary path p (c;, ci+I ) is allowed if the proper symbols are assigned to ci and c, + + The paths in C-space are evaluated by a cost function having k components representing the different requirements (path length, number of via holes, direction changes, etc.). A function f is called monotonic if for all paths in C-space The theorem of Lee states that for an interconnection problem defined in the complex C-space with a monotonic cost function f , there exists an algorithm finding the path for which f is minimal if there exists such a path at all. Remarks 1. If f h a s only one component, the distance, then the algorithm solves the shortest path problem. 2. The time requirement of the algorithm is proportional to the area of the enclosing rectangle of the points to be connected. Owing to this fact, the Lee-model-based routing programmes are slow. Efforts were made to accelerate the routing by add-on boards.14 3. The Lee algorithm does not deal with the problem of in which order the interconnections have to be designed.I4 There are some commonly used heuristics for the ordering problem: e.g. to start with the shortest path; to start with the extremely long connections and then to continue with the shortest wires; or to start with the power and ground points and then the other nodes.15 6.3. Outline of the lay-out design algorithm In the procedure of designing the lay-out of a printed circuit board, we assumed a two-layer model, one layer containing only vertical and the other only horizontal wires. By slightly modifying the templates, this model can easily be extended to more than two layers and the separation of the horizontal and vertical wires can also be omitted; therefore single-layer lay-outs can also be designed. A traditional processor controls the algorithm, using a CNNUM as coprocessor to execute most of the computing. The processor reads the PCB description file containing the size of the board, the location of the devices and the lists of equipotential nodes. One major step of the algorithm deals with a set of equipotential nodes. These nodes are sent to the CNNUM, which interconnects them with the shortest path, taking into account that restrictions might apply to the position of the wires. These restrictions are represented in the form of fixed state maps, a concept extensively used in the algorithm. It means that some cells do not change throughout 160 P.L. VENETIANER ETAL the transient. Such restricted locations are the pins of devices and already existing wires, which cannot be crossed by later wires. The key element of this procedure is interconnecting equipotential nodes with the shortest path. The next subsection will describe the algorithm for finding the shortest path. 6.4. Finding the shortest puth The well-known Dijkstra algorithmI6 is used to find the shortest path between points. This subsection contains the description of the algorithm, while the corresponding templates will be given in the next subsection. For the sake of better understanding, first let us consider the simplest case where only two points are given and we are looking for the shortest path interconnecting them. Let us call the two points the source and the target. In the first step of the algorithm a wave-like propagation is initiated from the given source point, marking each cell with a value a unit greater than the mark of the cell from which it was reached. In other words, this step is a breadth-first search exploring all routes starting from the source and marking each cell with a value corresponding to its distance from the source. In the second step the shortest path has to be selected. This can easily be done based on the marks of the previous step. It follows from the method of how the cells were marked that each cell, except for the source, has exactly one smaller neighbour (a cell with a smaller mark). If we move from a cell to this smaller neighbour, we get closer to the source. Thus, starting from an arbitrary point and always moving towards a smaller neighbour, we will finally reach the source on the shortest path. The above algorithm can also be used when we have more than two points. In that case several questions can be asked: e.g. given a target and several sources, connect the target with the closest source; or, given several targets and a source, connect all targets with the source. This latter problem is of importance to our problem, because it makes it possible to interconnect not just two but an arbitrary number of equipotential nodes simultaneously. The procedure is similar to the two-point case: first, all cells should be explored from the source; in the second step the selection should be started from all targets. As a result, all targets will be connected to the source on the shortest path. 6.5. Lay-out design on the CNNUM In our experiments we used a two-layer model, one layer for the horizontal and the other for the vertical wires, with a penalty for going from one layer to another to minimize the number of via holes An example of a lay-out designed with the CNNUM is shown in Figure 19. The main steps of the algorithm are as follows (see Figure 20 for a detailed flowchart). 1. Generate initial fixed state maps. 2. Connect a set of equipotential nodes. 3. Update fixed state maps. 4. If more equipotential nodes are left, go to step 2. The steps are detailed in the next subsections. 6.5.1. Generate initial fixed state maps. A fixed state map is a mask determining whether the state of a cell can change throughout a transient. Practically, it is a black-and-white image, white pixels corresponding to fixed and black ones to normal cells. Fixed state maps are used to prevent drawing wires at some places on the board. At the very beginning, such a map contains only the pins of the components. This map is created by the digital processor and it is used on both layers (ro). 6.5.2. Connect a set of equipotential nodes. The second step of the algorithm interconnects a set of equipotential nodes. This is realized on the CNNUM. First the nodes belonging to the actual set are deleted from the fixed state maps, since they are not restricted by the wires interconnecting them. Next the equipotential nodes need to be connected. This is performed in two steps Exploring all cells. The first step is exploring all cells starting from one of the nodes (This corresponds 161 ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA to the source in the above description.) For this, feed the white source point against a black background to the initial state of both layers, use the modified fixed state maps and apply the template of Figure 21(a). This template uses as unity and marks each cell by - 1 + x (distance from source), counting the crossing of layers as a move as well. Afterwards some postprocessing is required using the target points as a fixed state map and the template of Figure 21 (b) on the previous images. This equalizes the marks of the two layers at the target points. Selecting the path. This step selects the shortest path from the target point(s) to the source using a period-four cyclic time-varying template. The four parts of the template correspond to the four directions (up, down, left and right). The templates are given in Figure 22; the other three directions can be generated by rotating the template values. Apply the output of the exploring step to the input and the black target .. .. .... . . . . ........... ........ .. .. ... ... ....................... ... ... ...... ................ .I. 1.. .I. .. .. .. .. ................. .. .. .. .. .. .. .. .. ............... .. .. .. .. .. .. .. .. ............... .. .. .. .. .. .. .. .. ................. .. .. .. .. .. .. .. .. ........... ................ . . .. .. .. .. .. ......... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...................... . . . ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ................ .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ...... .. .. .. .. .. .. ...... &&At.. ...... ...... ...... ...... ...... ...... ...... ::::::I ...... ..::::id .. .. .~::I :::::j :. :. :. :. 1. :I. , . I . : : :.:.: .d :::::I:I . . . . . .I ..... :. :. .: .: .: . :::::4 ::::::I ...... :. : .: :.: .4 . ....... ..... .. .. .. .. .... ....... ..... .. .. .. .. .. .. ... ... ... ... ...... ...... ..... :::I:! ..... ..... . . . . . . . . . . . . . .:::::+I ..... A .. .. .. .. .. .. .. .. .. .. .. .. ............ .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .................. .. .. ... .. .. .. ... .. .. .. ... .. .. .. .. ................. ................ ................. .. .. .. .. .. .. ............. .. .. .. .. .. . .................. .................. Figure 19. A PCB lay-out designed with a CNNUM 162 P.L.VENETIANER ET AL. 1 generate fixed state maps I delete actual set of equipotentialI Fig. 21a [ postprocess exploration [ I I+ Isearch path u&ghtldown/left I Fig. 22aldelg wires=OR(wires,output) delete pixels of line Y updatefixed state maps fixed=NOR(fixed,NOT(output)) I ore points to be interconect n Y Figure 20. Flowchart of the layout design algorithm A,, =A,, -* =[(I 1 U] A,, = A , , = [u] Yij'YkI (8) A,, = A 2 , = A,, = A 2 , = [ a ] i ' l Ti- Yil-Ykl @) Figure 21. Templates of the exploring step: (a) explore all routes from the source; (b) postprocess explored routes 163 ANALOGUE COMBINATORICS AND CELLULAR AUTOMATA A l l = [ l 3 O]BI1=[u 0 O ] I , = l I:[= A,, A,, = 0 u] I1=1 (4 (c) B,, ]=! I, = 1 AZ2= (el A,,=[O 3 B,, =[o 1 3 4 =[o h,=[i] 12=1 (f) 0 u]1,=1 All = 4, = [ a 0 01 I, = 1 (h) (g) ta t" -t' i- -812 Uipkl -24- ti) (9 Figure 22. Templates of the selection step: (a, c , e, g) select up, left, down and right respectively using (i) as the non-linearityof the templates; (b, d, f , h) delete the actual line up, left, down and right respectively using (j) as the non-linearity of the templates points against a white background to the initial state. Starting from black pixels, the template of Figure 22(a) goes upwards till the corresponding input cell values are decreasing. This line is part of the wire, so it should be stored. Afterwards the template of Figure 22(b) deletes all cells of this line except for the last one. This deletion ensures that only one path is selected. Then the same procedure is run left, down, right and again up cyclically till the source point is reached. 6.5.3. Update fured state maps. Completing the previous phase of the algorithm results in the wires interconnecting the equipotential nodes. No later wire can cross these ones, so they should be added to the fixed state maps ( rin the Lee model). 7. CONCLUSIONS In this paper we have shown through theory and demonstration that many important combinatorial tasks can be solved by a CNN. This ability widens the field of problems which can be efficiently solved by the CNN universal machine. Some of these algorithms are no faster than the traditional digital ones, but it is very important that they can be used as subroutines of more complex CNNUM applications. The analogic layout design algorithm solves a very important real-life problem at an extremely high speed. 164 P. L. VENETIANER ET AL. ACKNOWLEDGEMENTS This work has been supported by joint research grant INT 90-01336 of the National Science Foundation and the Hungarian Academy of Sciences. K.R.C.is sponsored under the Joint Services Electronics Program, contract F49620-C-0038. REFERENCES 1. L. 0. Chua and L. Yang, ‘Cellular neural networks: theory’, IEEE Trans. Circuits andSystems, CAS-35, 1257-1272 (1988). 2. L. 0. Chua and L. Yang,’Cellular neural networks: applications’, IEEE Trans. Circuits and Systems, CAS-35, 1273- 1290 (1988). 3. L. 0. Chua and T. Roska, ‘The CNN paradigm’, IEEE Trans. Circuits und Systems I , CAS-40, 147- 156 (1993). 4. L. 0. Chua, T. Roska and P. L. Venetianer, ‘The CNN is as universal as the Turing machine’, IIEEE Trans. Circuits and Systems, CAS-40,289-291 (1993). 5. T. Roska and L. 0. Chua, ‘The CNN universal machine: an analogic array computer’, IEEE Trans. Circuits and Systems I , CAS-40, 163- 173 (1993). 6. H. Harrer and J. A. Nossek, ‘Discrete time cellular neural networks’, Int. j . cir. theor. appl., 20,453-468 (1992). 7. T. Toffoli and N. Margulos, Cellular Automata Machines: A New Environment for Modeling, MIT Press, Cambridge, MA, 1987. 8. E. Berlekamp, J. H. Conway and R. K. Guy, Winning ways, Academic, New York, 1982, Chap. 25, pp. 817-850. 9. L. 0. Chua and B. E. Shi, ‘Multiple layer cellular neural networks a tutorial’, in F. Deprettere and A. van der Veen (eds), Algorithms and Parallel VLSI Architectures, Elsevier. Amsterdam, 1991, pp. 137- 168. 10. V. Biktashev, V. Krinsky and H. Haken,’A wave approach to pattern recognition (with application to optical character recognition)’, Int. J . Bifurc. Chaos, 4, !93-207 (1994). 11. T. Roska, L. 0. Chua, T. Kozek and A. Zarindy, ‘Cellular neural networks: a short tutorial’, in T. Roska and J. Vandewalle (eds), Cellular Neural Networks, Wiley, Chichester, 1993, pp. 1-14. 12. C. Y. Lee, ‘An algorithm for path connections and its applications’, IRE Trans. on EC, EC-10,346-365 (1961). 13. I. Abos, ‘On some problems of computer aided layout design’, Proc. Sixth Colloq. on Microwave Conimunicution, Budapest, 1978, Vol. I, pp. II-2/10.1-4. 14. E. S . Kuh and T. Ohtsuki, ‘Recent advances in VLSI layout’, Proc. IEEE, 78,237-263 (1990). 15. I. Abos and P. Szolgay, ‘Printed circuit layout design with highly efficient algorithms on small computers for medium sized companies’, in J. Mermet (ed.), CAD in Medium Sized and Smalllndustries North-Holland, Amsterdam, 1981, pp. 385-395. 16. E. W. Dijkstra, ‘A note on two problems in connexion with graphs’, Numer. Math., 1, 269-271 (1959).