Arithmetic built-in self test of multiple scan-based integrated circuits

What is claimed is:

1. An apparatus comprising:

a processor core including data paths;

a plurality of peripheral devices having associated parallel scan registers coupled to the processor core; and

operating logic for generating pseudo-random test patterns for the peripheral devices, employing a mixed congruential generation scheme, and using the data paths of the processor core.

2. The apparatus as set forth in claim 1, wherein the operating logic includes operating logic for multiplying n least significant bits of a 2n-bit pseudo-random number generated in an immediately preceding iteration and stored in a first register, with an n-bit multiplier constant stored in a second register to produce a 2n-bit product, adding the 2n-bit product to n most significant bits of the 2n-bit pseudo-random number stored in n least significant locations of an accumulator with 2n locations to produce a new 2n-bit pseudo-random number for a current iteration, and outputting n least significant bits of the new 2n-bit pseudo-random number as an n-bit pseudo-random test vector for the peripheral devices.

3. The apparatus as set forth in claim 2, wherein the operating logic further includes operating logic for copying the n least significant bits of the new 2n-bit pseudo-random number into the first register, and right shifting the 2n-bit new pseudo-random number in the accumulator by n-bits.

4. The apparatus as set forth in claim 3, wherein the operating logic further includes operating logic for repeating said multiplying, adding, outputting, copying and right shifting sufficient number of times to generate a sufficiently large pseudo-random test pattern to fill the parallel scan registers.

5. The apparatus as set forth in claim 2, wherein the operating logic further includes operating logic for storing a 2n-bit initial value into the accumulator, and storing the n-bit multiplier constant in the second register.

6. The apparatus as set forth in claim 5, wherein the variable n, the 2n-bit initial value and the n-bit multiplier constant are equal to (3, 6, 1), (3, 6, 5), (4, 15, 1), (4, 15, 7), (5, 27, 1), (5, 27, 5), (6, 45, 1), (6, 45, 7), (7, 126, 1), (7, 126, 5), (8, 249, 1), (8, 249, 5), (9, 507, 1) (9, 507, 5), (10, 1020, 1), (10, 1020, 5), (11, 2016, 1), (11, 2016, 5), (12, 4077, 1), (12, 4077, 7), (13, 8175, 1), (13, 8175, 7), (14, 16371, 1), (14, 16371, 5), (15, 32766, 1), (15, 32766, 5), (16, 65514, 1), or (16, 65514, 5) respectively.

7. The apparatus as set forth in claim 2, wherein the apparatus further comprises a test port register through which the parallel scan registers are coupled to the processor core, and the operating logic further includes operating logic for moving a pseudo-random test vector from the processor core to the test port register, and then moving the pseudo-random test vector in parallel to the parallel scan registers.

8. The apparatus as set forth in claim 7, wherein the test port register comprises a plurality of output ports correspondingly coupled to first cells of the parallel scan registers, and a plurality of input ports correspondingly coupled to last cells of the parallel scan registers.

9. The apparatus as set forth in claim 7, wherein the operating logic further includes operating logic for applying one or more clock cycles to the peripheral devices to apply the test pattern in the parallel scan registers to the peripheral devices.

10. The apparatus as set forth in claim 7, wherein the operating logic further includes operating logic for moving test responses of the peripheral devices from the test port register to the processor core.

11. The apparatus of claim 1 wherein the operating logic is further for generating deterministic test patterns for the peripheral devices, emulating a plurality of linear feedback shift register (LFSR)-based segments interconnected by a network of linear functions, and using the data paths of the processor core.

12. The apparatus as set forth in claim 11, wherein the operating logic includes operating logic for modifying n.times.L storage locations of a circular buffer formed with L registers, each having n storage locations, emulating shifting of the content of the LFSR-based segments, and outputting the content of a head one of the L registers as a portion of a deterministic test pattern being generated for the peripheral devices.

13. The apparatus as set forth in claim 12, wherein the operating logic further includes operating logic for repeating said modification and outputting sufficient number of times to generate a sufficiently large deterministic test pattern to fill the parallel scan registers.

14. The apparatus as set forth in claim 12, wherein the operating logic further includes operating logic for advancing a head pointer for identifying the head one of the L registers.

15. The apparatus as set forth in claim 11, wherein the operating logic generates the deterministic test patterns emulating LFSR-based segments interconnected with a network of linear functions that implements an identical feedback polynomial for each of the LFSR-based segments.

