Parallel operation linear feedback shift register

• US 5,412,665 A
• Filed: 01/10/1992
• Issued: 05/02/1995
• Est. Priority Date: 01/10/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Szabo, Kurt P., Patel, Piyushkumar C., Gruodis, Algirdas J.
• Primary Examiner(s): Voeltz, Emanuel T.
• Assistant Examiner(s): CHOI, KYLE JAEHUN
• Application Number:
  US07/819,438
• Time in Patent Office: 1,208 Days
• Field of Search: 371/22.4, 371/27, 371/20.1, 371/20.4, 371/20.5, 371/22.1, 371/22.3, 371/22.5, 324/73, 324/158 R
• US Class Current: 714/739
• 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/277 with comparison between actual response and known fault-free response
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• 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 7/584 using finite field arithmetic, e.g. using a linear feedback shift register

Abstract

A parallel operation linear feedback shift-register (LFSR) that generates random test patterns or creates a signature that represents the response of a device under test at ultra high speed using low speed components and/or a slow rate clock. The apparatus is comprised of: a register connected to an external clock, and a plurality of combinatorial logic networks sequentially connected, the last of which drives the register which in turn feeds back into the first of the combinatorial logic networks. Each of the combinatorial networks provides a pseudo-random pattern which are then outputted in parallel, thereby creating a high speed data flow. By providing additional data inputs to the combinatorial networks, the pseudo-random patterns become the signature of the input data.

Claims

1. A Linear Feedback Shift Register (LFSR) for generating random test patterns, comprising:

register means for storing data, said register means comprising a plurality of latches, wherein at least one of said latches is driven by a clock;

a plurality of sequentially connected, functionally equivalent combinatorial logic networks, one of said networks driving said register means, said register means driving a second of said networks to provide a feedback path;

parallel driving means for driving a parallel pattern at an output bus responsive to psuedo-random patterns generated by said networks; and

configuration means inputted to said combinatorial logic networks for reconfiguring said combinatorial logic network that generates said pseudo-random patterns.

2. The LFSR according to claim 1, further comprising input control means inputted to said combinatorial logic networks for controlling said generated pseudo-random patterns, whereby the number of said patterns generated during a clock cycle is reduced.

3. The LFSR according to claim 1, further comprising weighting means responsive to said combinatorial logic networks for weighting said pseudo-random patterns.

4. A Multiple Input Shift Register (MISR) for generating a signature from a plurality of data-in signals, comprising:

register means for storing data, said register means comprising a plurality of latches, wherein at least one of said latches is driven by a clock;

a plurality of sequentially connected, functional equivalent combinatorial logic networks, one of said networks driving said register means, said register means driving a second of said networks to provide a feedback path, each of said networks generating a signature; and

means for receiving a plurality of data-in signals at each of said combinatorial logic networks and for receiving one of said generated signatures, such that one of said generated signatures is combined with said data-in signals to generate a new signature.

5. The MISR according to claim 4, further comprising input control means for controlling data-in signals received at an input bus of said combinatorial logic networks, whereby the number of said signatures generated during a clock cycle is reduced.

6. The MISR according to claim 4, further comprising configuration means inputted to said combinatorial logic networks for reconfiguring said combinatorial logic network that generates said signature.

7. A Linear Feedback Shift Register (LFSR) for generating random test patterns, comprising:

a register for storing data, said register comprising a plurality of latches, wherein each said latch is driven by an external clock;

a plurality of multiplexers (MUXs), each of said MUXs drives one said latch and is provided with two data and one control inputs, the first of said data inputs is a feedback line linking the output of the latch said MUX is driving back into said MUX to inhibit data stored in said latch from being altered, and said control input for providing a signal that selects which data is to appear at the output of said MUX;

a plurality of exclusive-OR circuits (XORs), which number equals the number of said latches, wherein each said XORs subsequent to the first said XORs links one said latches to the next adjacent one via a first data input, wherein the output of each said XORs is connected to the second said two data inputs of said MUX to maintain normal operation of the LFSR, and wherein the first input of the first said XORs for providing data to the first said latches; and

a plurality of dual input AND gates which number is equal to the number of XORs, wherein the output of each said AND gates is connected to said second data input of said XOR, the first of said dual inputs of each said AND gates is connected to the output of the last stage of said register, and the second said dual inputs is respectively connected to one of a plurality of external lines, wherein binary values on said external lines dynamically reconfigure the LSFR by selectively adding a signal from said output of said last latch of said register.

8. The LFSR according to claim 7, further combining said AND gates, XORs and MUXs into a four-inputs and one output XOR Network, said output is comprised of the outputs of said MUXs, the first of said inputs is comprised of the outputs of said register, the second of said inputs is an external skip-cycle line, the third of said inputs is comprised by external configuration lines and the fourth of said inputs provides data to said XOR Network, whereby said skip-cycle line inhibits said XOR network from modifying test data in said register.

