US5268899A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus for generating pseudo-random numbers in a communication system, or other system involving a shared resource
Assignee: HP Inc
•
Filing: 1991-10-17
•
Granted: 1993-12-07
•
Expires: 2011-10-17
Abstract
Abstract A pseudo-random number generator for a communications network, such as a CSMA/CD network, is based on a circuit which supplies a pseudo-random signal which normally changes according to a first algorithm, and changes according to a second algorithm during intervals having duty cycle behavior known to vary from node to node, such as transmission times of the node. Because it is very unlikely that two nodes in a given network will have transmission times that are equal, it is unlikely that pseudo-random number generators responsive to the local transmission times will proceed in lock-step. The pseudo-random number generator comprises, for instance, a counter which runs at a first clock rate normally, and runs at a second clock rate during intervals having lengths determined by the transmission times of the node.
Inventors
- 👤 David R. Brown
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 21:21
CPC Classifications
H; H04; H04L; H04L12/00; H04L12/28; H04L12/40; H04L12/407; H04L12/413
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
92 words
An apparatus for generating a pseudo-random number at nodes, wherein nodes include a circuit generating a clock signal and a circuit generating a local signal expected to exhibit a different duty cycle from node to node, the apparatus comprising: a first circuit, receiving the clock signal and a control signal, that supplies an output indicating the pseudo-random number in response to the clock signal and the control signal; and a second circuit, receiving the local signal, that supplies the control signal as a function of the duty cycle of the local signal.
Claim 2
Independent Claim
92 words
An apparatus for generating a pseudo-random number at nodes, wherein nodes include a circuit generating a clock signal and a circuit generating a local signal expected to exhibit a different duty cycle from node to node, the apparatus comprising: a first circuit, receiving the clock signal and a control signal, that supplies an output indicating the pseudo-random number in response to the clock signal and the control signal; and a second circuit, receiving the local signal, that supplies the control signal as a function of the duty cycle of the local signal.
Claim 3
Dependent Claim
29 words
The apparatus of claim 1, wherein the second circuit comprises a connection form the circuit generating the local signal to thereby supply the local signal as the control signal.
Claim 4
Dependent Claim
11 words
The apparatus of claim 2, wherein the connection includes a buffer.
Claim 5
Dependent Claim
35 words
The apparatus of claim 1, wherein the second circuit comprises: logic, receiving the clock signal and the local signal, that generates the control signal as a function of the local signal and the clock signal.
Claim 6
Dependent Claim
61 words
The apparatus of claim 1, wherein the nodes further include circuits generating a plurality of local control signals including the local signal, and the first circuit includes: logic, receiving the local signal and at least one other local control signal, that generates the control signal as a function of the local signal and the at least one other local control signal.
Claim 7
Dependent Claim
29 words
The apparatus of claim 1, wherein the first circuit includes a counter having a clock input receiving the clock signal and a counter enable input receiving the control signal.
Claim 8
Dependent Claim
29 words
The apparatus of claim 1, wherein the first circuit includes a shift register having a clock input receiving the clock signal and a shift input receiving the control signal.
Claim 9
Independent Claim
101 words
An apparatus for generating a pseudo-random number for use in controlling access for use by a node of a common resource, comprising: a first circuit that supplies a first signal indicating a duration of time intervals during which the common resource is in use by the node; and a second circuit, coupled with the first circuit, for supplying a second signal indicating the pseudo-random number, the second signal normally changing according to a first algorithm and changing according to a second algorithm during intervals having lengths that are a function of the duration of time intervals indicated by the first signal.
Claim 10
Independent Claim
101 words
An apparatus for generating a pseudo-random number for use in controlling access for use by a node of a common resource, comprising: a first circuit that supplies a first signal indicating a duration of time intervals during which the common resource is in use by the node; and a second circuit, coupled with the first circuit, for supplying a second signal indicating the pseudo-random number, the second signal normally changing according to a first algorithm and changing according to a second algorithm during intervals having lengths that are a function of the duration of time intervals indicated by the first signal.
Claim 11
Dependent Claim
33 words
The apparatus of claim 8, wherein the node includes logic generating a use signal during use of the common resource by the node, and the first circuit is responsive to the use signal.
Claim 12
Dependent Claim
24 words
The apparatus of claim 9, wherein the first circuit includes a connection from the logic to supply the use signal to the second circuit.
Claim 13
Dependent Claim
44 words
The apparatus of claim 8, wherein the second circuit comprises: a counter, normally running at a first clock rate and running at a second clock rate intervals having lengths that are a function of the duration of time intervals indicated by the first signal.
Claim 14
Dependent Claim
33 words
The apparatus of claim 11, wherein the node includes logic generating a use signal during use of the common resource by the node, and the first circuit is responsive to the use signal.
Claim 15
Dependent Claim
33 words
The apparatus of claim 11, wherein the node further includes a clock generator providing a node clock signal, and the first and second clock rates are respective functions of the node clock signal.
Claim 16
Dependent Claim
95 words
The apparatus of claim 13, wherein: the node includes logic generating a use signal during use of the common resource by the node, and the counter includes a clock input connected to the clock generator and an enable input receiving the first signal, and generates an output which changes in response to the node clock signal supplied to the clock input during assertion of the first signal supplied to the enable input; and the first circuit further including logic, receiving the use signal, that supplies the first signal as a function of the use signal.
Claim 17
Dependent Claim
57 words
The apparatus of claim 8, wherein the second circuit comprises: a shift register, having a shift input and a clock input; and a third circuit, connected to the shift input, that supplies the first signal to the shift input; a fourth circuit, connected to the clock input, that supplies a shift clock signal to the clock input.
Claim 18
Dependent Claim
34 words
The apparatus of claim 15, wherein the node includes logic generating a use signal during use of the common resource by the node, and the first signal is a function of the use signal.
Claim 19
Dependent Claim
31 words
The apparatus of claim 15, wherein the node further includes a clock generator providing a node clock signal, and the shift clock signal is a function of the node clock signal.
Claim 20
Dependent Claim
96 words
The apparatus of claim 8, the node includes logic generating a use signal during use of the common resource by the node, and the node further includes a clock generator providing a node clock signal, and the second circuit comprises: a shift register, having a shift input and a clock input; and a third circuit, connected to the shift input, that supplies the first signal to the shift input in response to the use signal; a fourth circuit, connected to the clock input, that supplies a shift clock signal in response to the node clock signal.
Claim 21
Dependent Claim
119 words
A node connected to a network medium of a communications network, comprising: a transmitter transmitting signals on the network medium; a collision detector detecting collisions on the network medium between signals transmitted by the node an other signals on the network medium; a backoff control circuit, connected to the collision detector and the transmitter, that disables the transmitter upon detection of a collision for a backoff interval having a length determined by a backoff interval length signal; and a backoff length circuit, coupled with the backoff control circuit, that supplies the backoff interval length signal, normally according to a first algorithm and according to a second algorithm during intervals that are a function of transmission times of the transmitter.
Claim 22
Dependent Claim
119 words
A node connected to a network medium of a communications network, comprising: a transmitter transmitting signals on the network medium; a collision detector detecting collisions on the network medium between signals transmitted by the node an other signals on the network medium; a backoff control circuit, connected to the collision detector and the transmitter, that disables the transmitter upon detection of a collision for a backoff interval having a length determined by a backoff interval length signal; and a backoff length circuit, coupled with the backoff control circuit, that supplies the backoff interval length signal, normally according to a first algorithm and according to a second algorithm during intervals that are a function of transmission times of the transmitter.
Claim 23
Dependent Claim
62 words
The node of claim 19, wherein: the transmitter includes transmit control logic, coupled to the backoff length circuit, that asserts a transmit enable signal during transmissions by the node on the network, and deasserts the transmit enable signal during the backoff intervals; and wherein the backoff interval length signal changes according to the second algorithm in response to the transmit enable signal.
Claim 24
Dependent Claim
40 words
The node of claim 20, wherein the backoff length circuit comprises: a counter, running at a first clock rate during deassertion of the transmit enable signal and running at a second clock rate during assertion of the transmit enable signal.
Claim 25
Dependent Claim
34 words
The node of claim 21, wherein the transmitter further includes a transmit clock generator providing a transmit clock signal, and the first and second clock rates are respective functions of the transmit clock signal.
Claim 26
Dependent Claim
78 words
The node of claim 21, wherein: the counter includes a clock input connected to the transmit clock generator and an enable input, ad generates an output which changes in response to the transmit clock signal at the clock input during assertion of a counter enable signal at the enable input; and further including logic, receiving the transmit enable signal, that generates the counter enable signal as a function of the transmit enable signal and the transmit clock signal.
Claim 27
Dependent Claim
57 words
The node of claim 20, wherein the backoff length circuit comprises: a shift register, having a shift input and a clock input; and a first circuit, connected to the shift input, that supplies a shift signal in response to the transmit enable signal; a second circuit, connected to the clock input, that supplies a shift clock signal.
Claim 28
Dependent Claim
32 words
The node of claim 24, wherein the transmitter further includes a transmit clock generator providing a transmit clock signal, and the shift clock signal is a function of the transmit clock signal.
Claim 29
Dependent Claim
83 words
The node of claim 20, the transmitter further includes a transmit clock generator providing a transmit clock signal, and wherein the backoff length circuit comprises: a shift register, having a shift input and a clock input; and a first circuit, connected to the shift input, that supplies a shift signal in response to the transmit enable signal and the transmit clock signal; a second circuit, connected to the clock input, that supplies a shift clock signal in response to the transmit clock signal.
Claim 30
Independent Claim
168 words
An apparatus providing an interface between a data processor and a communication medium for a CSMA/CD network, comprising: a transmitter, responsive to a transmit enable signal and a transmit clock signal, for transmitting signals on the communications medium; a collision detector generating a collision signal in response to collisions on the communications medium between the transmitter and other sources of signals on the communications medium; control logic, receiving requests to transmit frames of data from the data processor and receiving the collision signal, that generates the transmit enable signal, wherein the transmit enable signal is deasserted in response to the collision signal for a backoff interval having a length determined by a pseudo-random signal; and a circuit, coupled with the control logic and responsive to the transmit clock signal, that generates the pseudo-random signal determinant of the backoff interval, the pseudo-random signal normally changing according to a first algorithm and changing according to a second algorithm during intervals that are a function of transmission times of the transmitter.
Claim 31
Independent Claim
168 words
An apparatus providing an interface between a data processor and a communication medium for a CSMA/CD network, comprising: a transmitter, responsive to a transmit enable signal and a transmit clock signal, for transmitting signals on the communications medium; a collision detector generating a collision signal in response to collisions on the communications medium between the transmitter and other sources of signals on the communications medium; control logic, receiving requests to transmit frames of data from the data processor and receiving the collision signal, that generates the transmit enable signal, wherein the transmit enable signal is deasserted in response to the collision signal for a backoff interval having a length determined by a pseudo-random signal; and a circuit, coupled with the control logic and responsive to the transmit clock signal, that generates the pseudo-random signal determinant of the backoff interval, the pseudo-random signal normally changing according to a first algorithm and changing according to a second algorithm during intervals that are a function of transmission times of the transmitter.
Claim 32
Dependent Claim
21 words
The apparatus of claim 27, wherein the pseudo-random changes according to the second algorithm in response to the transmit enable signal.
Claim 33
Dependent Claim
43 words
The apparatus of claim 27, wherein the circuit that generates the pseudo-random signal comprises: a counter, running at a first clock rate during deassertion of the transmit enable signal and running at a second clock rate during assertion of the transmit enable signal.
Claim 34
Dependent Claim
33 words
The apparatus of claim 29, wherein the transmit clock runs at the first clock rate, and the second clock rate equals essentially the first clock rate divided by a constant other than one.
Claim 35
Dependent Claim
20 words
The apparatus of claim 29, wherein the first and second clock rates are respective functions of the transmit clock signal.
Claim 36
Dependent Claim
74 words
The apparatus of claim 29, wherein: the counter includes a clock input receiving to the transmit clock signal and an enable input, and generates an output which changes in response to the transmit clock signal during assertion of a counter enable signal at the enable input; and further including logic, receiving the transmit enable signal, that supplies the counter enable signal as a function of the transmit enable signal and the transmit clock signal.
Claim 37
Dependent Claim
60 words
The apparatus of claim 27, wherein the circuit that generates the pseudo-random signal comprises: a shift register, having a shift input and a clock input; and a first circuit, connected to the shift input, that supplies a shift signal in response to the transmit enable signal; a second circuit, connected to the clock input, that supplies a shift clock signal.
Claim 38
Dependent Claim
72 words
The apparatus of claim 27, wherein the circuit that generates the pseudo-random signal comprises: a shift register, having a shift input and a clock input; and a first circuit, connected to the shift input, that supplies a shift signal in response to the transmit enable signal and the transmit clock signal; a second circuit, connected to the clock input, that supplies a shift clock signal in response to the transmit clock signal.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-12-06 | 1997-06-07 | 1997-12-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-12-06 | 2001-06-07 | 2001-12-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-12-06 | 2005-06-07 | 2005-12-07 | $7700.00 | Window Closed / Lapsed |