Note: Descriptions are shown in the official language in which they were submitted.
~ ~77~
FJEI,D OF THE INVENTION
The invention relates to cellular automata which are capable of
generating random data.
~ACKGROU~D OF THE INVE~TION
The invention has specific, though by no means exclusive,
application to digital circuits with built-in self-testing mechanisms,
particularly those configured in modular form and appropriate, for example,
for use in microprocessor-based systems employing buses for data and
address transfer.
Such digital circuits may be functional modules such as
read-only memories (ROM's), random access memories (RAM's), arithmetic
logic units (ALU's), or inputtoutput (ItO) devices. Clocked latches would
norrnally be used to interface such modules with data buxes for data transfer.
Por purposes of self-testing, the latches might be replaced with built-in logic
block observers (BILBO's), one such BILBO being associated with the input
terminals of the modules principal circuit, and the other, with the output
terminals. The BILBO's function not only as conventional data latches for
purposes of norrnal module operation, but have modes of operation in which
one BILBO serves as a pseudorandom data generato¢, applying various digital
test pattems to the input terrninals of the principal circuit associated with the
module, and in which the other BILBO serves as a signature analyzer which
compresses the output data produced by the circuit under test into a unique set
of data bits or signature. The resulting signature can be compared with a
predetermined expected signature to determine whether the circuit under test is
function properly.
BILBO's have typically been shift registers with feedback
.
logic gates coupling the output terminals of higher order flip-flops to a
multiplexor associated with the input terminal of the lowest order flip-flop.
With appropriate signalgating circuitry, and upon application of appropriate
control signals to such circuitry, as, for exarnple, to disable the feedback gates,
5 the shift register can function in four distinct modes: as a conventional datalatch; as a conventional linear shift register; as a pseudorandom data generator;
and as a signature analyzer. As a pseudorandom data generator, the contents
of the shift register runs through a pseudorandom sequence with a
predetermined maximum period dependent on the number of flip-flops
10 involved and the characteristic polynomial created by the associated feedback gates.
A principal problem associated with using linear feedback shift
registers in such applications relates to the need to tap the output terminals of
selected flip-flops in the shift register and to feed their state values through15 appropriate logic gates to a multiplexor associated with the lowest order bitAn immediate concern in selecting appropriate feedback taps is that their
configuration is not independent of the length of the register for maxirnum
length polynomial division, Another potential problem relates to finding an
appropriate circuit topology which can accommodate the required feedback
20 from higher order flip-flops to the input multiplexor, particularly as the shift
register is made large
~IMARY OF THE I~VEN~
In one aspect, the invention provides a cellular automaton
which generates pseudorandom data The automaton comprises a series of
25 cells arranged such that each cell receives signals from f~rst and second
electrically adjacent cells Each particular cell has a storage unit for electrically
storing a data bit having two distinct states, and logic circuitry for coupling
:
, .
~ 277769
the storage unit of the particular cell to the storage unit of the associated first
electrically adjacent cell and to the storage unit of the associated second
electrically adjacent cell. The logic circuit~y changes the value of the data bit
stored by the particular cell according to the following relationship
a(hl)=afirst(t) XOR [a(t) OR asecond(t)]
where, a(t) represents the current state of the data bit stored by the particular
cell, a(t+l) represents the next state of the data bit stored by the particular cell,
af~rst(t) represents the current state of the data bit stored by the first electrically
adjacent cell, and asecOnd (t) represents the current state of the data bit stored
by the second electrically adjacent cell.
A principal advantage of such autornata is that the succeeding
state of each cell is dependent only on the current state of the two electrically
adjacent cells The need to tap certain higher order bi~s and to feed state values
back to a multiplexor, as has been characteristic of prior random data
generators incorporating linear feedback shift registers, has accordingly been
eliminated Basically, what has been provided is a unique cell design for
construction of such cellular automata, which permits an automaton of any
desired bit size to be constructed by effectively juxtaposing the required
number of cells
Other aspects and advantages associated with the present
invention will be apparent from a description of a preferred embodiment
below and will be more specifically defined in the appended claims
DESCRlPTlON OF THE DR~WIN~
The invention will be better understood with reference to
drawings in which:
fig 1 schematically illustrates a eight automaton embodying the
invention;
.~ .
~2777~
fig. 2 schematically illustrates a typical application for the
cellular automaton of fig. 1.
~ON OF A PR~FERRED EMBODIMENT
Reference is made to fig. 1 which illustrates an eight-cell
autornaton embodying the invention. The cells of the automaton have been
designated with reference numeral 1-8 inclusive. The cells 1-8 are arranged
in a series such that each of the cells 2~ intermediate of end cells 1 and 8 is
associated with first and second electrically adjacent cells. Each cell has two
"electrically adjacent" cells in the sense that each cell receives cell state signals
only from such cells. Terminals Al and Bl associated with the end cells 1, 8
are preferably electrically connected and also terminals A2 and B2 associated
with the end cells 1, 8 such that the cells 1-8 constitute a ring structure in
which the cell 1 is associated with two electrically adjacent cells, namely, cells
2 and 8, and in which the cell 8 is associated with two electrically adjacent
cells, namely, cells 1 and 7. Accordingly, each cell of the automaton may be
seen to bear a sirnilar relationship with two electrically adjacent cells.
Certain signal gating and control circuitry associated with each
of the cells 1-8 responds to control signals applied to two control lines Cl, C2and to the logic states of data signals applied to eight data input terminal
Tl-T8. This arrangement pe~rnits the automaton to operate in four distinct
operating modes: as a linear shift register, æ a conventional data latch for
storing data received at the eight input terminals, as a pseudorandom data
generator, or as a signature analyzer which compresses data received at the
eight data input terminals Tl-T8 into a unique eight bit signature.
For purposes of understanding cell operation, the operations
inherent in the cell 3 will be discussed below. Since the cells have identical
1~7776`~
configurations, common components of the various cells 1-8 have been
indicated with common alphabetic designators followed by the appropriate cell
number or the cell number and a second identifying numeral. It should be
understood that the description provided regarding the configuration and
S internal operations of the cell 3 is equally applicable to the other cells.
The cell 3 comprises a ~type flip-flop FP3 which stores a
single data bit having two distinct logic states. The current state of the data bit
can be detected electrically at the output terminal associated with the flip-flop
FF3. As is well known, a ~type flip-flop is characterized in that the next
10 state of the flip-flop in response to a clock signal corresponds directly to the
current state of the input signal applied to its input terrninal. The cell structure
can, however, be implemented with other types of flip-flops or storage units.
The cell 3 has logic circuitry which generates a logic signal in
response to the current state of thc flip-flop FF3 and the current states of the15 flip-flops FP2, PP4 of the electrically adjacent cells 2, 4. This logic circuitry
comprises an OR gate OR31 and an EXCLUSIVE OR gate XOR31. The gate
OR31 has an input terminal connected to output terrninal of the flip-flop FF2
and another input terminal connected to output terminal of the flip-flop FF3.
The gate XOR31 has one input terminal which receives the signal generated
20 by the gate OR31 and has another input terminal which is coupled to output
terminal of the flip-flop FF4 to detect the current state of its data bi~
Accordingly, the logic circuitry produces an output signal as follows:
a4 (t) XOR [a3 (t) OR a2 (t)]
where, a2 (t), a3 (t) and a4 (t) represent the current states of the fli~flops
25 F~2, FF3, and FF4, respectively, at the time step number t of circuit
operation. This logic signal is applied to the input terminal of the flip-flop
FF3 when the automaton is operated as a pseudorandom data generator.
1;;~777S9
The cell 3 has signal gating circuitry which deterrnines what
signal is actually applied to input terminal of the associated fli~flop FF3.
This gating circuitry applies particular signals in response to the logic levels of
control lines Cl, C2 and the logic levels of the input terrninals Tl-T8, The
5 signal gating circuitry includes a multiplexer M3 which receives the logic
signal generated by the gate OR31 and the gate XOR31 and the state signal of
adjacent cell 2. The multiplexer M3 is controlled by the control line Cl, and
provides at its output terminal the logic signal if the control line Cl is at a
logic one, and the current state signal of the adjacent cell 2 if the control line
10 Cl is at a logic zero, The signal gating circuitry also includes an AND gate
AND3, an OR gate OR32, and an EXCLUSIVE OR gate XOR32. The gate
AND3 has one input terminal coupled to control line Cl and another input
terminal coupled to the data input tçnninal T3 to receive data bits applied
thereto, The gate OR32 has one input terminal coupled to control line C2 and
15 another to the output terminal of the multiplexer M3. The output signals
generated by the gate OR32 and the gate AND 3 are received by the gate XOR
32, The output terminal of XOR32 is coupled directly to input terminal
associated with fli~flop FF3.
The operation of the cell 3 which is typical is best understood
20 by considering various operating states for the control lines Cl, C2.
If the control lines Cl, C2 are both at logic zero values, the
cells 1-8 of the automaton are configured to operate as a simple shift register.In the cell 3, for exarnple, the output t~}ninal of the gate AND3 is fL1~ed at alogic zero, In response to the logic zero value of the control line Cl, ~}e
25 multiplexer M3 simply passes the state value of the fli~flop FF2 of the
adjacent cell 2, Since each of the gates OR32 and XOR32 has one of its
terminals fixed at a logic zero, each simply passes the current logic state of the
1~777~3
preceding flip-flop FF2, which is applied to the input terminal of the fli~flop
FF3. Accordingly, upon application of a clock pulse to the fli~flops of the
various cells, the fli~flop FF3 assumes the logic state of the adjacent
flip-flop FF2 Accordingly, in this mode of operation, data bits are simply
S transmitted serially between the flip-flops 1-8 of the various cells.
When the control lines Cl and C2 are both set to logic high
values, the automaton is configured to operate as a conventional data latch.
With respect to the cell 3, it will be noted that the gate AND3 has one input
terminal at the logic one associated with the control line Cl and consequently
10 passes the data bit received at the data input terminal T3. Since the gate OR32
has one tenninal fixed at a logic one, its output terminal is fixed at a logic one
value and no data from the multiplexer M3 is passed by the gate OR32.
Since one input terminal of the gatc XOR32 is at a logic one, it acts as an
inverter, inverting the state value of the data bit received at the input terminal
15 T3. With the next system clock pulse, that inverted value of the data bit is
recorded in the cell 3.
If the control terminal Cl is set to a logic one and the control
terminal C2 to a logic zero, and an eight-bit data signal is applied to the input
terminals Tl-T8, the automaton operates as a signature analyur. In the cell 3,
20 for example, because the control line Cl is set at a logic one state, the
multiplexer M3 pasæs the logic signal generated by the gate XOR31. The
logic signal is in turn simply passed by the gate OR32, which has one input
terminal fixed at the logic zero value associated with the control line C2. The
gate AND3, which has one input terminal fixed at the logic one value
25 associated with the control line Cl, sirnply passes the data bit received at the
data input terminal T3. Accordingly, gate XOR32 produces and applies to
'~
7~3
the input terminal of the flip-flop FF3 a signal which corresponds to the
binary addition of the received data bit and the }ogic signal generated at the
output terminal of the gate XOR31 in response to the current states of the
flip-flop PP3 and its associated adjacent flip-flops 2, 4. Accordingly, after a
5 predetermined number of clock pulses, data bits which have been applied to
the input terminals Tl-T8 during the clock pulses are compressed into a
unique 8-bit signature which is stored in the cells 1-8.
If the control tenninal Cl is set to a logic one and the control
terminal C2 to a logical zero, as in the signature analyzing mode described
10 above, and the input terminals Tl-T8 are maintained at constant logic values,the automaton functions as a random data generator. It will be assumed that
the logic states of each of the input terminals Tl-T8is maintained at a logic
zero. With respect to the cell 3, the principal difference in cell operation from
signal analyzer operation is tbat the gate XOR 32 simply passes whatever
15 signal is otherwise transmitted by the multiplexer M3 and the gate OR32. In
such circumstances, the gate OR31 and the gate XOR31 associated with the
cell 3 effectively apply the logic signal derived from the current states of thefli~flop PF3 and adjacent fli~flops 2, 4 to the input tenninal of the flip-flop
FP3, and the current value of tbe logic signal is adopted by the flip-flop PF3
20 at the next clock pulse. With repeated clocking of the cells 1-8, a series ofpseudorandom numbers is generated at the output tenninals of the associated
flip-flops 1-8.
Several advantages of the automaton over prior devices
incorporating shift registers wi~h feedback logic gates should be noted. First,
25 cornmunication is local, being restricted to a particular cell and its irnmediately
adjacent cells. The basic cell structure consequently constitutes a building
block which can be used to immediately design an automaton of any desired
~.~77769
cell size without the need to determine where feedback taps rnight be required.
Second, because feedback taps characteristic of prior shift register based
BILBO's is not required, routing of conductors and components is markedly
simplified, especially in respect of devices having a large number of cells.
Another aspect of the configuration of the automaton should be
noted. It is not critical for purposes of generating pseudorandom data that the
terminals Al and B 1 be connected and that the terrninal A2 and B2 be
connected. If the terrninals Al, Bl are maintained at constant logic values,
and the control and input signals applied to the automaton are appropriately setfor random data generation, it is fully expected that the automaton will
generate useful random dat~ sequences, although a complete ring
configuration is preferred for such purposes. Such end conditions are
expected to have less impact on random data generation as the number of cells
in an automaton embodying the invention is increased.
Reference is made to fig. 2 which illustrates a typical
application for the automaton. In fig. 2 a circuit module 10 is shown
connected to a data bus 12. The module 10 may be seen to comprise a circuit
14 which may be a RAM, ROM, ALU or other digital device and to comprise
two cellular automata 16, 18 substantially identical to the automaton illustrated
in fig. 1. In normal operation, the automaton 16 may serve as a latch for
input of digital data from the bus 12 to the circuit 14, while the automaton 18
serves as an output latch for transfer of digital data to the bus 12. In self-
testing of the circuit 14, the automaton 16 may be conditioned with
appropriate control signals, as described above, to function as a random data
generator, applying a stream of random binary numbers to the input terminals
associated with the circuit 14. The automaton 18 may be simultaneously
conditioned to operate as a signature analyzer, compressing the digital signals
12777~
produced by the circuit 14 in response to the random binary data into an 8-bit
signature. The signature can then be transmitted to a processor for
companson with a stored expected signature and for determination of circuit
faults. The overall configuration of the self-testing module 10 of fig. 2 is
S standard, and the general operation of the automata 10, 12 in such
applications will be understood by persons skilled in the art.
Although the automaton has been described herein largely in the
context of self-testing circuits, an important area of application, it should benoted that the one of the more significant aspects of the automaton is its ability
10 to generate random numbers. In thatregard, the cells of the automaton might
be stripped of much of their signal gating circuitry so that the automaton
functions solely as a random data generator. So adapted, the automaton is
expected to provide a high-speed alt~native to software-based random
number generating routines,
It will be appreciated that a particular embodiment of the
invention has been described in a specific context to illustrate the principles
inherent in the invention. Accordingly, the specific teachings herein should
not be regarded as necessarily limiting the spirit of the invention or the scopeof the appended claims.