9. The LFSR according to claim 7, further comprising said register connected to a weighting network for generating weighted random test patterns.

10. The LFSR according to claim 8, further comprising a plurality of sequentially connected said XOR Networks, wherein one said XOR Networks drives said data register, said data register feeds back into a second of said XOR Networks, and wherein each said XOR Networks are provided data with a configuration input, skip-cycle input and data input, thereby converting the LFSR mode of operation to parallel operation.

11. The LFSR according to claim 9, further comprising a weighting network connected to each said XOR Networks for weighting said patterns.

12. A Linear Feedback Shift Register (LFSR) provided with fixed configuration capabilities, comprising:

a register for storing data, comprising a plurality of latches, wherein each said latch is driven by an external clock;

a plurality of multiplexer circuits (MUXs), each said MUXs drives one of said latches and is provided with two data and one control inputs, the first of said data inputs is a feedback line tying the output of the latch said MUX is driving back into said MUX to inhibit test data stored in said latch from being altered, and said control input is a line for providing a signal that selects which data input will appear at the output of said MUX;

a plurality of exclusive-OR circuits (XORs), in which the number of said XORs is less than the number of said latches in said register, wherein each said XORs links one said latches to the next adjacent one via a first data input, the output of the last said latches of said register provides a second data input to each said XORs, wherein the output of each said XORs is connected to the second said two data inputs of said MUX to maintain normal operation of the LFSR,

wherein the second input of the first said MUXs is provided by the output of the last said latches, and

such that in the absence of one of said XORs connected to one of said MUXs, the output of the previous latch in said register is directly connected to said second data input of said MUX so that test data stored in each of said latches is selectively modified when test data shifts from one of said latches to the next one.

13. The LFSR according to claim 12, further comprising said XORs and MUXs correspondingly combined to form a three input, one output XOR Network, said output is comprised of the outputs of said MUXs, the first input is comprised of the outputs of said register, the second of said inputs providing data to said XOR Network, and the third of said inputs is provided by the external skip-cycle line which inhibits the altering of test data in said register.

14. The LFSR according to claim 13, further comprising weighting means responsive to said XOR Network for generating weighted random patterns.

15. The LFSR according to claim 13, further comprising a plurality of sequentially connected said XOR Networks, wherein one said XOR Networks drives said register, said register feeds back into a second of said XOR Networks, and wherein said XOR Networks are provided each with inputs, comprising a configuration input, and a skip-cycle input, whereby converting the LFSR mode of operation to parallel mode.

16. The LFSR according to claim 15, wherein each said XOR Networks is connected to a weighting network for providing weighted random patterns.

17. A Multiple Input Shift Register (MISR) for generating a signature from plural data-in signals, comprising:

a register for storing data, said register comprising a plurality of latches, wherein each said latch is driven by an external clock;

a plurality of multiplexer circuits (MUXs), each said MUXs drives one of said latches and is provided with two data and one control inputs, the first of said data inputs is a feedback line linking the output of the latch said MUX is driving back into said MUX to inhibit test data stored in said latch from being altered, and said control input for providing a signal that selects which data input will appear at the output of said MUX;

a plurality of exclusive-OR circuits (XORs), which number equals the number of said latches, for generating a signature, wherein each said XORs subsequent to the first said XORs links one said latches to the next adjacent one via a first data input, wherein the output of each said XORs is connected to the second said two data inputs of said MUX to maintain normal operation of the MISR, wherein the first input of the first said XORs provides data to the first said latches, and wherein at least one of said XORs is provided with a third input for providing data; and

a plurality of dual input AND gates which number is equal to the number of XORs, such that the output of each said AND gates is connected to said second data input of said XOR, the first of said dual inputs of each said AND gates is connected to the output of the last stage of said register, and the second said dual inputs is respectively connected to a line, wherein a binary value on said line dynamically reconfigures the MISR by selectively adding a signal from said output of said last latch of said register.

18. The MISR according to claim 17, further comprising said AND gates, XORs and MUXs correspondingly combined into a four inputs, one output XOR Network, said output is comprised of the outputs of said MUXs, the first input is comprised of the outputs of said register, the second of said inputs providing data to said XOR Network, the third of said inputs is comprised of external configuration lines, and the fourth of said inputs is the skip-cycle line which inhibits the altering of said signature.

19. The MISR according to claim 18, further comprising a plurality of said XOR Networks sequentially connected, wherein one said XOR Networks drives said data register means, said data register means feeds back into a second of said XOR Networks, and wherein said XOR Networks are additionally provided each with a configuration input, a skip-cycle input and data inputs, whereby converting the MISR mode of operation to a parallel mode.