16. The apparatus as set forth in claim 11, wherein the operating logic generates the deterministic test patterns emulating LFSR-based segments interconnected with a network of linear functions that provides inter-segment feedback at identical tap positions of the LFSR-based segments.

17. The apparatus as set forth in claim 11, wherein the apparatus further comprises a test port register through which the parallel scan registers are coupled to the processor core, and the operating logic further includes operating logic for moving a deterministic test vector from the processor core to the test port register, and then moving the pseudo-random test vector in parallel to the parallel scan registers.

18. The apparatus of claim 1 wherein the operating logic is further for compacting test responses from the peripheral devices, employing a cascaded approach, and using the data paths of the processor core.

19. The apparatus as set forth in claim 18, wherein the operating logic includes operating logic for moving a first test response into a first accumulator, adding a first signature to the first accumulator, moving a second test response into a second accumulator, outputting the content of the first accumulator and adding the output of the first accumulator into the second accumulator.

20. The apparatus as set forth in claim 19, wherein the operating logic further includes operating logic for moving the second test response into the first accumulator, adding a second signature that includes the first test response into the first accumulator, moving a third test response into the second accumulator, outputting the content of the first accumulator, and adding the output of the first accumulator to the second accumulator.

21. The apparatus as set forth in claim 20, wherein the operating logic adds the output of the first accumulator into the second accumulator in accordance with a 1's complement convention.

22. The apparatus as set forth in claim 20, wherein the operating logic adds the output of the first accumulator into the second accumulator using a rotate carry scheme.

23. The apparatus as set forth in claim 18, wherein the apparatus further comprises a test port register through which the parallel scan registers are coupled to the processor core, and the operating logic further includes operating logic for moving a test response of the peripheral devices from the test port register to the processor core.

24. The apparatus as set forth in claim 23, wherein the test response of the peripheral devices is recovered in the test port register as an integral part of storing a test vector in parallel into the parallel scan registers.

25. The apparatus of claim 1 wherein the operating logic is further for placing the processor core in a test mode, saving a pre-test state of the parallel scan registers, applying a plurality of test patterns to the peripheral devices using the data paths of the processor core, and restoring the pre-test state of the parallel scan registers.

26. A method for generating pseudo-random test patterns comprising the steps of:

multiplying n least significant bits of a 2n-bit pseudo-random number generated in an immediately preceding iteration and stored in a first register, with an n-bit multiplier constant stored in a second register to produce a 2n-bit product,

adding the 2n-bit product to n most significant bits of the 2n-bit pseudo-random number stored in n least significant locations of an accumulator with 2n locations to produce a new 2n-bit pseudo-random number for a current iteration, and

outputting n least significant bits of the new 2n-bit pseudo-random number as an n-bit pseudo-random test vector for a plurality of peripheral devices.

27. The method as set forth in claim 26, wherein the method further includes the step of copying the n least significant bits of the new 2n-bit pseudo-random number into the first register, and right shifting the 2n-bit new pseudo-random number in the accumulator by n-bits.

28. The method as set forth in claim 27, wherein the method further includes the step of repeating said multiplying, adding, outputting, copying and right shifting steps sufficient number of times to generate a sufficiently large pseudo-random test pattern to fill a plurality of parallel scan registers.

29. The method as set forth in claim 26, wherein the method further includes the step of storing a 2n-bit initial value into the accumulator, and storing the n-bit multiplier constant in the second register.

30. The method as set forth in claim 29, wherein the variable n, the 2n-bit initial value and the n-bit multiplier constant are equal to (3, 6, 1), (3, 6, 5), (4, 15, 1), (4, 15, 7), (5, 27, 1), (5, 27, 5), (6, 45, 1), (6, 45, 7), (7, 126, 1), (7, 126, 5), (8, 249, 1), (8, 249, 5), (9, 507, 1) (9, 507, 5), (10, 1020, 1), (10, 1020, 5), (11, 2016, 1), (11, 2016, 5), (12, 4077, 1), (12, 4077, 7), (13, 8175, 1), (13, 8175, 7), (14, 16371, 1), (14, 16371, 5), (15, 32766, 1), (15, 32766, 5), (16, 65514, 1), or (16, 65514, 5) respectively.

