Patent ID: 11907682
Assignee: COMMISSARIAT A L'ENERGIE ATOMIQUE ET AUX ENERGIES ALTERNATIVES
Field: Digital communication (Electrical engineering)
Classification: CPC G  H | IPC G

Claim 9:
10. A method for generating a discrete random number, this random number being coded on Nk 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 Nk bits, each probability F(k) being coded on NF bits, the number NF being higher than the number Nk and lower than or equal to a number Nr,
a step of generating random numbers each coded on Nr bits and drawn according to a uniform distribution, the number Nr being a positive integer number higher than or equal to the number Nk, 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 Nr 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 rmsb coded only on Nmsb bits, the only sample k for which, whatever a number rlsb belonging to an interval [0; 2Nr−Nmsb−1], the following condition is met: F(k−1)<(rmsb, rlsb)≤F(k), where:
(rmsb, rlsb) is the binary number coded on Nr bits and the Nmsb most significant bits of which are equal to the Nmsb bits of the truncated random number rmsb and the (Nr−Nmsb) least significant bits of which are equal to the (Nr−Nmsb) bits of the number rlsb,
Nmsb is a positive integer number lower than Nr,
a fast-sampling step, this step comprising:
receiving the Nmsb most significant bits of the random number r generated by the generator, these Nmsb bits forming a received truncated random number rmsb,
in response, searching for this received truncated random number rmsb 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 rmsb, 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 Nmsb most significant bits of which are equal to the truncated random number rmsb 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 Nmsb bits of the random number r generated at the start of this new sampling interval, with this new activated fast sampler.