the architecture of a bit - fixing bist scheme according to the present invention is shown in fig3 . an lfsr 24 , or other similar sequence generator , feeds a binary sequence into a scan chain 26 through a bit - altering logic circuit 28 . bit - altering circuit 28 alters predetermined bits of the sequence in accordance with fix - to - 1 and fix - to - 0 signals from a bit - fixing ternary sequence generator 30 . if neither signal is active , the sequence passes unaltered into the scan chain . the purpose of the bit - fixing ternary sequence generator 30 is to generate bit - fixing signals used to alter the pseudo - random sequence of bits that is shifted into the scan chain 26 . the pattern of alteration is selected in order to embed into the sequence deterministic test cubes that will ensure complete fault coverage . the specific alteration signals generated by bit - fixing ternary sequence generator 30 depend upon a state of the lfsr 24 , as described in more detail below . fig4 is a block diagram showing the components of bit - fixing ternary sequence generator 30 . the ternary sequence generator 30 comprises bit - fixing ternary sequence selection logic 32 which decodes a state of lfsr 24 , such as a subsequence starting state , and generates a ternary sequence identification ( id ). the ternary sequence id is stored in a ternary sequence id register 34 and then passed on to bit - fixing generation logic 36 . bit - fixing generation logic 36 generates bit alteration signals based upon the ternary sequence id and upon signals from a mod -( m + 1 ) counter 38 , where m is the length in bits of the scan chain . note that the mod -( m + 1 ) counter 38 is not additional overhead . it is needed in the control logic for any test - per - scan bist technique to generate a control signal to clock the circuit - under - test when the scan chain is full . thus , this scheme advantageously uses existing bist control logic . the mod -( m + 1 ) counter 38 counts the number of bits that have been shifted out of lfsr 24 and into the scan chain . after m bits have shifted , the scan chain is full , so when the counter reaches the ( m + 1 ) state , the pattern of bits in the scan chain is applied to the cut and the response is loaded back into the scan chain . at this point , the lfsr 24 contains the starting state for the next subsequence of bits that will be shifted into the scan chain . the bit - fixing ternary sequence selection logic 32 decodes the starting state in the lfsr 24 and selects a bit - fixing ternary sequence that will be used to alter the next sequence of bits . the selected bit - fixing ternary sequence id is loaded into the ternary sequence id register 34 . as the counter 38 counts through the next m bits that are shifted out of the lfsr 24 , the bit - fixing generation logic 36 generates the fix - to - 1 and fix - to - 0 control signals based on the value of the counter 38 and the bit - fixing ternary sequence id stored in the ternary sequence id register 34 . note that if both bit - fixing control signals are low , the original bit generated by lfsr 24 passes unaltered through bit - altering circuit 28 and into the scan chain . thus , if the bit - fixing ternary sequence element is an x , then both bit - fixing signals are set to 0 . for each subsequence that is shifted out of the lfsr 24 , the bit - fixing ternary sequence generator 30 is capable of generating one of 2 n different bit - fixing ternary sequences where n is the size of the ternary sequence id register 34 . a deterministic test pattern for an r . p . r . fault can be shifted into the scan chain by generating an appropriate bit - fixing ternary sequence for a given subsequence generated by the lfsr 24 . the bit - fixing ternary sequence fixes certain bits in the subsequence such that the resulting pattern that is shifted into the scan chain detects the r . p . r . fault . as will be described in more detail below , the bit - fixing ternary sequence generator 30 is designed so that it generates enough deterministic test patterns to satisfy the fault coverage requirement for the cut . bit correlations ( i . e . compatible values in particular bit positions ) among the test patterns for the r . p . r . faults are used to minimize both the number of different bit - fixing ternary sequences that are required and the amount of decoding logic . one characteristic of the test cubes for r . p . r . faults is that subsets of them often have the same specified bits ( i . e . 1 &# 39 ; s or 0 &# 39 ; s ) in particular bit positions ( this will be referred to as &# 34 ; bit correlation &# 34 ;). for example , the 1st , 2nd , and 3rd bit elements of the test cubes 11011 , 11x00 , and 1x0x0 are correlated , while the 4th and 5th elements are not . that is , all of the specified bits in the 1st and 2nd bit positions are 1 &# 39 ; s , and all of the specified bits in the 3rd bit position are 0 &# 39 ; s . however , the 4th and 5th bit positions have conflicts because some of the specified bits are 1 &# 39 ; s and some are 0 &# 39 ;&# 39 ; s . note that the unspecified elements ( i . e . the x &# 39 ; s ) do not matter . the reason why a significant amount of bit correlation often exists among the test cubes for the r . p . r . faults is probably due to the fact that several r . p . r . faults may be caused by a single random pattern resistant structure in the circuit . for example , if there is a large fan - in and gate in a circuit , then that may cause all of the input stuck - at 1 faults and the output stuck - at 0 fault of the gate to be r . p . r . accordingly , many of the specified bits in particular bit positions of the test cubes for these r . p . r . faults will be the same . thus , there will be a significant amount of bit correlation among the test cubes . this phenomenon is seen in weighted pattern testing where probabilistic biasing of certain bit positions results in detecting a significant number of r . p . r . faults . according to the teaching of the present invention , bit correlation among the test cubes for the r . p . r . faults is advantageously used to minimize both the number of different bit - fixing ternary sequences that are required and the amount of decoding logic needed . a procedure for designing a test pattern generator in accordance with the present invention is now described . for a given lfsr and cut , a bit - fixing ternary sequence generator 30 which satisfies test length and fault coverage requirements can be designed using an automated procedure . according to this procedure , the bit - fixing ternary sequence generator 30 is designed to produce bit - fixing signals that alter the pseudo - random bit sequence generated by the lfsr to achieve the desired fault coverage for the given test length ( number of scan sequences applied to the circuit - under - test ). the first step in the design procedure is to simulate the r - stage lfsr for the given test length l to determine the set of pseudo - random subsequences that would normally be applied to the circuit - under - test . for each of the l subsequences that are generated , the starting r - bit state of the lfsr is recorded ( i . e ., the contents of the lfsr right before shifting the first bit of the subsequence into the scan chain ). fault simulation is then performed on the cut for the bit subsequences to see which faults are detected and which are not . the bit subsequence that drops each fault from the fault list ( i . e ., detects the fault for the first time ) is recorded . the faults that are not detected are the faults that require altering of the subsequence . the pseudo - random sequence must be altered to generate test patterns that detect the undetected faults . an automatic test pattern generation ( atpg ) tool is used to obtain test cubes for the undetected faults by leaving unspecified inputs as x &# 39 ; s . a simple contrived design example will be used to illustrate the procedure . a test pattern generator will be designed to provide 100 % fault coverage for a sequence of 12 test subsequences ( l = 12 ) generated by a 5 - stage lfsr ( r = 5 ) and shifted into a 12 - bit scan chain ( m = 12 ), as shown in fig5 . the 12 bit subsequences that are generated by the lfsr and applied to the circuit - under - test through the scan chain are shown in table 1 . table 1______________________________________starting subsequence faultsstate generated dropped______________________________________01011 010000101011 711010 111110011010 511000 010111011000 200001 110100100001 011100 110001111100 101110 000010101110 001001 111001101001 000011 011101100011 000101 010010000101 010011 000111110011 111011 001010111011 000100 100110100100 0______________________________________ for each subsequence , the starting state of the lfsr is shown and the number of faults that are dropped from the fault list is shown . five of the subsequences drop faults while the other 7 do not . the pseudo - random subsequences detect 16 out of 20 possible faults giving a fault coverage of 80 %. a conventional atpg tool is used to obtain test cube patterns for the 4 undetected faults . these patterns are shown in table 2 . the bit - fixing ternary sequence generator must be designed so that it alters the pseudo - random bit sequence in a way that all 4 test cubes are present in the scan chain . once the set of test cube patterns for the undetected faults has been obtained , the bit - fixing ternary sequence generator 30 is then designed to produce the bit - fixing ternary sequence signals corresponding to the test cube patterns . the bit - fixing signals are applied to the pseudo - random sequence in a way that guarantees that faults currently detected by the pseudo - random bit sequence will remain detected after the sequence is altered by the bit - fixing signals . this is done by only altering those bit subsequences that do not drop any faults . as long as the other subsequences that drop faults are not altered , the dropped faults are guaranteed to remain detected . this ensures that fault coverage will not be lost in the process of altering the original bit subsequences . the goal in designing the bit - fixing ternary sequence generator 30 is to generate the required bit - fixing signals with a minimal amount of hardware . a hill - climbing strategy is used in which one bit position at a time is added to the ternary sequence id register based on maximizing the number of test cubes that are generated each time . bit positions continue to be added to the ternary sequence id register until a sufficient number of test cubes can be generated to satisfy the fault coverage requirement . complete fault coverage can be obtained by designing the circuit to generate test cubes for all of the undetected faults . for each bit position that is added to the ternary sequence id register during design , the first step is to determine for which subsequences the bit will be active ( i . e . which subsequences will be altered ). in order not to reduce the fault coverage , it is important to choose a set of subsequences that do not currently drop any faults in the cut . in order to minimize the bit - fixing ternary sequence selection logic 32 , it is also important to choose a set of bit subsequences that are easy to decode . the set of bit subsequences for which the new ternary sequence id register bit will be active are decoded from the starting state of the lfsr for each sequence . let f be a boolean function equal to the sum of the minterms corresponding to the starting state for each bit subsequence that drops faults . then an implicant in f &# 39 ; corresponds to a set of subsequences that do not drop faults and can be decoded by an n - input and gate , where n is the number of literals in the implicant . a conventional binate covering procedure can be used to choose the largest implicant in f &# 39 ;. the largest implicant requires the least logic to decode and corresponds to the largest set of pseudo - random bit subsequences that do not drop any faults and thus is most desirable . these are the bit subsequences that will activate the new ternary sequence id register bit . in the design example there are 5 starting lfsr states that correspond to the bit subsequences that drop faults . they are listed in table 3 . the function f is formed . and the largest implicant in the complement of f is found . the largest implicant is 00xxx . accordingly , whenever the first two bits in a starting state of the lfsr are both ` 0 `, then the new ternary sequence id register bit is activated . thus , there are 4 bit subsequences for which the new ternary sequence id register bit will he activated . after the set of subsequences that activates the new ternary sequence id register bit have been determined , the next step is to determine which bits in the subsequences will be fixed when the new ternary sequence id register bit is activated . the goal is to fix the bits in a way that maximizes the number of test cubes . the strategy is to find some good candidate sets of bits to fix and then compute how many test cubes would be generated if each were used . the candidate that produces the largest number of test cubes is then selected . the candidate sets of bits to fix are determined by looking at bit correlation among the test cubes . for example , if the two test cubes 1010x and 00x11 are to be embedded , then fixing the 2nd bit position to a 0 , the 3rd bit position to a 1 , and the 5th bit position to a 1 would help to produce both test cubes . but fixing the 1st bit to a 1 or fixing the 4th bit to a 0 would only help to produce the first test cube ; it would prevent the second test cube from being generated . the reason for this difference is that the two test cubes have conflicting values in the 1st and 4th bit . so , given a set of test cubes to generate , the best bits to fix are the ones in which there are no conflicting values among the test cubes . a general procedure for selecting the set of bits to fix is as follows . 1 . place all test cubes to be generated into an initial set of test cubes . that is , begin by considering all of the test cubes that need to be generated to ensure complete coverage . in the design example , all 4 test cubes in table 2 are considered initially . 2 . identify candidate bit positions where there are no conflicting bits among the test cubes . that is , for each bit position , if one or more test cube has a 1 and one or more test cube has a 0 in that same bit position , then there is a conflict . if all of the test cubes have either a 1 or an x in a given bit position , then the bit can be fixed to a 1 . similarly , if all of the test cubes have either a 0 or an x in a given bit position , then the bit can be fixed to a 0 . in the design example , when all 4 test cubes in table 2 are considered , only the last bit position has no conflicting bit , since all 4 of the test cubes have either a ` 0 ` or an ` x ` in the last bit position . 3 . compute the number of test cubes that would be generated by fixing the candidate bits . that is , for each subsequence that activates the new ternary sequence id register bit , fix the candidate bits that were determined in step 2 . count the number of test cubes that are generated by altering the subsequences by the resulting bit - fixing ternary sequence . in the design example , when the last bit position is fixed to a 0 in the 4 subsequences , it generates the test cube 01xx01xxxx10 , which is used to alter the pseudo - random subsequence 011101100011 . 4 . if the number of test cubes for this candidate set of bits is larger than that of the best candidate then mark this set as the best candidate . the goal of choosing the set of bits to fix is to generate as many test cubes as possible . 5 . remove the test cube that will eliminate the most conflicts . one test cube is removed from consideration in order to increase the number of bits that can be fixed . the test cube that is removed is chosen based on reducing the number of conflicting bits in the remaining set of test cubes . in the design example , if the third test cube is eliminated from consideration , the remaining 3 test cubes have two bit positions where there are no conflicts . the third bit can be fixed to a 1 in addition to fixing the last bit to a 0 . 6 . if the number of test cubes that are embedded by the best candidate is greater than the number of test cubes that remain , then select the best candidate . otherwise loop back to step 2 . the next candidate set of bits to fix will only help to generate the remaining set of test cubes , and therefore has limited potential . if it is not possible for the next candidate to embed more test cubes than the best candidate , then the best candidate is selected as the set of bits to fix . 7 . eliminate as many fixed bits as possible without reducing the number of generated test cubes . in order to minimize hardware area , it is desirable to fix as few bits as possible . it may be possible to generate the test cubes without fixing all of the bits in the selected set . an attempt is made to reduce the number of fixed bits by eliminating one bit at a time and checking to see if the same test cubes are generated . the bit - fixing ternary sequence generator is designed so that when the new ternary sequence id register bit is activated , the set of bits selected by the procedure above is fixed . the pseudo - random bit subsequences that are altered to contain each test cube are added to the set of subsequences that drop faults ( one subsequence per generated test cube ). this is done to ensure that those subsequences are not further altered such that they would no longer generate the required test subsequences . if the fault coverage is not sufficient after adding the new ternary sequence id register bit , then another ternary sequence id register bit is added to allow for the generation of more test cubes . in the design example , when all 4 test cubes are considered , the only specified bit position where there are no conflicts is the last bit position which can be fixed to a 0 . fixing this bit generates one test cube . however , when one of the test cubes is eliminated from consideration then the remaining 3 test cubes have two bit positions where there are no conflicts . fixing these two bits enables all 3 of the remaining test cubes to be embedded . thus , this is the selected set of bits to fix when the new ternary sequence id register bit is activated . there is still one test cube that has not been generated , however . since complete fault coverage is required , another bit must be added to the ternary sequence id register . the three pseudo - random subsequences which generate the three test cubes are added to the set of subsequences that drop faults , and the procedure for adding a new ternary sequence id register bit is repeated . when enough bits have been added to the ternary sequence id register to provide sufficient fault coverage , the remaining task is to synthesize the bit - fixing ternary sequence generation logic 36 . the bit - fixing ternary sequence generation logic generates the fix - to - 1 and fix - to - 0 control signals to fix the appropriate bits in the sequence depending on which ternary sequence id register bits are active . for each ternary sequence id register bit that is active , control signals are generated when certain states of the counter are decoded . the process of constructing the bit - fixing ternary sequence generation logic is best explained by an example . the bit - fixing ternary sequence generation logic for the design example is shown in fig6 . the first bit in the ternary sequence id register 34 is activated whenever the first two bits in the starting seed for a subsequence are both 0 . this condition is decoded using bit - fixing ternary sequence selection logic 32 . in particular , a two - input and gate 40 in selection logic 32 ensures that the first bit of the ternary sequence id register is 1 when the first two bits of the lfsr seed are 0 . the id register is loaded right before shifting a new subsequence into the scan chain . when the first bit in the ternary sequence id register is active , it fixes the first bit shifted into the scan chain to a 0 and the tenth bit shifted into the scan chain to a 1 . this is done by generating a fix - to - 0 signal when the counter is in the &# 34 ; cnt - 1 &# 34 ; state and a fix - to - 1 signal when the counter is in &# 34 ; cnt - 10 &# 34 ; state . the second bit in the ternary sequence id register is activated whenever the third and fourth bits in the starting seed for a sequence are both 1 . when the second bit in the ternary sequence id register is activated , it fixes the second bit shifted into the scan chain to a 0 . this is done by generating a fix - to - 0 signal when the counter is in &# 34 ; cnt - 2 &# 34 ; state . when constructing the bit - fixing ternary sequence generation logic 36 , the states of the counter can be decoded by simply using n - input and gates where n is equal to the number of bits in the counter . however , once the logic has been constructed , it should be minimized using , for example , a conventional multilevel logic optimization tool . the &# 34 ; don &# 39 ; t care &# 34 ; conditions due to the unused states of the counter can be used to minimize the logic , but more importantly , the logic can be factored . because the number of inputs to the logic is small , factoring is very effective for significantly minimizing the bit - fixing ternary sequence generation logic . since the bit - fixing ternary sequence generation logic is synthesized from a two - level starting point , it can be made prime and irredundant using synthesis procedures known in the art . if the full &# 34 ; don &# 39 ; t care &# 34 ; set is used ( i . e ., all input combinations that do not occur during bist are &# 34 ; don &# 39 ; t cares &# 34 ;), then the resulting logic will be 100 % tested for single stuck - at faults by the patterns applied during bist . the procedure described above has been used to design bit - fixing ternary sequence generators for benchmark circuits that contain random - pattern - resistant faults . the primary inputs and flip - flops in each circuit were configured in a scan chain . the bit - fixing ternary sequence generators were designed to provide 100 % fault coverage of all detectable single stuck - at faults for a test length of 10 , 000 patterns . the results are shown in table 4 . the size of the scan chain is shown for each circuit , followed by the maximum number of specified bits in any test cube contained in the test set ( as reported in hellebrand et al ., &# 34 ; pattern generation for a deterministic bist scheme ,&# 34 ; proc . of international conference on computer - aided design ( iccad ), pp . 88 - 94 , 1995 ). if the characteristic polynomial of the lfsr is primitive ( as is the case in these results ) and the number of stages in the lfsr is greater than or equal to the number of specified bits in a test cube for a fault , then the lfsr is guaranteed to be capable of generating patterns that detect the fault . if the number of stages in the lfsr is less than the number or specified bits in a test cube for some fault , then it may not be possible for the lfsr to generate a pattern that detects the fault due to linear dependencies in the lfsr . table 4______________________________________ bit - fixing ternarycircuit reseeding sequences scan max . no . lfsr rom lfsr id reg . literalname size spec . bits size size size size count______________________________________s420 34 20 20 250 20 1 27 14 3 70 10 4 70s641 54 22 22 183 22 2 63 14 4 87 9 6 109s838 66 36 36 1623 36 5 168 14 7 176 12 7 199s1196 32 17 17 267 17 4 67 14 4 71 12 8 102s5378 214 19 27 726 19 3 163 14 4 174 12 9 367c2670 233 48 60 3412 48 4 328 16 5 334 10 12 427c7552 207 100 100 5241 100 7 741 36 8 782 17 13 828______________________________________ results are shown for the test pattern generator required for different size lfsr &# 39 ; s . for each different size lfsr , the number of bits in the ternary sequence id register is shown along with the factored form literal count for the multilevel logic required to implement the test pattern generator . for each circuit , results are shown for an lfsr with as many stages as the maximum number of specified bits . these lfsr &# 39 ; s are guaranteed to be capable of generating patterns to detect all of the faults . for the smaller lfsr &# 39 ; s there are some faults that are not detected because of linear dependencies in the lfsr . extra test cubes must be produced in order to detect those faults thereby resulting in an increase in the area of the test pattern generator . as can be seen , in some cases adding just a small amount of logic to the test pattern generator permits the use of a much smaller lfsr . consider c2670 ; using a 16 - stage lfsr instead of a 48 - stage lfsr only requires an additional 6 literals . however , in some cases there is a large increase in the amount of logic required for using a smaller lfsr . consider s5378 ; using a 12 - stage lfsr instead of a 14 - stage lfsr increases the amount of logic in the test pattern generator by more than a factor of two . results for the reseeding method presented by hellebrand et al . are shown in table 4 for comparison . the size of the lfsr and the number of bits stored in a rom are shown . note that the reseeding method requires that the lfsr have at least as many stages as the maximum number of specified bits in any test cube . it is difficult to directly compare the two methods because they are implemented differently ( rom versus multilevel logic ) and require very different control logic . the reseeding method requires that the lfsr have programmable feedback logic and parallel load capability as well as additional control logic for loading the seeds from the rom . there are numerous new and important features that distinguish the mixed - mode scheme disclosed above from other mixed - mode schemes for test - per - scan bist . one is that the present method deterministically alters a pseudo - random bit sequence to contain predetermined test cubes for detecting random - pattern - resistant faults . since there are so many possible pseudo - random sequences , correlations between certain bit positions can be used to minimize the test pattern generator hardware another feature is that a one - phase test may be used . having only one phase simplifies the bist control logic . a third feature is that smaller lfsr &# 39 ; s can be used . there is a tradeoff between the size of the lfsr and the amount of bit - fixing logic , so the lfsr size can be chosen to minimize the overall area . these features , and others , make the scheme of the present invention an attractive option for bist in circuits with scan . in addition , it should be emphasized that this method allows for a reduction in the size of the sequence generator . one way to achieve an even greater overhead reduction is to combine the present bit - fixing technique with various reseeding techniques . for example , by reseeding the lfsr with just a few selected seeds to generate some of the least correlated test cubes that require a lot of bit - fixing to generate , it may be possible to significantly reduce the complexity of the test pattern generator . another way to reduce the overhead is to develop a special atpg procedure that finds test cubes for each r . p . r . fault in a way that maximizes the bit correlation among the test cubes . this reduces the amount of bit - fixing that is required to generate the test cubes . note that while the experimental results presented in this paper were for single stuck - at faults , the approach of embedding deterministic test cubes in a pseudo - random sequence works for other fault models ( e . g .. multiple stuck - at faults and bridging faults ) as well . those skilled in the art will appreciate that the above embodiment may be altered in many ways without departing from the scope of the invention . for example , the lfsr may be replaced by another other circuit which generates pseudo - random bit sequences , such as a cellular automaton . moreover , the bit sequences need not be pseudo - random , but may be any type of bit sequences whose bits fluctuate in value . in addition , the sequence generator may feed more than one scan line from different stages . alternatively , multiple scan lines can be produced by multiple sequence generators . also , the feedback algorithm in the lfsr or similar circuit can be changed instead of , or in addition to , reseeding . another possible variation of the invention is to use a rom to generate a set of subsequences n times and have bit - fixing logic that alters each subsequence n different ways . for example , a rom can contain q subsequences , and each subsequence can be loaded from the rom and shifted into the scan chain n times . each time a subsequence is shifted into the scan chain , some bit - fixing logic is used to alter the subsequence so that it detects r . p . r . faults . the alteration is controlled by a counter which keeps track of how many times a particular subsequence has been shifted into the scan chain . bit correlation among the test cubes for the r . p . r . faults is exploited in this manner by repeatedly generating a subsequence that is very similar to some of the test cubes and performing a small amount of bit - fixing to make the subsequence match a different test cube each time it is generated . these and other variations will be obvious to those skilled in the art . accordingly , the scope of the invention should be determined not by the specific embodiments described in detail above , but by the following claims and their legal equivalents .