CEB NT - 97/03

30 September 1997

**A Cellular AutomatON for Cluster Selection**

**in THE HERA-B PRETRIGGER BOARD**

C.Baldanza, M.Bruschi, I.D'Antone

Istituto Nazionale di Fisica Nucleare

Bologna,Italy

**Abstract**

In this note the development of a cellular automaton for cluster selection
is described. The work has been developed to elaborate data coming from
the electromagnetic calorimeter in the HERA-B experiment. The cellular
automaton has been implemented in 1/4 Xilinx 4020 FPGA and it handles 10x5
arrays. This application shows how a cellular automaton, able to select
interesting clusters in bidimensional (2D) array, can be fitted in an FPGA.
General criterions are also given to optimize the architecture of the cellular
automata.

CENTRO DI ELETTRONICA

ISTITUTO NAZIONALE DI FISICA NUCLEARE

Sezione di Bologna

(It is also a HERA-B internal note, ID 97-177)

**1.Introduction**

The technique described here has been used in the pretrigger board developed
for the electron selection in the ECAL detector for the HERA-B experiment.
The *e ^{+}e^{-}* candidates are selected by means
of a threshold function on the energy release of the particles on one ECAL
single cell. The total energy release is measured summing up the signal
formed by 3x3 calorimeter cells. To select the interesting clusters, each
cell has been compared with the neighbours. The cells having an energy
value higher than that of the neighbours at north, south, east and west
have been selected.

**2.Cellular automata**

Cellular automata (CA) were originally conceived by Ulam and von Neumann
[1] in the 1940s to provide a formal framework for investigating the behaviour
of complex, extended systems. CAs are dynamical systems in which space
and time are discrete.

A cellular automaton [2] consists of a regular grid of cells, each of
which can be in one of a finite number of *k* possible states, updated
synchronously in discrete time steps according to a local, identical interaction
rule. The state of a cell is determined by the previous states of a surrounding
neighbourhood of cells.

The infinite or finite cellular array (grid) is n-dimensional, where
n=1,2,3 is used in practice. The identical rule contained in each cell
is essentially a finite state machine, usually specified as a *rule table*
(also known as the *transition function *or* evolution matrix*),
with an entry for every possible neighbourhood configuration of states.
The neighbourhood of a cell consists of the surrounding (adjacent) cells.
For one-dimensional CAs, a cell is connected to *r* local neighbours
(cells) on either side, where *r* is a parameter called the radius
(thus, each cell has 2r+1 neighbours, including itself). For two-dimensional
CAs, two types of cellular neighbourhoods are usually considered: 5 cells,
consisting of the cell along with its four immediate nondiagonal neighbours,
and 9 cells, consisting of the cell along with its eight surrounding neighbours.
The term configuration refers to an assignment of states to cells in the
grid. When considering a finite-sized grid, spatially periodic boundary
conditions are frequently applied, resulting in a circular grid for the
one-dimensional case, and a toroidal one for the two-dimensional case.
A one-dimensional CA is illustrated in fig. 1

__Rule table__

neighbourhood: 111 110 101 100 011 010 001 000

new state: 1 1 1 0 1 0 0 0

__Grid__

t=0 0 1 1 0 1 0 1 1 0 1 1 0 0 1 1

t=1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1

fig.1

In fig. 1 is illustrated a one-dimensional, 2-state CA. Each cell can be in one of two states, denoted 0 and 1. The connectivity radius is r=1, meaning that each cell has two neighbours, one to its immediate left and one to its immediate right.

Grid size is N=15. The rule table for updating the grid is shown on top. The grid configuration over one time step is shown at the bottom. Spatially periodic boundary conditions are applied, meaning that the grid is viewed as a circle, with the leftmost and

rightmost cells each acting as the other's neighbour.

The systematic study of CAs in this context was pioneered by Wolfram
[2] and studied extensively by him, identifying four qualitative classes
of CA behaviour (called Wolfram classes), with analogs in the field of
dynamical systems:

Class I -- evolution to a uniform state

Class II -- evolution to isolated cyclic states

Class III -- evolution to comprehensive cycle states, in chaotic fields whose behaviour is

never predictable

Class IV -- evolution to complex isolated states.

Non-uniform CAs can also be considered in which the local update rule
(i.e., rule table) need not be identical for all grid cells.

**3. Cluster selection**

In the electronic pretrigger board, developed in our laboratory, the selection of interesting clusters is performed comparing each cell with the nondiagonal neighbours. The cells having an energy value higher than that of the neighbours at north, south, east and west have been selected. Each cell has an energy digitalized in 7bits.

To perform the comparison of each cell with four neighbours it is required the implementation of four 7bit parallel comparators for each cell.

