Self-timed random number generator

• US 10,095,477 B2
• Filed: 11/12/2015
• Issued: 10/09/2018
• Est. Priority Date: 12/18/2014
• Status: Active Grant

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Best, Scott C.
• Primary Examiner(s): SANDIFER, MATTHEW D
• Application Number:
  US15/528,069
• Publication Number:
  US 20170344343A1
• Time in Patent Office: 1,062 Days
• Field of Search: 708250-256
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

The embodiments described herein describe a chain of pattern generators organized in a ring topology. Each of the pattern generators in the chain includes asynchronous digital logic and implements an update rule that generates a bidirectional pattern within the chain of pattern generators. The asynchronous digital logic of a first pattern generator in the chain asynchronously updates a next state of the first pattern generator based on at least (a) a current state of the first pattern generator, (b) a second state of a second pattern generator that is before the first pattern generator in the chain, and (c) a third state of a third pattern generator that is after the first pattern generator in the chain.

Claims

1. An integrated circuit comprising:

a plurality of chaotic pattern generators (CGs) arranged in a looping sequence, wherein the plurality of CGs are self-timed digital CGs to generate a random digital value, wherein a first CG of the plurality of CGs is coupled to a second CG of the plurality of CGs that is earlier in the looping sequence and to a third CG of the plurality of CGs that is later in the looping sequence, wherein the first CG comprises an asynchronous digital logic circuit comprising;

a first output;

a first input;

a second input; and

a third input,

wherein the first input is coupled to the first output and represents a first state Q1 of the first CG, the second input is coupled to a second output of the second CG and represents a second state Q0 of the second CG, and the third input is coupled to a third output of the third CG and represents a third state Q2 of the third CG,

wherein the asynchronous digital logic circuit is to update a next state Q1′

of the first CG using the Q0, Q1, and Q2, and

wherein the random digital value is generated based on at least an output of the first CG.

2. The integrated circuit of claim 1, wherein the asynchronous digital logic circuit comprises:

a first logic gate coupled to the first input and the third input;

a second logic gate coupled to the second input and an output of the first logic gate; and

an internal latch coupled to an output of the second logic gate, wherein the internal latch is configured to receive a capture signal, wherein the internal latch is configured to permit chaotic pattern generation based on Q0, Q1, and Q2 when the capture signal is not active and to stop the chaotic pattern generation when the capture signal is active, wherein the output of the first CG is one bit of the random digital value.

3. The integrated circuit of claim 2, wherein the first logic gate is an OR gate and the second logic gate is an exclusive OR (XOR) gate, and wherein the internal latch comprises:

a multiplexer coupled to the first output and the output of the XOR gate, wherein the multiplexer is configured to pass the output of the XOR gate when the capture signal is not active and to capture the first output when the capture signal is active; and

a pair of sequential inverters coupled between an output of the multiplexer and the first output.

4. The integrated circuit of claim 3, wherein the next state at the output of the XOR gate (Q1′

) is represented by the following equation;

Q1′

=Q0 XOR (Q1 OR Q2).

5. The integrated circuit of claim 1, further comprising a plurality of flip-flops (FFs) coupled to outputs of the plurality of CGs and to output the random digital value when clocked by a capture signal, wherein randomness of the random digital value is based on chaos and metastability of internal latches of the plurality of CGs.

6. The integrated circuit of claim 5, wherein a first number of the plurality of CGs is greater than a second number of the plurality of FFs, and wherein at least one of the plurality of CGs is not coupled to the plurality of FFs.

7. The integrated circuit of claim 5, wherein the plurality of CGs is organized in a first N-bit random number generator (RNG), where N is a positive integer, wherein the internal latches of the plurality of CGs are configured to receive the capture signal, and wherein the plurality of FFs is configured to latch a first N-bit value output from the plurality of CGs when the capture signal is active.

8. The integrated circuit of claim 7, further comprising

a value detector logic comprising inputs coupled to the outputs of the plurality of CGs and a reset output coupled to a reset input of one of the plurality of CGs to reset the one of the plurality of CGs when the first N-bit value is a pre-defined value.

9. The integrated circuit of claim 7, further comprising:

value detector logic comprising a reset output and inputs coupled to the outputs of the plurality of CGs; and

an OR gate comprising a control output and inputs to receive the capture signal and a SET signal from the reset output when the first N-bit value is a pre-defined value;

a second plurality of CGs organized in a second N-bit RNG, wherein internal latches of the second plurality of CGs are configured to receive a second capture signal from the control output of the OR gate, and wherein the second N-bit RNG is to output a second N-bit value; and

XOR logic comprising inputs coupled to the first N-bit RNG and inputs coupled to the second N-bit RNG, wherein the XOR logic comprises outputs coupled to the plurality of FFs, wherein the XOR logic performs an XOR operation on the first N-bit value and the second N-bit value to generate the random digital value that is latched by the plurality of FFs when the capture signal is active.

10. The integrated circuit of claim 5, further comprising mixing logic coupled to the plurality of FFs to receive the random digital value and coupled to a random number generator to receive a random number, wherein the mixing logic is configured to combine the random digital value with the random number to generate another random number.

