Random number generation based on logic circuits with feedback

• US 8,150,900 B2
• Filed: 08/09/2004
• Issued: 04/03/2012
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Telecom Italia S.p.A.
• Original Assignee: Telecom Italia S.p.A.
• Inventors: Golic, Jovan
• Primary Examiner(s): Bullock, Jr., Lewis A
• Assistant Examiner(s): Yaary, Michael D
• Application Number:
  US11/659,715
• Publication Number:
  US 20070273408A1
• Time in Patent Office: 2,794 Days
• Field of Search: None
• US Class Current: 708/250
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

A random binary sequence generator for generating a random binary sequence adapted to be used for producing random numbers, includes at least one logic circuit corresponding to an associated finite-state machine having a state-transition function including states arranged to form cycles of states, wherein the at least one logic circuit has a set of logic circuit inputs and a set of logic circuit outputs fed back to the logic circuit inputs; the associated finite-state machine is autonomous and asynchronous; the state-transition function is void of loops; and any of the cycles of states has either a minimum length equal to three states, in case the cycle is stable, or a minimum length of two states, in case the cycle is meta-stable.

Claims

1. A random binary sequence generator for generating a random binary sequence adapted to be used for producing random numbers, comprising:

at least one logic circuit with a set of logic circuit inputs and a set of logic circuit outputs wherein;

said at least one logic circuit comprises a plurality of asynchronous logic inversion units connected in cascade one to another, respectively;

said plurality of asynchronous logic inversion units comprises a first and a last asynchronous logic inversion unit in the cascade, said set of logic circuit outputs comprising an output of the last asynchronous logic inversion unit and said set of logic circuit inputs comprising an input of the first asynchronous logic inversion unit, said at least one logic circuit comprising a first feedback path from the output of the last asynchronous logic inversion unit to the input of the first asynchronous logic inversion unit;

said at least one logic circuit is operated without a clock signal and autonomously by connecting said logic circuit outputs to said logic circuit inputs; and

said at least one logic circuit implements a set of Boolean functions, each of said logic circuit outputs having a value defined by a respective Boolean function of at least one of said logic circuit inputs, said respective Boolean function belonging to said set of Boolean functions;

and wherein;

said logic circuit outputs represent states of said at least one logic circuit;

said set of Boolean functions forms a state-transition function defining transitions of said states, wherein said states are arranged so as to form at least one cycle of states, said at least one cycle of states having a cycle length equal to a number of states included therein;

said at least one cycle of states has a minimum length equal to two; and

in case the cycle length is two, said at least one cycle of states is meta-stable for said at least one logic circuit operated without a clock signal and autonomously.

2. The random binary sequence generator according to claim 1, wherein the number of said logic circuit inputs is equal to the number of said logic circuit outputs.

3. The random binary sequence generator according to claim 1, wherein in case the at least one cycle of states is a non meta-stable cycle, the minimum cycle length is three.

4. The random binary sequence generator according to claim 1, further comprising at least one output logic circuit operatively connected to at least one of said logic circuit outputs of the at least one logic circuit, the output logic circuit having an output for providing an output signal by implementing an output Boolean function.

5. The random binary sequence generator according to claim 4, wherein said at least one of said logic circuit outputs has a value that is not constant.

6. The random binary sequence generator according to claim 4, further comprising a sampling circuit for sampling said output signal.

7. The random binary sequence generator according to claim 1, wherein said plurality of asynchronous logic inversion units comprises at least one intermediate asynchronous logic inversion unit in the cascade, wherein said at least one logic circuit comprises at least one second feedback path from an output of a respective asynchronous logic inversion unit in the cascade to the input of the first asynchronous logic inversion unit, wherein said respective asynchronous logic inversion unit is chosen from the group of the first asynchronous logic inversion unit and the at least one intermediate asynchronous logic inversion unit.

8. The random binary sequence generator according to claim 7, wherein the at least one logic circuit further comprises an XOR logic combination of the first and the at least one second feedback paths.

9. The random binary sequence generator according to claim 8, wherein said at least one second feedback path comprises a plurality of second feedback paths.

10. The random binary sequence generator according to claim 9, wherein the at least one logic circuit has an associated binary polynomial f(x) defined as:

