Test method of semiconductor intergrated circuit and test pattern generator

A semiconductor integrated circuit test method which reduces the required data volume for testing and efficiently detects faults in a circuit to be tested, the method comprising means 110 to generate identical pattern sequences repeatedly and means 120 to control flipped bits in pattern sequences, in order to generate neighborhood pattern sequences and use the neighborhood patterns to test the circuit under test 130. The neighborhood patterns include, in whole or in part, such pattern sequences as ones without flipped bits, ones with all or some flipped bits in one pattern and ones with all or some flipped bits in consecutive patterns or patterns at regular intervals, the interval being equivalent to a given number of patterns. Because a test pattern generator is provided independently of the circuit to be tested, the problem of a prolonged design period can be eliminated, a loss in the operating speed of the circuit under test is minimized and a high fault coverage can be achieved with less hardware overhead and a smaller volume of test data.

FIELD OF THE INVENTION

This invention relates to a semiconductor integrated circuit test method, and a test pattern generator and semiconductor integrated circuit which are used in the test method.

BACKGROUND OF THE INVENTION

Typical test methods for checking whether a semiconductor integrated circuit is acceptable or not are a stored test method and a built-in self-test method (BIST). In the stored test method, a test pattern for an assumed fault is obtained according to an algorithm and applied to the circuit to be tested through a test device which stores the pattern for comparison of response pattern from the circuit with an expected pattern. In the BIST method, the semiconductor integrated circuit incorporates a pseudo-random pattern generator and a signature analyzer to give a huge volume of pseudo-random patterns to the circuit to be tested and compare the compacted result of response pattern with an expected pattern.

The stored test method has the following problem: in order to achieve a high fault coverage for a large-scale circuit to be tested, the required number of test patterns or the required volume of test data is too large for the semiconductor integrated circuit test device to store such patterns or data. The problem of the BIST method is that, since pseudo-random patterns generated by a linear feedback shift register (LFSR) are used, the required volume of test data is relatively small but a high fault coverage cannot be guaranteed when a limited number of pseudo-random patterns are used for a large-scale circuit.

