US5446683A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and apparatus for generating pseudo-random binary patterns
Assignee: Agilent Technologies Inc
•
Filing: 1994-03-31
•
Granted: 1995-08-29
•
Expires: 2014-03-31
Abstract
Abstract Method and apparatus for generating a pseudo-random binary pattern having a variable characteristic polynomial. The pseudo-random binary pattern is formed as a plurality of serial bit streams, with corresponding bits in each stream forming together one of successive w-bit words in the binary pattern. A plurality of linear feedback shift register (LFSR) sequence generators are each arranged to generate bits for respective ones of the serial bit streams. Each LFSR generator includes a plurality of stages, the stages having an input stage, at least one intermediate stage, and an output stage, the stages being coupled for sequential propagation of signals through the stages. At least one of the stages in each LFSR generator is responsive to a respective control signal for that stage to determine whether signal propagation through that stage is influenced by a feedback signal for that LFSR generator. A portion of predetermined length of one of the serial bit streams is produced in accordance with the variable characteristic polynomial. The control signal is derived from that portion.
Inventors
- 👤 Sean F. Mullen
- 👤 Jonathan Jebwab
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:02
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/22; G06F11/26; G06F11/27; G01; G01R; G01R31/00; G01R31/28; G01R31/317; G01R31/3181; G01R31/31813; G01R31/3183; G01R31/318385; G06F7/00; G06F7/58; G06F7/582; G06F7/584; H; H03; H03K; H03K3/00; H03K3/84; G06F2207/00; G06F2207/58; G06F2207/581; G06F2207/583
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
167 words
Apparatus for generating a pseudo-random binary pattern having a variable characteristic polynomial, said pseudo-random binary pattern formed as a plurality of serial bit streams, corresponding bits in each said stream forming together one of successive w-bits words in said binary pattern, comprising: a plurality of LFSR sequence generators, each said LFSR sequence generator arranged to generate bits for one of said serial bit streams and including a plurality of stages, said stages having an input stage, at least one intermediate stage, and an output stage, said stages being coupled for sequential propagation of signals through said stages, and at least one of said stages in each LFSR generator being responsive to a respective control signal for that stage to determine whether signal propagation through said stage is influenced by a feedback signal for that LFSR generator; and means for producing in accordance with said variable characteristic polynomial a portion of predetermined length of one of said serial bit streams, and deriving said control signal from said portion.
Claim 2
Dependent Claim
167 words
Apparatus for generating a pseudo-random binary pattern having a variable characteristic polynomial, said pseudo-random binary pattern formed as a plurality of serial bit streams, corresponding bits in each said stream forming together one of successive w-bits words in said binary pattern, comprising: a plurality of LFSR sequence generators, each said LFSR sequence generator arranged to generate bits for one of said serial bit streams and including a plurality of stages, said stages having an input stage, at least one intermediate stage, and an output stage, said stages being coupled for sequential propagation of signals through said stages, and at least one of said stages in each LFSR generator being responsive to a respective control signal for that stage to determine whether signal propagation through said stage is influenced by a feedback signal for that LFSR generator; and means for producing in accordance with said variable characteristic polynomial a portion of predetermined length of one of said serial bit streams, and deriving said control signal from said portion.
Claim 3
Dependent Claim
25 words
The apparatus of claim 1, wherein said pseudo-random binary pattern is 2 n 1 bits in length, and said portion comprises at least 2n bits.
Claim 4
Dependent Claim
23 words
The apparatus of claim 2, wherein said control signal for each stage is derived from said portion in accordance with the Berlekamp-Massey algorithm.
Claim 5
Dependent Claim
21 words
The apparatus of claim 1, including means for detecting occurrence of a maximal length sequence of bits of a predetermined value.
Claim 6
Dependent Claim
43 words
The apparatus of claim 1, wherein said control signal is related to said characteristic polynomial for the LFSR sequence such that signal propagation through a stage corresponding to a term of the polynomial having a non-zero coefficient is influenced by said feedback signal.
Claim 7
Dependent Claim
23 words
The apparatus of claim 5, wherein said feedback signal for a generator comprises an output signal from said output stage of that generator.
Claim 8
Dependent Claim
95 words
The apparatus of claim 6, wherein each stage comprises: store means for storing a signal representative of the operational state of the stage; means for summing, modulo-2, an input signal for the stage and said output signal from said output stage to produce a sum signal; and switch means responsive to said control signal for said stage to couple a selected one of said input signal and said sum signal to said store means; each of said intermediate and output stages receiving as its said input signal an output signal from its respective preceding stage.
Claim 9
Dependent Claim
13 words
The apparatus of claim 7, wherein said summing means comprises an exclusive-OR gate.
Claim 10
Dependent Claim
12 words
The apparatus of claim 7, wherein said switch means comprises a multiplexer.
Claim 11
Dependent Claim
14 words
The apparatus of claim 7, wherein said store means comprises a D-type latch circuit.
Claim 12
Dependent Claim
75 words
The apparatus of claim 7, wherein said output stage includes output switch means for selecting one of a signal representative of the operational state of said output stage and a signal at an input terminal, said output signal from the output stage being derived from the signal selected by said output switch means, and said signal representative of the operational state of said output stage is taken from the switch means in said output stage.
Claim 13
Dependent Claim
53 words
The apparatus of claim 1, wherein said output stage includes output switch means for selecting one of a signal representative of the operational state of said output stage and a signal at an input terminal, said output signal from the output stage being derived from the signal selected by said output switch means.
Claim 14
Independent Claim
163 words
A method for generating a pseudo-random binary pattern having a variable characteristic polynomial, said pseudo-random binary pattern formed as a plurality of serial bit streams, corresponding bits in each said stream forming together one of successive w-bit words in said binary pattern, comprising: arranging a plurality of LFSR generators, such that each of said LFSR generators generates bits for one of said serial bit streams and each of said LFSR generators has an input stage, at least one intermediate stage and an output stage, said stages being coupled for sequential propagation of signals through said stages, and at least one of said stages in each LFSR generator being responsive to a respective control signal for that stage to determine whether signal propagation through that stage is influenced by a feedback signal for that LFSR generator; producing in accordance with said variable characteristic polynomial a portion of predetermined length of one of said serial bit streams; and deriving said control signal from said portion.
Claim 15
Independent Claim
163 words
A method for generating a pseudo-random binary pattern having a variable characteristic polynomial, said pseudo-random binary pattern formed as a plurality of serial bit streams, corresponding bits in each said stream forming together one of successive w-bit words in said binary pattern, comprising: arranging a plurality of LFSR generators, such that each of said LFSR generators generates bits for one of said serial bit streams and each of said LFSR generators has an input stage, at least one intermediate stage and an output stage, said stages being coupled for sequential propagation of signals through said stages, and at least one of said stages in each LFSR generator being responsive to a respective control signal for that stage to determine whether signal propagation through that stage is influenced by a feedback signal for that LFSR generator; producing in accordance with said variable characteristic polynomial a portion of predetermined length of one of said serial bit streams; and deriving said control signal from said portion.
Claim 16
Dependent Claim
25 words
The method of claim 13, wherein said pseudo-random binary pattern is 2 n -1 bits in length, and said portion comprises at least 2n bits.
Claim 17
Dependent Claim
20 words
The method of claim 14, wherein said control signal is derived from said portion in accordance with the Berlekamp-Massey algorithm.
Claim 18
Dependent Claim
46 words
The method of claim 13, wherein said bit signal propagation is influenced by said feedback signal in respect of propagation steps for which said control signal has a value indicative of a non-zero coefficient in the corresponding term of said characteristic polynomial for the LFSR sequence.
References Cited (Backward Citations)
US4536881A
Cited
SU1248030A1
Cited
US4734921A
Cited
WO1988004097A1
Cited
US5111416A
Cited
EP0438322A2
Cited
US5268949A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-08-28 | 1999-02-27 | 1999-08-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-08-28 | 2003-02-27 | 2003-08-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-08-28 | 2007-02-27 | 2007-08-29 | $7700.00 | Window Closed / Lapsed |