Arrangement of data cells and neural network system utilizing such an arrangement

An arrangement of data cells which stores at least one matrix of data words which are arranged in rows and columns, the matrix being distributed in the arrangement in order to deliver/receive, via a single bus, permuted data words which correspond either to a row or to a column of the matrix. Each data cell is connected to the single bus via series-connected switches which are associated with a respective addressing mode, the switches which address a same word of a same mode being directly controlled by a same selection signal. Circulation members enable the original order of the data on the bus to be restored. An arrangement of this kind is used in a layered neural network system for executing the error backpropagation algorithm. Application: Calculator, microprocessors, processor, neural network system. Reference: FIG. 4.

The invention relates to an arrangement of data cells which stores at least 
one matrix of data words which are arranged in rows and columns, the 
matrix being distributed in the arrangement in order to deliver/receive, 
via a single bus and by means of mode selection means, permuted data words 
which correspond either to a row or to a column of the matrix. 
The invention also relates to a neural network system utilizing such an 
arrangement. 
BACKGROUND OF INVENTION 
The document WO 84/00629 discloses a memory system with multi-dimensional 
access. This document relates to the writing and reading of a 
two-dimensional data table stored in a memory. In order to enable the 
addressing of the data words either rows-wise or column-wise in the table, 
the data is arranged in the memory in a special way so that it can be 
read/written by means of a single bus. To this end, the data is loaded one 
row after the other, the first row loaded corresponding to the first row 
of the table, the second row loaded corresponding to the second row of the 
table, be it that the data of one memory block have been subjected to a 
circular permutation. Each row loaded is thus shifted through one memory 
block with respect to the preceding row and hence subjected to the 
corresponding circular permutation. The data which was arranged in a 
column of the table is thus arranged along a diagonal of the memory. The 
data which was situated in a row of the table is still situated in the row 
of the same rank of the memory, be it with a given circular permutation. 
For the addressing of a row or a column of the table, distributed over 
several memory columns, it is thus necessary to determine each time the 
real address in the memory by means of an address modifier. The data which 
appears with a given permutation can be reestablished in the initial order 
by means of a member which performs the rotation of the data. Each address 
modifier associated with each column performs an address calculation which 
depends on the row and the column of the table and on the column of the 
memory. Such calculations necessitate a large quantity of hardware which 
has the drawback that it delays the calculation of the real addresses and 
that it is too elaborate to enable a compact integrated realization. 
SUMMARY OF INVENTION 
The problem, therefore, is to realize an arrangement of the type described 
above which is fast and which can be integrated in a compact manner. The 
solution to this problem consists of an arrangement for which each data 
cell is connected to the single bus via switches which are connected in 
series and which are associated with each addressing mode, the switches 
addressing a same word of a same mode being directly controlled by a same 
selection signal. 
Thus, a single line carrying a single mode selection signal can address an 
entire given word by simultaneously activating all relevant switches for 
each bit of a word. Each switch may be formed by a selection transistor. 
This increases the compactness and the speed of the arrangement notably 
when it is realized as an integrated circuit. 
The matrix of data words can be diagonally distributed in the arrangement 
so that one row (one column) of the matrix is distributed diagonally in 
the arrangement, the other rows (other columns) of the matrix being 
distributed parallel to said diagonal. 
The bits constituting the data words appear on the bus in an order which 
deviates from their order in the data words of the matrix. In order to 
reestablish this order, therefore, a sorting operation is required; this 
operation is performed by a circulation shift register which is controlled 
by a circulation member which shifts the data along the addressed row of 
the matrix. This sorting of data on the bus can also be performed by an 
adder which determines an internal address of the buffer circuit by adding 
a predetermined value, belonging to the addressed row in the arrangement, 
to an external address of the buffer circuit. 
When distribution of several matrices of data words is desired, this can be 
realized in a two-dimensional or a multi-dimensional arrangement. In the 
latter case each dimension has its selection mode. Thus, there may be 
three selection modes X, Y, Z in a three-dimensional arrangement. 
The importance of a compact and fast realization becomes manifest notably 
in systems necessitating the storage of a large number of tables which may 
have large dimensions. This is the case, for example in neural network 
systems. An as dense as possible integration with high processing speeds 
is then required. 
The neural networks are formed by elementary functional units which are 
interconnected by synapses with which synaptic coefficients are 
associated. A neural network performs resolving steps during which the 
states V.sub.j of output neurons j are determined on the basis of states 
V.sub.i of input neurons i. This resolving phase takes place in accordance 
with: 
##EQU1## 
However, for adaptation to a given task the neural network must also 
perform training steps. Such a neural network is described, for example in 
the document "A chipset for high speed simulation of neural network 
systems", S. C. J. Garth, IEEE Conference on Neural Networks, San Diego 
III-443 (1987). The training steps serve to modify the synaptic 
coefficients so as to adapt the network to a given problem. 
For performing the training algorithm according to error backpropagation, 
the neural network has a layered structure. During a step of the 
"resolving" type, states of output neurons are determined by means of 
synaptic coefficients stored in the network. Subsequently, a host computer 
compares the states of the output neurons determined with the states of 
the neurons considered. The errors observed are introduced into the last 
layer of the network, after which they are backpropagated with a 
propagation direction which has been reversed with respect to the 
resolving mode. For successively performing a resolving step and 
subsequently a training step, use is made of synaptic coefficients 
according to a matrix C.sub.ij in the resolving step and according to a 
matrix C.sub.ji, being the transposed matrix C.sub.ij, during the training 
step as disclosed in the document by S. C. J. Garth. 
For each change-over between the steps this necessitates the execution of 
repeated loading operations for the storage means for the synaptic 
coefficients by either the matrix C.sub.ij or the transposed matrix 
C.sub.ji. 
The execution of these loading operations requires a large amount of time. 
The number of calculations to be performed being very large, the speed can 
be increased by performing a parallel processing operation. To this end it 
must be possible to read/write the matrix C.sub.ij in blocks of rows or 
columns, depending on the relevant step. 
To this end, it may be attempted to double the number of means for storing 
the synaptic coefficients or the number of buses, but that will be at the 
expense of the compactness of the system and also necessitates the use of 
supplementary selection means which slow down the operation. 
Therefore, the invention utilizes the arrangement of data cells described 
above. In this case the invention relates to a layered neural network 
system comprising: 
resolving means for determining, for each layer, the states of output 
neurons i on the basis of the states of input neurons j which are linked 
by way of synapses, 
storage means for the synaptic coefficients C.sub.ij associated with these 
synapses, 
means for training and for updating the synaptic coefficients C.sub.ij, 
means for storing the neuron states, characterized in that the means for 
storing the synaptic coefficients are formed by at least one arrangement 
of the type described above which stores at least one square matrix of 
synaptic coefficients C.sub.ij which are distributed in at least one 
memory which is of the dual-addressing type and comprises a single bus so 
that a word of synaptic coefficients relating to either a row or to a 
column of the square matrix can be addressed and placed on the single bus 
in order to ensure that the neural network system performs training steps 
either with the synaptic coefficient matrix or with the transposed matrix 
in order to execute the error backpropagation algorithm. 
In a preferred version, the synaptic coefficients are diagonally 
distributed in a two-dimensional memory so that one row (one column) of 
the matrix is distributed along a diagonal of the memory, the other rows 
(other columns) of the matrix being distributed parallel to said diagonal. 
Thus, the synaptic coefficient words preferably appear on the bus in a 
predetermined order and nevertheless remain easy to use in their initial 
order by means of a circulation shift register. To this end, the means for 
storing the neuron states comprise a circulation shift register which 
enables circulation of the neuron states in order to link each neuron 
state to its synaptic coefficient. 
Thus, instead of resetting the synaptic coefficients in their initial 
order, the neuron state vectors are subjected to appropriate circular 
permutations. 
These circular permutations are controlled by an address calculator which 
performs the circulation in the shift register by generating the commands 
corresponding to the row of the addressed synaptic coefficient word. As 
can be deduced from the above, the invention relates in general to a data 
handling system comprising a plurality of cell for upon selection 
communicating data with an environment, the data handling system being 
provided with selection means for selecting a group of cells for 
establishing parallel couplings between the selected cells and a single 
data-bus via respectively data paths. Each particular cell belongs at 
least to a respective first group and a respective second group, that have 
only the particular celll in common and that can be selected in a first 
and a second selection mode, respectively. The selection means transmits 
at least a first and a second selection signal for in dependence thereon 
controlling the data path between each cell and the databus. 
Thus, access to the cells is enabled according to predetermined patterns 
controlled by the two selection signals. In case the plurality of cells 
has been organized as a main matrix selection modes might enable for 
instance a parallel row-wise data communication as regards the rows of the 
matrix organization and a parallel data communication as regards diagonals 
of for instance square submatrices in the main matrix. 
This is advantageous in appliances involving data processing performed on 
both the data matrix and its transposed. As has been described 
hereinabove, an applicance of this kind is found in the adaptive layered 
neural nets that are trained according to the so-called 
backpropagation-algorithm. In general, the advantages lie in the use of a 
single data matrix to be stored, the parallel data communication enabling 
high speed, and a simple mode selection mechanism. 
As already has been mentioned, each datapath may comprise a series 
arrangement of switches each being controlled by a respective selection 
signal. One can easily imagine an embodiment of the invention wherein this 
datapath includes a series arrangement of conduction channels of 
transistors that represent the switches. A practical equivalent might 
include a transistor controlled by a further selection signal 
representative of a logic function of said first and second selection 
signals and generated by means of a logic gate proper to each cell, thus 
reducing threshold and saturation losses in the datapath-transistor. In 
case each cell stores a multibit word this architecture might save 
substrate area on an IC. 
This neural network system may form a compact integrated circuit for fast 
parallel processing.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
For the sake of clarity, the description is based on a two-dimensional 
arrangement of memory points. Its extension to three dimensions is shown 
in the FIGS. 6A and 6B. Higher-order dimensions can be readily deduced 
therefrom. 
FIG. 1 shows a matrix 10 in which the data is stored with customary row or 
column addressing. For the clarity of the description, the numbers stated 
in each block represent the data stored. In this case the rows/columns of 
the matrix coincide with the rows/columns of the arrangement. Thus, the 
row L1 contains the data 00 to 70 and the column C1 contains the data 00 
to 07. The matrix can be addressed either row-wise or column-wise. Thus, 
if the column C3 is addressed the data of the column appear on the bus 
11.sub.1 and can be stored in the buffer register 12.sub.1. The data 20 is 
stored in the upper block of the register and the data 27 is stored in the 
lower block of the register. Moreover, if the row L3 is addressed, the 
data selected appears on the bus 11.sub.2 and can be stored in a buffer 
register 12.sub.2. The data 02 is stored in the left-hand block of the 
register and the data 72 is stored in the right-hand block of the 
register. The data of the rows or the columns thus appear on different 
buses, necessitating the use of different buffer circuits. If the use of a 
single buffer circuit is to be realized for such an arrangement, it can be 
achieved only at the expense of supplementary interconnections, some of 
which are very long, and with the addition of numerous selection elements. 
In accordance with the cited prior art document, the data word matrix will 
be disposed in the arrangement of data cells as shown in FIG. 2. Contrary 
to the former case, a line/row of the matrix and a line/row of the 
arrangement are distinguished. In this arrangement it can be observed that 
the data which were present on the first row of FIG. 1 are placed on the 
diagonal of the square matrix of FIG. 2. Each column is then arranged by 
placing the value of the first row of FIG. 1 in the block of FIG. 2 which 
is situated on the diagonal, followed by the other values, for example by 
displacement towards the bottom; when the bottom of the matrix is reached, 
the loading of the column is continued with the block of the first row. In 
accordance with this arrangement, when the column C3 is addressed the data 
of the column appear on the output bus and then possibly in the buffer 
register 12.sub.1 in the arrangement represented by I. It appears that the 
output data is the same as in FIG. 1, be it in a different arrangement. 
Thus, the data 20 no longer appears in the upper block but in the third 
block of the buffer circuit 12.sub.1. Thus, each data is shifted over a 
number of positions equal to the rank number of the addressed column. 
Similarly, when the row L3 is addressed, the selected data appears on the 
same bus and in the same buffer circuit 12.sub.1 as before in accordance 
with the arrangement represented by II. The buffer circuit 12.sub.1 is 
shown twice in FIG. 2 for the sake of clarity. It appears again that the 
data is the same as when the row L3 is addressed in accordance with the 
arrangement shown in FIG. 1, be it again with a different arrangement. 
Each data is thus shifted through a number of positions equal to the rank 
number of the addressed row. 
The example given relates to a square matrix, but the invention also holds 
good for rectangular matrices M.times.N subject to the condition that the 
single bus and, if necessary, the single buffer circuit are arranged at 
the side of the matrix which delivers the maximum bits. The memory 
elements which have the same diagonal address are obtained by translation 
of the square matrix, either M.times.M or N.times.N, inscribed in the 
rectangular matrix M.times.N. 
FIG. 4 shows the addressing structure of the arrangement of data cells in 
accordance with the invention which utilizes the arrangement of the data 
matrix shown in FIG. 2. In this simple example, corresponding to a 
3.times.3 arrangement, the points P11, P21, P31 of the same column are 
selected by the same selection signal CI1 which acts on transistors T11, 
T21, T31. Similarly, the signals CI2, CI3 select the other columns. The 
memory points P11, P22, P33 situated on the same diagonal of the 
arrangement (same column of the matrix) are selected by the signal LI1 
which acts on the transistors R11, R22, R33. The signal LI2 acts on the 
points P21, P32 and P13. The signal LI3 operates on the points P31, P12 
and P23. In order to perform the selection of a point, it is necessary to 
activate, for example either all signals LI and one of the signals CI or 
vice versa. The data is delivered to the bus 11.sub.1. Conversely, for 
writing it suffices to present the data on the bus 11.sub.1, to perform 
the addressing operation and to set the memory points to the write state. 
The described example concerns a two-dimensional arrangement. The FIGS. 6A 
and 6B show a three-dimensional arrangement of cells. In this case, in 
accordance with the invention (FIG. 6A) addressing can be performed, for 
example in a direction D corresponding to one dimension of the matrix and 
in one diagonal direction, for example the directions E or F. The 
three-dimensional matrix is represented by three indices, the direction D 
corresponding to points having one of the constant indices. When the 
addressing in the direction D concerns exclusively the part of the matrix 
at the front face of cube shown (a single constant index), the selected 
groups of cells correspond to one column of cells of this front face. When 
the addressing in the direction D concerns the entire three-dimensional 
space (two constant indices), the selected groups of cells correspond to a 
slice which is based on said column and which extends in the direction 
perpendicular to said front face. For the benefit of explanation the 
three-dimensional matrix is shown in the form of a cube, but it may also 
have an arbitrary other shape. The multi-dimensional arrangement can 
notably be topographically arranged according to one surface (two 
dimensions). 
The second addressing operation must be performed in the diagonal 
directions E or F for which either two or three indices remain mutually 
identical. Thus, this concerns the diagonals themselves and also the rows 
of cells which extend parallel thereto. 
With each of the dimensions of the matrix there are associated addressing 
means which are shown in FIG. 6B and which follow from the structure of 
FIG. 4. A single memory element P314 is shown. The transistors T314 
(command CI.sub.1), S314 (command DI.sub.4), R314 (command LI.sub.3) 
enable the addressing in the three dimensions of the matrix. A memory 
point, for example P314, is selected by activating, for example all 
commands CI and DI and only the command LI.sub.3. Actually, for activating 
an arbitrary cell it is necessary to activate the complete addressing in 
two dimensions of the matrix and in the other dimension only the command 
relating to the relevant cell. 
FIGS. 3A and 3B show an M.times.N matrix 10 provided with a single bus 
11.sub.1 which is connected to a buffer circuit 12.sub.1 which is capable 
of storing slices of M bits. FIG. 3A shows a first embodiment of the means 
for sorting the output data. To this end, a generator 20 supplies 
addresses which determine the addressing of the row 21.sub.1 and the 
column 21.sub.2, under the control of an external command 19, by means of 
decoders 25.sub.1 and 25.sub.2, respectively. The same command 19 reaches 
a circulation member 22 which delivers, depending on the rank of the 
address supplied, either a row address or a column address, a circulation 
command 23 to the buffer circuit 12.sub.1 which is formed by an end-around 
coupled shift register. Thus, the data read during the addressing 
operation and subsequently stored in the buffer circuit 12.sub.1 are 
arranged in the desired order by this operation before being delivered to 
the bus 13. 
FIG. 3A enables parallel data output. It may be interesting to enable 
series output the desired order. To this end, in FIG. 3B the output data 
are arranged directly by means of address decoding. To this end, the 
addressing command 19 for the memory 10 is applied to an adder 31 which 
also receives an external address 35 for reading the buffer circuit 
12.sub.1 which in this case is no longer formed by a end-around coupled 
shift register but by a row of memory points which is connected to a 
single series output 36. To the address 35 there is added a value which is 
contained in the command 19 and which depends on the rank of the row or 
the column addressed in the memory 10. The adder is connected to a decoder 
which supplies the internal address of the desired memory point in the 
buffer circuit 12.sub.1. The external address 35 may arrive from an 
external device or a counter which determines the addresses for the 
reading of the buffer circuit 12.sub.1. 
FIG. 5A shows a part of a neural network circuit concerning a simplified 
example in the case of a two-dimensional arrangement. For a neuron 1 the 
arrangement 10 supplies on its bus the four synaptic coefficients 
C.sub.11, C.sub.12, C.sub.13, C.sub.14 which arrive at multipliers 
50.sub.1, 50.sub.2, 50.sub.3, 50.sub.4 which receive the neuron states 
V.sub.1, V.sub.2, V.sub.3, V.sub.4, respectively, stored in the shift 
register 12.sub.1 which in this case forms the neuron state memory. These 
multipliers are connected to an adder tree 51 which delivers a result S so 
that: 
EQU S=S.sub.11 .multidot.V.sub.1 +C.sub.12 .multidot.V.sub.2 +C.sub.13 
.multidot.V.sub.3 +C.sub.14 .multidot.V.sub.4. 
For a neuron 2 the arrangement will deliver the synaptic coefficients with 
a different arrangement is as shown in FIG. 5B. Before performing the 
calculation for the resolving step, the shift register 12.sub.1 circulates 
the neuron states for correct assignment of each neuron state to its 
synaptic coefficient. The synaptic coefficient C.sub.23 is associated with 
the state V.sub.3, the synaptic coefficient C.sub.22 being associated with 
the state V.sub.2 and so on. 
FIG. 5C concerns the training step. Actually, in this case the synaptic 
coefficients are read according to the transposed matrix: C.sub.11, 
C.sub.21, C.sub.31, C.sub.41. In this case the register 12.sub.1 no longer 
contains the neuron states but the errors D.sub.1, D.sub.2, D.sub.3, 
D.sub.4 in order to execute the error backpropagation algorithm. The same 
circulation mechanisms are used for assigning the data. Thus, the 
customary register which stores the neuron states is transformed into a 
circulation shift register in order to enable adaptation to the permuted 
synaptic coefficient words supplied by the arrangement. 
However, the circulation mechanism cannot be realized by the shift 
register, the coefficients being stored in temporary registers which are 
loaded by multiplexers comprising N channels (for N synaptic coefficients) 
which restore the correct order of the coefficients. 
In the case where no random access to the neurons takes place but rather 
sequential access in the order: neuron 1, followed by the neuron 2, 
followed by the neuron 3 etc., after each evaluation of the neurons a 
shift takes place in the shift register containing either the neuron 
states or the errors, these terms thus corresponding each time with the 
synaptic coefficients whereby they are weighted. At the end of N 
calculations, the starting position is reached again. 
In a circuit where the states are encoded on m bits and where the 
multipliers also perform multiplications by m-bit terms, the shift 
register is formed by m identical shift registers, each of which has one 
of the weights for the representation of the states. 
In a circuit where the states are encoded on m bits and where the 
multipliers perform multiplications on 1 bit (using, for example, 
AND-gates or exclusive-OR gates), m cycles are required for calculating 
the weighted sum for a neuron. In this case the shift register comprises 
N*m positions and performs a shift after each bit calculation.