Many proposals for improvement in the fault coverage by the BIST method have been made. In the test point insertion methods disclosed in J-P-A-No. 197601/1998 and J-P-A-No. 142481/1999, a circuit called a test point is added to the circuit under test to achieve a high fault coverage even with random patterns. According to the procedure described in a paper by K. H. Tsai et al, entitled “STARBIST: Scan Autocorrelated Random Pattern Generation” (literature: Proceeding of Design Automation Conference '97. 1997, pp. 472-477), in order to generate neighborhood patterns each of which has one bit flipped with respect to a reference pattern with a specific probability, a circuit which controls the weight of random patterns generated by an LFSR and a circuit which controls bit-flipping are added midway in a scan chain for efficient fault detection. According to the method described in a paper by G. Kiefer et al, “Deterministic BIST with Multiple Scan Chains” (literature: Proceeding of International Test Conference '98. 1998 pp. 1057-1064), a logic for flipping some bits is added in order to transform pseudo-random patterns generated by an LFSR into similar test patterns. In the Reseeding technique stated in a paper by S. Hellebrand, “Generation of vector patterns through reseeding of multiple-polynomial linear feedback shift registers” (literature: Proceeding of International Test Conference '92. 1992, pp. 120-129), LFSR's initial value (called “seed”) is calculated from a test pattern to be generated and the seed is replaced one after another.

All the above-mentioned BIST-based methods for fault coverage improvement have problems to be solved when they are applied to large-scale semiconductor integrated circuits. The test point insertion method has the following two problems: one is that the circuit operating speed is slowed because a test point is inserted into the path in the semiconductor integrated circuit to be tested (hereinafter called a “circuit under test” or “CUT”) and the other is that, since the test point should depend on the CUT, the layout and wiring pattern of the CUT cannot be determined even locally until where to insert the test point is determined, and thus the period of semiconductor integrated circuit design may be prolonged.

The methods proposed by K. H. Tsai et al and G. Kiefer et al have not only the problem of a prolonged design period because the layout or wiring pattern cannot be determined without modifying the circuit which controls bit-flipping or the like depending on the result of test pattern generation (a time consuming process), and the scan chain, but also the problem that, for a large-scale CUT, the method by H. Tsai et al has a restriction on the way of scan chain arrangement, thereby increasing the overhead of wirings, while, in the method by G. Kiefer et al, the bit flipping control circuit must be increased. Regarding the Reseeding technique, although it has no problem of hardware overhead or a prolonged design period in comparison with the original BIST method, the number of seeds is expected to be equal to or larger than the number of stored patterns and thus the main objective of the BIST method, reduction of test data, is not satisfactorily achieved.

SUMMARY OF THE INVENTION

A major object of this invention is to realize a method for testing semiconductor integrated circuits or the like which provides a high fault coverage with a smaller volume of test data, and particularly a BIST-based such test method.

Another object of this invention is to realize a semiconductor circuit device in which a circuit added to embody the above-said test method does not depend on the CUT and is easy to design.

A further object of this invention is to realize a circuit device which causes no loss in operating speed due to the addition of the circuit to embody the above-mentioned test method and minimizes the overhead of hardware such as gates and wirings.

In order to achieve the above objects, this invention provides a semiconductor integrated circuit test method in which test pattern signals (hereinafter called “test patterns”) as pseudo-random patterns are added to the CUT and the response pattern from that circuit is compared with the expected pattern;wherein there are three steps of generating the above test patterns: a first step for generating an identical pattern sequence cluster at least once, where a pattern sequence cluster consists of plural pattern sequences with a given number of bits and a given number of times and all pattern sequences in such a cluster are identical; a second step for flipping some bits in the pattern sequences in said pattern sequence cluster; and a third step for changing the bits (bit positions) in each pattern to be flipped according to the pattern sequence cluster, pattern sequence number and time in pattern sequence in the cluster at the second step.

According to a semiconductor integrated circuit test method as a preferred embodiment of this invention, a pattern sequence cluster is applied to the CUT at least once, the cluster being composed of plural pattern sequences whose number of bits and maximum length of scan chain depend on the number of scan chains and the number of external input terminals and whose number of times depends on the unit test sequence length, where the cluster has one reference pattern sequence in the pattern sequence cluster and, in whole or in part, with respect to the reference pattern sequence, such pattern sequences as ones without flipped bits, ones with all or some bits flipped and ones with all or some flipped bits in plural consecutive patterns or patterns at regular intervals, the interval being equivalent to a given number of patterns are used.

Also, in order to embody the above-said semiconductor integrated circuit test method, the test pattern generator according to this invention comprises: an identical pattern sequence generator which generates an identical pattern sequence cluster at least once, where a pattern sequence cluster is composed of plural pattern sequences with a given number of bits and a given number of times and all pattern sequences in the cluster are all identical; and a bit-flipping sequence generator which uses the pattern sequence cluster generated by said identical pattern sequence generator as input, flips some bits in the pattern sequences in the cluster and changes the bits in the pattern to be flipped according to the pattern sequence cluster, pattern sequence number and time in pattern sequence in the cluster.

According to a preferred embodiment of the invention, when the above-said test pattern generator and the CUT are integrated into one semiconductor integrated circuit, there are two possible configurations: one is that the bit-flipping sequence generator in the-above test pattern generator and the CUT are integrated into a semiconductor integrated circuit, and the other is that the semiconductor integrated circuit consists of a test pattern generator which is independent of the CUT, where the test pattern generator or test pattern generating circuit independent of the CUT constitutes a semiconductor integrated circuit test device and the probe included in the semiconductor integrated circuit test device is to be connected with the external input terminal of the CUT in order to carry out a test.

The identical pattern sequence generator has a linear feedback shift register and a register which holds the seed in the linear feedback shift register, with a serial or parallel copy function for the registers in the linear feedback shift register having. In order to generate plural pattern sequence clusters as mentioned above, a register which holds plural initial values for registers in the linear feedback shift register may be provided.

In a semiconductor integrated circuit according this invention, a circuit for generating neighborhood patterns is added independently of the CUT, thereby avoiding the problem of a prolonged design period, eliminating the overhead concerning the operating speed of the CUT, and reducing hardware overhead to ensure a high fault coverage with less test data.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Next, preferred embodiments of this invention will be described referring to the attached drawings.

FIG. 1shows the structure of the circuit for embodying the test method according to this invention.

The circuit for embodying the test method according to the invention is composed of an identical pattern sequence generator110, a bit-flipping sequence generator120and a circuit under test (CUT)130. Output lines PT1, PT2, . . . PTn in the identical pattern sequence generator110are inputted to the bit-flipping sequence generator120, in which the output lines are inputted to input terminals IN1, IN2, . . . INn in the CUT130.

The identical pattern sequence generator110outputs patterns whose bit width corresponds to the number of output lines n, synchronously with clocks. Regarding patterns generated by the identical pattern sequence generator110, on the assumption that patterns for a given number of times are called a pattern sequence, the bit-flipping sequence generator120outputs different pattern sequence clusters sequentially, where plural identical pattern sequences constitute what is called a “pattern sequence cluster.”

The bit-flipping sequence generator120flips some bits in each pattern of the input pattern sequence cluster according to pattern sequence number and time in pattern sequence. The bit-flipping sequence generator120incorporates the following: a bit-flipping controller121which outputs a pattern representing the bit flipping positions in the input pattern with regard to each time (logical value 1 for only bits corresponding to bit flipping positions); and circuits122to124for obtaining exclusive OR for each bit in the input pattern in the bit-flipping sequence generator120depending on each bit in the pattern outputted by the bit-flipping controller121.

A pattern sequence cluster outputted by the bit-flipping controller121comprises, in whole or in part, such pattern sequences as ones all of which components have logical value 0, and ones with all or some bits of logical value 1 in only one pattern and ones with all or some bits of logical value 1 in plural consecutive patterns or plural patterns at regular intervals, the interval being equivalent to a given number of patterns. Here, each of the pattern sequence clusters outputted by the bit-flipping sequence generator120comprises, in whole or in part, with respect to one reference pattern sequence, such pattern sequences as ones without flipped bits, ones with all or some flipped bits in one pattern and ones with all or some flipped bits in plural consecutive patterns or plural patterns at regular intervals, the interval being equivalent to a given number of patterns. The CUT130is a semiconductor circuit intended to be tested, among the circuits designed by the logic designer.

FIG.2(a) shows a first example of the above-said CUT. The first example is a full scan design CUT200, where all storage elements (211,212. . .233) in the CUT200are provided with a scan function to enable setting and reading during testing to test the CUT200as a combinational circuit. FIG.2(b) shows the circuit240for a scan flip-flop as mentioned above. A selector242is added to a flip-flop241having clock input C, data input D and output Q, and if the logical value for input line SE is 0, the input value for input line D is stored (normal mode), while if it is 1, the input value for input line SI is stored (scan mode).

As shown in FIG.2(a), scan flip-flops211to213,221to223, and231to233are serially connected on scan chains201,202and203, respectively. The figure shows only flip-flops or storage elements but omits the combinational circuit which is usually used in normal mode. Boundary scan flip-flops are inserted in external input terminals (not shown here). The CUT200operates as follows: when scan enable signal SEN for terminal204is 0, if clock CLK for terminal205is turned on, the circuit works in its normal mode, while it works in the mode of scan shift on each of scan chains201,202and203if clock CLK is turned on when signal SEN is 1. Inputs IN1, IN2, . . . INn in the CUT200are valid in the scan shift mode.

FIG.2(c) shows a second example of the above-said CUT. The second example is a non-scan design CUT260, where all flip-flops or storage elements (251,252,261,262,271,272and so on) in the CUT200have no scan function. Here, a signal line equivalent to an external input terminal serves as input INn for the CUT260. In this case, the CUT260is tested as a sequential circuit.

As stated above, according to this embodiment, for any of full scan or non-scan design circuits, the test pattern generator, which comprises an identical pattern sequence generator110and a bit-flipping sequence generator120, can generate neighborhood patterns known as valid for fault detection, or patterns having several bits flipped with respect to one reference pattern, thereby enabling a high fault coverage to be achieved by the BIST method when it is used in combination with the Reseeding method.

Here, the linear feedback shift register (LFSR) as a constituent part of the identical pattern sequence generator110is first explained below.

FIG. 3shows an example of a linear feedback shift register which is of the same type as ones used in conventional test pattern generators. In LFSR300, outputs from storage elements301to303which operate as shift registers, and from circuits304and305which obtain exclusive OR of the value of the bottom storage element303and the value of a specific storage element are fed back to the top storage element301through selector306. Here, storage elements301to303are of the edge trigger type which imports data input when clock input changes. In the explanation given below, the state of shift registers within LFSR300is called “seed.”

FIG.9(a) shows mode data for LFSR300. The condition that the logical value of input INTSEL is 1 is called an initialization mode, where storage elements301to303shift synchronously with input BRC and the initial value of seed can be set through input SEEDIN. The condition that the logical value of input INTSEL is 0 is called a pattern generation mode, where pseudo-random patterns are generated from outputs PT1, PT2, . . . PTn of the storage elements synchronously with input BRC.

The nature of LFSR is as follows: when n bit strings expressing, by 0 or 1, whether or not to use outputs of storage elements in n-bit LFSR for input of exclusive OR for feedback, are made to correspond to coefficient of the first or n-th degree term (0 or 1) in a polynomial of the n-th degree of the residue system of 2, if the polynomial is a primitive polynomial, or an irreducible polynomial, the cycle of patterns which are generated when the logical values of all the components of seed in n-bit LFSR are other than 0 is the maximum, or 2 raised to the n-th power minus 1. For example, in the residue system of 2, since polynomial of the fourth degree X^4+X+1=0 is a primitive polynomial, if LFSR300is a 4-bit register, the cycle of generated patterns is maximized to 15 by feeding back the exclusive OR of outputs PT1and PT4.

FIGS. 4,5,6,7and8show examples of the circuit of the identical pattern sequence generator110according to the above embodiment of the invention.

FIG. 4shows LFSR400which enables parallel seed recovery, as a first example of the circuit of the identical pattern sequence generator110. Outputs of storage elements401to403which operate as shift registers, and exclusive ORs404and405of the value of the bottom storage element403and the value of a specific storage element are fed back to the top storage element401through selector406. This feedback structure is the same as for LFSR300as shown in FIG.3. To store the seed, storage elements (seed backup registers)401to403are paired with storage elements407to409and seed recovery is controlled by selectors410to412.

FIG.9(b) shows mode data for LFSR400. The condition that clock BRC is applied with the logical value of input INTSEL1and that of input RDSEL0is called an initialization mode, where storage elements401to403shift synchronously with clock BRC and the initial value of seed is set through input SEEDIN. The seed is copied to storage elements407to409in parallel. The condition that the logical value of input INTSEL is 0 and that of RDSEL is 0 is called a pattern generation mode, where pseudo-random patters are generated from outputs PT1, PT2, . . . PTn of storage elements401to403synchronously with clock BRC so that the values of storage elements407to409are held. The condition that the logical value of input INTSEL is 0 and that of RDSEL is 1 is called a seed recovery mode, where the values of storage elements407to409are recovered as seed in parallel or simultaneously in storage elements401to403synchronously with clock BRC. The condition that clock BRC is not applied with the logical value of input INTSEL1and that of input RDSEL0is called a seed update mode, where the values of storage elements401to403are copied to storage elements407to409in parallel.

FIG. 5shows LFSR420which enables serial seed recovery, as a second example of the circuit of the identical pattern sequence generator110. Outputs of storage elements421to423which operate as shift registers, and outputs of exclusive ORs424and425of the value of the bottom storage element423and that of a specific storage element are fed back to the top storage element421through selector426. This feedback structure is the same as for LFSR300as shown in FIG.3. To store the seed, storage elements (seed backup registers)421to423are paired with storage elements427to429and seed recovery is controlled by selector430.

FIG.9(c) shows mode data for LFSR420. The condition that clock BRC is applied with the logical value of input INTSEL1and that of input RDSEL0is called an initialization mode, where storage elements421to423shift synchronously with clock BRC and the initial value of seed is set through input SEEDIN. The seed is copied to storage elements427to429in serial. The condition that the logical value of input INTSEL is 0 and that of RDSEL is 0 is called a pattern generation mode, where pseudo-random patterns are generated from outputs PT1, PT2, . . . PTn of the storage elements synchronously with clock BRC so that the values of storage elements427to429are held. The condition that the logical value of input INTSEL is 0 and that of input RDSEL is 1 is called a seed recovery mode, where the values of storage elements427to429are recovered as seed serially in storage elements421to423synchronously with clock BRC.

FIG. 6shows LFSR440which deals with a plurality of polynomials for parallel seed recovery, as a third example of the circuit of the identical pattern sequence generator110. The figure assumes that LFSR has four bits. The structure in which outputs of storage elements441to444which operate as shift registers, and output of the circuit445for exclusive OR of the value of the bottom storage element444and that of the top storage element441are fed back to the top storage element441through selector446, as well as the storage elements447to450for seed storage and the selectors451to454for seed recovery control are the same as those for LFSR400. The difference is that, in LFSR440, the input of the circuit445for exclusive OR is connected with the output terminal of AND element456and part of the input of the exclusive OR circuit for feedback is masked according to the setting of storage element455.

This configuration makes it possible that there can be a plurality of polynomials in the residue system of 2 which are matched to LFSR. In the example shown here, such polynomials are x^4+x+1=0 (primitive polynomial) and x^4+1=0 (shift register). LFSR440operates in the same way as LFSR400, except that it is necessary to set a value for storage element455which controls the input of the exclusive OR circuit for feedback in the initialization mode.

FIG. 7shows LFSR460which enables parallel seed recovery and pattern generation by shift, as a fourth example of the circuit of the identical pattern sequence generator110. The structures of 4-bit shift registers461to464and seed recovery storage elements467to470of LFSR460are identical to those of LFSR440, except that, in the pattern generation mode, if the logical value of storage element475is 0, the exclusive OR of values of shift registers461and464is fed back to storage element461, while if it is 1, the value from input SEEDIN is brought into shift registers461to464through storage element475. This is used for another LFSR state in the identical pattern sequence generator having a plurality of LFSRs which will be explained later by reference to FIG.17.

FIG. 8shows a group of shift registers480as a fifth example of the circuit of the identical pattern sequence generator110. When the input INTSEL logical value is 1, storage elements481to483and selector484, storage elements485to487and selector488, and storage elements489to491and selector492, set initial values from inputs SEEDIN1, SEEDIN2, . . . SEEDINn, respectively, by shifting synchronously with input BRC; on the other hand, when the INTSEL logical value is 0, they work as shift registers and a pattern signal which is composed of values of last storage elements483,487and491is generated from outputs PT1, PT2, . . . PTn.

The major features of the above-mentioned five examples of the circuit of the identical pattern sequence generator110can be summarized as follows. In the first example LFSR400, parallel seed recovery is done so the test time can be shortened. In the second example LFSR420, serial seed recovery is done so the test time is prolonged but the overhead of gates is smaller than in LFSR400. The third example LFSR460can have a plurality of LFSR polynomials. When the fourth example LFSR480has more than one LFSR, another LFSR state can be used for pattern generation. In the fifth example, though the overhead of gates and the volume of data required for setting all storage elements are considerable, all pattern sequence combinations can be represented.

Next, the detailed structure of the bit-flipping controller121will be explained. The explanation will assume that the number of patterns in a pattern sequence is 256.

FIG. 10shows a first example 600 of the circuit of the bit-flipping controller121. The bit-flipping controller600outputs 256 kinds of pattern sequences which include only one pattern all of which bits have logical value 1. The bit-flipping controller600comprises: an B-bit counter601for time in pattern sequence which has outputs C1-C2; an 8-bit counter602for pattern sequence number which has outputs C1-C2; and a comparator604which determines whether or not the value of the counter601agrees with that of the counter602. The output is distributed to n outputs RVS1, RVS2, . . . RVSn through the AND element605for masking. Clock BRC is used as clock C for the counter601for time in pattern sequence while the AND (logical product) element603for clock BRC and input HCCKEN supplies clock C for the pattern sequence number counter602.

FIG.14(a) shows an example of the circuit of the n-bit counter used in the bit-flipping controller600. The n-bit counter700is composed of the following: storage elements701to704which represent the counter state; storage elements712to714for calculation of exclusive OR; storage elements721to724which reset the counter to zero; and selectors731to734which select either the function as a counter or the shift function. The counter state is outputted by n outputs C1, C2, . . . Cn.

FIG.14(b) shows mode data for counter700. The condition that the logical value of input SFTEN is 1 and that of input R is 0 is called a shift mode, in which storage elements701to704shift synchronously with clock C through input SFTIN to set an initial value for the counter. The condition that the logical value of input SFTEN is 0 and that of input R is 1 is called a reset mode, in which the counter is reset to zero synchronously with clock C. The condition that the logical value of input SFTEN is 0 and that of input R is 0 is called an increment mode, in which the counter is incremented by 1 synchronously with clock C.

Next, the operation modes for the bit-flipping controller600will be explained. With the logical value of input INTSEL1, that of input RDSEL0and that of input HCCKEN1, the contents of the storage elements in the two counters601and602shift synchronously with clock BRC, so their initial values can be set through input CTIN. With the logical value of input INTSEL0and that of input RDSEL1, the counter601for time in pattern sequence is set to zero (all storage elements are set to zero) synchronously with clock BRC. With the logical value of input INTSEL0, that of input RDSEL0and that of input HCCKEN0, only the counter601for time in pattern sequence is incremented by clock BRC; if the logical value of HCCKEN is 1, the two counters601and602are incremented by clock BRC. Also, if the logical value of NBEN is always 1 in a pattern sequence, a pattern all of which components have logical value 1 only when the values of the two counters agree is generated, and all other output patterns have logical value 0. When the logical value of input NBEN in pattern sequences is always 0, pattern sequences all of which components have logical value 0 will be generated.

FIG. 11shows a second example of the circuit of the bit-flipping controller121. The bit-flipping controller620outputs 512 kinds of pattern sequences which each include only one pattern the half of which bits have logical value 1. The bit-flipping controller620comprises a counter621for time in pattern sequence and a comparator624; its AND element625for masking and the AND element623for input HCCKEN are identical to the AND element605and AND element603of the bit-flipping controller600. The counter622for pattern sequence number has such a structure that the 9th bit C9is added to the same structure as that of the pattern sequence number counter602in the bit-flipping controller600. The logical value of bit C9or its inverse is connected with n outputs RVS1, RVS2, . . . RVSn through AND elements626to630. In the circuit as shown inFIG. 11, if the logical value of the 9th bit C9in the pattern sequence number counter622is 0, patterns where only RVS1, RVS3and so on have logical value 1 are generated, while if it is 1, patterns where only RVS2, RVS4and so on have logical value 1 are generated.

FIG. 12shows a third example of the circuit of the bit-flipping controller121. The bit-flipping controller640outputs 256 kinds of pattern sequences which each include only one pattern all of which bits have logical value 1 and 256 kinds of pattern sequences which each include, on a cycle of128, two patterns all of which bits have logical value 1, that is 512 kinds of pattern sequences in total. The bit-flipping controller640comprises a counter641for time in pattern sequence; its AND element645for masking and the AND element643for input HCCKEN are identical to the AND element605and AND element603of the bit-flipping controller600.

The counter642for pattern sequence number has such a structure that the 9th bit C9is added to the AND element605and the AND element603; the circuit644is a modified version of the above-said comparator604in which some function has been modified. If the logical value of the 9th bit C9in the pattern sequence number counter642is 0, the circuit644works in the same way as a conventional 8-bit comparator, but if the logical value of the 9th bit C9is 1, its works as a comparator which uses the lower 7 bits. As a consequence, if the logical value of the 9th bit C9in the pattern sequence number counter642is 0, pattern sequences which each include only one pattern all of which bits have logical value 1 are generated; if it is 1, pattern sequences which include, on a cycle of128, two patterns all of which bits have logical value 1, are generated.

FIG. 13shows a fourth example of the circuit of the bit-flipping controller121. The bit-flipping controller660outputs a total of 1024 kinds of pattern sequences: 256 kinds of pattern sequences which each include only one pattern all of which bits have logical value 1, 256 kinds of pattern sequences which each include two patterns serial in time all of which bits have logical value 1, 256 kinds of pattern sequences which each include two patterns with all bits of logical value 1, spaced at an interval equivalent to one time, and 256 kinds which each include two patterns with all bits of logical value 1, spaced at an interval equivalent to 2 times.

The bit-flipping controller660comprises a counter661for time in pattern sequence, an AND element665for masking and an AND circuit663for input HCCKEN and signal BRD. These are identical to the counter601for time in pattern sequence, the comparator604, the AND element605for masking and the AND circuit603of the bit-flipping controller600. The counter662for pattern sequence number has such a structure that the 9th bit C9and 10th bit C10are added to the same structure as that of the counter602of the bit-flipping controller600. The AND elements666to668control the output of the 9th bit C9and 10th bit C10of the counter662. If both the logical values of bits C9and C10are 0, the AND elements666to668all output logical value 0; if C9is 1 and C100, only the AND element666outputs logical value 1; if C9is 0 and C101, only the AND element667outputs logical value 1; and if both C9and C10are 1, only the AND element668outputs logical value 1.

Storage elements669to672memorize the output values of the comparator664at the current time, one time before, two times before and 3 times before. The OR element673has four inputs: the output value of the comparator604; the logical product of the storage element670holding the comparator664's output value one time before, and the AND element666's output value; the logical product of the storage element671holding the comparator664's output value two times before, and the AND element668's output value; and the logical product of the register672holding the comparator664's output value three times before, and the AND element668's output value. If one of these inputs is 1, logical value 1 is conveyed to outputs RVS1, RVS2, . . . RVSn. As a consequence, if both the logical values of the 9th and 10th bits or C9and C10, in the pattern sequence number counter662are 0, pattern sequences which each include only one pattern all of which bits have logical value 1 are generated; if C9is 1 and C10is 0, pattern sequences which each include two patterns serial in time all of which bits have logical value 1 are generated; if C9is 0 and C10is 1, pattern sequences which each include two patterns with all bits of logical value 1, spaced at an interval equivalent to one time are generated; if C9and C10are both 1, pattern sequences which each include two patterns with all bits of logical value 1, spaced at an interval equivalent to two times are generated.

Regarding the number of bits for each counter in the bit-flipping controller121, for instance, the counter601for time in pattern sequence in the bit-flipping controller600has 8 bits; the counter cycle of 256 which is derived from this number of bits indicates the upper limit for the number of patterns in a pattern sequence but the number of bits should not be limited to 8. If the number of patterns in a pattern sequence is larger than the cycle of the counter601for time in pattern sequence, the bit-flipping controller600sequentially outputs pattern sequences in which patterns with all bits of logical value 1 are generated on the corresponding cycle.

On the other hand, though the counter602for pattern sequence number has 8 bits, the counter cycle of 256 which is derived from this number of bits indicates the upper limit for the number of pattern sequences in a pattern sequence cluster but it is also possible that the number of bits for the counter is other than 8. If the number of pattern sequences in a pattern sequence cluster should be larger than the cycle of the counter602for pattern sequence number, only identical pattern sequences would be generated, so such a case is not assumed. The above consideration concerning the number of bits for each counter is applicable to the other examples of the bit-flipping controller121.

In preferred embodiments, the test pattern generator, bit-flipping sequence generator and bit-flipping controller as mentioned above may be independent of each other or combined to make up a semiconductor integrated circuit. Next, embodiments of a semiconductor integrated circuit according to this invention will be explained.

FIG.15(a) shows the structure of a first embodiment of a semiconductor integrated circuit having a test pattern generator according to this invention. A semiconductor integrated circuit800(test pattern generator) comprises an identical pattern sequence generator810, a bit-flipping sequence generator820, and a pattern generating controller830. The identical pattern sequence generator810may be either of the identical pattern sequence generators400,420and440as shown inFIGS. 4,5and6, respectively. The bit-flipping controller821in the bit-flipping sequence generator820may be either of the bit-flipping controllers600,620,640and660as shown inFIGS. 10,11,12and13, respectively. The pattern generating controller830is a decoder which turns outputs INTSEL, RDSEL, NBEN and HCCKEN from two inputs BINIT and NHGEN into four signals. FIG.15(b) shows different combinations of the two inputs with the four outputs and the relevant modes.

In the initialization mode841, the initial value for the identical pattern sequence generator810is set on the storage elements in the identical pattern sequence generator810and bit-flipping controller821serially through input SEEDIN. In the pattern generation mode842, the identical pattern sequence generator810works as LFSR to generate pseudo-random patterns sequentially and the bit-flipping controller821continues to output patterns all of which components RVS1, RVS2, . . . RVSn have logical value 0, so the test pattern generator800outputs the pseudo-random patterns generated by the identical pattern sequence generator810as they are. In the seed recovery mode843, the seed is recovered in parallel or serial into the register which has once stored it, in the identical pattern sequence generator to reset the counter for time in pattern sequence in the bit-flipping controller821to zero.

In the neighborhood pattern generation mode844, neighborhood patterns are generated, where neighborhood patterns include, in whole or in part, with respect to the reference pattern sequence, such pattern sequences as ones without flipped bits, ones with all or some flipped bits in one pattern and ones with all or some flipped bits in plural consecutive patterns or patterns at regular intervals, the interval being equivalent to a given number of patterns. In the explanation given below, among neighborhood patterns generated by the test pattern generator800, the reference pattern sequence is called the parent pattern and other pattern sequences with some flipped bits with respect to the reference pattern are called child patterns.

FIG. 16shows the structure of a second embodiment of a semiconductor integrated circuit having a test pattern generator according to this invention. The semiconductor integrated circuit900is composed of a test pattern generator901and a circuit under test (CUT)902. The test pattern generator901has the same structure as the test pattern generator800shown in FIG.15(a), where any combination of the relevant circuits mentioned above may be used for the identical pattern sequence generator810and the bit-flipping sequence generator820. The circuit under test902may be either CUT200shown in FIG.2(a) or CUT260as shown in FIG.2(c). In this embodiment, neighborhood patterns which are valid for fault detection can be generated and thus a high fault coverage can be achieved with a smaller volume of test data.

FIG. 17shows the structure of a third embodiment of a semiconductor integrated circuit having a test pattern generator according to this invention. The semiconductor integrated circuit920is composed of plural test pattern generators921to922and a circuit under test (CUT)923. Each of the test pattern generators921to922has the same structure as the test pattern generator800, where any combination of the relevant circuits may be used for the identical pattern sequence generator810and the bit-flipping sequence generator820. The circuit under test923may be either CUT200shown in FIG.2(a) or CUT260as shown in FIG.2(c). This embodiment offers not only the advantage of achieving a high fault coverage with a smaller volume of test data, but also another advantage that the overhead relating to wirings for scan chains in the CUT can be reduced by distribution of smaller size test pattern generators within the semiconductor integrated circuit.

FIG. 18shows the structure of a fourth embodiment of a semiconductor integrated circuit having a test pattern generator according to this invention. The semiconductor integrated circuit940is composed of a test pattern generator941, a circuit under test (CUT)942and a pattern compactor943. This embodiment is a standard configuration based on BIST according to this invention. The test pattern generator941has the same structure as the test pattern generator800, where any combination of the relevant circuits may be used for the identical pattern sequence generator810and the bit-flipping sequence generator820. The circuit under test942has the same structure as the full scan design CUT200shown in FIG.2(a).

FIG. 19shows the circuit of the pattern compactor as shown in FIG.18. The circuit960of the pattern compactor943has the same structure as a multiple input signature register (MISR) which is commonly used in the BIST method. In the MISR structure, storage elements961to964, exclusive OR elements965and966and their feedback constitute LFSR, where exclusive ORs of inputs SA1, SA2, . . . SAn are calculated by exclusive OR elements967to980just before storage elements961to964. Pattern sequences from inputs SA1, SA2, . . . SAn are encoded (compacted) onto storage elements961to964synchronously with clock BMC. If the polynomial in the residue system of 2 is a primitive polynomial, the probability of error detection failure (last storage elements961to964do not have errors in the bit strings though input pattern sequences have errors) is known to be very low. This implies that comparison of the result of reading against the expected final state of MISR brings about the same fault detection effect as comparison of each pattern against the expected pattern. Therefore, the circuit shown inFIG. 19will achieve a high fault coverage with a volume of test data which is far smaller than in the above-mentioned case.

FIG. 20shows the structure of a fifth embodiment of a semiconductor integrated circuit having a test pattern generator according to this invention. The semiconductor integrated circuit980is composed of a seed stored register981, a test pattern generator941, a circuit under test (CUT)942and a pattern compactor943. The difference from the semiconductor integrated circuit940as the fourth embodiment is that the seed stored register981is added between input TDI and the test pattern generator941(the same components as those used in the semiconductor integrated circuit940are marked with the same reference numerals). The seed stored register981works as a shift register synchronously with clock BRC in the initialization mode, or when input BINT is 1 and input NHGEN is 0. The number of storage elements983to985is the same as the number of storage elements in the pattern compactor943. The storage elements983to985store the initial value (seed) for the pattern compactor943. The number of storage elements986to988, that of989to991, and that of992to994are the same as the number of storage elements in the test pattern generator941, and storage elements986to988,989to991and992to994store the first, second and s-th initial values for the test pattern generator941, respectively (s denotes the number of pattern sequence clusters). In the fourth embodiment, since the initial value for the test pattern generator941is given with regard to each pattern sequence cluster from the semiconductor integrated circuit test device, there remains the problem of overhead relating to interfacing with the test device. On the other hand, in the fifth embodiment, since the initial values for the test pattern generator941with regard to a plurality of pattern sequence clusters can be stored initially, the overhead relating to interfacing with the test device is reduced.

In the above-said first to fifth embodiments, each semiconductor integrated circuit incorporates an identical pattern sequence generator110and a bit-flipping sequence generator120according to the invention. These may be separated from the CUT and configured as an independent semiconductor integrated circuit test device. Also, the above-said test device may incorporate an identical pattern sequence generator110, and the semiconductor integrated circuit to be tested may incorporate a bit-flipping sequence generator120. Also, the invention is effective even when the identical pattern sequence generator110and the bit-flipping sequence generator120are built on the wafer area other than the semiconductor integrated circuit area to make up an on-wafer semiconductor integrated circuit test device.

Next, how the semiconductor integrated circuit with a test pattern generator according to this invention operates will be described by reference to the timing diagrams.

FIG. 21is a timing diagram illustrating the basic operation of the semiconductor integrated circuit940shown in FIG.18. First, in the BIST initialization mode1001, the pattern generating controller830in the test pattern generator941(equal to 800 inFIG. 5) is set to the initialization mode841; as many pulses as storage elements in the test pattern generator941and pattern compactor943are alternately given to clock BMC and clock BRC; then the initial values of the test pattern generator941and pattern compactor943including seeds are inputted through TDI sequentially.

In the parent pattern setting mode1002, the pattern generating controller830in the test pattern generator941is set to the pattern generation mode842; scan enable SEN is set to logical value 1; and pulses are given to scan chain shift clock CLK and clock BRC alternately by the amount equivalent to the maximum length of scan chain so that every storage element in the CUT942has a logical value to produce a parent pattern for testing the CUT942.

In the clock advance and seed recovery mode1003, the pattern generating controller830in the test pattern generator941is set to the seed recovery mode843; scan enable SEN is set to logical value 0; and a pulse is given once to each of clock CLH for capturing data and seed recovery clock BRC.

In the neighborhood pattern setting/compaction mode1004, the pattern generating controller830in the test pattern generator941is set to the neighborhood pattern generation mode844; scan enable SEN is set to logical value 1; and pulses are given to scan chain shift clock CLK and clock BRC sequentially by the amount equivalent to the maximum length of scan chain so that compaction of result of clock advance and setting of the next child pattern take place simultaneously. Then, modes1003and1004are repeated, with the number of repetitions being 1 (parent pattern) plus the number of child patterns or so. Through the steps from mode1001to mode1004, the test pattern generator941generates one pattern sequence cluster to test the CUT942with one parent pattern and child patterns, and the resultant response pattern is compacted into the last state of the pattern compactor943(value of all storage elements).

The sequence from mode1001to mode1004is repeated almost as many times as seeds or pattern sequence clusters. In the BIST initialization mode1001during the second and subsequent cycles, at the same time when the test pattern generator941and the pattern compactor943are initialized, the last state of the pattern compactor943as the compacted result of the pattern of response to the test is also read out. In the last cycle of the above sequence, the last state of the pattern compactor943is read out in the compacted result judgment mode1005.

Here, what kind of patterns can be used to test the CUT942is explained, referring toFIG. 18(semiconductor integrated circuit940) and the timing diagram in FIG.20. For better illustration, it is assumed that the length of scan chain for the full scan design CUT942is 259 and the number of scan chains is n. Thus, the number of patterns in a pattern sequence generated by the test pattern generator941is 259. Referring toFIGS. 24to27, an explanation will be given below for each of the bit-flipping controllers shown inFIGS. 10to13, concerning how variations of a reference pattern sequence or child patterns from the parent pattern can be generated in a pattern sequence cluster by scanning.

FIGS. 24to27outline the CUT200as shown in FIG.2(a), where each square represents a scan flip-flop and a hatched square represents a flipped bit with respect to the parent pattern. The number of a child pattern denotes the value on the counter for pattern sequence number at the time of generation of the child pattern.

FIG. 24illustrates 256 child patterns in case of using the bit-flipping controller600. Child patterns0to2are patterns which include two columns of flipped bits on a cycle of 256 (bits), while child patterns3to255are patterns which include one column of flipped bits.

FIG. 25illustrates 512 child patterns in case of using the bit-flipping controller620. The columns having flipped bits in child patterns0to255and256to511, correspond to the columns of flipped bits in the child patterns in FIG.24. In this case, however, such columns in child patterns0to255have flipped bits in odd-numbered rows (storage elements on a scan chain of IN1, IN3and so on) and those in child patterns256to511in even-numbered rows (storage elements on a scan chain of IN2, IN4and so on).

FIG. 26illustrates child patterns256to384in case of using the bit-flipping controller640. Here, child patterns0to255are omitted because they are identical to the ones in FIG.24. Child patterns256to258are patterns which include three columns of flipped bits on a cycle of128, while child patterns259to383are patterns which include two columns of flipped bits on a cycle of 128 bits.

FIG. 27illustrates child patterns256to1023among1024child patterns in case of using the bit-flipping controller660. Here, child patterns0to255are omitted because they are identical to the ones in FIG.24. Child patterns256to511are patterns which include two consecutive columns of flipped bits on a cycle of256; child patterns256and257have a total of four such columns; child pattern258has a total of three; child patterns259to511have two. Child patterns512to767have two columns of flipped bits on a cycle of256with one non-flipped bit column between them; child pattern512has a total of four columns of flipped bits, child patterns513and514a total of three, and child patterns515to767a total of two. Child patterns768to1023have two columns of flipped bits have two columns of flipped bits on a cycle of256with two non-flipped bit columns between them; child patterns768to770have a total of three columns of flipped bits, and child patterns771to1023a total of two.

FIG. 28shows the structure of a sixth embodiment of a semiconductor integrated circuit having a test pattern generator according to this invention. The semiconductor integrated circuit1200is composed of a test pattern generator1210and a circuit under test (CUT)1220. The CUT1220has eight storage elements1221to1228, an AND element1229which uses their outputs x1to x8as input, and a storage element1230which uses output x0of the AND element1229as input and output y0of the storage element1230is added to inputs D of storage elements1221to1228.

The CUT1220is a full scan design circuit, in which the storage element1230is on scan chain1231and storage elements1221to1228are on scan chain1232. The test pattern generator1210has the same structure as the test pattern generator800in FIG.15. It generates a pattern with four bits: outputs PG1, PG2, PG3and PG4. The identical pattern sequence generator810has the same structure as the identical pattern sequence generator440in FIG.6. The bit-flipping controller821has the same structure as the bit-flipping controller600inFIG. 10, where the number of bits for both the counters601and602is 3.

FIG.28(b) illustrates a test pattern set when 0 stuck-at fault and 1 stuck-at fault are assumed for storage element outputs x0, x1, . . . x8, y0in the CUT1220. Column1241represents each test pattern number, column1242each test pattern as expressed by a set of logical values for storage element output names, and column1243detectable stuck-at fault as expressed by “signal line name/stuck value.” In column1242, X represents an indefinite value, whether it is logical value 0 or 1.

The nature of the test pattern set as given in FIG.28(b) is as follows. Patterns of pattern Nos.2to9are patterns which include one flipped bit with respect to No.1pattern all of which bits have logical value 1. In other words, neighborhood patterns whose Hamming distance from No.1pattern is 1 can detect virtually all faults. The paper by K. H. Tsai et al as discussed earlier points out that neighborhood patterns are valid as test patterns for many circuits.

FIG. 29is a table explaining details of operation of the semiconductor integrated circuit1200during testing. A timing diagram showing the operation should be the same as the one shown inFIG. 21except that, due to the non-existence of a pattern compactor, clock BMC does not exist. “P” in the table means that a pulse is given to clock. For initialization of the test pattern generator, the feedback enable storage element is set to 0, LFSR seed to (1,1,1,1) and the 3-bit counter for pattern sequence number to 7. The 3-bit counter for time in pattern sequence need not be initialized because it is reset to zero at every appearance of a child pattern.

Times1to11are for initialization of the test pattern generator; the above-said initialization is completed at time11. Times12to19are for setting a parent pattern by scan shift, where the parent pattern is set on storage elements y0, x1, . . . x8at time19. At time20, the result of response to the parent pattern is stored into y0and x1, . . . x8by clock advance. At times21to28, the result of response to the parent pattern is read through external output terminals O1and O2by scan shift and at the same time, child pattern0(only x8is flipped to 0) is set on storage elements x0, x1, . . . x8at time28. Clock advance and child pattern setting/result reading are repeated in this way. At time91, child pattern7is set on storage elements y0, x1, . . . x8; and at time92, response pattern is stored in y0, x1, . . . x8by clock advance. Lastly, at times93to100, the pattern of response to child pattern7is read.

The test patterns which are realized by the above sequence can cover all the test patterns as given in FIG.28(b). Specifically, the parent pattern covers pattern No.1and pattern No.10; child pattern0covers pattern No.2and pattern No.10; child pattern1covers pattern No.3and pattern No.10; child pattern2covers pattern No.4and pattern No.10; child pattern3covers pattern No.5and pattern No.10; child pattern4covers pattern No.6and pattern No.10; child pattern5covers pattern No.7and pattern No.10; child pattern6covers pattern No.8and pattern No.10; child pattern7covers pattern No.9and pattern No.11.

Therefore, the volume of test data required to test for all stuck-at faults in the semiconductor integrated circuit1200corresponds to the initial value for the test pattern generator1210, 1 seed or 10 bits (including the counter initial value). If the CUT1220is to be tested for all stuck-at faults by the stored test method, the required test data volume corresponds to eleven patterns or a total of 74 bits. It is, therefore, obvious that the semiconductor integrated circuit according to this invention can remarkably reduce the required data volume for testing.

From now on, an explanation will be made in connection with timing diagrams for pseudo-random pattern generation and relevant complicated timing diagrams and test patterns.

FIG. 22is a timing diagram for generation of pseudo-random patterns similar to ones generated by a conventional LFSR, in the semiconductor integrated circuit940shown in FIG.18. The BIST initialization mode1011and the initial pattern setting mode1012are the same as modes1001and1002inFIG. 21, respectively. In the clock advance mode1013and the random pattern setting/compaction mode1014, the same settings as those for the pattern generation mode842(FIG.15(b)) are made. Here, since each of the identical pattern sequence generators400(FIG.4),420(FIG.5),440(FIG. 6) and460(FIG. 7) works in the same way as LFSR itself, their output patterns are pseudo-random patterns. The last step, or compacted result judgment mode1015, is the same as mode1005in FIG.21.

FIG. 23is an example of a complicated timing diagram for the semiconductor integrated circuit940in FIG.18. In comparison with the timing diagram inFIG. 21, the parent pattern setting mode (1022to1025) and the neighborhood pattern setting/pattern compaction mode (1027to1030) are complicated and a seed update mode1031is newly added in this timing diagram for the circuit in FIG.18. Only the points which are different from the diagram inFIG. 21are described below.

At the step of CUT-clock skip1022in the parent pattern setting mode, pulses are given only to clock BRC, so the state of LFSR only changes but no scan chain shift occurs. This is repeated the number of times equal to a specified number of CUT-clock skips. At TPG-clock skip1023(TPG: test pattern generator), pulses are given only to clock CLK, so only scan chain shift occurs but LFSR remains unchanged. This is repeated the number of times equal to a specified number of TPG-clock skips. At step1024, pulses are given alternately to clock CLK and clock BRC, so scan chain shift occurs and the state of LFSR changes as well. These modes1022to1024are repeated until a logical value is set on every storage element in the CUT942. After that, at the step of additional TPG-clock skip1025, pulses are given only to clock CLK, so only scan chain shift occurs. This is repeated the number of times equal to a specified number of additional TPG-clock skips. The number of CUT-clock skips must be smaller than the number of scan chains; the number of TPG-clock skips must be smaller than the maximum length of scan chain; and the number of additional TPG-clock skips must be smaller than the number of TPG-clock skips.

Furthermore, the neighborhood pattern setting/pattern compaction mode (1027to1030) is the same as the parent pattern setting mode (1022to1025) except clock BMC which activates the pattern compaction circuit943. In the seed update mode1031, the pattern generating controller830in the test pattern generator941is set to the initialization mode841and no pulse is given to clock BRC, so the state of LFSR is copied to the seed backup registers.

Here, the meanings of the terms “CUT-clock skip,” “TPG-clock skip,” and “seed update” are as follows. “CUT-clock skip” is defined in the gazette incited earlier, J-P-A-No. 170609/1998. For instance, in the case of the semiconductor integrated circuit940inFIG. 18, it is assumed that the test pattern generator941is the same as the identical pattern sequence generator440based on 4-bit LFSR (FIG.6), the number of scan chains in the CUT942is 4, and the length of scan chain is all 5. Under this condition, test patterns set for the CUT942and the LFSR state at completion of setting are illustrated inFIGS. 31 and 32. In these figures, only the four bits of LFSR are illustrated on behalf of the section1401representing logical values in the test pattern generator941, where the feedback controller1402and seed input1403are schematically represented. As for LFSR seeds, s1, s2, s3and s4are serially set through seed input1403; a random number sequence generated after LFSR seed setting is r1, r2, r3and so on. If the input of the feedback controller1402is 0, it follows that r1=s1, r2=s2, r3=s3and so on. If the input of the feedback controller1402is 1, it follows that r1=s1+s4, r2=s2+r1, r3=s3+r2and so on.

FIG.31(a) indicates that when the number of CUT-clock skips=1 and the number of TPG-clock skips=0, in the test pattern for the CUT1411there is a correlation among storage elements in the direction from right top to left bottom. When the number of CUT-clock skips=0 and the number of TPG-clock skips=0, in the test pattern for the CUT1411there is a correlation among storage elements in the direction from right top to left bottom. FIG.31(b) indicates that when the number of CUT-clock skips=1 and the number of TPG-clock skips=0, in the test pattern for the CUT1412there is a correlation among storage elements in the direction from right top to left bottom with one non-correlated row between correlated rows. FIG.31(c) indicates that when the number of CUT-clock skips=0, the number of TPG-clock skips=1 and the number of additional TPG-clock skips=0, in the test pattern for the CUT1413there is a correlation among storage elements in the direction from right top to left bottom with two successive storage elements in the scan chain shift direction having an equal logical value. FIG.31(d) indicates that when the number of CUT-clock skips=0, the number of TPG-clock skips=1 and the number of additional TPG-clock skips=1, in the test pattern for the CUT1414there is a different correlation among storage elements with the patterns being shifted to the right from those for the CUT1413by one column. FIG.31(e) indicates that when the number of CUT-clock skips=0 and the number of TPG-clock skips=0 and seeds are updated, the test pattern for the CUT1415may be considered as the second pseudo-random pattern generated from LFSR or the test pattern generated when r2, r3, r4, r5are set as LFSR seed.

As can be understood from the above explanation, “CUT-clock skip” has the effect of improving the fault coverage as it changes the correlation among storage elements in test patterns. “TPG-clock skip” has the effect of suppressing the rate of generation of state change signals during scan chain shift or clock advance, thereby reducing noise in testing. “Additional TPG-clock skip” changes the correlation among storage elements resulting from “TPG-clock skip,” thereby improving the fault coverage.

Next, test patterns which are generated when a plurality of test pattern generators are provided as in the semiconductor integrated circuit920shown in FIG.17, and their effect will be described. Each of the test pattern generators921to922has an identical pattern sequence generator460(FIG. 7) which can switch between pseudo-random pattern generation and pattern generation by shift. In the CUT923, there are 12 scan chains and 4 such chains are connected to each of pattern generators921to922where the length of scan chain is 5. FIG.32(a) shows the test pattern generated when the storage element475in the identical pattern sequence generator460is all set to logical value 0. FIG.32(b) shows the test pattern generated when only the storage element475in the test pattern generator1423, a test pattern generator nearest to input TDI for initialization, is set to 0, and the register475in the other test pattern generators1421and1422is set to 1.

To help the reader better understand how easy seed encoding is, a comparison between the case in FIG.32(a) and the one in FIG.32(b) is made below. It is assumed that the set of storage elements to be set for a test pattern are on a scan chain connected to one test pattern generator. Here, while the number of 6 variables in simultaneous linear equations for storage elements1431,1432,1433and1443is 4, the number of variables for storage elements1441and1442is 8 (variables for storage elements1441are s11, s12, s13, s14, s21, s22, s23, s24; variables for storage elements1442are s21, s22, s23, s24, s31, s32, s33, s34). The larger the number of variables, the more likely success in seed encoding, so it can be thought that pattern generation by shift as in FIG.32(b) is advantageous for seed encoding. Thus, the identical pattern sequence generator460, which can switch between pseudo-random pattern generation and pattern generation by shift, increases the possibility of successful seed encoding in case of existence of plural pattern generation stages.

Explained below by example are the procedures for extracting information necessary for testing a semiconductor integrated circuit according to this invention, particularly the procedures for determining pattern sequences in the identical pattern sequence generator110.

The explanation assumes that the identical pattern sequence generator110is LFSR-based like other identical pattern sequence generators400,420,440and460, and the CUT is a full scan design circuit like the CUT200.

The testing procedure is assumed as follows: for achieving virtually 100% fault coverage efficiently, testing with a given number of patterns (BIST) is first made in the random pattern setting/compaction mode1014shown inFIG. 22; then the neighborhood pattern setting/compaction mode1004shown inFIG. 21is executed before testing by the stored test method is lastly conducted to compensate for imperfection in fault coverage by the BIST method. This means that the required information is a seed set for use in the identical pattern sequence generator and an additional test pattern set to compensate for imperfection in fault coverage. Elements in the seed set are test pattern generator initial values and such initial values include the number of CUT-clock skips, the number of TPG-clock skips, the number of additional TPG-clock skips, LFSR polynomial selection and pattern sequence number counter initial values, in addition to LFSR seeds.

The procedure for obtaining the seed set and additional test pattern set is outlined in FIG.33. At step1501, calculation of the expected pattern in the BIST random pattern mode and fault simulation are carried out to output fault information1512. At step1502, test pattern generation or redundancy judgment are made on undetected faults known from the fault information1512to output a test pattern set1513and make the result of the redundancy judgment reflect in the fault information1512. At step1503, the test pattern set1513is used to generate a parent pattern as a central pattern among neighborhood patterns and output a parent pattern set1514. At step1504, the parent pattern set1514is converted into a seed set1515as information which enables the BIST neighborhood pattern generation mode, and calculation of relevant expected pattern and fault simulation are performed to update the fault information1512. At step1505, the test pattern necessary for compensating for imperfection in fault coverage is extracted from the test pattern set1513and fault information1512to output an additional test pattern set1516and update the fault information1512.

In test pattern generation at step1502, each pattern should be generated in a way that the values of storage elements which need not be set are indefinite, as far as possible, in order to make the pattern cluster in parent pattern generation at step1503(stated later) effective. For instance, it is recommended that the following sequence be repeated: a test pattern for a fault is generated using an existing test pattern generation algorithm and fault simulation is performed while the values of storage elements which need not be set remain indefinite, to detect a fault at the same time. It is, however, advisable to avoid what is called “test pattern compaction,” or merging parts of indefinite values in generated patterns.

FIG. 34shows the procedure for parent pattern generation1503in FIG.33. At step1701, the test pattern set is classified into pattern groups in each of which patterns are identical in the set of storage elements whose logical value 0 or 1. At step1702, the pattern groups classified at step1701are further classified into pattern subgroups so that the Hamming distance for test patterns within each subgroup is under the Hamming distance which depends on the functionality of the bit-flipping controller121. For instance, in bit-flipping controllers600and620, the Hamming distance should be under 1, and in bit-flipping controllers640and660, it should be under 2. Each of test pattern groups thus generated is called a pattern cluster. At step1703, a pattern decided by majority of bits for each pattern cluster is defined as a parent pattern.

FIG. 35shows the procedure for seed set generation1504in FIG.33. At step1811, an untried parent pattern is selected from the parent pattern set1514; at step1812, the conditions for untried patterns are selected from pattern generating conditions (the number of CUT-clock skips, the number of TPG-clock skips, the number of additional TPG-clock skips and LFSR polynomial). The following steps are taken for the selected parent pattern and pattern generating conditions. At step1813, a check is made of the scan chain connection and the correlation among storage elements which depends on, the number of CUT-clock skips, the number of TPG-clock skips and the number of additional TPG-clock skips. In case the pattern is found to be unrealizable, if yes at step1814, or there is an untried pattern generating condition, the process goes back to step1812; if no, or there is no untried pattern generating condition, the process goes to step1820. If yes at step1813or there is no problem in the correlation check result, the process goes to step1815and LFSR seed is calculated using simultaneous linear equations so that a parent pattern can be realized by random number sequences from the selected LFSR polynomial. If there is no seed which satisfies the condition, the process goes from step1816to step1614. If there exists a seed which satisfies the condition, the process goes to step1817, in which fault simulation is performed on a parent pattern and child patterns which are generated depending on the functionality of the bit-flipping controller121. If no new fault is detected at step1818, the process goes to step1820. If a new fault is detected, a set of valid child pattern numbers are registered. At step1819, an LFSR seed, the storage element value which specifies the LFSR feedback position as determined by the selected LFSR polynomial, and the initial value of the pattern generator which depends on the value of the pattern sequence number counter as determined by the first number of valid child patterns are applied, and pattern generating conditions (the number of CUT-clock skips, the number of TPG-clock skips, the number of additional TPG-clock skips, and the number of child patterns as the difference between the first and last valid child pattern numbers plus 1) are registered. At step1820, if an untried parent pattern is found, the process goes back to step1811; if it is found that all parents patterns have been tried, the process is ended.

FIG. 36shows the procedure for additional test pattern generation1505in FIG.33. At step1931, an untried test pattern is selected from the test pattern set1513and at step1932, fault simulation is performed on that pattern. At step1933, if there is a newly detected fault, the process goes to step1934; if not, it goes to step1937. If it is found at step1934that the test pattern being tried can be merged with a stored pattern, the pattern is merged at step1936; if not, the pattern is newly stored at step1935. At step1937, if an untried test pattern is found, the process goes to step1931; if it is found that all test patterns in the test pattern set1513have been tried, the process is ended.

The process of carrying out steps1502,1503and1504on the semiconductor integrated circuit1200inFIG. 28is explained below as an example. The test pattern set1513as the result of test pattern generation1502refers to test patterns1242as shown in FIG.28(b). The step of parent pattern generation1503takes place as follows. At step1701, test pattern numbers1to11are classified into two groups: a group composed of pattern Nos.1to9which require signal lines x1, x2, . . . x8to be set, and a group composed of pattern Nos.10and11which require signal line y0to be set. At step1702, if the predetermined Hamming distance is 1, because the former group (pattern Nos.1to9) is in the neighborhood of pattern No.1and the latter group (pattern Nos.10and11) in the neighborhood of pattern No.10, each group can become a pattern cluster. At step1703, for the group of pattern Nos.1to9, the parent pattern which is decided by majority of bits coincides with pattern No.1, and for the group of pattern Nos.10and11, the parent pattern coincides with pattern No.10.

The next step is seed set generation1504. At step1711, pattern No.1or the parent pattern is selected and at step1712, 0 as the number of CUT-clock skips, 0 as the number of TPG-clock skips, and LFSR polynomial x^4+1=0 (operation as a shift register) are selected. At step1613, a check is made of the correlation among storage elements; in this case, there is no such correlation in the CUT1220so the check result is OK (yes). At step1615, when seed is expressed as (s1, s2, s3, s4), the conditions for storage elements1228to1221are s1=1, s2=1, s3=1, s4=1, r1=1, r2=1, r3=1, r4=1, r5=1; these simultaneous linear equations are solved. It should be, however, noted that r1, r2, . . . r5are random number sequences which are generated after initialization of LFSR and the following relations hold: r1=s1, r2=s2, r3=s3, r4=s4, r5=s5. The solutions of the simultaneous linear equations exist as follows: s1=1, s2=1, s3=1, s4=1. In other words, seed encoding is successful so fault simulation is made on the parent pattern and eight child patterns generated from this seed at step1617. The result is generation of test patterns as shown inFIG. 29to detect all stuck-at faults. Thus, at step1619, this seed is applied; information on the seed as (1,1,1,1) and pattern generating conditions (the number of CUT-clock skips=0, the number of TPG-clock skips=0, and LFSR polynomial x^4+1=0) is registered. After that, the process goes back to step1611, from which steps1612,1613,1615,1616and1617for the parent pattern, or pattern No.10, are carried out to extract seed (X,1, X, X); since at step1618it is found that there is no newly detected fault, this seed is not applied.

FIG. 37illustrates another circuit example for the bit-flipping controller in a test pattern generator according to this invention. The circuit shown inFIG. 11enables flipping control in even-numbered or odd-numbered rows as shown in FIG.25. By contrast, the circuit shown inFIG. 37enables flipping control in any desired row. Regarding the circuit components, the counter681for time in pattern sequence, counter682for pattern sequence number, comparator684and AND element685are functionally equivalent to the counter601for time in pattern sequence, counter602for pattern sequence number, comparator604and AND element605inFIG. 10; so their descriptions are omitted here. The distinct feature of this circuit is that a bit-flipping information registers694is provided in order to control bit-flipping for each row. The bit-flipping information register includes n registers and the logical product of the output of each register and the output of AND element685is outputted to output RVS1, RVS2, . . . RVSn.

Patterns for flipping bits in specific rows are inputted through CTIN to the bit-flipping information register694.FIG. 38shows child patterns generated in case that (1,1,0, . . .1) is inputted as a pattern for flipping bits in rows to (register1, register2, register3, . . . register n), where register i corresponds to output RVSi. In this case, in a bit-flipping column (e.g. the third column in child pattern0), the bits in the first, second and n-th rows are flipped with respect to the parent pattern and the bit in the third row is not flipped. Of course, it is also possible to adopt the structure of the circuit shown inFIG. 12to make variable the bit flipping column cycle or to adopt the structure of the circuit shown in FIG.13to include a plurality of bit-flipping columns. In either case, the bit in a predetermined row in a bit-flipping column is not flipped.

The value to be stored in the bit-flipping information register is basically the one stored in its registers but can be varied for each child pattern. If that is the case, it is necessary to add to the bit-flipping information register694another circuit for generating a pattern for flipping bits in desired rows. Although, in the circuit shown inFIG. 37, the bit-flipping information register694and counters681and682are connected on a scan chain, it is also allowable to arrange that the initial value for the bit-flipping information register694is entered independently of the counters. If so, the value of the bit-flipping information register694can be controlled independently of the counters.

As can be understood from the above description, information necessary for the test method for a semiconductor integrated circuit according to this invention, or initial values for test pattern generators can be calculated by following the above procedures.

The invention has been described with reference to the preferred and alternate embodiments. Obviously, modifications and alternations will occur to those of ordinary skill in the art upon reading and understanding the present invention. It is intended that the invention be construed as including all such modification and alternation in so far they come with the scope of the appended claims or the equivalent thereof.