Random time interval generator

• US 5,910,956 A
• Filed: 11/05/1996
• Issued: 06/08/1999
• Est. Priority Date: 11/05/1996
• Status: Expired due to Fees

• Current Assignee: Northrop Grumman Corporation
• Original Assignee: Northrop Grumman Corporation
• Inventors: Guthrie, Warren E., Trainor, Michael J.
• Primary Examiner(s): Pham, Chi H.
• Assistant Examiner(s): Tran, Maikhanh
• Application Number:
  US08/743,943
• Time in Patent Office: 945 Days
• Field of Search: 370/445, 370/446, 370/447, 370/448, 380/46, 364/717, 307/139
• US Class Current: 370/445
• 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: G07C 9/28 the pass enabling tracking or indicating presence
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

A method for generating a random time interval suited for use in defining re-transmission time intervals so as to avoid communication contention utilizes at least one external seed and a plurality of linear maximal sequences. According to one embodiment, a first seed is provided and a first linear maximal sequence is initialized therewith. A second seed is generated via cooperation of the first linear maximal sequence and the external signal. At least one second linear maximal sequence is initialized with the second seed. A new time interval is started when the second linear maximal sequence sequences to a predetermined value.

Claims

1. A method for generating a random time interval, the method comprising the steps of:

a) providing a first seed;

b) initializing a first linear maximal sequence with the first seed;

c) generating a second seed via cooperation of the first linear maximal sequence and an external signal;

d) initializing at least one second linear maximal sequence with the second seed;

e) starting a new time interval when the second linear maximal sequence sequences to a predetermined value; and

f) repeating steps a-e, as desired.

2. The method as recited in claim 1 wherein the step of generating a second seed comprises:

a) receiving the external signal; and

b) generating the second seed such that it is representative of the state of the first linear maximal sequence at a time proximate that of which the external signal was received.

3. The method as recited in claim 1 wherein the step of generating a second seed comprises:

a) sequencing the first linear maximal sequence to a predetermined value;

b) sensing an external signal when the first linear maximal sequence reaches the predetermined value; and

c) generating a second seed which is representative of the sensed external signal.

4. The method as recited in claim 1 wherein the step of initializing at least one second linear maximal sequence with the second seed comprises sequentially initializing a plurality of different second linear maximal sequences with the second seed, each of the second linear maximal sequences defining a random subinterval.

5. The method as recited in claim 4 wherein the step of initializing a plurality of different second linear maximal sequences comprises initializing a plurality of different second linear maximal sequences selected substantially at random.

6. A method for transmitting a signal at random intervals, the method comprising the steps of:

a) providing a first seed;

b) initializing a first linear maximal sequence with the first seed;

c) generating a second seed via cooperation of the first linear maximal sequence and an external signal;

d) initializing at least one second linear maximal sequence with the second seed;

e) transmitting the signal when the second linear maximal sequence sequences to a predetermined value; and

f) repeating steps a-f, as desired.

7. A random interval generator comprising:

a) a circuit for providing a first seed;

b) a first linear maximal sequence responsive to the circuit for providing a first seed so as to be initialized thereby;

c) a circuit for generating a second seed via the cooperation of the first linear maximal sequence and an external signal;

d) at least one second linear maximal sequence responsive to the circuit for generating a second seed such that the second linear maximal sequence(s) are initialized thereby; and

e) wherein a new time interval commences when the second linear maximal sequence(s) sequences to a predetermined value provide a random time interval.

8. The random time interval generator as recited in claim 7 wherein the circuit for generating a second seed comprises a circuit for receiving an external signal and a circuit for generating the second seed such that it is representative of the state of the first linear maximal sequence at a time proximate that of which the external signal was received.

9. The random time interval generator as recited in claim 7 wherein the circuit for generating a second seed comprises a circuit for sequencing the first linear maximal sequence to a predetermined value and a circuit for sensing an external signal when the first linear maximal sequence reaches the predetermined value, such that the second seed generated is representative of the sensed external signal.

10. The random time interval generator as recited in claim 7 wherein at least one second linear maximal sequence comprises a plurality of different second linear maximal sequences which are initialized with the second seed.

11. The random time interval generator as recited in claim 7 further comprising a circuit for randomly selecting a desired plurality of different second linear maximal sequences at random.

12. A method for generating a random time interval, the method comprising the steps of:

a) selecting a plurality of linear maximal sequence(s) according to the steps of;

i) selecting 127 of a possible 176 2¹¹ -1 long linear maximal sequence(s);

ii) selecting 15 of a possible 18 2⁷ -1 long linear maximal sequence(s);

iii) selecting 4 of a 4 2⁴ -1 long linear maximal sequence(s);

b) storing four recent bump intervals;

c) selecting one of the 2⁴ -1 long linear maximal sequence(s) utilizing two least significant bits of a first one of the four stored bump intervals;

d) initializing the selected 2⁴ -1 long linear maximal sequence utilizing four least significant bits of a second one of the four stored bump intervals;

e) selecting one of the 2⁷ -1 long linear maximal sequence(s) utilizing the state of the selected 2⁴ -1 long linear maximal sequence when a next bump is received;

f) initializing the selected 2⁷ -1 long linear maximal sequence utilizing seven least significant bits of a third one of the four stored bump intervals;

g) selecting one of the 2¹¹ -1 long linear maximal sequence(s) utilizing the state of the selected 2⁷ -1 long linear maximal sequence when the next bump is received;

h) initialing the selected 2¹¹ -1 long linear maximal sequence with a state of a previously selected 2¹¹ -1 long linear maximal sequence when the next bump is received; and

i) sequencing the selected 2¹¹ -1 long linear maximal sequence until another bump is received, the state of the selected 2¹¹ -1 long linear maximal sequence defining the random time interval.

13. A method for generating a random time interval, the method comprising the steps of:

a) providing a first seed;

b) initializing a first linear maximal sequence with the first seed;

c) i) receiving an external signal;

ii) generating a second seed such that it is representative of the state of the first linear maximal sequence at a time proximate that of which the external signal was received;

d) initializing at least one second linear maximal sequence with the second seed;

e) starting a new time interval when the second linear maximal sequence sequences to a predetermined value; and

f) repeating steps a-e, as desired.

14. A method for generating a random time interval, the method comprising the steps of:

a) providing a first seed;

b) initializing a first linear maximal sequence with the first seed;

c) i) sequencing the first linear maximal sequence to a predetermined value;

ii) sensing an external signal when the first linear maximal sequence reaches the predetermined value;

iii) generating a second seed which is representative of the sensed external signal;

d) initializing at least one second linear maximal sequence with the second seed;

e) starting a new time interval when the second linear maximal sequence sequences to a predetermined value; and

f) repeating steps a-e, as desired.