Apparatus and method for generating a random number

• US 20050286718A1
• Filed: 10/29/2004
• Published: 12/29/2005
• Est. Priority Date: 04/29/2002
• Status: Active Grant

• Current Assignee: Infineon Technologies AG
• Original Assignee: Infineon Technologies AG
• Inventors: Meintrup, David, Stromberg, Guido, Stoehr, Annelie, Sturm, Thomas
• Granted Patent: US 7,647,366 B2
• Time in Patent Office: Days
• US Class Current: 380/46
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

Apparatus for generating a random number includes a sampler that samples a noise signal to obtain a noise signal sample, and a provider that provides at least three noise signal threshold values selected such that a first probability of the noise signal sample being between the first and second threshold values, and a second probability of the noise signal sample being between the second and third threshold values are different from each other by less than a predetermined differential value or are identical. An outputter outputs the random number such that when the noise signal sample is between the first and second threshold values, a first digit of a random number is occupied by a first logical state, whereas a second digit is occupied with a different logical state, so that a random number which is at least 2 bits wide results from one noise signal sample.

Claims

1. An apparatus for generating a random number, comprising:

a sampler that samples a noise signal so as to obtain a noise signal sample;

a provider that provides at least three noise signal threshold values, the at least three noise signal threshold values being selected such that a first probability of the noise signal sample being between the first and second noise signal threshold values, and a second probability of the noise signal sample being between the second and third noise signal threshold values are different from each other by less than a predetermined differential value or are identical; and

an outputter that outputs the random number having at least two digits which depend on the noise signal sample, wherein, if the noise signal sample is between the first and second noise signal threshold values, a first digit of the random number obtains a first state, and a second digit of the random number, representing a range between the second noise signal threshold value and the third noise signal threshold value, obtains a second state which differs from the first state,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the provider is configured to specify the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

2. The apparatus as claimed in claim 1,

wherein the outputter that outputs the random number comprises at least one threshold-value gate x₁ into which the noise signal sample may be fed and by which the first or second digits of the random number may be determined depending on whether the noise signal sample exceeds or falls below the second threshold value.

3. The apparatus as claimed in claim 1,

wherein the provider is configured to provide at least four noise signal threshold values, a smallest noise signal threshold value being a minimum noise signal sample determined by a predetermined minimum probability,

wherein a highest noise signal threshold value is a maximum noise signal sample determined by a predetermined maximum probability, and

wherein the at least two remaining noise signal threshold values are between the smallest and highest noise signal threshold values.

4. The apparatus as claimed in claim 3,

wherein each of the at least two remaining noise signal threshold values has a threshold-value gate of its own provided for it, a specific digit of the random number being determinable by each threshold-value gate, the logical state of each digit of the random number depending on whether the noise signal sample falls below or exceeds the threshold value associated with the respective threshold-value gate.

5. The apparatus as claimed in claim 4,

wherein at least three remaining noise signal threshold values are present, and which further comprises:

an encoder that encodes the random number so as to obtain an encoded random number having a smaller redundancy than the random number.

6. The apparatus as claimed in claim 5,

wherein the random number and the encoded random number are binary, and the first state is a first binary state, and the second state is a second binary state differing from the first binary state.

7. The apparatus as claimed in claim 6,

wherein the encoder comprises a table, by means of which an encoded random number is uniquely associated with a random number, the encoded random number comprising fewer digits than the random number.

8. The apparatus as claimed in claim 6,

wherein the encoder is configured to implement the following logical equation:

$\begin{array}{cc}{y}_{n-i}=\underset{q<br><br>{=}^{2<br><br>{\left(n-1\right)}_{\pm <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}\pm <br><br>2}<br><br>\left(n-i\right)}<br><br>-1}{\oplus <br><br>}<br><br>{\hat{x}}_{q^{\mathrm{\prime <br><br>}}}<br><br>\text{\hspace{1em}<br><br>}<br><br>i=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n& \left(2\right)\end{array}$

wherein {circumflex over (x)}_q is a digit of the random number with an index q,

wherein y_n-i is a digit of the encoded random number with an index;

wherein n is the number of digits of the encoded random number;

wherein i is a control valuable running from 1 to n, and

wherein ⊕

is a modulo-2 addition of the digits x_q which are calculated by means of the following equation;

q=2<sup>(n−

1)</sup>±

. . . ±

2<sup>(n−

i)</sup>−

1.

9. The apparatus as claimed in claim 1,

wherein the provider that provides the at least three threshold values comprises:

a monitor that monitors the noise signal samples, the noise signal, or the random number;

a transmitter that transmits a statistical distribution of a monitored variable; and

an adapter that adapts the noise signal threshold values so as to reduce a deviation between the first and second probabilities.

10. The apparatus as claimed in claim 5,

wherein the provider that provides the at least three threshold values comprises:

a monitor that monitors the encoded random numbers;

a transmitter that transmits a statistical distribution of the encoded random numbers; and