31. The method as set forth in claim 26, wherein the method further comprises the step of moving a pseudo-random test vector to a test port register, and then moving the pseudo-random test vector in parallel to a plurality of parallel scan registers.

32. The method of claim 26 further comprising generating deterministic test patterns comprising the steps of:

modifying n.times.L storage locations of a circular buffer formed with L registers, each having n storage locations,

emulating shifting of the content of a plurality of LFSR-based segments, and

outputting the content of a head one of the L registers as a portion of a deterministic test pattern being generated.

33. The method as set forth in claim 32, wherein the method further includes the step of repeating said modifying and said outputting the content a sufficient number of times to generate a sufficiently large deterministic test pattern to fill a plurality of parallel scan registers.

34. The method as set forth in claim 32, wherein the method further includes the step of advancing a head pointer for identifying the head one of the L registers.

35. The method as set forth in claim 32, wherein the emulation step emulates shifting of LFSR-based segments interconnected with a network of linear functions that implements an identical feedback polynomial for each of the LFSR-based segments.

36. The method as set forth in claim 32, wherein the emulation step emulates shifting of LFSR-based segments interconnected with a network of linear functions that provides inter-segment feedback at identical tap positions of the LFSR-based segments.

37. The method as set forth in claim 32, wherein the method further comprises the steps of moving a deterministic test vector to a test port register, and then moving the deterministic test vector in parallel to the plurality of parallel scan registers.

38. The method of claim 26 further comprising the steps of:

moving a first test response into a first accumulator,

adding a first signature to the first accumulator,

moving a second test response into a second accumulator,

outputting the content of the first accumulator and

adding the output of the first accumulator into the second accumulator.

39. The method as set forth in claim 38, wherein the method further includes the step of:

moving the second test response into the first accumulator,

adding a second signature that includes the first test response into the first accumulator,

moving a third test response into the second accumulator,

outputting the content of the first accumulator, and

adding the output of the first accumulator to the second accumulator.

40. The method as set forth in claim 39, wherein the step of adding of the output of the first accumulator into the second accumulator is performed in accordance with a 1's complement convention.

41. The method as set forth in claim 39, wherein the step of adding the output of the first accumulator into the second accumulator is performed using a rotate carry scheme.

42. The method as set forth in claim 38, wherein the method further comprises the step of moving a partial test response from a test port register.

43. The method as set forth in claim 42, wherein the step of moving the partial test response is performed as an integral part of a step of providing a test vector from the test port register.

44. The method of claim 26 further wherein the test patterns are generated using mission data paths of a processor core, and the test patterns are used for testing peripheral devices of an integrated circuit, the method further comprising the steps of:

loading a plurality of parallel scan registers with a first set of test patterns from a test port register, one bit slice for each scan register at a time, and simultaneously recovering test responses for a previously generated second set of test patterns from the parallel scan registers into the test port register, one bit slice per scan register a time;

moving the test responses into the processor core; and

compacting the test responses into a signature.

45. The method as set forth in claim 44, wherein the method further includes the step of applying one or more clock cycles to the peripheral devices to apply the first set of test patterns in the parallel scan registers to the peripheral devices.

46. The method of claim 26 further comprising the steps of:

placing a processor core in a test mode;

saving a pre-test state of a plurality of parallel scan registers;

applying a plurality of the test patterns to a plurality of peripheral devices using the data paths of the processor core and the parallel scan registers; and

restoring the pre-test state of the parallel scan registers.

47. The method as set forth in claim 46 further comprising compacting test responses of the peripheral devices using the data paths of the processor core.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to testing of integrated circuits (IC) and more particularly to arithmetic built-in self-test (ABIST) of multiple scan-based ICs.

2. Background Information

Many ICs are produced in large volume and very often operate at high speeds. Since their manufacturing yield strongly depends on the silicon area, and their performance is directly related to the delays on critical paths, it is essential that the testing strategy provides a high fault coverage without a significant area overhead and performance degradation. As the costs associated with detecting faults rise over thousands of times from the time ICs are fabricated to the time the final product is released to customers, the most effective way to prevent costly rework is to consider testing issues as early in the design cycle as possible. Practical importance of this problem in conjunction with the increasing complexity of VLSI circuits not balanced by a corresponding increase in the number of input and output pins, has made built-in self-test (BIST) one of the most important technology in IC testing that is expected to profoundly influence the area requirement of ICs in upcoming years.