11. The integrated circuit of claim 1, wherein the plurality of CGs is arranged in a ring topology in which the second CG is directly adjacent to the first CG in one direction in the looping sequence and the third CG is directly adjacent to the first CG in another direction in the looping sequence.

12. The integrated circuit of claim 1, wherein the plurality of CGs is arranged in a daisy-chain configuration.

13. A circuit comprising:

a plurality of flip-flops (FFs); and

a chain of self-timed chaotic pattern generators (CGs) organized in a ring topology, wherein outputs of CGs of the chain are coupled to the plurality of flip-flops, wherein each of the CGs of the chain comprises an internal latch to store a current state, an output coupled to the current state, and asynchronous digital logic, wherein the asynchronous digital logic of a first one of the CGs in the chain is to asynchronously update a next state Q1′

of the first one of the CGs based on the current state Q1, a second state Q0 of a second one of the CGs that is before the first one in the chain, and a third state Q2 of a third one of the CGs that is after the first one in the chain, wherein the plurality of FFs capture a random digital value from at least one of the outputs of the CGs in response to a control signal, wherein randomness of the random digital value is based on chaos and metastability of the internal latches of the CGs.

14. The circuit of claim 13, wherein the chain of CGs organized in the ring topology form an N-bit RNG, where N is a positive integer, wherein the N-bit RNG is responsive to the control signal, wherein, in a first mode of the control signal, the N-bit RNG is to actively generate new random digital values, and wherein, in a second mode of the control signal, the N-bit RNG latches its current state.

15. The circuit of claim 13, wherein the asynchronous digital logic comprises logic primitives that implement a one-dimensional binary cellular automaton rule equation.

16. The circuit of claim 15, wherein the one-dimensional binary cellular automaton rule equation is at least one of Rule-30, Rule-86, Rule-135, or Rule-149.

17. The circuit of claim 13, wherein the next state is determined by the following equation:

Q1′

=Q0 XOR (Q1 OR Q2).

18. The circuit of claim 13, wherein the asynchronous digital logic comprises

an OR gate to receive Q1 and Q2;

an exclusive OR (XOR) gate to receive Q0 and an output of the OR gate;

a multiplexer to receive an output of the XOR gate and Q1; and

a pair of sequential inverters coupled to an output of the multiplexer and to output Q1.

19. A method comprising:

storing a current state Q1 in an internal latch of a first chaotic pattern generator (CG), wherein the first CG is located in a chain of CGs organized in a ring topology;

asynchronously updating, by asynchronous digital logic coupled to the internal latch, a next state Q1 of the first CG based on the current state Q1, a second state Q0 of a second CG that is before the first CG in the chain, and a third state Q2 of a third CG that is after the first CG in the chain, wherein the Q1, Q0, and Q2 are output from the chain of CGs and update asynchronously at individual update rates; and

latching, by a plurality of flip-flops (FFs), a random digital value from at least one of the outputs of the chain of CGs in response to a control signal, wherein randomness of the random digital value is based on chaos and metastability of internal latches of the chain of CGs.

20. The method of claim 19, wherein the asynchronously updating comprises performing a one-dimensional binary cellular automaton rule equation by the asynchronous digital logic, wherein the one-dimensional binary cellular automaton rule equation is at least one of Rule-30, Rule-86, Rule-135, or Rule-149.

21. The method of claim 19, wherein the asynchronously updating comprises determining the next state by the following equation:

Q1′

=Q0 XOR (Q1 OR Q2).

22. The method of claim 19, wherein the asynchronously updating comprises implementing a one-dimensional binary cellular automata update rule by the asynchronous digital logic, wherein the one-dimensional binary cellular automata update rule generates a bidirectional pattern for the outputs of the chain of CGs.

23. The method of claim 19, wherein the asynchronously updating comprises implementing an update rule that generates a bidirectional pattern within the chain of CGs.

24. The method of claim 19, wherein the asynchronously updating comprises performing a first update rule that causes unidirectional update events in a first direction of the chain of CGs, and wherein the method further comprises:

storing the second state Q0 of the second CG in a second internal latch of the second CG; and

asynchronously updating, by second asynchronous digital logic coupled to the second internal latch, a next state Q0′

of the second CG based on the second state Q0, the current state Q1 of the first CG that is after the second CG in the chain, and a third state Q3 of a fourth CG that is before the second CG in the chain, wherein the Q1, Q0, and Q3 update asynchronously at individual update rates, and wherein the asynchronously updating the next state Q0′

of the second CG comprises performing a second update rule that causes unidirectional update events in a second direction of the chain of CGs.

25. A circuit comprising

a chain of self-timed pattern generators organized in a ring topology, wherein each of the self-timed pattern generators in the chain comprises asynchronous digital logic and implements an update rule that generates a bidirectional pattern within the chain of self-timed pattern generators, wherein the asynchronous digital logic of a first self-timed pattern generator in the chain is to asynchronously update a next state of the first self-timed pattern generator based on at least (a) a current state of the first self-timed pattern generator, (b) a second state of a second self-timed pattern generator that is before the first self-timed pattern generator in the chain, and (c) a third state of a third self-timed pattern generator that is after the first self-timed pattern generator in the chain,

wherein the chain of self-timed pattern generators outputs a random digital value based at least in part on the current state output from the first self-timed pattern generator.