Abstract:
A test circuit which utilizes a multi-bit impact signature register and an additional register coupled to the output of the signature register and configured as a linear feedback multi-stage shift register. The total number of stages in the two registers is larger than the width of the test data (number of bits) to be input. A single feedback loop couples the output of the last additional register stage back to the first stage of the signature register. Each bit of the test data is input to an exclusive-or element at the input to each stage of the shift register and is exclusive-or-operated sequentially with the result of an exclusive-or operation stored in the preceding stage, and the result of the operation in the last stage is fed from the additional register back to the first-stage exclusive-or- element of the signature register with a delay. Only one additional register having one or more stages is required for the hardware configuration while providing an error detecting rate of the same degree as the case of using a primitive polynomial, simplifying the actual circuit configuration, and reducing the occupying area on the chip.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a test circuit for a microprocessor or the like, and more specifically, relates to a test circuit having a signature register. 
     2. Description of Related Art 
     FIG. 1 is a schematic diagram showing an example of the conventional circuit configuration of a multi-input signature register. 
     In FIG. 1, numeral 1 designates signal lines, numeral 2 designates exclusive-or elements, numeral 3 designates registers, numeral 4 designates feedback taps, numeral 5 designates signature output terminals for outputting a test result, and numeral 6 designates an input terminal of a clock CLK. 
     The number of the signal lines 1 is n(1 0  through 1 n-1 ) corresponding to the number of bits n of a test data I(x), and each of them is connected to one input of each of the exclusive-or elements 2(2 0  through 2 n-1 ). Also, outputs of the respective exclusive-or elements 2 0  through 2 n-1  are inputted to the registers 3 0  through 3 n-1  of D 0  through D n-1 . 
     Outputs of the registers 3 0  through 3 n-1  (D 0  through D n-1 ) are connected to the feedback taps 4 n-1  through 4 0  (P n-1  through P 0 ) and inputs of the next-stage exclusive-or elements 2&#39; n-1  through 2&#39; 1 , and become the test result output lines 5 0  through 5 n-1  of a signature output of n bits S(x), respectively. 
     Each output of the feedback taps 4 n-1  through 4 1  (P n-1  through P 1 ) is connected to one input of each of the exclusive-or elements 2&#39; n-1  through 2&#39; 1 , and to the other input of each of the exclusive-or elements 2&#39; n-1  through 2&#39; 2 , each of the next-stage exclusive-or elements 2&#39; n-2  through 2&#39; 1  is connected in a feedback manner (note that the output of the feedback tap 4 0  (P 0 ) is connected to 2&#39; 1 ). Then, the output of the exclusive-or element 2&#39; n-1  whereto the output of the feedback tap 4 n-1  (P n-1 ) is inputted is connected to the other input of the exclusive-or element 2 0  giving an output to the register 3 0  (D 0 ). 
     Also, an output string Y(x) of the last-stage register 3 n-1  (D n-1 ) is coupled to the feedback tap 4 0  (P 0 ), and becomes the test result output line 5 n-1 . 
     In addition, each of the registers 3 0  through 3 n-1  is configured as a flip-flop synchronized with the clock CLK input to the clock input terminal 6. Then, as to the presence or absence of a feedback loop from each of the registers 3 0  through 3 n-1 , when a set value p j  (i=0 through n-1) of each of the feedback taps 4 n-1  through 4 0  (P n-1  through P 0 ) is &#34;1&#34;, connection is made and a feedback loop is configured, and when the set value is &#34;0&#34;, no connection is made and no feedback loop is configured. 
     In addition, in the case of p j  =&#34;0&#34;, the exclusive-or elements 2&#39; n-1  through 2&#39; 1 , to which the outputs of the feedback taps 4 n-0  through 4 0  are coupled, are not required. 
     FIG. 2 illustrates a single-input signature register as contrated with the signature register having an n-bit input shown in FIG. 1, but both are the same in principle. 
     A test data 1(I(x)) coupled as an input to the single-input signature register shown in FIG. 2 is input to the exclusive-or element 2 0  in synchronism with the clock 6 (CLK). Then, it is sequentially operated on using the exclusive-or elements 2; and the flipflops 3;, with the result of each operation being transferred to the next-stage flip-flop 3. 
     FIG. 2 shows a circuit wherein a division by the following characteristic polynomial is executed. 
     
         P(x)=x.sup.n +P.sub.n-1 x.sup.n-1 + . . . +P.sub.2 x.sup.2 +p.sub.1 x+p.sub.0                                                 ( 1) 
    
     Here, when the value of pj is &#34;1&#34;, the connected state is represented, and when the value is &#34;0&#34;, the non-connected state is represented, respectively. 
     The test data I(x) as shown by the following equation (2) is inputted sequentially from a higher-order term to such a circuit. 
     
         I(x)=i.sub.m x.sup.m + . . . +i.sub.2 x.sup.2 +i.sub.1 x+i.sub.0( 2) 
    
     When the original input term first reaches the flip-flop 3 n-1  (D n-1 ) (when it becomes &#34;1&#34;), feedback is applied according to the value of P n-1  through P o  set in each feedback tap 4. 
     This means that the circuit shown in FIG. 2 performs the following operation. ##EQU1## 
     Next, when the value of the register is shifted by one and x n  appears, a subtraction is executed, and when x n  does not appear, no subtraction is executed. Such an operation is a division, and it is understood that the circuit shown in FIG. 2 is a division circuit by means of a characteristic polynomial P(x). 
     Accordingly, the output string Y(x) is equivalent to a quotient Q(x) of the test data I(x) divided by P(x), and a residue R(x) thereof is held in each flip-flop 3. 
     
         I(x)=Q(x)·P(x)+R(x)                               (3) 
    
     
         Y(x)=Q(x)                                                  (4) 
    
     
         Where, 
    
     
         Quotient:Q(x)=q.sub.m-n x.sup.m-n + . . . +q.sub.2 x.sup.2 +q.sub.1 x+q.sub.0                                                 ( 5) 
    
     
         Residue: R(x)=r.sub.n-1 x.sup.n-1 + . . . +r.sub.2 x.sup.2 +r.sub.1 x+r.sub.0                                                 ( 6) 
    
     Consideration will now be made of the effect on the value of each flip-flop 3 (register value) when an error string e(x) is contained in the test data I(x). 
     The error string e(x) is represented by the following equation. 
     
         e(x)=Qe(x)·P(x)+Re(x)                             (7) 
    
     Therefore, the test data containing an error is represented as follows. 
     
         I(x)+e(x)=(Q(x)+Qe(x))·P(x)+(R(x)+Re(x))          (8) 
    
     Then, as the register value (signature S(x)) after the quotient (Q(x)+Qe(x)) has been output, the residual (R(x)+Re(x)) containing the error remains. By judging whether or not the signature S(x)=R(x) holds from this, the error can be detected. 
     However, when e(x) is reducible by P(x), the signature becomes the same as the true value, and therefore the error is missed. 
     A similar problem exists also in the multi-input circuit shown in FIG. 1. In the FIG. 1 example, the test data has a width of n and a depth of m, and therefore data is input in parallel in synchronism with the clock CLK. Thereafter, the compressed data present as the test result on output lines 5 is compared with correct data, and the presence or absence of an error in the test data is determined. 
     Since the signature register compresses data for the purpose of reducing the testing time, this produces a high probability of missing an error in the process. This probability of missing an error is referred to as the error missing probability. 
     In the signature register having the conventional circuit configuration, a primitive polynomial is adopted as a characteristic polynomial to reduce the error missing probability. However, this increases the area occupied by the circuit in the case where an actual circuit is configured on a chip, and as described above, the feedback loop is required to be configured by disposing the exclusive-or elements at positions corresponding to the number of terms. As a consequence the positions of disposition of these elements become irregular, resulting in a complicated circuit design. 
     SUMMARY OF THE INVENTION 
     The present invention provides a test circuit which can suppress the error missing probability lower than 1/2 n , where n is the number of bits of a test input signal. As an example, the invention affords an error detecting rate of 99.99847% or more in the case of n=16. 
     A test circuit in accordance with the present invention utilizes a so-called signature register configured as a linear feedback shift register; is provided with a number of registers larger than the width (number of bits) of test data to be input to the circuit and is provided with a feedback loop which feeds back only the output from the last register in the series. 
     In the test circuit of the present invention, each bit of the test data is input to an exclusive-or element associated to a corresponding stage of the shift register. Each shift register stage is coupled in sequence to the exclusive-or element in the next stage, and the result of the operation in the last stage is fed back with a delay from an additional register coupled to the output of the last stage to the first-stage exclusive-or element. 
     The above and further objects and features of the invention will more fully be apparent from the following detailed description with accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a circuit diagram showing a conventional general multi-input signature register, 
     FIG. 2 is a circuit diagram showing a conventional general single-input signature register, 
     FIG. 3 is a circuit diagram showing a test circuit in accordance with the present invention, 
     FIG. 4 is an illustrative table relating the number of register stages, the number of steps in a test sequence and the number of exclusive-or-operated probabilities of test data error for 6 bit input data, 
     FIG. 5 is a graph showing the error missing rate when n is 16 and the number of registers is 17, and 
     FIG. 6 is a graph showing the error missing rate when n is 16 and the number of registers is 18; and 
     FIG. 7 is a circuit diagram showing a test circuit in accordance with the present invention having an additional register with a plurality of stages. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Hereinafter, detailed description is made of the present invention based on drawings showing embodiments thereof. 
     In addition, in an embodiment detailed hereinafter, description is made principally of an example wherein the number of stages of registers is larger by one than the width of the test data to be input. It is noted that the present invention is applicable also to the case where the number of stages is larger by two or more. 
     FIG. 3 is a schematic diagram showing a configuration of a test circuit, that is, a signature register of the present invention. 
     In FIG. 3, numerals 1 0  through 1 n-1  designate signal lines to which respective bits of a test data I(x) are input. 
     Numerals 2 0  through 2 n-1  designate exclusive-or elements to one input of which each of the signal lines 1 0  through 1 n-1  is connected. 
     Numerals 3 0  through 3 n  designate registers, which are provided in a number n+1 in the circuit of the present invention. Each of the registers 3 0  through 3 n  is configured, respectively, with flip-flops D 0  through D n , and the output of each of the exclusive-or elements 2 0  through 2 n-1  is coupled to the data input terminal of the adjacent register. Thus, each of the flip-flops D 0  through D n-1  corresponds to each of the n number of signal lines 1 0  through 1 n-1 , and additional flip-flop D n  (register 3 n ) coupled to the data output of the flip-flop D n-1  is also provided. The output of flip-flop 3 n  is connected to the other input of the exclusive-or element 2 0 , the output of which is coupled to the input of first-stage flip-flop D 0  to provide a feedback loop 40. 
     Numerals 5 0  through 5 n  designate the signature output terminals for outputting the test results from the flip-flops D 0  through D n , respectively. 
     Numeral 6 designates a clock input terminal to which the clock CLK is coupled, which supplies the clock CLK to the n+1 flip-flops D 0  through D n . In the following description the quantity n+1= k. 
     Exclusive-or elements 2 0  through 2 n-1  and registers 3 0  through 3 n-1  comprise a first shift register, register 3 n  comprises a second shift register, and the first and second shift registers form a multistage shift register. Each exclusive-or element 2 0  (or 2 1  through 2 n-1 ) and each corresponding register 3 0  (or 3 1  through 3 n-1 ) compromise each test data latch and each such test data latch corresponds to each stage of the first shift register. The register 3 n  also comprises a test data latch (or dummy register) and corresponds to each stage (one stage in this embodiment) of the second register. 
     In addition, each stage (one stage in this embodiment) of the second shift register is considered to have an an exclusive-or element with one input permanently fixed to logical low level or is considered to be a dummy register which receives the output signal from the register in the preceding stage and samples this signal in synchronization with the clock signal. 
     A characteristic polynomial of the signature register having such a configuration is expressed by (1+x k ) or (1+x n+1 ). 
     Operation of the test circuit of the present invention shown in FIG. 3 is as follows. 
     In the circuit shown in FIG. 3, each of the flip-flops D 0  through D n  starts from the all-ZERO state, and when an error exists, it becomes &#34;1&#34;, and if the all-ZERO state is held after the test has been completed, it is judged that no error exists. Also, the case where a plurality of errors exist, resulting in that &#34;1&#34; is finally erased and the all-ZERO state is produced is referred to as &#34;missing the error&#34;. 
     First, the case where all inputs are erroneous (p=1: p is the probability of an error contained in a test pattern) is equivalent with the case in which one input of each of the exclusive-or elements 2 0  through 2 n-1  is &#34;1&#34; all the time. For this reason, when the initial value is &#34;0&#34;, the value of each of the flip-flops D 0  through D n-1  becomes &#34;0&#34; in an even sequence. 
     On the other hand, in the case where the flip-flop D n  is added after the last-stage flip-flop D n-1 , the case where all the exclusive-or elements 2 0  through 2 n-1  are put in the all-ZERO state takes place only when a shift is performed by the number of stages k of the flip-flops D. In other words, the error missing probability in the case of p =1 becomes 1/k. 
     Next, consideration is made for the case of 0&lt;p&lt;1. 
     Denoting a test data input to the i-th flip-flop D i-1  at the point of a test sequence j as S ij , and denoting the probability that an error is contained in the test data as p, since the initial state is all-ZERO, the probability that an error is contained in the test data S io  in each flip-flop D at the point of the test sequence j=1 becomes as follows. 
     
         ______________________________________The first-stage flip-flop               D.sub.0 :    S.sub.11 = pThe second-stage flip-flop               D.sub.1 :    S.sub.12 = p.                   .       .    ..                   .       .    ..                   .       .    .The n-th-stage flip-flop               D.sub.n :    S.sub.1n = pThe (n + 1)-th-stage flip-flop               D.sub.n+ 1                       :    S.sub.1(n+ 1) = 0______________________________________ 
    
     In the case of j=2, exclusive-or of the present input and the probability of the value of the shifted flip-flop becomes as follows when exclusive-or operation is expressed by ##EQU2## 
     Then, hereinafter this continues as follows. ##EQU3## 
     On the other hand, paying attention to the i-th flip-flop, a probability t im  (=1-s im ) of the value becoming &#34;0&#34; at the point of a test sequence m is expressed as follows. ##EQU4## 
     A solution meeting the above-mentioned equation is given by the following equation. This means that the probability that the i-th flip-flop value at the point of the test sequence m is &#34;0&#34; is given by the following equation. ##EQU5## 
     The above shows that if the number of p to be exclusive-or-operated is confirmed, the error missing probability of the whole signature register is confirmed. 
     Here, consideration is made with the case of n=6 taken as example. FIG. 4 shows a table of a number t of p to be exclusive-or-operated. In addition, m represents the test sequence, and y represents the position (1≧y≧7) of the flip-flop D. From this table shown in FIG. 4, it is understood that the following relationship is obtained. ##EQU6## This relationship holds also for an arbitrary number n. 
     An error missing probability Pal of the whole signature register is given as a product of the error missing probabilities of the individual registers, being expressed by the following equation. ##EQU7## here, m: number of test vectors (sequence length of test data) 
     n: number of inputs of signature register (width of test data) 
     k: number of stages of signature register 
     p: probability of error contained in test pattern 
     Also, representing the exponential part of the numerator of Equation (11) by t, the following equation is obtained. ##EQU8## 
     Next, consideration is made on the case where the test sequence m is a multiple of the number of stages k of the register (m=αk). ##EQU9## 
     Here, since k=n+1, in the case where the test sequence m is a multiple of the number of stages k of the register, the exponential part t of (1-2p) of each term becomes the same. This shows that in the case of p=1, if α(k-1) is an even number, an error is missed. 
     In other words, if all of input data are erroneous (p=1), the case where error missing takes place differs depending on the number of data inputs n. Specifically, in the case where n is an even number, error missing in the case of p=1 takes place when the test sequence m is a multiple of n+1=k (the case of m mod. k=0), and in the case where n is an odd number, error missing in the case of p=1 takes place when the test sequence m is double of (n+1)=k (the case of m mod 2 k=0). 
     From the above, it is understood that the probability p of error contained in the test data to be input approaches 1/2 k  asymptotically in a range of 0&lt;p&lt;1, and in the case of p=1, it becomes 1/k. 
     The graph in FIG. 5 shows the error missing probability versus the test sequence m of the multi-input signature register in the case of n=16 and k=17. Note that a region of m&lt;k is not shown. From this graph in FIG. 5, the following is understood. 
     
         ______________________________________0 &lt; p &lt; 0.5      →            The missing probability Pal con-            verges smoothly to 1/2.sup.k.p = 0      →            The missing probability Pal takes a            value of 1/2.sup.k from the beginning.0.5 &lt; p &lt; 1      →            The missing probability Pal asymp-            totically approaches 1/2.sup.k while            oscillating.p = 1      →            The missing probability Pal becomes            1/k or 1/2.sup.k.______________________________________ 
    
     As described above, the missing probability Pal converges to 1/2 k  except for the case of p=1. Also, since n is an even number, an error is missed when the test sequence m is a multiple of k (=17), but an error is detected in the other cases. In other words, the missing probability Pal in the case of p=1 becomes 1/k. 
     The above case is an example where the number of stages k of the register is larger than the number of bits n of the test data by only one, and next description is made of the case where k is larger than n by two, that is, the number of stages of the register is larger than the number of bits of the test data by two. 
     In addition, in such a case where the number of stages k of the register is larger than the number of bits n of the test data, each added register is operated as a shift register connected in series. 
     The graph in FIG. 6 shows a characteristic of the error missing probability versus the test sequence of the multi-input signature register in the case of n=16 and K=18. Note that a region of m&lt;k is not shown. 
     The error missing probability Pal of the whole signature register in this case is given as a product of the error missing probabilities of the individual registers, being expressed by the following equation. ##EQU10## here, m: number of test vectors (sequence length of test data) 
     n: number of inputs of signature register (width of test data) 
     k: number of stages of signature register 
     p: probability of error contained in test pattern 
     Also, representing the exponential part of the numerator of Equation (13) by t, the following equations are obtained. ##EQU11## 
     Next, in the case where the test sequence m is a multiple of the number of stages k of the register (m=αk), Equation (14) becomes as follows. ##EQU12## This means that the exponential parts of the first through the n-th registers become α(k-2). 
     Equation (15) of the exponential part of the +1 register becomes as follows. ##EQU13## 
     Also, Equation (16) of the exponential part of the +2 register becomes as follows. ##EQU14## 
     Accordingly, all of the exponential parts of the term (1-2p) of k number of registers become α(k-2). 
     Here, the missing probability Pal in the case of p=1, in others words, in the case where all of the input data are erroneous becomes as follows, and an error is sometimes missed when α(k-2) is an even number. ##EQU15## 
     In other words, if all of the input data are erroneous (p=1), the case where error missing takes place differs depending on the number of data inputs. 
     Specifically, where n is an even number, error missing in the case of p=1 takes place when the test sequence m is a multiple of n+2=k (in the case of m mod k=0), and when n is an odd number, error missing in the case of p=1 takes place when the test sequence m is double of n+2=k (the case of m mod 2k=0). 
     From the above, it is understood that when the probability p of error contained in the test data to be input is within a range of 0&lt;p&lt;1, the error missing probability of this signature register asymptotically approaches 1/2 k , and becomes 1/k in the case of p=1. 
     The graph in FIG. 6 shows a characteristic of the error missing probability versus test sequence m of the multi-input signature register in the case of n=16 and k=18. Note that a range of m&lt;k is not shown. From the graph in FIG. 6, the following is understood. 
     
         ______________________________________0 &lt; p &lt; 0.5      →            The missing probability Pal con-            verges smoothly to 1/2.sup.k.p = 0      →            The missing probability Pal takes a            value of 1/2.sup.k from the beginning.0.5 &lt; p &lt; 1      →            The missing probability Pal asymp-            totically approaches 1/2.sup.k while            oscillating.p = 1      →            The missing probability Pal becomes            1/k or 1/2.sup.k.______________________________________ 
    
     As described above, the missing probability Pal converges to 1/2 k  except for the case of p=1. Also, since n is an even number, when the test sequence m is a multiple of k (=18), an error is missed, but an error is detected in the other cases. In other words, the missing probability Pal in the case of P=1 becomes 1/k. 
     In accordance with the test circuit of the present invention, an error detecting rate of the same degree as the case where the primitive polynomial is used is obtainable by configuring the signature register with registers whose number is larger than the width of the test data to be input even if the primitive polynomial is not used as a characteristic polynomial of the signature register, and only one feedback loop is required. Also, for the hardware configuration, only one auxiliary shift register having one or more register is added, and no additional exclusive-or elements are required for the auxillary shift register, therefore simplifying the actual circuit configuration and reducing the circuit occupying area on the chip. 
     As this invention may be embodied in several forms without departing from the spirit of essential characteristics thereof, the present embodiment is therefore illustrative and not restrictive, since the scope of the invention is defined by the appended claims rather than by the description preceding them, and all changes that fall within the metes and bounds of the claims, or equivalents of such metes and bounds thereof, are therefore intended to be embraced by the claims.