In BIST, the original circuit designed to perform the system functions is appended with additional circuitry for generation of test patterns.sup.1 and compaction of test responses. Thus, the BIST approach can be applied at all levels of testing, starting from wafer and device to system and field testing. Appending these circuitry to the original circuit satisfies the high fault coverage requirement while reducing the dependence on expensive external testing equipment. However, this solution compromises an IC's area and performance as it inevitably introduces either a hardware overhead or additional delays and increased latency. These delays may be excessive for high-speed ICs used in several applications such as high-performance microprocessors, digital signal processing (DSP) systems, new generations of floating point processors, and others. Therefore, BIST schemes are often evaluated on the basis of the fault coverage they provide, area overhead they require, and the performance penalty they produce. Other criteria include test application time, scalability, and test-pattern portability. For further description of BIST, see, for example, V. D. Agrawal, C. R. Kime, and K. K. Saluja, "A Tutorial on Built-In Self Test. Part 1: Principles", IEEE Design and Test of Computers, March 1993, pp. 73-82, and V. D. Agrawal, C. R. Kime, and K. K. Saluja, "A Tutorial on Built-In Self-Test. Part 2: Applications", IEEE Design and Test of Computers, June 1993, pp. 69-73.

High fault coverage in BIST can be achieved only if all faults of interest are detected, and their effects are retained in the final compacted signature. A number of test pattern generation and test response compaction techniques have been proposed in the open literature and are used in the industrial practice. The majority of these techniques employ Linear Feedback Shift Registers (LFSRs), Multiple Input Signature Registers (MISRs), or Cellular Automata (CAs), as implementation platforms to cope with various types of failures and errors, and to support variety of test scenarios.

An efficient test pattern generator which guarantees complete fault coverage while minimizing test application time, area overhead, and test data storage is clearly essential for a successful BIST scheme. The generation schemes proposed in the art so far offer trade-offs between these parameters. The solutions range from pseudo-random techniques that do not use any storage (for test data) but take a long application time and often do not detect some faults to deterministic techniques that may require significant storage but achieve complete fault coverage in a relatively short time. Since most of the traditional design for testability (DFT) techniques use internal and external scan paths, several test pattern generators for incorporating into these designs have been also employed. They differ in the requirements placed on the nature of produced test vectors and on the scan-path features they utilize. A common drawback of the scan-path techniques is a long test application time due to the need to scan data in and out of the circuit. This usually alleviated by breaking the scan chain (also referred to as the scan register) into many shorter paths which are loaded in parallel from the generator, and scanned out in parallel to a signature generator. Consequently, a number of techniques have been proposed in the art for two-dimensional test-sequence generation. They are mostly based on LFSRs as shown for example by W. J. Hurd in the paper entitled "Efficient Generation of Statistically Good Pseudonoise by Linearly Interconnected Shift Resisters", IEEE Trans. Computers, vol. C-23, 1974, pp. 146-152, and, due to structural and linear dependencies, may not be able to produce some test patterns.

In general, schemes based on pseudo-random patterns may fail to detect some faults in some circuits due to inherent limitations of pseudo-random test vectors. In such a case, deterministic patterns are used to target the remaining hard-to-test faults. Using these deterministic patterns in conjunction with the pseudo-random patterns allows obtaining different trade-offs between test data storage and test application time by varying the relative number of deterministic and pseudo-random patterns. However, the overall efficiency of BIST scheme resting on such mixed-mode generation techniques strongly depends on the methods employed to reduce the amount of test data.