If we have time to perform the selection, a serial solution can be adopted.
In this case four 1bit comparators for each cell can be implemented. The
same 1bit comparators (fig.2 ) can be used to perform in 7 cycles the complete
comparation. The assembled array of cells in the serial approach is a *cellular
automaton* with 1bit state. In one evolution step it reaches a stable
state; it belongs to the *Wolfram class I* cellular automata.

To clarify the behaviour of the cellular automaton we consider a simple one dimensional CA. A great advantage of working with one dimensional CA is that their time evolution can be shown on a two dimensional chart, whereas the evolution of a two dimensional structure would require a third dimension.

Suppose a 50 cells CA with 1 neighbour on each side and with the following
rule table:

__Rule table__

neighbourhood: 111 110 101 100 011 010 001 000

new state: 0 0 0 0 1 1 0 0

Wolfram has shown, in its CA classification, that it is convenient to
refer to the rule by the decimal equivalent of the resulting number. This
number is called the *Wolfram rule number*.

fig.3

The second row of the rule table shows how the three-cell neighbourhood evolve.

In fig.3 is shown the evolution of a CA with 50 cells starting from some random configurations evolving with the Wolfram's Rule 12. We see that the rule performs a clusterization algorithm: some clusters at t=0 are grouped in one single cell at the next evolution time t=1.

The CA with the Wolfram's Rule 12 reaches a stable state in one evolution step. We show in fig.3 five evolutions starting from random configurations at t=0, t=t1, t=t2, t=t3, t=t4.

In a bidimensional array (2D), with five neighbours defined and indexed as shown in fig.4, the possible rules are 2^(2^5). In this case the 2D Rule 240 can be used to have a behaviour as the 1D Rule 12.

In fig.4 is shown the rule table as a matrix in which five pixels in a column represent a central cell (numbered 2) with its four immediate non diagonal neighbours (numbered 0, 1, 3, 4). The pixel may be white (state 0) or black (state 1).

Following the criterion described above, the Rule 240 can be used to
perform a clusterization algorithm.

fig.4

**4. FPGA Implementation**

The energy values coming from the detector are updated, in the HERA-B
experiment, with about 10 MHz rate (96ns). We have performed several hardware
simulations of the FPGA fitting. The best solution to do the selection
within 96ns has been an intermediate architecture between the parallel
and the serial solution.

fig.5

The serial solution is implemented by using the same *cellular automaton*
(CA) sequentially 7 time with cells having 1bit state. The parallel solution
is obtained with a CA having cells with 7bit state.

In fig.5 is shown the area occupied in the FPGA, indicated in logic block CLB, needed to realize one cell, related to the CA state number of bits. It is also shown the elaboration time to perform one complete clusterization step related to the CA state number of bits. We see that the best solution is the choice of 2bit state, because the elaboration time is less than 96ns and the area occupied by the CA is low.

Then in our configuration, a cellular network performing the comparison on 2bit has been chosen; each CA cell has 2^2= 4 states.

To handle a bidimensional array composed of 50 cells included the border
cells, i.e. 84 cells, a Xilinx 4020 FPGA has been used. The *cellular
automaton* is fitted in 1/4 Xilinx 4020 FPGA. With the same FPGA we
handle two different architectures of the cell array loading two different
programs in the FPGA at the start-up.

We use the same *cellular automaton* with 2bit state for 4 cycles
to perform the complete clusterization algorithm in 96ns.

The data arrives in the *cellular automaton* in a serial format
and they concern the central and the border cells (fig.6). In output the
clusters are reduced to the central cells and furthermore another circuit
gives the addresses of the central cells selected.

The criterions for the choice of a cell are:

1. the cell must have a value higher than the cell in the upper side and the cell to the left side.

2. the cell must have an equal or higher value than the cell in the
lower side and to the right side.

To compare two cells a serial comparator in double line is used, adapted to the input data format. At each fCLK edge (fCLK=96/4=24ns) a couple of 2bit of energy value, related to two adjacent cells, are read and compared. The information of the comparator is stored and transferred to the next circuit at the next synchronization impulse.

Any C cell is connected to 4 comparators called Upper (U), Lower (D), Left (L) and Right (R).

Fig. 7

As it is seen in Fig.2, two cells to be compared are connected to the
**d**
and **c** inputs of the comparators. In fig.7 is shown the digital circuit
performing the comparation as described above.

**5.Conclusion**

In this report the use of a cellular automaton for cluster selection has been described. The cellular automaton handles 10x5 matrix and it has been efficiently implemented in 1/4 Xilinx 4020 FPGA . This application shows how a cellular automaton, able to select interesting clusters in 2D array, can be fitted in an FPGA.

Some quantitative parameters have been given to optimize the number
of bits of the cellular automaton state related to the FPGA area and the
one step evolution time.

**References**

[1] John von Neumann, *Theory of Self-reproducing Automata*, University
of Illinois

Press, 1966

[2] S.Wolfram, *Universality and complexity in cellular automata*,
Physica D, 10:1-35,

1984

*Page edited by Bisi
Fabio*