Methods and apparatus for generating pseudo-random binary patterns

• US 5,446,683 A
• Filed: 03/31/1994
• Issued: 08/29/1995
• Est. Priority Date: 04/06/1993
• Status: Expired due to Term

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Jebwab, Jonathan, Mullen, Sean F.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/221,354
• Time in Patent Office: 516 Days
• Field of Search: 364/717, 331/78, 380/46
• US Class Current: 708/256
• CPC Class Codes: G01R 31/31813 Test pattern generators
• CPC Class Codes: G01R 31/318385 Random or pseudo-random test pattern
• CPC Class Codes: G06F 11/27 Built-in tests
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

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.

Claims

1. 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.

2. The apparatus of claim 1, wherein said pseudo-random binary pattern is 2ⁿ 1 bits in length, and said portion comprises at least 2n bits.

3. The apparatus of claim 2, wherein said control signal for each stage is derived from said portion in accordance with the Berlekamp-Massey algorithm.

4. The apparatus of claim 1, including means for detecting occurrence of a maximal length sequence of bits of a predetermined value.

5. 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.

6. The apparatus of claim 5, wherein said feedback signal for a generator comprises an output signal from said output stage of that generator.

7. 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.

8. The apparatus of claim 7, wherein said summing means comprises an exclusive-OR gate.

9. The apparatus of claim 7, wherein said switch means comprises a multiplexer.

10. The apparatus of claim 7, wherein said store means comprises a D-type latch circuit.

11. 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.

12. 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.

13. 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.

14. The method of claim 13, wherein said pseudo-random binary pattern is 2ⁿ -1 bits in length, and said portion comprises at least 2n bits.

15. The method of claim 14, wherein said control signal is derived from said portion in accordance with the Berlekamp-Massey algorithm.

16. 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.