The quantity of test data can be reduced by compressing deterministic test patterns. This approach rests on the fact that the deterministic test patterns frequently feature a large number of unspecified positions. A compression method based on the reseeding of LFSRs has been originally proposed by B. Koenemann in the paper entitled "LFSR-Coded Test Patterns for Scan Designs", in Proc European Test Conf., Munich 1991, pp. 237-242. A comprehensive analysis of this scheme as well as a new reseeding scenario based an Multiple Polynomial Linear Feedback Shift Registers (MP-LFSRs) has been provided by S. Hellebrand, J. Rajski, S. Tarnick, S. Venkataraman and B. Courtois in the paper entitled "Built-In Test for Circuits with Scan Based on Reseeding of Multiple-Polynomial Linear Feedback Shift Registers", IEEE Trans. on Computers, vol. C-44, February 1995, pp. 223-33. A similar technique has been also discussed by S. Hellebrand, B. Reeb, S. Tarnick, and H.-J. Wunderlich in the paper entitled "Pattern Generation for a Deterministic BIST Scheme", in Proc. ICCAD, November 1995, pp. 88-94. Using this method, a concatenated group of test cubes with a total of s specified bits is encoded with approximately s bits specifying a seed and a polynomial identifier. The content of the MP-LFSR is loaded for each group, and has to be preserved during the decompression of each test cube within the group. An alternative to concatenation was proposed by N. Zacharia, J. Rajski, and J. Tyszer in the paper entitled "Decompression of Test Data using Variable-Length Seed LFSRs", Proc. VLSI Test Symposium, Princeton 1995, pp. 426-33. The underlying idea rests on the concept of variable-length seeds. Deterministic patterns are generated by an LFSR loaded with the seeds whose lengths may be smaller than the size of the LFSR. Allowing such "shorter" seeds yields higher encoding efficiency even for test cubes with varying number of specified positions.

Efficiency of the test response compaction techniques, in common with the test generation schemes, is another essential factor for a successful BIST scheme. Many schemes have been proposed to compact test responses in the conventional BIST environments. The best-known compaction techniques are based on LFSRs, CAs, counters and check sums. Extensive theoretical studies have been conducted to analyze both the asymptotic and transient behavior of the aliasing probability (i.e., the average probability of no faults being detected due to compaction after a sufficiently long test experiment) introduced by these schemes. The most commonly used compactors for compaction of parallel responses in the multiple scan environments are based on the MISRs. They introduce the aliasing probability of 2.sup.-n, where n is the size of the register, and their transient behaviors depend on the characteristic polynomials. A systematic review of the compaction schemes and related theoretical results is provided by S. Pilarski and T. Kameda in A Probabilistic analysis of test-response compaction, IEEE Computer Society Press, 1995.

Circuits based on data-path architectures constitute an increasingly large portion of integrated chips manufactured by the microelectronics industry. The proliferation of embedded cores and high-performance computing systems, such as DSP circuits, micro-controllers, and micro-processors clearly demonstrates inadequacy of existing BIST schemes if they are to entail non-intrusive, at-speed and portable testing. Recently, a new BIST paradigm was proposed by S. Adham, M. Kassab, N. Mukherjee, K. Radecka, J. Rajski, and J. Tyszer in the paper entitled "Arithmetic built-in self-test for digital signal processing architectures", Proc. CICC, pp. 659-662, 1995, which makes it possible to use the functionality of these circuits (also referred to as mission logic or mission data paths) to perform built-in self-test for a DSP core rather than adding test hardware which can introduce area overhead and performance degradation. The resulting test sessions are controlled by microcode and use the mission data path building blocks, such as adders, multipliers, and ALUs, to generate test patterns for a DSP core, and compact its test responses. In such an environment, the need for extra hardware is either entirely eliminated or drastically reduced, test vectors are easily distributed to different parts of the DSP core, test responses are easily collected, and there is virtually no performance degradation. Furthermore, the approach can be used for at-speed testing, thereby providing a capability to detect failures that may not be detected by conventional low-speed testing. However, the ABIST proposal presented in the Adham article did not address generation of test patterns for peripheral devices, in particular, peripheral devices with "shortened" multiple scan-chains in ICs.

Thus, it is desirable to be able to extend the ABIST methodology to provide efficient BIST methods for multiple scan-based ICs, and tailoring the ABIST to conventional DFT environmental.

SUMMARY OF THE INVENTION

In accordance with one aspect of the present invention, an IC with an embedded processor core, peripheral devices, and associated multiple scan chains, is provided with microcode that implements an arithmetic pseudo-random number generator, which when executed by the embedded processor core, generates two-dimensional (2-D) pseudo-random test vector sequences for testing the peripheral devices. The arithmetic pseudo-random number generator employs an improved mixed congruential generation scheme.

In accordance with another aspect of the present invention, the IC is further provided with microcode that implements an arithmetic parallel decompressor, which when executed by the embedded processor core, generates 2-D deterministic test vectors for testing the peripheral devices. The arithmetic parallel decompressor generates multiple segments of each deterministic test vector in parallel, emulating a number of LFSR-based segments interconnected by a network of linear functions.