11. The random binary sequence generator according to claim 1, wherein said plurality of asynchronous logic inversion units comprises at least one intermediate asynchronous logic inversion unit in the cascade, and said at least one logic circuit comprises at least one second feedback path from said output of the last asynchronous logic inversion unit to an input of a respective asynchronous logic inversion unit, said respective asynchronous logic inversion unit being chosen from the group of the at least one intermediate asynchronous logic inversion unit and the last asynchronous logic inversion unit in the cascade.

12. The random binary sequence generator according to claim 11, wherein the at least one logic circuit further comprises an XOR logic combination of said at least one second feedback path and the output of a preceding asynchronous logic inversion unit that precedes said respective asynchronous logic inversion unit where said at least one second feedback path terminates.

13. The random binary sequence generator according to claim 12, wherein said at least one second feedback path comprises a plurality of feedback paths.

14. The random binary sequence generator according to claim 13, wherein the at least one logic circuit has an associated binary polynomial g(x) defined as:

15. The random binary sequence generator according to claim 14, wherein the binary polynomial g(x) satisfies the further condition:

k(1)=1.

16. The random binary sequence generator according to claim 1, wherein each of said asynchronous logic inversion units comprises a predetermined odd number of logic inverters.

17. The random binary sequence generator according to claim 1, wherein the state-transition function is an affine transformation, affine with respect to the binary field.

18. The random binary sequence generator according to claim 17, wherein the generic element of the at least one logic circuit is selected from the group of binary complement elements, binary identity elements and binary addition elements.

19. The random binary sequence generator according to claim 6, wherein the sampling circuit operates according to a timing signal.

20. The random binary sequence generator according to claim 19, wherein the sampling circuit comprises a D-type flip-flop.

21. The random binary sequence generator according to claim 4, wherein said at least one logic circuit comprises at least a first and a second logic circuit having respective output logic circuits operatively connected thereto, the output logic circuits having each a respective output for providing an output signal.

22. The random binary sequence generator according to claim 21, further comprising a combination of the output signals of the output logic circuits for producing a combined output signal.

23. A random number generator comprising the random binary sequence generator according to claim 1, for generating a raw random binary sequence, and a post-processing circuit adapted to be fed with the raw random binary sequence for processing it, so as to produce a purely random binary sequence.

24. A method of generating a random binary sequence adapted for producing random numbers, comprising:

providing at least one logic circuit having a set of logic circuit inputs and a set of logic circuit outputs, wherein;

said at least one logic circuit comprises a plurality of asynchronous logic inversion units connected in cascade one to another, respectively;

said plurality of asynchronous logic inversion units comprises a first and a last asynchronous logic inversion unit in the cascade, said set of logic circuit outputs comprising an output of the last asynchronous logic inversion unit and said set of logic circuit inputs comprising an input of the first asynchronous logic inversion unit, said at least one logic circuit comprising a first feedback path from the output of the last asynchronous logic inversion unit to the input of the first asynchronous logic inversion unit;

the at least one logic circuit implements a set of Boolean functions, each of said logic circuit outputs having a value defined by a respective Boolean function of at least one of said logic circuit inputs, said respective Boolean function belonging to said set of Boolean functions;

said set of Boolean functions forms a state-transition function defining transitions of said states, wherein said states are arranged so as to form at least one cycle of states, the at least one cycle of states having a cycle length equal to a number of states included therein; and

said at least one cycle of states has a minimum length equal to two; and

in case the cycle length is two, said at least one cycle of states is meta-stable for said at least one logic circuit operated without a clock signal and autonomously;

operating the logic circuit autonomously by feeding back the set of logic circuit outputs to said logic circuit inputs; and

operating the logic circuit without a clock signal.

25. The method according to claim 24, wherein the number of said logic circuit inputs is equal to the number of said logic circuit outputs.

26. The method according to claim 24, wherein in case the at least one cycle of states is a non meta-stable cycle, the minimum cycle length is three.

27. The method according to claim 24, further comprising generating an output signal from said set of logic circuit outputs and sampling said output signal.

28. The method according to claim 27, wherein said sampling comprises providing a timing signal, feeding the output signal to a sequential circuit element, and using the timing signal to clock the sequential circuit element.

29. The method according to claim 28, wherein said generating an output signal comprises providing at least a first and a second logic circuit having respective output signals, and obtaining said output signal by combining the respective output signals.