Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-12-12
2004-06-15
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S255000
Reexamination Certificate
active
06751639
ABSTRACT:
This invention relates to a method and apparatus for generating a non-repeating sequence of numbers, and particularly but not exclusively uncorrelated random numbers distributed uniformly over a specified interval.
Random numbers uniformly distributed over a set of integers {0, 1, . . . , 2
N−1
} are required for stochastic simulation and also for spread-spectrum communications and radar. It is particularly desirable to provide truly random numbers in contrast to pseudorandom numbers that can be generated in accordance with the many existing techniques.
It is known that the use of random numbers as frequency-hopping patterns (codes) in radar results in low probability of intercept and enhanced resistance to intelligent jamming. Furthermore, when random numbers are subjected to suitable digital-to-analogue conversion, the resulting signals can be utilized for modulating radar transmissions, thereby providing radar waveforms with maximum unpredictability. Random waveforms are also useful for applications in multiuser environments where many similar or disparate systems operate in the same geographical region and those systems share, at least partly, the same wide frequency band.
Several classes of methods are known to generate truly random numbers by exploiting various physical phenomena such as thermal or avalanche noise, gaseous discharge, particle-induced scintillation, phase fluctuation of harmonic oscillators, etc.
The best known method for generating truly random numbers is based on converting a random signal produced by a physical noise source into a random binary waveform with two equiprobable values. Next the binary waveform is suitably sampled to yield a sequence of independent random bits occurring with equal probabilities. Random N-bit numbers with uniform distribution are then formed from this sequence by using different nonoverlapping sub-sequences of length N. In order to obtain a fast random number generator, N independent sequences of random bits may be utilized in a parallel scheme.
Because of inherent instabilities of physical noise sources and associated electronic circuits, it is not possible in practice to produce random binary sequences with equiprobable bits. Accordingly, numbers formed from such sequences will not be uniformly distributed. This results in inefficient use of frequency bands in communications and radar systems, increased predictability and other disadvantages.
To overcome this problem, various solutions have been proposed: either by incorporating a suitable stabilising feedback loop or by exploiting a ‘divide-by-two’ operation to obtain equiprobable bits. Although the technique employing a ‘divide-by-two’ operation can produce equiprobable bits, in general those bits may be correlated.
Another example of an implementation of a random number generator is the T7001 Random Number Generator chip, manufactured by AT&T. The principle of operation is based on the phase jitter of a free-running oscillator. As a result, the output bit stream is truly random, not pseudorandom. However, the output data rate is not sufficient for high-frequency operation.
It would, accordingly, be desirable to provide an apparatus and method for the generation of truly random numbers with uniform distribution suitable for spread-spectrum radar and other applications.
It would also be desirable to provide an apparatus and method for the generation of truly random numbers to yield frequency-hopping patterns and other suitable waveforms which are intended for application in multiuser environments, and/or are resistant to deliberate intelligent jamming, and/or have a low probability of detection and intercept.
It would also be desirable to provide a method and apparatus for generating a non-repeating sequence of uniformly-distributed numbers. Such numbers would be useful, for example, in the production of uncorrelated random numbers distributed uniformly over a specified interval, intended for example for simulation or other purposes.
Aspects of the present invention are set out in the accompanying claims.
According to a preferred embodiment of the invention, a truly random primary binary sequence, not necessarily with equiprobable bits, is generated. The bits of this sequence are manipulated in such a way as to obtain a plurality of uncorrelated binary sets with equiprobable bits. Uncorrelated chaotic N-bit binary numbers with uniform distribution are formed from those sets by suitably selecting subsets comprising N bits. The operational procedure employed for manipulating bits of a primary binary sequence is based on the chaotic behaviour of the so-called “tent” map, widely explored in chaos theory, resulting from a procedure known as “stretching and folding” to produce successive values. This operational procedure is implemented in an embodiment of the invention by a hybrid chaos generator.
Preferably, a truly random auxiliary binary sequence, not necessarily with equiprobable bits, is also generated. Each of the generated N-bit uncorrelated chaotic numbers and N bits suitably selected from this auxiliary sequence are XOR'ed bit by bit to obtain a resulting truly random N-bit binary number with uniform distribution and also with maximum unpredictability. Thus all the functions and operations required to achieve maximum unpredictability of generated numbers are implemented by a randomisation subsystem which operates on the chaotic numbers.
In an embodiment of the present invention, both the primary binary sequence and the auxiliary binary sequence are obtained from a single physical noise source.
As indicated above, the operational procedure for manipulating the bits of the preliminary binary sequence to obtain sets of equiprobable bits may be based on the tent map, the simplest form of which, shown in
FIG. 1
, is given by
T
(
v
)
=
{
2
v
,
0
<
v
≤
1
/
2
2
(
1
-
v
)
,
1
/
2
<
v
<
1
(
1
)
It is well known that a sequence of numbers, generated according to
v
k+1
=T
(
v
k
),
k
=0, 1, . . . (2)
will be infinite and nonrepeating with uniform distribution over the unit (0,1)-interval, if the initial value v
0
has been suitably selected. Furthermore, the autocorrelation function of this sequence will be zero for all non-zero shifts. For example, an infinite and nonrepeating sequence {v
k
; k=0, 1, . . . } can be obtained when the initial value v
0
is an irrational (or a transcendental) number.
Although the chaotic behaviour of sequences generated by the tent map T(v) can be observed experimentally in analogue electronic circuits, any attempt to generate such infinite and nonrepeating sequences digitally will fail because irrational numbers cannot be represented by finite binary numbers. As a result, a sequence of numbers generated by a digital implementation of equation (2) will be either periodic or it will quickly iterate to zero.
However, according to a preferred aspect of the present invention an infinite sequence of bits (the primary binary sequence) required to represent a suitable initial value v
0
is supplied, bit by bit, by a generator producing random, but not necessarily equiprobable, bits. Those bits are utilized sequentially by a finite-length shift register with suitable feedback arranged in such a way as to implement equation (2) governing the generation of a chaotic sequence. This technique is also applicable to other schemes employed to produce infinite and non-repeating chaotic sequences.
REFERENCES:
patent: 4513386 (1985-04-01), Glazer
patent: 4903266 (1990-02-01), Hack
patent: 4905176 (1990-02-01), Schulz
patent: 5251165 (1993-10-01), James, III
patent: 5706218 (1998-01-01), Hoffman
patent: 5961577 (1999-10-01), Soenen et al.
patent: 2 113 879 (1983-08-01), None
Malzahn David H.
Mitsubishi Denki & Kabushiki Kaisha
LandOfFree
Method and apparatus for generating numbers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating numbers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating numbers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318334