In accordance with yet another aspect of the present invention, the IC is further provided with microcode that implements an arithmetic test response compactor, which when executed by the embedded processor core, compacts test responses of the peripheral devices into a signature. The arithmetic test response compactor compacts the test responses in a cascaded add-and-accumulate manner, reducing the impact of an error compensation phenomenon.

In accordance with yet another aspect of the present invention, the IC is further provided with a test port register for interfacing between the embedded processor core and the multiple scan chains associated with the peripheral devices, providing the multiple scan chains with the pseudo-random and deterministic test vectors generated by the embedded processor core, and returning the test responses of the peripheral devices to the embedded processor core (through the multiple scan chains).

In accordance with yet another aspect of the present invention, the IC is further provided with microcode that implements a number of instructions for moving the generated pseudo-random and deterministic test vectors to the test port register, and then to the scan chains, applying the test vectors to the circuits under test (i.e. the peripheral devices), and moving the test responses from the test port register and then to the embedded processor core. In one embodiment, the test responses are moved from the scan chains to the test port register, as an integral part of moving test vectors into the scan chains.

BRIEF DESCRIPTION OF DRAWINGS

The present invention will be described by way of exemplary embodiments, but not limitations, illustrated in the accompanying drawings in which like references denote similar elements, and in which:

FIG. 1 illustrates an exemplary IC incorporated with the teachings of the present invention;

FIG. 2 illustrates one embodiment of the method steps for performing ABIST for the exemplary IC in accordance with the present invention;

FIGS. 3-4 illustrate one embodiment of the arithmetic pseudo-random generator of the present invention;

FIGS. 5-7 illustrate one embodiment of the arithmetic parallel decompressor of the present invention;

FIGS. 8-10 illustrate one embodiment of the arithmetic test response compactor of the present invention;

FIG. 11 illustrate one embodiment of the ABIST instructions provided to the exemplary IC; and

FIGS. 12-14 illustrate generation deterministic test vectors.

DETAILED DESCRIPTION OF THE INVENTION

In the following description, various aspects of the present invention will be described. However, it will be apparent to those skilled in the art that the present invention may be practiced with only some or all aspects of the present invention. For purposes of explanation, specific numbers, materials and configurations are set forth in order to provide a thorough understanding of the present invention. However, it will also be apparent to one skilled in the art that the present invention may be practiced without the specific details. In other instances, well known features are omitted or simplified for clarity.

Parts of the description will be presented in terms of operations performed inside an integrated circuit with an embedded processor core and peripheral devices, using terms such as data, bits, values, numbers and the like, consistent with the manner commonly employed by those skilled in the art to convey the substance of their work to others skilled in the art. As well understood by those skilled in the art, these quantities take the form of electrical signals capable of being stored, transferred, combined, and otherwise manipulated through electrical elements of the IC; and the term embedded processor core include microcontroller, microprocessor, digital signal processor (DSP) cores, and the like.

Various operations will be described as multiple discrete steps performed in turn in a manner that is most helpful in understanding the present invention. However, the order of description should not be construed as to imply that these operations are necessarily order dependent.

Referring now to FIG. 1, wherein an exemplary IC incorporated with the teachings of the present invention is shown. Exemplary IC 10 includes embedded processor core 12, peripheral devices 14 having multiple associated scan registers 16, non-volatile memory 18, and test port register 20, coupled to each other as shown. Peripheral devices 14 are also designated as circuit under test (CUT), whereas scan registers 16 are also referred to as scan chains. Except for test port register 20, ABIST instructions provided to processor core 12, and the manner embedded processor core 12, scan registers 16, and non-volatile memory 18 are used to practice various aspects of the present invention, embedded processor core 12, peripheral devices 14, scan registers 16, and non-volatile memory 18 perform their conventional functions known in the art. They are intended to represent a broad category of these elements known in the art. In other words, except for test port register 20, ABIST instructions provided to processor core 12, and the manner the various other elements are used to practice the present invention, exemplary IC 10 is intended to represent a broad category of ICs known in the art.

As will be described in more detail below, non-volatile memory 18 includes various microcode that implement an arithmetic pseudo-random number generator, an arithmetic parallel decompressor and a test response compactor of the present invention. When executed by embedded processor core 12, the arithmetic pseudo-random number generator generates 2-D pseudo-random test vector sequences, whereas the arithmetic parallel decompressor generates 2-D deterministic test vectors for testing peripheral devices 14. When executed by embedded processor core 12, the arithmetic test response compactor compacts test responses of peripheral devices 14 into a signature.

