Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-05-05
2003-09-30
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S253000
Reexamination Certificate
active
06629116
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention generally relates to random sequence generators, and more particularly to cellular automaton devices for generating random sequence signals.
Random sequence generators have been used to generate random sequence signals in many applications. For example, they are used for generating random sequence signals in implementing randomized algorithms in computers. They are also used for generating instruction sequences for self-testing of microcontrollers, encryption in smart cards, and dithering in image processing.
A conventional random sequence generator in the form of linear cellular automaton device is schematically illustrated in FIG.
1
.
FIG. 2
shows an equivalent functional block diagram of the embodiment in FIG.
1
. In
FIG. 1
, a plurality of linear cellular automatons or cells
10
are inter-connected to one another. Each cell
10
may optionally receive a one-bit input
12
from data and address busses and generates a one-bit output
14
. Outputs
14
are loaded into an instruction register (not shown) as pseudo-random instruction sequences for use, for example, in self-testing of microcontrollers.
In each cell
10
, a storage element
22
, such as a flip-flop, stores a current value of output
14
for use to generate a next value of the output and for providing to adjacent cells
10
as input
32
. Storage element
22
is connected to an exclusive-OR gate
24
via a control gate
26
, which controls whether to allow the current value of output
14
to pass through control gate
26
for inputting to an exclusive-OR gate
24
. For example, if control gate
26
has a coefficient k
n
equal to 1, the current value of output
14
is allowed to pass through the control gate. However, if the coefficient k
n
is equal to 0, the current value of output
14
cannot pass through control gate
26
. The coefficient values (k
n
, k
n+1
, k
n+2
, are determined from a mathematical lookup table which is well known in the art. For example, the coefficients are described in “Minimal Cost One-Dimensional Linear Hybrid Cellular Automata of Degree Through 500”, Journal of Electronic Testing: Theory and Applications, 6,255-258 (1995), by Kevin Cattell and Shujian Zhang, the disclosure of which is hereby incorporated by reference.
Exclusive-OR gate
24
receives additional inputs
32
from adjacent cells
10
. Inputs
32
are the current output values of adjacent cells
10
. All of the inputs at gate
24
are exclusive-ORed and the result is the next value of output
14
. Thus, the next value of output
14
is determined based on the combination of its current value, inputs
32
from adjacent cells and optional input
12
.
In a specific example shown in
FIG. 3
, a linear cellular automaton device
40
that comprises a group of
24
cells
10
, i.e., having a 24-bit length, is used to generate pseudo-random instruction sequences. In this example, it is assumed that the instruction width is 8 bit and optional inputs
12
are not provided.
Cellular automaton device
40
is organized into three byte sections: byte
1
, byte
2
and byte
3
, which are inter-connected to one another. Each byte section includes
8
cells
10
, which are also inter-connected to one another. Cellular automaton device
40
generates 8-bit output sequences B
1
, B
2
and B
3
, which may be loaded into an instruction register (not shown). The output sequences B
1
, B
2
and B
3
of cellular automaton device
40
are supposed to provide sufficient randomness for use in various applications. However, the randomness of these sequences is very limited, as will be illustrated
FIGS. 4A-4C
.
FIG. 4A
shows that the next state of output B
1
for byte
1
is one of two possible states B
1-1
and B
2-2
. The next state of output B
1
is determined based on its current state and the input value received from adjacent byte
2
, which is either bit
0
or
1
, as illustrated in FIG.
3
. For example, if the input value from byte
2
is
0
, the next state of output B
1
is B
1-1
. On the other hand, if the input value from byte
2
is
1
, the next state of output B
1
is B
1-2
. Each of the next possible states B
1-1
and B
1-2
may have 256 values.
Similarly,
FIG. 4B
shows that the next state of output B
2
for byte
2
is one of four possible states B
2-1
, B
2-2
, B
2-3
and B
2-4
.
FIG. 4C
shows that the next state of output B
3
for byte
3
is one of two possible states B
3-1
and B
3-2
.
As can be seen from the above, only a limited number of states can be generated by cellular automaton-device
40
due to the insufficient connections between the byte sections. As a result, the sequences generated do not provide sufficient randomness such that use of these sequences will inevitably result in inefficiencies and errors and could even cause serious security problems if used for encryption purposes.
Another conventional random sequence generator with similar problems is described in U.S. Pat. No. 4,691,291 issued to Wolfram on Sep. 1, 1987, which is hereby incorporated by reference.
Thus, there is a need for a random sequence generator that can generate a large number of states that provide sufficient randomness for a variety of applications.
SUMMARY OF THE INVENTION
The present invention provides a random sequence generator for generating an output signal having random values. The generator comprises a plurality of cells inter-connected to one another such that each cell receives, as an input, an output from each cell connected thereto and generates a cell output based on a current value of the cell output and each cell output received. The plurality of cells include k subsets each subset including n cells. A pre-selected cell from each of the k subsets generates an output and the output of the k pre-selected cells is provided as the output signal of the generator. In a specific embodiment, each of the cells is a linear cellular automaton, with k being an instruction width and k*n being an instruction length.
The invention is particularly suitable for internal self-testing of a micrbcontroller in a smart card. This eliminates the need for external test contacts and thus prevents potential break-ins through the external contacts.
The invention also provides a method for generating an output signal having random values from a plurality of inter-connected cells. The method comprises the steps of: (a) arranging the plurality of cells in k subsets, each subset including n cells; (b) applying to each of the cells, as an input, an output from each cell connected thereto; (c) generating a cell output from each of the cells based on a current value of the cell output and each cell output received; (d) extracting an output from a pre-selected cell of each of the k subsets; and (e) providing the output of the k pre-selected cells as the output signal.
By using the present invention, a huge number of sequences can be generated, thus providing tremendous amount of randomness for a wide range of applications.
Other objects and attainments together with a fuller understanding of the invention will become apparent and appreciated by referring to the following description and claims taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 3885139 (1975-05-01), Hurd
patent: 4691291 (1987-09-01), Wolfram
patent: 4961159 (1990-10-01), McLeod et al.
patent: 5224165 (1993-06-01), Reinhardt et al.
patent: 5257282 (1993-10-01), Adkisson et al.
patent: 5331581 (1994-07-01), Ohkubo et al.
patent: 5754762 (1998-05-01), Kuo et al.
patent: 4139151 (1993-06-01), None
patent: 0075713 (1983-04-01), None
patent: 0333153 (1989-09-01), None
“Minimal Cost One-Dimensional Linear Hybrid Cellular Automata of Degree Through 500”, by K. Cattell et al., Journal of Electronic Testing: Theory and Applications 6,255-258 (1995).
Koninklijke Philips Electronics , N.V.
Ngo Chuong Dinh
Schmitt Michael
LandOfFree
Random sequence generators does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Random sequence generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random sequence generators will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3046085