Device and method for generating a random number drawn according to a nonuniform distribution

1. A device for generating a discrete random number, this random number being coded on N k bits and drawn according to a nonuniform, discrete and bounded probability distribution ρ, this device comprising:

a microprocessor configured to implement

a generator of random numbers that are coded on N r bits and drawn according to a uniform distribution, the number N r being a positive integer number higher than or equal to the number N k ,

a slow sampler comprising:

a complete table associating, with each possible probability F(k) of the cumulative probability density F of the distribution ρ, the corresponding sample k coded on N k bits, each probability F(k) being coded on N F bits, the number N F being higher than the number N k and lower than or equal to the number N r ,

a first searching module able:

to receive the N r bits of a random number r generated by the generator,

in response, to select, from the complete table, the only probability F(k) such that F(k−1)<r≤F(k), then

to transmit the sample k, associated by the complete table with the selected probability F(k), of as the discrete random number drawn according to the distribution ρ,

a fast sampler (ER i ) comprising:

a truncated table, which is smaller than the complete table, associating with truncated random numbers r msb coded only on N msb bits, the only sample k for which, whatever a number r lsb belonging to an interval [0; 2 Nr−Nmsb −1], the following condition is met: F(k−1)<(r msb , r lsb )≤F(k), where:

(r msb , r lsb ) is the binary number coded on N r bits and the N msb most significant bits of which are equal to the N msb bits of a truncated random number r msb and the (N r −N msb ) least significant bits of which are equal to the (N r −N msb ) bits of the number r lsb ,

N msb is a positive integer number lower than N r ,

a second searching module able:

to acquire the N msb most significant bits of the random number r generated by the generator, these N msb bits forming a received truncated random number r msb ,

in response, to search for the received truncated random number r msb in the truncated table, and

if the search is successful, to transmit the sample k, associated, by the truncated table, with the received truncated random number r msb , as the discrete random number drawn according to the distribution ρ, and, alternatively, if the search is unsuccessful, to send a failure signal, and

the slow sampler is able to:

receive the failure signal and the random number r generated by the generator and the N msb most significant bits of which are equal to the truncated random number r msb that led to this failure signal being sent, then

in response, to select, using the complete table, and to transmit the only sample k that meets the condition F(k−1)<r≤F(k) and that was unable to be transmitted by the fast sampler,

the generator is able to generate a new random number r at the start of each sampling interval, these sampling intervals being repeated periodically,

wherein the device comprises:

a plurality of fast samplers each able to work in parallel with the other fast samplers and in parallel with the slow sampler, and

an arbitrating module able to activate, on each new sampling interval, a new fast sampler different from the fast sampler activated in the preceding sampling interval, to process the N msb bits of the random number r generated at the start of this new sampling interval, with this new activated fast sampler.

2. The device as claimed in claim 1 , wherein the slow sampler is able, for each of the fast samplers, to receive:

the failure signal generated by this fast sampler, and

the random number r that led to the generation of this failure signal.

3. The device as claimed in claim 1 , wherein:

the device comprises a memory able:

to receive and to store each transmitted sample k, and

to deliver as output from the device, at the end of each sampling interval and provided that there are samples k stored in this memory, the oldest stored sample k.

4. The device as claimed in claim 3 , wherein:

the number of fast samplers is comprised between three and five,

the size of the memory allows at most T MF samples k to be stored, where the number T MF is comprised between eight and sixteen, and

the number N msb is comprised between four and six.

5. The device as claimed in claim 1 , wherein the number N msb is five times smaller than the number N r .

6. The device as claimed in claim 1 , wherein the number N r is a positive integer number at least two or four times higher than the number N k .

7. The device as claimed in claim 1 , wherein the generator is able to firstly generate the N msb bits of the random number r and, the fast sampler is able to inhibit the generation, by the generator, of the (N r −N msb ) bits following the random number r each time the search in the truncated table is successful.

8. The device as claimed in claim 1 , wherein:

the truncated table contains 2 Nmsb−s cells ordered in order of increasing index, where s is a positive or zero integer number lower than N msb , each sample k associated, by the truncated table, with a corresponding truncated random number r msb comprised between 0 and 2 Nmsb−s −1 being stored in the cell the index of which is equal to this corresponding truncated random number r msb , the other cells that contain no sample k containing a failure symbol different from all the samples k, and

the second searching module is able to directly read the content of the cell in the truncated table the index of which is equal to the received truncated random number r msb searched for in this truncated table and, when the read content is a sample k, to transmit this sample k, and when the read content is the failure symbol, to send the failure signal.

9. The device as claimed in claim 1 , wherein the distribution ρ is a discrete and bounded Gaussian probability distribution.

10. A method for generating a discrete random number, this random number being coded on N k bits and drawn according to a nonuniform, discrete and bounded probability distribution ρ, this method comprising:

a step of providing a complete table associating, with each possible probability F(k) of the cumulative probability density F of the distribution ρ, the corresponding sample k coded on N k bits, each probability F(k) being coded on N F bits, the number N F being higher than the number N k and lower than or equal to a number N r ,

a step of generating random numbers each coded on N r bits and drawn according to a uniform distribution, the number N r being a positive integer number higher than or equal to the number N k , this generating step comprising the generation of a new random number r at the start of each sampling interval, these sampling intervals being repeated periodically,

a slow-sampling step, this step comprising:

receiving the N r bits of a random number r generated by the generator,

in response, selecting, from the complete table, the only probability F(k) such that F(k−1)<r≤F(k), then

transmitting the sample k, associated by the complete table with the selected probability F(k), as the discrete random number drawn according to the distribution ρ,

providing a truncated table, which is smaller than the complete table, associating with truncated random numbers r msb coded only on N msb bits, the only sample k for which, whatever a number r lsb belonging to an interval [0; 2 Nr−Nmsb −1], the following condition is met: F(k−1)<(r msb , r lsb )≤F(k), where:

(r msb , r lsb ) is the binary number coded on N r bits and the N msb most significant bits of which are equal to the N msb bits of the truncated random number r msb and the (N r −N msb ) least significant bits of which are equal to the (N r −N msb ) bits of the number r lsb ,

N msb is a positive integer number lower than N r ,

a fast-sampling step, this step comprising:

receiving the N msb most significant bits of the random number r generated by the generator, these N msb bits forming a received truncated random number r msb ,

in response, searching for this received truncated random number r msb in the truncated table, and

if the search is successful, transmitting the sample k, associated, by the truncated table, with the received truncated random number r msb , as the discrete random number drawn according to the distribution ρ, and, alternatively, if the search is unsuccessful, sending a failure signal, then

in response to the reception of the failure signal and of the random number r generated by the generator and the N msb most significant bits of which are equal to the truncated random number r msb that led to this failure signal being sent, triggering the execution of the slow-sampling step with a view to selecting, using the complete table, and transmitting the only sample k that meets the condition F(k−1)<r≤F(k) and that was unable to be transmitted at the end of the fast-sampling phase,

wherein the method comprises:

providing a plurality of fast samplers each able to work in parallel with the other fast samplers and in parallel with the slow sampler, and

activating, on each new sampling interval, a new fast sampler different from the fast sampler activated in the preceding sampling interval, to process the N msb bits of the random number r generated at the start of this new sampling interval, with this new activated fast sampler.

11. A non-transitory data-storage medium that is readable by a microprocessor, wherein this medium comprises instructions for executing a method as claimed in claim 10 , when these instructions are executed by the microprocessor.