Test port register 20 serves as an interface between embedded processor core 12 and scan registers 16. For ease of explanation, the data path between embedded processor core 12 and test port register 20 for the illustrated embodiment is n-bit wide, and there are n scan registers 16, each having the same length L (i.e. L.sub.1, L.sub.2, . . . , L.sub.n-1 all equal L). However, based on the descriptions to follow, those skilled in the art will appreciate that the present invention may by practiced with data path of any size, any number of scan registers of any identical or different lengths. For the illustrated embodiment, test port register 20 includes a number of output ports correspondingly coupled to the first cell of each of scan registers 16, and a number of input ports correspondingly coupled to the last cell of each of scan registers 16. Test port register 20 may be constituted in any one of a number of manners known in the art.

Embedded processor core 12 includes data paths formed with adders, multipliers, ALUs, shifters, registers, etc. Embedded processor core 12 further includes microcode (e.g. in a control store) that implements the ABIST instructions, including instructions for moving the generated pseudo-random/deterministic test vectors to test port register 20 and then to scan registers 16, applying the test vectors to peripheral devices 14, and moving test responses of the peripheral devices 14 from test port register 20 to embedded processor core 12. For the illustrated embodiment, test vectors are shifted into scan registers 16 from test port register 20 by one of the ABIST instructions, and test responses are recovered into test port register 20 from scan registers 16 at the same time, as an integral part of the shifting operation.

In other words, in accordance with the present invention, exemplary IC 10 is provided with ABIST through microcode that leverage on the mission logic of embedded processor core 12, requiring only one extra register in terms of hardware, i.e. test port register 20. Thus, there are virtually no area requirement, nor performance impact on IC 10. Before further describing how ABIST is provided to exemplary IC 10, it should be noted that why the present invention is being described with the exemplary 10 having non-volatile memory 18 storing the various microcode implementing the arithmetic pseudo-random test vector generator, arithmetic parallel decompressor, and arithmetic test response compactors, and so forth, the present invention may be practiced with some or all of the microcode stored in non-volatile or volatile storage medium disposed inside or outside the IC.

FIG. 2 illustrates one embodiment of the method steps for performing ABIST for exemplary IC 10 in accordance with the present invention. As shown, for the illustrated embodiment, in step 21, embedded processor core 12 is first placed into a test mode. In step 22, one or more 2-D pseudo-random or deterministic test vectors are generated using mission data paths of embedded processor core 12 to execute the arithmetic pseudo-random number generator or the arithmetic parallel decompressor of the present invention. The generated 2-D pseudo-random/deterministic test vectors are provided to peripheral devices 14, by way of test port register 20 and scan registers 16, one bit-slice for each scan register at a time for L times. At the same time, test responses to a prior set of test vectors are recovered into embedded processor core 12 from scan registers 16 by way of test port register 20, one bit-slice from each scan register at a time for L times, except of course for the initial provision of test vectors, where the pre-test state of scan registers 16 is recovered instead. The partial test responses are compacted into a signature as they are recovered, using also mission data paths of embedded processor core 12 to execute the arithmetic test response compactor, except of course for the initial application of the first set of test vectors, where the recovered pre-test state of scan registers 16 is saved instead. As in the prior art, pseudo-random test vectors are used to detect most of the faults, whereas deterministic test vectors are used to detect the minority of faults that are known to be difficult to detect.

In step 23, the generated 2-D pseudo-random/deterministic test pattern (i.e. one or more test vectors/cubes) is applied to the circuits under test (i.e. peripheral devices 14).

Steps 22-23 are repeated until it is determined in step 24 all desired test patterns have been generated and applied to peripheral devices 14. Then, in step 25, the save pre-test state of scan registers 16 is restored, one bit slice for each scan register at a time for L times. At the same time, test responses to the last set of test vectors are recovered, one bit slice from each scan register at a time for L times. The partial test responses to the last set of test vectors are compacted into the signature as they are recovered, as earlier described.

FIGS. 3-4 illustrate one embodiment of the arithmetic pseudo-random number generator of the present invention. The arithmetic pseudo-random number generator generates two-dimensional pseudo-random test vector sequences, using an improved mixed congruential generation scheme. The scheme operates in accordance with the following rule:

PRN.sub.i =nLSB(PRN.sub.i-1).times.M+nMSB(PRN.sub.i-1)

