Digital randomizer for on-chip generation and storage of random self-programming data block

• US 5,570,307 A
• Filed: 01/06/1995
• Issued: 10/29/1996
• Est. Priority Date: 01/06/1995
• Status: Expired due to Term

• Current Assignee: NXP B.V. (NXP Semiconductors NV)
• Original Assignee: VLSI Technology, Inc. (Koninklijke Philips N.V.)
• Inventors: Takahashi, Richard J.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/369,616
• Time in Patent Office: 662 Days
• Field of Search: 364/717, 380/46, 331/78
• US Class Current: 708/256
• CPC Class Codes: G06F 1/02 Digital function generators
• CPC Class Codes: G06F 2101/14 Probability distribution functions

Abstract

A purely digital randomizer system generates an undeterministic data block using standard cell library units and includes a random number generator. The generator preferably includes at least two metastable blocks that each include a plurality of D-type flip-flops. Each flip-flop is coupled to a dedicated free-running oscillator whose frequency is based on a relative prime number for each frequency leg. Each of the D-type flip-flops is also coupled to receive a common jitter clock signal. The flip-flops are thus forcibly operated in a metastable state by intentionally violating the flip-flop set-up or hold time margins of incoming data relative to the jitter clock. To further maximize entropy, the flip-flop outputs are exclusively `OR`d ("EX-OR'"'"'d") and then passed through first and second shift registers of uneven and preferably even and odd bit lengths. Preferably each shift register includes at least one metastably-operated D-type flip-flop, to further promote randomness. The shift register outputs are combined in an EX-OR tree are cross-fed back to the EX-ORs at the shift register inputs. The input from each shift register is then EX-OR'"'"'d and clocked out with a system clock to provide first and second channels of undeterministic data.

Claims

1. A system for generating an undeterministic data signal, comprising:

a plurality of N1 D-type flip-flops, each flip-flop including;

a clock input port coupled to a common jitter clock signal;

a delay input port coupled to receive a dedicated free-running oscillator signal; and

an output port;

a jitter clock, outputting a phase noise signal causing said flip-flops to operate metastably;

N1 free-running oscillators, each oscillator oscillating at a frequency that is a prime number relative to a frequency of oscillation of each other of said oscillators, each oscillator having an output port coupled to a said delay input port of one of said flip-flops; and

exclusive-OR means for outputting the undeterministic data signal, said exclusive-OR means coupled to receive an output signal from each said D-type flip-flop;

wherein N1 is an integer.

2. The system of claim 1, wherein said exclusive-OR means includes:

for each pair of said D-type flip-flops, a flip-flop combining exclusive-OR gate having first and second input ports coupled to receive an output signal from each said output port of the pair of said D-type flip-flops, said flip-flop combining exclusive-OR gate further having an output port;

for each flip-flop combining exclusive-OR gate pair, an output exclusive-OR gate having two input ports, each of which input ports is coupled to an output port of a said flip-flop combining exclusive-OR gate comprising the pair, said flip-flop combining exclusive-OR gate further having an output port;

for any odd-numbered D-type flip-flop not included in a D-type flip-flop pair, a chosen one of (a) an exclusive-OR gate receiving as a first input an output signal from any said odd-numbered D-type flip-flop, and receiving as a second input a signal from said output port of said flip-flop combining exclusive-OR gate, and providing as an output said undeterministic data signal; and

(b) wherein at least one said flip-flop combining exclusive-OR gate includes a third input coupled to receive an output signal from any said odd-numbered D-type flip-flop, wherein an undeterministic data signal is present at said output port of said output exclusive-OR gate.

3. The system of claim 1, further including a shift register having a delay element coupled in series between adjacent bit positions in said shift register;

said shift register having an input port coupled to said output port of said output exclusive-OR gate, having a clock port coupled to receive said jitter clock signal, and having an output port;

wherein an undeterministic data signal is present at said output port of said shift register, which data signal has increased entropy relative to said undeterministic data signal present at said output port of said output exclusive-OR gate.

4. The system of claim 3, wherein said shift register includes M bit positions, each of said positions being defined by a D-type flip-flop having a said clock port, a flip-flop D input port, and a Q output port;

wherein said delay element includes a logic gate whose delay is substantially equal in time to a D-to-Q delay of a said D-type flip-flop in said register.

5. The system of claim 1, wherein said jitter clock includes a digital mixer having first and second input ports coupled to receive respective first and second signals having respective first and second frequencies;

said digital mixer having an output port providing a phase signal of frequency equal to a frequency difference between said first and second frequencies.

6. The system of claim 1, wherein said jitter clock outputs a phase noise signal that violates a chosen one of set-up time margin and hold time margin for said flip-flops to cause said flip-flops to operate metastably.

13. The system of claim 6, wherein said jitter clock includes a digital mixer having first and second input ports coupled to receive respective first and second signals having respective first and second frequencies;

said digital mixer having an output port providing a phase signal of frequency equal to a frequency difference between said first and second frequencies.

7. A system for generating first and second channels of undeterministic data signals, comprising:

a first plurality of N1 D-type flip-flops, each flip-flop including;

a clock input port coupled to a common jitter clock signal;

a delay input port coupled to receive a dedicated free-running oscillator signal; and

an output port;

a second plurality of N2 D-type flip-flops, each flip-flop including;

a clock input port coupled to a common jitter clock signal;

a delay input port coupled to receive a dedicated free-running oscillator signal; and

an output port;

a jitter clock, outputting a phase noise signal causing said flip-flops to operate metastably;

N1 free-running oscillators, each oscillator oscillating at a frequency that is a prime number relative to a frequency of oscillation of each other of said oscillators, each oscillator having an output port coupled to a said delay input of one of said flip-flops comprising said first plurality N1 of D-type flip-flops;

N2 free-running oscillators, each oscillator oscillating at a frequency that is a prime number relative to a frequency of oscillation of each other of said oscillators in said system, each oscillator having an output port coupled to a said delay input of one of said flip-flops comprising said second plurality of N2 D-type flip-flops;

first exclusive-OR means for outputting a first channel of undeterministic data, said first exclusive-OR means coupled to receive an output signal from each said D-type flip-flop in said first plurality of N1 D-type flip-flops;

second exclusive-OR means for outputting a second channel of undeterministic data, said second exclusive-OR means coupled to receive an output signal from each said D-type flip-flop in said second plurality of N2 D-type flip-flops;

an M-bit shift register having an input port coupled to an output port of said first exclusive-OR means, having a clock port coupled to receive said jitter clock signal, and having an output port;

an N-bit shift register having an input port coupled to an output port of said second exclusive-OR means, having a clock port coupled to receive said jitter clock signal, and having an output port;

wherein N1 and N2 are integers, and wherein first and second channels of undeterministic data signal are provided at said output port of said M-bit shift register and said N-bit shift register.

8. The system of claim 7, wherein:

said first exclusive-OR means includes, for each pair of said D-type flip-flops in said first plurality of N1 D-type flip-flops, a first flip-flop combining exclusive-OR gate having first and second input ports coupled to receive an output signal from each said output port of the pair of said D-type flip-flops, and having an output port;

said second exclusive-OR means includes, for each pair of said D-type flip-flops in said second plurality of N2 D-type flip-flops, a second flip-flop combining exclusive-OR gate having first and second input ports coupled to receive an output signal from each said output port of the pair of said D-type flip-flops, and having an output port;

for each first flip-flop combining exclusive-OR gate pair, a first output exclusive-OR gate having two input ports, each of which input ports is coupled to an output port of a said flip-flop output exclusive-OR gate comprising the pair, said first output exclusive-OR gate further having an output port;

wherein a first channel of undeterministic data signal is present at said output port of said first output exclusive-OR gate;

for each second flip-flop combining exclusive-OR gate pair, a second output exclusive-OR gate having two input ports, each of which input ports is coupled to an output port of a said flip-flop output exclusive-OR gate comprising the pair, said second output exclusive-OR gate further having an output port;

for any odd-numbered D-type flip-flop not included in a D-type flip-flop pair, a chosen one of (a) an exclusive-OR gate receiving as a first input an output signal from any said odd-numbered D-type flip-flop, and receiving as a second input a signal from said output port of a said flip-flop combining exclusive-OR gate, and providing as an output said undeterministic data signal; and

(b) wherein at least one said flip-flop combining exclusive-OR gate includes a third input coupled to receive an output signal from any said odd-numbered D-type flip-flop, wherein an undeterministic data signal is present at said output port of said output exclusive-OR gate;

wherein a second channel of undeterministic data signal is present at said output port of said second output exclusive-OR gate;

said M-bit shift register has said input port coupled to said output port of said first output exclusive-OR gate; and

said N-bit shift register has said input port coupled to said output port of said second output exclusive-OR gate.

9. The system of claim 7, wherein:

each said shift register includes bit positions defined by a D-type flip-flop having a said clock port, a flip-flop D input port, and a Q output port;

at least one of said M-bit and said N-bit shift registers includes a delay element coupled in series between adjacent bit positions in said shift register;

said delay element including a logic gate whose delay is substantially equal in time to a D-to-Q delay of a said D-type flip-flop in said register.

10. The system of claim 7, wherein M and N are numbers having a characteristic selected from the group consisting of (a) M and N are unequal, (b) M is even and N is odd, (c) the smaller of M and N exceeds 9, and (d) the difference between M and N exceeds 5.

11. The system of claim 7, further including an exclusive-OR tree coupled to receive as inputs said first and second channels of undeterministic data signal output by said M-bit shift register and said N-bit shift register;

said exclusive-OR tree providing a first and second intermediate output channels of data in response to said first and said second channel of undeterministic data signal from said output port of said first and said second output exclusive-OR gate, respectively;

a first intermediate exclusive-OR gate coupled in series between said first output exclusive-OR gate and said M-bit shift register;

said first intermediate exclusive-OR gate having a first input pert coupled to receive said first channel of undeterministic data from said output port of said first output exclusive-OR gate, having a second input port coupled to receive the second intermediate channel of data from said exclusive-OR tree, and having an output port coupled to said input of said M-bit shift register;

a second intermediate exclusive-OR gate coupled in series between said second output exclusive-OR gate and said N-bit shift register;

said second intermediate exclusive-OR gate having a first input port coupled to receive said second channel of undeterministic data from said output port of said second output exclusive-OR gate, having a second input port coupled to receive the first intermediate channel of data from said exclusive-OR tree, and having an output port coupled to said input of said N-bit shift register;

wherein independent first and second channels of undeterministic data are output by the first and second intermediate exclusive-OR gates.

12. The system of claim 11, further including:

third and fourth exclusive-OR gates, each having a first input port coupled to said input port of said M-bit shift register, each having a second input port coupled to said input port of said N-bit shift register, and each having an output port;

first and second output D-type flip-flops, each having a D-input port, an output port, and a system clock input port coupled to receive a common system clock signal that is asynchronous relative to said jitter clock signal;

said output port of the third exclusive-OR gate being coupled to said D-input port of said first output D-type flip-flop;

said output port of the fourth exclusive-OR gate being coupled to a D-input of said second output D-type flip-flop;

wherein first and second independent channels of undeterministic data having increased entropy are present at the output port of said first and said second output D-type flip-flop.

14. The system of claim 7, wherein said jitter clock outputs a phase noise signal that violates a chosen one of set-up time margin and hold time margin for said flip-flops to cause said flip-flops to operate metastably.

15. The system of claim 7, wherein N1≧

N2.

16. The system of claim 7, wherein at least one integer of said N1 and N2 has a characteristic selected from the group consisting of (i) said integer is even, and (ii) said integer is odd.

17. A method for generating an undeterministic data signal, the method including the following steps:

(a) providing a plurality of N1 D-type flip-flops, each flip-flop including;

a clock input port coupled to a common jitter clock signal, where N1 is an integer;

a delay input port coupled to receive a dedicated free-running oscillator signal; and

an output port;

(b) providing a jitter clock, outputting a phase noise signal causing said flip-flops to operate metastably;

(c) providing N1 free-running oscillators, each oscillator oscillating at a frequency that is a prime number relative to a frequency of oscillation of each other of said oscillators, each oscillator having an output port coupled to a said delay input port of one of said flip-flops;

(d) providing exclusive-OR means for outputting the undeterministic data signal, wherein said exclusive-OR means is coupled to receive an output signal from each said D-type flip-flop.

18. The method of claim 17, including an additional step of providing a shift register having a delay element coupled in series between adjacent bit positions in said shift register;

said shift register having an input port coupled to an output port of said exclusive-OR means, having a clock port coupled to receive said jitter clock signal, and having an output port;

wherein an undeterministic data signal is present at said output port of said shift register, which data signal has increased entropy relative to said undeterministic data signal present at said output port of said exclusive-OR means.

19. The method of claim 18, wherein said shift register includes M bit positions, each of said positions being defined by a D-type flip-flop having a said clock port, a flip-flop D input port, and a Q output port;

wherein said delay element includes a logic gate whose delay is substantially equal in time to a D-to-Q delay of a said D-type flip-flop in said register.

20. The method of claim 17, wherein step (b) includes providing a jitter clock comprising a digital mixer having first and second input ports coupled to receive respective first and second signals having respective first and second frequencies;

said digital mixer having an output port providing a phase signal of frequency equal to a frequency difference between said first and second frequencies.

21. The method of claim 17, wherein said jitter clock outputs a phase noise signal that violates a chosen one of set-up time margin and hold time margin for said flip-flops to cause said flip-flops to operate metastably.

22. A method for generating first and second channels of undeterministic data signals, the method including the following steps:

(a) providing a first plurality of N1 D-type flip-flops, each flip-flop including;

a clock input port coupled to a common jitter clock signal;

a delay input port coupled to receive a dedicated free running oscillator signal; and

an output port;

(b) providing a second plurality of N2 D-type flip-flops, each flip-flop including;

a clock input port coupled to a common jitter clock signal;

a delay input port coupled to receive a dedicated free running oscillator signal; and

an output port;

(c) providing a jitter clock, outputting a phase noise signal causing said flip-flops to operate metastably;

(d) providing N1 free-running oscillators, each oscillator oscillating at a frequency that is a prime number relative to a frequency of oscillation of each other of said oscillators, each oscillator having an output port coupled to a said delay input of one of said flip-flops comprising said first plurality of N1 D-type flip-flops;

(e) providing N2 free-running oscillators, each oscillator oscillating at a frequency that is a prime number relative to a frequency of oscillation of each other of said oscillators in said system, each oscillator having an output port coupled to a said delay input of one of said flip-flops comprising said second plurality of N2 D-type flip-flops;

(f) providing first exclusive-OR means for outputting a first channel of undeterministic data, wherein said first exclusive-OR means is coupled to receive an output signal from each said D-type flip-flop in said first plurality of N1 D-type flip-flops;

(g) providing second exclusive-OR means for outputting a second channel of undeterministic data, wherein said second exclusive-OR means is coupled to receive an output signal from each said D-type flip-flop in said second plurality of N2 D-type flip-flops;

(h) providing an M-bit shift register having an input port coupled to said output port of said first exclusive-OR means, having a clock port coupled to receive said jitter clock signal, and having an output port; and

(i) providing an N-bit shift register having an input port coupled to said output port of said second exclusive-OR means, having a clock port coupled to receive said jitter clock signal, and having an output port;

wherein N1 and N2 are integers;

wherein M and N are numbers having a characteristic selected from the group consisting of (a) M and N are unequal, (b) M is even and N is odd, (c) the smaller of M and N exceeds 9, and (d) the difference between M and N exceeds 5;

wherein first and second channels of undeterministic data signal are present at said output port of said M-bit shift register and said N-bit shift register.

23. The method of claim 22, wherein:

at least one of step (h) and step (i) includes providing a said shift register having bit positions defined by a D-type flip-flop having a said clock port, a flip-flop D input port, and a Q output port;

wherein at least one of step (h) and step (i) includes providing a delay element coupled in series between adjacent bit positions in said shift register;

said delay element including a logic gate whose delay is substantially equal in time to a D-to-Q delay of a said D-type flip-flop in said register.

24. The method of claim 22, including further steps

(j) providing an exclusive-OR tree coupled to receive as inputs said first and second channels of undeterministic data signal output by said M-bit shift register and said N-bit shift register

said exclusive-OR tree providing a first and second intermediate output channels of data in response to said first and said second channel of undeterministic data signal from said output port of said first and said second exclusive-OR means, respectively;

(k) providing a first intermediate exclusive-OR gate coupled in series between said first exclusive-OR means and said M-bit shift register;

said first intermediate exclusive-OR gate having a first input port coupled to receive said first channel of undeterministic data from said output port of said first exclusive-OR means, having a second input port coupled to receive the second intermediate channel of data from said exclusive-OR tree, and having an output port coupled to said input of said M-bit shift register;

(n) providing a second intermediate exclusive-OR gate coupled in series between said second exclusive-OR means and said N-bit shift register;

said second intermediate exclusive-OR gate having a first input port coupled to receive said second channel of undeterministic data from said output port of said second exclusive-OR means, having a second input port coupled to receive the first intermediate channel of data from said exclusive-OR tree, and having an output port coupled to said input of said N-bit shift register;

wherein independent first and second channels of undeterministic data are output by the first and second intermediate exclusive-OR gates.

25. The method of claim 24, including the additional steps of:

(o) providing third and fourth exclusive-OR gates, each having a first input port coupled to said input port of said M-bit shift register, each having a second input port coupled to said input port of said N-bit shift register, and each having an output port;

(p) providing first and second output D-type flip-flops, each having a D-input port, an output port, and a system clock input port coupled to receive a common system clock signal that is asynchronous relative to said jitter clock signal;

said output port of the third exclusive-OR gate being coupled to said D-input port of said first output D-type flip-flop;

said output port of the fourth exclusive-OR gate being coupled to a D-input of said second output D-type flip-flop;

wherein first and second independent channels of undeterministic data having increased entropy are present at the output port of said first and said second output D-type flip-flop.

26. The method of claim 22, wherein step (c) includes providing a jitter clock comprising a digital mixer having first and second input ports coupled to receive respective first and second signals having respective first and second frequencies;

said digital mixer having an output port providing a phase signal of frequency equal to a frequency difference between said first and second frequencies.

27. The method of claim 22, wherein said jitter clock outputs a phase noise signal that violates a chosen one of set-up time margin and hold time margin for said flip-flops to cause said flip-flops to operate metastably.

28. The method of claim 22, wherein N1≧

N2.

29. The method of claim 22, wherein at least one integer of said N1 and N2 has a characteristic selected from the group consisting of (i) said integer is even, and (ii) said integer is odd.