close

Вход

Забыли?

вход по аккаунту

?

909

код для вставкиСкачать
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, =[2]
B, = [ u ]
A2=[001]
(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 , =[1]
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,, =[2]
0 u]
I1=1
(4
(c)
B,,
]=!
I, = 1
AZ2=[2]
(el
A,,=[O 3
B,, =[o
1 3 4 =[o
h,=[i]
12=1
(f)
0 u]1,=1
All =[2]
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).
Документ
Категория
Без категории
Просмотров
3
Размер файла
1 144 Кб
Теги
909
1/--страниц
Пожаловаться на содержимое документа