where PRN.sub.i stands for the pseudo-random number after ith iteration,

nLSB() stands for the n least significant bits,

nMSB() stands for the n most significant bits, and

M stands for an n-bit constant.

In other words, the pseudo-random number after ith iteration is generated by multiplying the n least significant bit of the pseudo-random number of the previous iteration with the constant M and then adding the result to the n most significant bits of the pseudo-random number of the previous iteration. The scheme is superior to prior art pseudo-random techniques in providing pseudo-random sequences on designated bit positions.

As shown in FIG. 3, for the illustrated embodiment, the scheme is practiced by using registers 30 and 32, multiplier 34, adder 36 and accumulator 38 of embedded processor core 12. Initially, as shown in FIG. 4, in step 40, the initial value (PRN.sub.0) and the n-bit constant (M) are loaded into accumulator 38 and register 30 respectively. In step 41, the n least significant bits of the content of accumulator 38 (i.e., PRN.sub.0) are copied into test port register 20 (to output the initial test vector) and register 32 (to prepare for the next iteration). In step 42, accumulator 38 is shifted right n-bit (to prepare for the next iteration). In step 43, the content of register 32, i.e., PRN.sub.i-1, is multiplied by the content of register 30, i.e., M. In step 44, the output of multiplier 34 is added to the content of accumulator 38. In step 45, as in step 41, the n least significant bits of the content of accumulator 38 (i.e., PRN.sub.i) are copied into test port register 20 and register 32. In step 46, as in step 42, accumulator 38 is shifted right n-bit again. In other words, after the first PRN, at each clock cycle, a PRN (and therefore a test vector) may be generated. Each n-bit test vector is provided to scan chains 16 in parallel by way of test port register 20, providing 1-bit to each scan chain 16. Thus, after L-1 iterations of steps 43-46 (L being the length of a scan chain 16), scan chains 16 will be filled with a 2-D pseudo-random test pattern.

A primary desirable property of any pseudo-random number sequence that is to be used as source for pseudo-random test vectors is a long period. Experience has shown that various combinations of initial values and multipliers M produce sequences with more desirable periods for various sizes of data paths. These combinations are summarized in Table 1. For instance, for a 3-bit wide data path (n), with an initial value of 1 (PRN.sub.0) and a multiplier value of 6 (M), the arithmetic pseudo-random number generator generates the sequence of 1, 6, 36, 28, 27, 21, 32, 4, 24, 3, 18, 14, 37, 34, 16, 2, 12, 25, 9, 7, 42, 17, 8 and 1 (a period of 23). Similarly, for the 3-bit wide data path, with an initial value of 5 (PRN.sub.0) and a multiplier value of 6 (M), the arithmetic pseudo-random number generator generates the sequence of 5, 30, 39, 46, 41, 11, 19, 20, 26, 15, 43, 23, 44, 29, 33, 10, 13, 31, 45, 35, 22, 38, 40, and 5 (also a period of 23). For all the combinations shown, almost in all cases, the period is close to 2.sup.2n-1. Thus, any 2.sup.2n random numbers (and therefore test vectors) may be generated by choosing two initial values in combination with a multiplier M.

TABLE 1 ______________________________________ Period Lengths by data path sizes, initial values, and multipliers. n M Initials Period n M Initials Period ______________________________________ 3 6 1, 5 23 10 1020 1, 7 522239 4 15 1, 7 119 11 2016 1, 5 2064383 5 27 1, 5 431 12 4077 1, 7 8349695 6 45 1, 7 1439 13 8175 1, 7 33484799 7 126 1, 5 8063 14 16371 1, 5 134111231 8 249 1, 5 31871 15 32766 1, 5 536838143 9 507 1, 5 129791 16 65514 1, 5 2146762751 ______________________________________

The ability to produce any q-tuple, regardless of location of bits of interest, is the next quality criteria considered. In contrast to LFSR-based generators, the arithmetic pseudo-random test vector generator of the present invention features non-linear dependencies originating from the congruential multiplicative formula used. These dependencies have been examined by Monte Carlo simulations with the objective of determining the probability that randomly selected q positions of the output sequence cannot be covered by some combinations of 0s and 1s, i.e., given a sequence of generated bits, it is verified whether the sequence contains q-bit pattern of 0s and 1s which matches a pre-computed vector of binary values and distances between positions on which these values occur. The Monte Carlo simu