Parallel pseudorandom pattern generator with varying phase shift

• US 4,959,832 A
• Filed: 12/09/1988
• Issued: 09/25/1990
• Est. Priority Date: 12/09/1988
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines SA (International Business Machines Corporation)
• Inventors: Bardell, Paul H. Jr.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Beausoliel, Robert W.
• Application Number:
  US07/281,617
• Time in Patent Office: 655 Days
• Field of Search: 371/27, 371/22.3, 371/22.4, 371/22.5, 364/717, 324/73 R, 324/73 AT, 324/73 A
• US Class Current: 714/739
• 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

Abstract

Phase enhancement means are employed in conjunction with linear feedback shift registers to generate sequences of binary pattern vectors which are much more structurally independent of one another thus enabling more thorough and comprehensive testing of integrated circuit systems. More particularly, the present invention employs a plurality of exclusive-OR gates in an array of one gate per register output cell to generate the desired uncorrelated pattern strings. This facilitates testing of integrated circuit devices and systems and is particularly useful for built-in test situations for very large scale integrated circuits which employ pseudorandom test methods.

Claims

1. A pseudorandom pattern generator comprising:

linear feedback shift register means having a plurality of cells for storing and sequentially shifting data patterns, each cell having input and output signal lines, said cells being connected in a feedback arrangement so that collectively said cells are cyclable through a pattern sequence determined by said feedback arrangement; and

phase shift enhancement means for increasing the phase shift between adjacent cell output lines.

2. The pseudorandom pattern generator of claim 1 in which said phase shift enhancement means comprises a plurality of exclusive-OR gates each such gate receiving one input signal from a distinct shift register cell output line and a second input from a common specified one of said shift register cell input lines.

3. The pseudorandom pattern generator of claim 2 in which said common specified one of said cell input lines is the input line to the leftmost cell in said shift register means.

4. The pseudorandom pattern generator of claim 1 in which said linear feedback shift register means is defined by a generating polynomial which is of maximum length.

5. The pseudorandom pattern generator of claim 1 in which said linear feedback shift register means is defined by a generating polynomial which requires a minimum number of exclusive-OR gates in its feedback arrangement.

6. The pseudorandom pattern generator of claim 1 in which said linear feedback shift register means is defined by a generating polynomial of the form p(x)=x³¹ +x⁶ +x² +x+1.

7. The pseudorandom pattern generator of claim 1 in which said linear feedback shift register means is defined by a generating polynomial of the form p(x)=x³¹ +x²⁹ +x¹³ +x¹¹ +1.

8. A method for increasing the phase shift between adjacent output lines of a linear feedback shift register having a plurality of cells for storing and sequentially shifting data patterns wherein each cell has input and output signal lines and said cells are connected in a feedback arrangement so that collectively said cells are cyclable through a pattern sequence determined by said feedback arrangement, said method comprising separately supplying signals on the output signal lines of said shift register cells to a plurality of exclusive-OR gates, said exclusive-OR gates also being supplied with a common second input from a specified one of said shift register cell input lines.

9. The method of claim 8 in which said second, common input to said exclusive-OR gates is supplied from the input line to the leftmost cell in said shift register.

10. The method of claim 8 in which said linear feedback shift register is defined by a generating polynomial which is of maximum length.

11. The method of claim 8 in which said linear feedback shift register is defined by a generating polynomial which requires a minimum number of exclusive-OR gates in its feedback arrangement.

12. The method of claim 8 in which said linear feedback shift register is defined by a generating polynomial of the form p(x)=x³¹ +x⁶ +x² +x+1.

13. The method of claim 8 in which said linear feedback shift register is defined by a generating polynomial of the form p(x)=x³¹ =x²⁹ +x¹³ +x¹¹ +1.