an adapter that adapts the noise signal threshold values so as to reduce a deviation between the first and second probabilities.

11. The apparatus as claimed in claim 9,

wherein the monitor comprises a memory having a sequence of memory cells arranged in an ascending order,

wherein noise signal values or noise signal samples may be sorted into the memory cell sequence depending on their magnitude,

wherein the provider is configured to read out memory cells with equally spaced-apart ordinal numbers, each threshold value being assigned a memory cell to be read out, and

wherein the provider is further configured to set a noise signal threshold value to a value stored in the memory cell with the ordinal number associated with the noise signal threshold value.

12. The apparatus as claimed in claim 11, wherein re-setting of a noise signal threshold value may be performed in an event of a predetermined deviation, at a predetermined point in time or in connection with a detection of a new noise signal sample.

13. The apparatus as claimed in claim 1,

wherein the provider is configured

to detect a noise value defined by the noise signal sample,

to ascertain whether the noise value is higher or smaller than one of the noise signal threshold values,

to perform an incrementation of the noise signal threshold value by an incrementation value in an event that a “

higher”

condition has been ascertained, or to perform a decrementation of the noise signal threshold value by a decrementation value in the event that a “

smaller”

condition has been ascertained, and to use the incremented and/or decremented noise signal threshold value as an adapted noise signal threshold value.

14. The apparatus as claimed in claim 13,

wherein an adapted noise signal threshold value is formed using several iteration steps, the incrementation or decrementation value being reduced with each iteration step, and

wherein the incrementation or decrementation value is re-set to the initial value after a predetermined number of iteration steps.

15. A method for generating a random number, comprising the steps of:

sampling a noise signal so as to obtain a noise signal sample;

providing at least three noise signal threshold values, the at least three noise signal threshold values being selected such that a first probability of the noise signal sample being between the first and second noise signal threshold values, and a second probability of the noise signal sample being between the second and third noise signal threshold values are different from each other by less than a predetermined differential value or are identical; and

outputting the random number having at least two digits which depend on the noise signal sample, wherein, if the noise signal sample is between the first and second noise signal threshold values, a first digit of the random number obtains a first state, and a second digit of the random number, representing a range between the second noise signal threshold value and the third noise signal threshold value, obtains a second state which differs from the first state,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the step of providing includes specifying the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

16. An apparatus for generating a binary random number, comprising:

a sampler that samples a noise signal to obtain a noise signal sample;

a provider that provides at least 2ⁿ+1 noise signal threshold values, n being higher than or equal to 2, wherein the noise signal threshold values define 2ⁿ ranges for a noise signal sample, the 2ⁿ+1 noise signal threshold values being selected such that probabilities of the noise signal sample being in one of the 2ⁿ ranges differ from each other by less than a predetermined differential value or are identical; and

an outputter that outputs the binary random number having n bits which depend on the noise signal sample, the n bits of the binary random number being determined such that each bit combination of the n bits of the binary random number is uniquely associated with one of the 2ⁿ ranges,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the provider is configured to specify the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

17. The apparatus as claimed in claim 16, wherein the provider that provides the noise signal threshold values is configured to adaptively track the noise signal threshold values.

18. A method for generating a binary random number, comprising the steps of:

sampling a noise signal to obtain a noise signal sample;

providing at least 2ⁿ+1 noise signal threshold values, n being higher than or equal to 2, wherein the noise signal threshold values define 2ⁿ ranges for a noise signal sample, the 2ⁿ+1 noise signal threshold values being selected such that probabilities of the noise signal sample being in one of the 2ⁿ ranges differ from each other by less than a predetermined differential value or are identical; and

outputting the binary random number having n bits which depend on the noise signal sample, the n bits of the binary random number being determined such that each bit combination of the n bits of the binary random number is uniquely associated with one of the 2ⁿ ranges,

wherein the noise signal has a probability-density function which has been predetermined,

wherein the probability of a noise signal sample being smaller than or equaling a noise signal threshold value is given by the following equation;

$F<br><br>\text{;<br><br>}<br><br>R-><br><br>\left[0,1\right],F<br><br>\left(x\right);<br><br>={\int <br><br>}_{-\mathrm{\infty <br><br>}}^x<br><br>p<br><br>\left(y\right)<br><br>d<br><br>y$

wherein p(y) is the probability-density function of the noise signal,

wherein y is a noise signal threshold value, and

wherein the step of providing includes specifying the noise signal threshold values in accordance with the following equation;

$x_i;<br><br>=F^{-1}<br><br>\left(\frac{i}{2_n}\right),i\in <br><br>\left\{0,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>2^n\right\}$

wherein i is a control variable, wherein F<sup>−

1</sup> is an inverse function of the function F, and wherein x_i is the noise signal threshold value sought.

19. The method as claimed in claim 18, wherein the step of providing includes the step of implementing 2ⁿ⁻

1 threshold-value gates.