Скачати 250.36 Kb.

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 14, 645667 (1998) A General Structure of Feedback Shift Registers for BuiltIn Self Test KuenJong Lee, WeiLun Wang and JhingFa Wang Department of Electrical Engineering National Cheng Kung University Tainan, Taiwan 701, R.O.C. Email: kjlee@mail.ncku.edu.tw A mixedtype feedback shift register (MFSR) is similar to a linear feedback shift register (LFSR) except that the connection between two consecutive flipflops (F/F's) may be through the Q or output, and an extra inverter may exist at the input to the first flipflop (stage) of the register. In this paper, we exploit the properties of MFSR's and show that by using an MFSR based pseudorandom pattern generator (PRPG) or multiple input signature analyzer (MISA), several good features for builtin self test can be obtained. Specifically we show that: (1) for any given initial seed, an MFSR always exists that can generate the same serial output sequence as can an LFSR with the same characteristic polynomial and any initial seed; (2) for any MFSR, we can always find an initial seed for this MFSR such that it can generate the same serial output sequence as can an LFSR with the same characteristic polynomial and any initial seed; and (3) for any given initial seed and any test response to be compressed, an MFSR based MISA can usually be found that will result in any required final signature. If such an MFSR cannot be found for a specific initial seed and a specific test response sequence, we show that by simply adding one arbitrary dummy pattern to the test response, one can always find the required MFSR. We also show that if the characteristic polynomial of the MFSR based MISA can be chosen freely, it is almost guaranteed that a feasible MFSR can be found without adding any dummy patterns to the test response. For example, for a 16stage MISA, the probability that a feasible MFSR does not exist is less than 232768. Keywords: mixedtype feedback shift register, linear feedback shift register, pseudorandom pattern generator, multiple input signature analyzer. 1. INTRODUCTION Received November 19, 1996; revised July 16, 1997. Communicated by YounLong Lin. Due to their simple and regular structure, linear feedback shift registers (LFSR's) and their extended versions have been widely used in the testing of digital circuits [1]. These include BILBO [2], MLFSR [3], combined LFSR/SR [4], combined LFSR/XOR [5], cyclic LFSR [6], the LFSR based parallel pseudorandom pattern generator [7], the LFSR based pseudoexhaustive test pattern generator [8, 9, 19], the reseeding and characteristic polynomial reprogramming techniques [10, 11], the multiple seed LFSR [12], the twopattern generator [20] etc. The properties and theories of LFSR's have been discussed in [13, 14, 15, 16]. The applications of LFSR's to digital testing are found in two major fields. One is the use of an LFSR as a test pattern generator, known as a pseudorandom pattern generator (PRPG), and the other is the use of an LFSR as a test response compressor, known as a signature analyzer (SA) [1]. It is well known that an LFSR with a primitive characteristic polynomial can generate a maximum sequence (msequence) of length 2^{k}1 if it contains a nonzero initial seed, where k is the number of F/F's in the LFSR [15]. Therefore, provision of a nonzero initial seed is an essential requirement for using an LFSR as a PRPG unless some extra logic is used. Conventionally, one may use F/F's with both preset and clear (reset) control lines, or use an externally controllable scan path to provide the nonzero seed. Both methods require extra area overhead [17]. For the signature analysis application, it is also clear that when the initial seed and test response are fixed, the final signature is fixed [15]. To determine the correctness of this final signature, either some storage for the correct signature and some comparison circuitry must be added to the circuit (chip) under test (CUT), or the signature must be scanned out of the CUT for comparison. Again, both methods require extra hardware overhead. In this paper, we propose a generalized type of feedback shift registers, called a mixedtype feedback shift registers (MFSR's), that can be used to reduce the difficulty of the above problems. An MFSR is similar to an LFSR except that the connection between two consecutive stages of F/F's in an MFSR may be through the true (Q) or complementary () output of the preceding F/F stage, and the input to the first F/F stage may or may not go through an extra inverter. Fig. 1 shows an example of a 4stage MFSR in which the output of F/F3 is through Q while F/F1, F/F2, and F/F4 are through . An inverter presents before F/F1. Since, in general, both Q and of an F/F can be used for interstage connection, the circuit complexity of an MFSR is the same as that of an LFSR except that one extra inverter may be required at the input of F/F1. The structure of an MFSR implies that an LFSR is a special case of an MFSR, where all the connections are through Q and no inverter presents before the first F/F stage. The intrainverted feedback shift register (IFSR) proposed in [17] is also a special case of an MFSR, where all the connections are through , including the feedback from the last stage to the first stage. Since both LFSR's and IFSR's are special cases of MFSR's, all useful properties existing in LFSR's and IFSR's also exist in MFSR's. However, there are several unique properties of MFSR's that may not exist in LFSR's and IFSR's. In this paper, we shall exploit these properties of MFSR's, emphasizing their application to random number generation and signature analysis. We shall show that: (1) for any given initial seed, an MFSR always exists that can generate the same output sequence as can an LFSR with the same characteristic polynomial and any initial seed; (2) for any MFSR, we can always find an initial seed for this MFSR such that it can generate the same output sequence as can an LFSR with the same characteristic polynomial and any initial seed; and (3) for any given initial seed and any test response to be compressed, an MFSR based MISA can usually be found that will result in any required final signature. If such an MFSR cannot be found for a specific initial seed and a specific test response sequence, we will show that by simply adding one arbitrary dummy pattern to the test response, one can always find the required MFSR. We will also show that if the characteristic polynomial of the MFSR based MISA can be chosen freely, it is almost guaranteed that a feasible MFSR can be found without adding any dummy pattern to the test response. For example, in a 16stage MFSR based MISA, the probability that one would need an arbitrary dummy pattern is less than 2^{32768}. According to the above properties (1) and (2), we can see that the nonzero initial seed requirement for an LFSR based PRPG does not exist for an MFSR based PRPG. Hence, one can simply design an MFSR with the reset capability, which should be simpler than an LFSR with both the preset and reset capabilities. On the other hand, since the initial seed and the final signature of an MFSR based MISA can be chosen freely, much more design flexibility is allowed. For example, one may select an allzero pattern for both the initial seed and the final signature, hence, simplifying the seeding and signature checking process. Another application is that if a register is to be used as an MISA in one test session and a PRPG in the next session, then we can set the final signature of the first session to be the same as the initial seed of the PRPG for the next session, hence, eliminating the need for seed reloading. This paper is organized as follows. Section 2 gives a brief review of the well known LFSR's. Section 3 describes the structures and polynomial representation of MFSR's. Based on some formal theoretical analysis, Sections 4 and 5 relate the behaviors of the MFSR based PRPG and MISA to those of the LFSR based PRPG and MISA, respectively. A comparison between MFSR and IFSR based PRPG's is also given in Section 4. Finally, we give a discussion and draw conclusions in Section 6. ^ Depending on the positions of exclusiveor gates, there are two types of LFSR's. In this paper, we will only consider the internal type LFSR and its corresponding MFSR based on polynomial representation. The results obtained in this paper also apply to other types of LFSR's or MFSR's though analysis based on matrix representation may be necessary since it is difficult to conduct polynomial analysis on external type LFSR's or MFSR's. Hereafter, all LFSR's or MFSR's referred to are internal ones. The structure of a kstage LFSR is shown in Fig. 2. The behavior of this LFSR can be described using mathematical polynomial representation over GF(2). Its characteristic polynomial C(X) is defined as , where C_{0} = C_{k} = 1. The symbols * and + denote binary multiplication and addition over GF(2), respectively. The initial state (a_{1}, a_{2},......., a_{k}) can be represented using an initial state polynomial L0(X) as: . (1) The ith state polynomial Li(X), i.e., the content of the kstage LFSR after i shifts, is represented by L_{i}(X) = [X^{i}*L_{0}(X) mod C(X)] i = 0, 1, 2, ... (2) This equation has also been used in [17], and it indicates that the ith internal state in an LFSR is dependent on both the initial seed and the characteristic polynomial. Fig. 3 shows an example of an LFSR with C(X) = X^{4} + X + 1 and an initial seed (0110), where and are clear and preset control lines to each F/F. When the initial state (1011) is needed, we let the values at A and B in Fig. 3 be 0 and 1, respectively. ^ Refer to Fig. 4. The output of each F/F in a mixedtype feedback shift register (MFSR) is either in true (Q) or complementary () form and can be specified by the value of an inversion variable d_{i}. If the Q () output of the ith F/F in MFSR is used, then d_{i} is zero (one). For the input to the first stage, which is fed by the output of the last stage, we assume that an inversion variable d_{0} is used. Therefore, compared with an LFSR, the behavior of a kstage MFSR can be characterized by a characteristic polynomial C(X) of degree k, an initial seed (s_{1}, s_{2},......, s_{k}), and an inversion vector (d_{0}, d_{1},......, d_{k}). It should be pointed out again that the ExclusiveOR gates and the d_{i} inputs shown in Fig. 4 are merely for our convenience in analyzing the properties of MFSR's. In the actual implementation, they need not exist. For example, Fig. 1 shows an MFSR with (d_{0}, d_{1}, d_{2}, d_{3}, d_{4}) = (1, 1, 1, 1, 0, 1). Similar to the analysis of an LFSR, the initial state polynomial T_{0}(X) of a kstage internal type MFSR can be expressed as . (3) Let M_{i}(X) be a polynomial whose coefficients are the content of each F/F adding the corresponding inversion variable after i shifts and let the ith internal state polynomial of the MFSR be T_{i}(X) then T_{i}(X) can be represented by T_{i}(X) = M_{i}(X) + D(X) (4) where D(X) is the inversion polynomial of an MFSR and is defined as . (5) Note that M_{0}(X) does not depend on d0 and can be expressed as: M_{0}(X) = T_{0}(X) + D(X). (6) By the shift operation of an MFSR, we see that M_{1}(X) = [M_{1}(X) * X + D(X) + d_{0}] mod C(X) = [T_{0} (X) * X + D(X) * (X+1) + d_{0}] mod C(X). M_{2}(X) = [M_{1}(X) * X + D(X) + d_{0}] mod C(X) = [T_{0}(X) * X_{2} + D(X) * (X_{2} + X + 1) + d_{0} * (X+1)] mod C(X). : Therefore, we can obtain a general expression for M_{i}(X) of an internal type MFSR: M_{i}(X) = [T_{0}(X) * X^{i} + D(X)*(X^{i} + X^{i1}^{ }+ ... + X + 1) + d_{0}*(X^{i1}^{ }+ X^{i2}^{ }+ ... + X + 1)] mod C(X) = [T_{0}(X) * X^{i} + D(X)*(X^{i+1} + 1)/(X+1) + d_{0}*(X^{i} + 1)/(X+1)] mod C(X). (7) Substituting this equation into Eq. (4), we obtain T_{i}(X) = {T_{0}(X) * X^{i} + [D(X) * X + d_{0}]*(X^{i} + 1)/(X+1)} mod C(X). i = 0, 1, 2, ... (8) Fig. 1 shows an example of an MFSR with C(X) = X^{4} + X + 1 and an initial seed (0000). Here, the inversion vector (d_{0}, d_{1}, d_{2}, d_{3}, d_{4}) is (1, 1, 1, 0, 1). Note that the initial seed can be obtained by simply setting A to 0. ^ In this section, we will discuss an MFSR based PRPG and its relation to an LFSR based PRPG. Let {O_{m}} = {O_{0}, O_{1}, O_{2}, ...} and {O'_{m}} = {O'_{0}, O'_{1}, O'_{2}, ...} represent the output sequence generated by an LFSR based PRPG and an MFSR based PRPG, respectively, where O_{0} (O'_{0}) is the first bit appearing at the output, O1 (O'_{1}) is the second, and so on. Fig. 2 shows the configuration of an internal type LFSR based PRPG. Each bit of the output sequence from this PRPG can be expressed as: O_{0} = a_{k} O_{1} = C_{k1 }* O_{0} + a_{k+1} : O_{k1} = C_{k1 }* O_{k2} + C_{k2 }* O_{k3} + .. + C_{1 }* O_{0} + a_{1} O_{k} = C_{k1 }* O_{k1} + C_{k2 }* O_{k2} + ... + C_{2 }* O_{2}_{ }+ C_{1 }* O_{1} + O_{0}_{ } O_{k+1} = C_{k1 }* O_{k} + C_{k2 }* O_{k1} + ... + C_{2 }* O_{3} + C_{1 }* O_{2} + O_{1}_{ } : The above equations can be generalized as: for p = 0, 1, 2, ..., (k1) (9a) or for p = k, (k+1), ... (9b) Refer to Fig. 4. Assume that the MFSR under consideration has the same characteristic polynomial C(X); then, each bit of the output sequence from the kstage MFSR is represented as: O'_{0}_{ }= s_{k} + d_{k} O'_{1} = C_{k1 }* O'_{0} + s_{k+1} + d_{k1} + d_{k} : O'_{k1} = C_{k1}*O'_{k2} + C_{k2}*O'_{k3} + .. + C_{1}*O'_{0} + s_{1} + d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} O'_{k} = C_{k1}*O'_{k1} + C_{k2}*O'_{k2} + ... + C_{2}*O'_{2}_{ }+ C_{1}*O'_{1} + O'_{0}_{ }+ d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} O'_{k+1} = C_{k1}*O'_{k} + C_{k2}*O'_{k1} + ... + C_{2}*O'_{3} + C_{1}*O'_{2} + O'_{1}_{ }+ d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} : The general form of the above equations is expressed as: for p = 0, 1, 2, ..., (k1) (10a) or for p = k, (k+1), ... (10b) In the following, Lemmas 1 and 2 show the requirement that both LFSR and MFSR based PRPG's can generate the same output sequences. Lemma 1: For internal type LFSR and MFSR based PRPG's with the same characteristic polynomial of degree k, if they generate the same output sequence with initial seeds of (a_{1}, a_{2}, ..., ) and (s_{1}, s_{2}, ..., s_{k}), respectively, then the relationship between these initial seeds can be expressed as for i = 1, 2, ..., k. (11) Proof: Since the two output sequences of LFSR and MFSR based PRPG's are the same, from Eqs. (9a) and (10a), we have: O_{0} = O'_{0}, i.e., a_{k}_{ }=_{ }s_{k} + d_{k}_{ } O_{1} = O'_{1}, i.e., C_{k1}*O_{0} + a_{k+1}_{ }=_{ }C_{k1}*O'_{0} + s_{k+1} + d_{k1} + d_{k}, which implies a_{k+1}_{ }=_{ }s_{k+1} + d_{k1} + d_{k}. : O_{k1} = O'_{k1}, i.e., C_{k1}*O_{k2} + C_{k2}*O_{k3} + .. + C_{1}*O_{0} + a_{1} = C_{k1}*O'_{k2} + *O'_{k3} + .. + C_{1}*O'_{0} + s_{1} + d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k}, which implies a_{1} = s_{1} + d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k}. These can be generalized as follows: for p = 0, 1, 2, ..., (k1). Or equivalently, we have , for i = 1, 2, ..., k. Q.E.D. Lemma 2: For internal type LFSR and MFSR based PRPG's with the same characteristic polynomial of degree k, if they generate the same output sequence, then the weight of the inversion vector in an internal type MFSR based PRPG must be even, where the weight of the inversion vector is defined as the summation of all the inversion variables. Proof: Since internal type LFSR and MFSR based PRPG's with the same characteristic polynomial generate the same output sequence, by Eqs. (9b) and (10b), the kth bit output sequence is O_{k} = O'_{k}, i.e., C_{k1}*O_{k1} + C_{k2}*O_{k2} + ... + C_{2}*O_{2}_{ }+ C_{1}*O_{1} + O_{0} = C_{k1}*O'_{k1} + *O'_{k2} + ... + C_{2}*O'_{2}_{ }+ C_{1}*O'_{1} + O'_{0}_{ }+ d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k}, and the (k+1)th bit output sequence is O_{k+1} = O'_{k+1}, i.e., C_{k1}*O_{k} + C_{k2}*O_{k1} + ... + C_{2}*O_{3} + C_{1}*O_{2} + O_{1} =_{ }C_{k1}*O'_{k} + *O'_{k1} + ... + C_{2}*O'_{3} + C_{1}*O'_{2} + O'_{1}_{ }+ d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} : All these equations result in d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} = 0, i.e., . (12) Q.E.D. Lemma 3: For two internal type LFSR and MFSR based PRPG's with the same characteristic polynomial of degree k, if Eqs. (11) and (12) hold, then the sequences generated by the two PRPG's are the same. Proof: By Eq. (11), we have , and this can becomes a_{k}_{ }+ s_{k} = d_{k} a_{k+1} + s_{k+1} = d_{k} + d_{k1}_{ } : a_{1} + s_{1} = d_{k} + d_{k1}_{ }+ ... + d_{1} + d_{0} By Eq. (12) we obtain 0 = d_{k} + d_{k1}_{ }+ ... + d_{1} + d_{0} Substituting these equations into Eq. (10a), we get O'_{0}_{ }= s_{k} + d_{k} = a_{k} =_{ }O_{0} O'_{1} = C_{k1}*O'_{0} + s_{k+1} + d_{k1} + d_{k}_{ }=_{ }C_{k1}*O_{0} + a_{k+1} = O_{1} : O'_{k1} = C_{k1}*O'_{k2} + C_{k2}*O'_{k3} + .. + C_{1}*O'_{0} + s_{1} + d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} = *O_{k2} + C_{k2}*O_{k3} + .. + C_{1}*O_{0} + a_{1} = O_{k1} O'_{k} = C_{k1}*O'_{k1} + C_{k2}*O'_{k2} + .. + C_{1}*O'_{1} + O'_{0} + d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} = C_{k1}*O_{k1} + C_{k2}*O_{k2} + .. + C_{1}*O_{1} + O_{0} = O_{k} O'_{k+1} = C_{k1}*O'_{k} + C_{k2}*O'_{k1} + .. + C_{1}*O'_{2} + O'_{1} + d_{0}_{ }+ d_{1}_{ }+ d_{2} + ... + d_{k1} + d_{k} = C_{k1}*O_{k} + C_{k2}*O_{k1} + .. + C_{1}*O_{2} + O_{1} = O_{k+1} : By induction the lemma holds. Q.E.D. Theorem 1: If an internal type LFSR and MFSR have the same characteristic polynomial, then their output sequences are the same if and only if Eqs. (11) and (12) hold. Proof: Lemma 1 and 2 give the necessary condition while Lemma 3 gives the sufficient condition. Q.E.D. Given the initial seeds of an LFSR and an MFSR, the following example can be used to show how the inversion vector (d_{0}, d_{1}, d_{2}, ..., d_{k}) can be found. Example 1: If the LFSR shown in Fig. 3, which has the initial state (a_{1}, a_{2}, a_{3}, a_{4}) = (1, 0, 1, 1), and the MFSR shown in Fig. 1, which has the initial state (s_{1}, s_{2}, s_{3}, s_{4}) = (0, 0, 0, 0), generate the same output sequence, then by Eqs. (11) and (12), we can obtain five equations as follows: obtain five equations as follows: a_{4} + s_{4} = d_{4} = 1 (13a) a_{3} + s_{3} = d_{3} + d_{4} = 1 (13b) a_{2} + s_{2} = d_{2} + d_{3} + d_{4} = 0 (13c) a_{1} + s_{1} = d_{1} + d_{2} + d_{3} + d_{4} = 1 (13d) d_{0} + d_{1} + d_{2} + d_{3} + d_{4} = 0 (13e) To solve these equations, firstly, d4 can be found in Eq. (13a); then, substituting d4 into Eq. (13b), d3 can be found and so on. Finally, d0 can be found in Eq. (13e). Thus, the value of the inversion vector (d_{0}, d_{1}, d_{2}, ..., d_{4}) in the MFSR is (1, 1, 1, 0, 1). In general, since a new inversion variable can be obtained in each equation by means of the above procedure, and there are totally (k+1) equations for the (k+1) unknowns, the solution is unique and is quite easy to obtain. Based on Theorem 1, we can make two observations: (1) If the initial seed of an LFSR is given, then for any given initial seed, we can find an MFSR that can generate the same output sequence as can the LFSR. (2) If the inversion vector of an MFSR and the initial seed of an LFSR are given, then we can find an initial seed for this MFSR to generate the same output sequence. An immediate application of observation 1 is that the nonzero initial seed requirement for an LFSR based PRPG is no longer needed when an MFSR based PRPG is used. In fact, not only the allzero initial seed, but also any initial seed can be used. This property gives somehow surprising results when compared with the IFSR based PRPG proposed in [17]. As mentioned before, an IFSR is a special case of an MFSR with all connections between two stages being through . Our results here apparently state that given any LFSR with any initial seed, we can always find an IFSR that can generate an msequence that the LFSR can generate. However, in [17] it was stated that there exist some LFSR's that do not have corresponding IFSR's. Through careful examination, we can find that the inverter before the first F/F plays the major role in this difference. Due to this inverter, the weight of the inversion variable can be kept even; hence, we can always find an initial seed for any MFSR to generate the required msequence while in the IFSR design, freedom in selecting d0 is not allowed, which results in the inability to generate the output sequence of some LFSR's using IFSR. So far, we have discussed the properties of the output sequences generated by MFSR and LFSR based PRPG's. Now, we will consider the internal states of MFSR based PRPG's and then discuss parallel pattern generators. The following lemma shows the initial seed relationship between an LFSR and an MFSR from the point of view of polynomials. Lemma 4: For internal type LFSR and MFSR based PRPG's with the same characteristic polynomial, if the relationship between their initial seeds can be expressed by Eq. (11), then the relationship between their initial state polynomials can be represented by L_{0}(X) + T_{0}(X) = [X*D(X) + d_{0}] / (1 +X). (14) Proof: The initial state polynomial L_{0}(X) of a kstage internal type LFSR and T_{0}(X) of an internal type MFSR are expressed as and . By Eq. (11) the relationship between these initial seeds of the LFSR and the MFSR is expressed as for i = 1, 2, ..., k. Then, (since ) = T_{0}(X) + d_{0}_{ }+ X*(d_{0}_{ }+ d_{1}) + X^{2}*(d_{0}_{ }+ d_{1}_{ }+ d_{2}) + ... + X^{k1}*(d_{0}_{ }+ d_{1}_{ }+ ... + d_{k1}) = T_{0}(X) + d_{0}*(1 + X^{k})/(1+X) + d_{1}*X*(1 + X^{k1})/(1+X) + d_{2}*X^{2}*(1 + X^{k2}) /(1+X) + ... + d_{k1}*X^{k1}*(1 + X)/(1 +X) = T_{0}(X) + [X*D(X) + d_{0}]/(1 + X). Thus, the lemma. Q.E.D. Theorem 2: For internal type LFSR and MFSR based PRPG's with the same characteristic polynomial C(X), their ith internal state polynomials, L_{i}(X) and T_{i} (X), can be expressed as L_{i}(X) + T_{i}(X) = [X*D(X) + d_{0}] / (1 + X) (15) if and only if they generate the same output sequence. Proof: By Theorem 1 and Eq. (8), the ith internal state polynomial Ti(X) of an internal type MFSR based PRPG is expressed as: T_{i }(X) = {T_{0}(X)*X^{i} + [D(X)*X + d_{0}]*(X^{i} + 1)/(X+1)]} mod C(X). By Eq. (14), T_{i}(X) can be rewritten as T_{i}(X) = {L_{0}(X)*X^{i} + X^{i}*(X*D(X) + d_{0})/(X + 1) + (X*D(X) + d_{0})*(X^{i} + 1)/(X + 1)} mod C(X) = {L_{0}(X)*X^{i} + (X*D(X) + d_{0})/(X + 1)} mod C(X). = L_{i}(X) + (X*D(X) + d_{0})/(X + 1). Thus, the theorem. Q.E.D. Lemma 4 and Theorem 2 show that the relationship between the internal states of LFSR and MFSR based PRPG's is invariant. This means that (1) the sequence from any F/F output of an LFSR is the same as the sequence from the corresponding F/F output of the corresponding MFSR, and (2) each state transition of an LFSR from one state L_{i}(X) to another state L_{j}(X) of the LFSR has a corresponding state transition from one state T_{i}(X) to another state T_{i}(X) in an MFSR. Thus, the behavior of an LFSR can be completely mapped onto an MFSR. If it is required that the 2^{k}1 parallel patterns generated by kstage LFSR and MFSR based PRPG's be the same, then Theorem 2 can be used to determine how the output of an MFSR to a circuit under test can be tapped, as described next. Let the ith true outputs of LFSR and MFSR based PRPG's be (Q_{L})_{i} and (Q_{M})_{i}, respectively. Then, Eq. (15) becomes _{ }_{(16)} By equating both sides of Eq. (16), we can obtain . (17) Eq. (17) indicates that to obtain the same parallel patterns as obtained in LFSR based PRPG's, the ith true (complement) output of MFSR based PRPG's must be used if = 0 ( = 1). For example, to generate the same parallel patterns in Fig. 3, the parallel pattern generator outputs in Fig.1 must be () with the inversion vector (d_{0}, d_{1}, d_{2}, d_{3}, d_{4}) = (1, 1, 1, 0, 1). The following theorem shows how many different internal type MFSR based PRPG's can generate the same output sequence as that it can be generated by an internal type LFSR based PRPG. Theorem 3: For a given characteristic polynomial of degree k, if the initial seed can be arbitrarily selected, then there are 2^{k} MFSR based PRPG's which can generate the same output sequence as that generated by an LFSR based PRPG with a given initial seed. Proof: To meet the condition that any MFSR based PRPG can generate the same output sequence as that for an LFSR based PRPG, Eqs. (11) and (12) for any MFSR based PRPG must hold, namely, , and . There are (k+1) coefficients in the inversion vector, i.e., Therefore, there are 2^{k} different combinations in the inversion vector if s_{i}, i = 1, 2,......, k can be arbitrarily selected. Thus, the theorem holds. Q.E.D. ^ In this section, we will discuss the behavior of both LFSR based and MFSR based MISA's. We assume that the length of the test response sequence to be compressed is L. For a kstage MISA, let its pth input be I_{p}. We can use the following L*k array to represent the test response sequence: where R_{p,q} means the bit of the qth test response applied to I_{p} of the MISA. ^ Consider the LFSR based MISA shown in Fig. 5 that has a characteristic polynomial C(X) and an initial seed (a_{1}, a_{2},......, a_{k}). The initial seed can also be expressed in terms of the polynomial L_{0}(X) as stated in Eq. (1). If we put the L*k test response array into this LFSR based MISA, its ith content after i shifts, L_{i}(X), can be expressed as: L_{1}(X) = [X*L_{0}(X) + R_{0,L1}_{ }+ R_{1,L1}*X + ... + R_{k1,L1}*X^{k1}] mod C(X) L_{2}(X) = [X*L_{1}(X) + R_{0,L2}_{ }+ R_{1,L2}*X + ... + R_{k1,L2}*X^{k1}] mod C(X) : (18) LL(X) in Eq. (18) is the final signature of an internal type LFSR based MISA for an L*k test response array. Once the initial seed and characteristic polynomial have been specified, the final signature is determined by the given test response array. ^ Fig. 6 shows a configuration of the MFSR based MISA. By means of the shift operation of an MFSR based MISA and an L*k test response array, we have M_{1}(X) = [X*M_{0}(X) + D(X) + d_{0} + ] mod C(X) = [X*T_{0}(X) + D(X)*(X+1) + d_{0} + ] mod C(X) M_{2}(X) = [X*M_{1}(X) + D(X) + d_{0} + ] mod C(X) = [X^{2}*T_{0}(X) + D(X)*(X^{2}+X+1) + d_{0}*(X+1) + ] mod C(X) : M_{L}(X) = [X^{L}*T_{0}(X) + D(X)*(X^{L+1}+1)/(X+1) + d_{0}*(X^{L}+1)/(X+1) + ] mod C(X). (19) ML(X) in Eq. (19) is the final signature of an internal type MFSR based MISA for an L*k test response array. Compared to Eq. (18), Eq. (19) indicates that even if the initial seed polynomial T_{0}(X) and characteristic polynomial C(X) of an MFSR based MISA have been specified, it may still be possible that the final state polynomial M_{L}(X) can be set to any desired value by adjusting the coefficients of the inversion vector (d_{0}, d_{1},......, d_{k}). Therefore, MFSR based MISA's are also called seedandsignature on demand (SASOD) MISA's. Next, we shall analyze this problem. Let three polynomials, A(X), B(X), and F(X), be expressed as: A(X) = M_{L}(X) + [X^{L}*T_{0}(X) + ] mod C(X) (20) B(X) = (X^{L+1}+1)/(X+1) (21) and F(X) = (X^{L}+1)/(X+1). (22) Substituting Eqs. (20), (21) and (22) into Eq. (19) we have A(X) = [D(X)*B(X) + d_{0}*F(X)] mod C(X). (23) The original meaning of Eq. (23) is that, given D(X), B(X), d_{0}*F(X), and C(X), it follows that A(X), which contains the final signature M_{L}(X), is fixed. However, our objective here is to control the final signature to any required value by adjusting D(X) and d0. Therefore, our question becomes: Given any A(X), B(X), C(X), and F(X), can we find a D(X) and a d_{0} such that Eq. (23) holds? Since the behavior of feedback shift registers can be described by polynomial operations, we shall next solve this problem based on polynomial analysis. Let the greatest common divisor polynomial of B(X) and C(X) be G(X), i.e., GCD[B(X), C(X)] = G(X). We will first consider the case where d_{0 }= 0. In this case, we have A(X) = [D(X)*B(X)] mod C(X). (24) The following theorem gives the necessary and sufficient conditions for D(X) to exist. Theorem 4: For any given three polynomials, A(X), B(X), and C(X), where deg A(X) < deg C(X). Eq. (24) has a solution on D(X) if and only if A(X) mod [GCD(B(X), C(X)] = 0. Proof: It is well known that (see, e.g., [18]) G(X) = GCD[(B(X), C(X)] if and only if we can find two nonzero polynomials, u(X) and v(X), such that G(X) = u(X)*B(X) + v(X)*C(X), (25) and GCD[u(X), v(X)] = 1. (26) By means of the polynomial division algorithm, we can find a unique nonzero polynomial Q(X) such that Eq. (24) becomes A(X) = D(X)*B(X) + Q(X)*C(X). (27) (a) Sufficiency: Since A(X) mod G(X) = 0, we may assume that A(X) = a(X)*G(X). (28) By Eq. (24), we know that deg A(X) < deg C(X); hence, by Eqs. (28) and (25), we get A(X) = A(X) mod C(X) = [a(X)*G(X)] mod C(X) = [a(X)*u(X)*B(X) + a(X)*v(X)*C(X)] mod C(X) = [a(X)*u(X)*B(X)] mod C(X). By Eq. (5), if D(X) exists, then we know that deg D(X) < deg C(X). Compared to Eq. (27), we know that if we set D(X) = [a(X)*u(X)] mod C(X), (29) then D(X) is a polynomial with degree less than deg C(X), and that D(X) satisfies Eq. (25). Therefore, a solution can be found. (b) Necessity: Since G(X) = GCD[B(X), C(X)],we can assume B(X) = y(X)*G(X) and C(X) = z(X)*G(X), where y(X) and z(X) are two nonzero polynomials. Substituting them into Eq. (27), we get A(X) = D(X)*y(X)*G(X) + Q(X)*z(X)*G(X) = [D(X)*y(X) + Q(X)*z(X)]*G(X). Thus, A(X) mod G(X) = 0. ^ Now, we will consider the case where d0 = 1. In this case, we have A(X) = [D(X)*B(X) + F(X)] mod C(X). (30) We modify the above equation and assume a polynomial A'(X) such that A'(X) = A(X) + [F(X) mod C(X)]. Then, we have A'(X) = [D(X)*B(X)] mod C(X). (31) Since Eqs. (31) and (24) have the same form, we have the following theorem that gives the necessary and sufficient condition for D(X) to exist for d_{0} = 1. Theorem 5: For any given four polynomials, A(X), B(X), C(X), and F(X), where deg A(X) < deg C(X), Eq. (29) has a solution on D(X) if and only if A'(X) mod [GCD(B(X), C(X)] = 0, where A'(X) = A(X) + [F(X) mod C(X)]. Proof: Similar to Theorem 4. Q.E.D. So far, we have proved the necessary and sufficient condition for D(X) to exist. Next, we will consider the case where d0 = 0 and A(X) mod [GCD(B(X), C(X))] * 0. The case where d0 = 1 can be similarly discussed. We have GCD[(XL+1+1)/(X+1), C(X)] * 1. Since, in general, C(X) is a primitive polynomial, in the following discussion, we shall make such an assumption. If GCD[(XL+1+1)/(X+1), C(X)] * 1, then GCD[(XL+1+1)/(X+1), C(X)] = C(X). The following theorem provides an approach to solve D(X) under this condition. Theorem 6: If GCD[(X^{L+1}+1)/(X+1), C(X)] 1 and C(X) is a primitive polynomial, then GCD[(X^{L+2}+1)/(X+1), C(X)] = 1. Proof: Since (XL+2+1)/(X+1) + (XL+1+1)/(X+1) = XL+1, which cannot be a multiplication of C(X), the theorem is proved. Q.E.D. Now, suppose we add one arbitrary dummy pattern to the test response such that M_{L+1}(X) is the final signature of the MFSR based MISA for a (L+1)*k test response array, where M_{L+1}(X) = [X^{L+1}*T_{0}(X) + D(X)*(X^{L+2}+1)/(X+1) + d_{0}*(X^{L+1}+1)/(X+1) + ] mod C(X). Then Eqs. (20) and (21) become A_{1}(X) = M_{L+1}(X) + [X^{L+1}*T_{0}(X) + ] mod C(X) and B_{1}(X) = (X^{L+2}+1)/(X+1). Since GCD[B_{1}(X), C(X)] = 1 if GCD[B(X), C(X)] 1, no matter what the value A_{1}(X) is, D(X) must always have a solution. Now, we will describe a procedure to find D(X) if one exists. From Eq. (29), we know that if we can find u(X) and v(X) that satisfy Eqs. (25) and (26), then D(X) can be easily found. Next, we shall analyze the procedure for finding G(X) = GCD[B(X), C(X)]. From this procedure, we can derive a method to find u(X) and v(X). A standard method for finding the greatest common divisor of two polynomials B(X) and C(X) is to apply the Euclidean algorithm [21] successively as follows: Euclidean algorithm [21] successively as follows: B(X) = Q_{1}(X) * C(X) + R_{1}(X) C(X) = Q_{2}(X) * R_{1}(X) + R_{2}(X) R_{1}(X) = Q_{3}(X) * R_{2}(X) + R_{3}(X) : R_{k3}(X) = Q_{k}(X) * R_{k2}(X) + R_{k1}(X) R_{k2}(X) = Q_{k+1}(X) * R_{k1}(X) + R_{k}(X) R_{k1}(X) = Q_{k+2}(X) * R_{k}(X) + R_{k+1}(X) until R_{k+1}(X) = 0. Then GCD[B(X), C(X)] = R_{k}(X). By reversing the above procedure, we can represent R_{k} (X) as a function of R_{k1}(X) and R_{k2}(X), then represent R_{k1}(X) as a function of R_{k2}(X) and R_{k3}(X), and so on. Finally, we can represent R_{k}(X) as a function of B(X) and C(X) in the form R_{k}(X) = u(X)*B(X) + v(X)*C(X). u(X) in this equation can then be used to determine D(X). We will use an example to illustrate the above process: let A(X) = X^{3} + X^{2} + 1, B(X) = (X^{11} + 1)/(X + 1), and C(X) = X^{4} + X^{3} + 1. We have B(X) = (X^{6} + X^{4} + X + 1) * C(X) + X^{2} C(X) = (X^{2} + X) * (X^{2}) + 1 X^{2} = (X^{2}) * 1 + 0 Therefore, ^ = C(X) + (X^{2} + X) * (X^{2}) = C(X) + (X^{2} + X) * [B(X) + (X^{6} + X^{4} + X + 1) * C(X)] = (X^{2} + X) * B(X) + (X^{8} + X^{7} + X^{6} + X^{5} + X^{3} + X + 1) * C(X). Thus u(X) = (X^{2} + X). Since GCD[B(X), C(X)] = 1, a(X) = A(X). From Eqs. (28) and (29), we have D(X)＝[a(X) * u(X)] mod C(X) = [(X^{3} + X^{2} + 1) * (X^{2} + X)] mod (X^{4} + X^{3} + 1) = X^{2} + 1. ^ We have shown that if D(X) does not exist for some specified initial seed and test response, then by simply adding one dummy pattern, one can always find the required D(X). In general, adding one dummy pattern should not be a problem because this only requires one more clock cycle during testing if a pseudorandom number generator is used for the pattern generator, or it requires that one more test pattern be scanned into the circuit under test if a scan system is used. In the case where such augmentation is absolutely not allowed, the following discussion shows that the problem may still be easy to solve. From Theorem 5, we know that if {GCD[B(X), C(X)] = 1}, then a solution for D(X) always exists. Therefore, if we can use different C(X)'s, then the probability for {GCD[B(X), C(X)] 1} will be smaller. According to [15], the number of primitive polynomials with degree k is , where the (X)function is the Euler's function and is defined as the number of positive integers less than or equal to X that are relatively prime to X. If k = 16, then = 2048. Now, if none of these primitive polynomials is prime to B(X), then the multiplication of these polynomials, denoted as MC(X), must also divide B(X). If the degree of MC(X) is N, then N = k* = . (32) The probability that MC(X) divides B(X) will be P = 2^{{deg B(X)}N} / 2^{{deg B(X)}} = 2^{N}. (33) If k = 16, then N = 16*2048 = 32768, and we have P = 2^{N} = 2^{32768}. Therefore, it is almost guaranteed that a feasible D(X) can be found if we have the freedom to choose C(X). ^ In this paper, we have presented a generalized type of feedback shift register, called the mixedtype feedback shift register (MFSR),and shown that the conventional LFSR and the IFSR proposed in [17] are two special cases of MFSR's. Some properties that MFSR's possess while conventional LFSR's or IFSR's do not have been described. These properties are quite useful in builtin selftest. Compared to LFSR's, MFSR's do not require any extra hardware overhead except for the inverter at the input of the first stage when d_{0} = 1. Our analysis shows that by using MFSR based PRPG's, one can generate the same serial output sequence and parallel patterns as those generated by any LFSR based PRPG, with the extra advantage that the initial seed can be any value. On the other hand, the seed and signature of an MISA (or the final state at the true outputs of an MFSR) can be set to any value if an MFSR is used. One of the typical applications of this type of MISA is in mass production, where the same kind of CUT's are tested using BIST. In such a case, the initial seed and the final state can be set to the same value. If the final signature from a CUT is correct, then the seed need not be reloaded; thus, testing time can be reduced. The analysis provided in this paper has been based on polynomial representation of feedback shift registers. It would be interesting to use matrix representation to analyze MFSR's because the behaviors of external types of feedback shift registers are difficult to analyze using polynomial representation. With the introduction of MFSR's, we expect that many test schemes that have previously been developed using LFSR's can be reexamined to see whether better properties or architectures exist when MFSR's are used. REFERENCES 1. M. Abramovici, M.A. Breuer and A.D. Friedman, Digital Systems Testing and Testable Design, Computer Science Press, New York, 1990. 2. B. Konemann, J. Mucha and G. Zwiehoff, "Builtin logic block observation technique," Digest of Papers 1979 Test Conference, 1979, pp. 3741. 3. R. Raina and P.N. Marinos, "Signature analysis with modified linear feedback shift registers (MLFSRs)," in Proceedings of FaultTolerant Computing: 21st International Symposium, 1991, pp. 8895. 4. Z. Barzilai, D. Coppersmith and A.L. Rosenberg, "Exhaustive generation of bit patterns with applications to VLSI selftesting," IEEE Transactions on Computers, Vol. C32, No. 2, 1983, pp. 190194. 5. S.B. Akers, "On the use of linear sums in exhaustive testing," Digest of Papers 15th Annual International FaultTolerant Computing Symposium, 1985, pp. 148153. 6. L.T. Wang and E.J. McCluskey, "Linear feedback shift register design using cyclic codes," IEEE Transactions on Computers, Vol. C37, No. 10, 1987, pp. 13021306. 7. P.H. Bardell, "Design considerations for parallel pseudorandom pattern generators," Journal of Electronic Testing and Applications, Vol. 1, No. 1, 1990, pp. 7387. 8. W.B. Jone and C.A. Papachristou, "A coordinated approach to partitioning and test pattern generation for pseudoexhaustive testing," in Proceedings of 26th ACM/IEEE Design Automation Conference, 1989, pp. 525530. 9. R. Srinivasan, S.K. Gupta and M.A. Breuer, "Novel test pattern generators for pseudoexhaustive testing," in Proceedings IEEE International Test Conference, 1993, pp. 10411050. 10. S. Hellebrand, S. Tarnick, J. Rajski and B. Courtois, "Generation of vector patterns through reseeding of multiplepolynomial linear feedback shift registers," in Proceedings of IEEE International Test Conference, 1992, pp. 120129. 11. S. Venkataraman, J. Rajski, S. Hellebrand and S. Tarnick, "An efficient BIST scheme based on reseeding of multiple polynomial linear feedback shift registers," in Proceedings of ICCAD93, 1993, pp. 572577. 12. J. Savir and W.H. McAnney, "A multiple seed linear feedback shift register," IEEE Transaction on Computers, Vol. 41, No. 2, 1992, pp. 250252. 13. R.A. Frohwerk, "Signature analysis: A new digital field service method," HewlettPackard Journal, Vol. 28, No. 9, 1977, pp. 28. 14. J.E. Smith, "Measures of the effectiveness of fault signature analysis," IEEE Transactions on Computers, Vol. C29, No. 6, 1980, pp. 510514. 15. P.H. Bardell, W.H. McAnney and J. Savir, Builtin Test for VLSI: Pseudorandom Techniques, Wiley, New York, 1987. 16. C.L. Chen, "Linear dependencies in linear feedback shift registers," IEEE Transactions on Computers, Vol. C35, No. 12, 1986, pp. 10861088. 17. A. Guha and L.L. Kinney, "Relating the cyclic behavior of linear and intrainverted feedback shift registers," IEEE Transactions on Computers, Vol. C41, No. 9, 1992, pp. 10881100. 18. R.E. Blahut, Theory and Practice of Error Control Codes, AddisonWesley, MA, 1983. 19. C.A. Chen and S.K. Gupta, "A methodology to design efficient BIST test pattern generators," in Proceedings of IEEE International Test Conference, 1995, pp. 814823. 20. C.A. Chen and S.K. Gupta, "BIST test pattern generators for twopattern testing  theory and design algorithms," IEEE Transactions on Computers, Vol. 45, No. 3, 1996, pp. 257269. 21. I.N. Herstein, Topics in Algebra, 2nd (ed.), Wiley, 1975. KuenJong Lee（李昆忠）received the B.S. degree in electrical engineering from National Taiwan University, Taiwan, R.O.C., the M.S. degree in electrical and computer engineering from the University of Iowa, Iowa City, Iowa, and the Ph.D. degree in electrical engineering from the University of Southern California, Los Angeles, California. He joined the faculty of National ChengKung University, Tainan, Taiwan, R.O.C., in 1991, and is currently a Professor in the Department of Electrical Engineering. His research interests include several aspects of computeraided design and implementation of integrated circuits, with particular emphasis on automatic test pattern generation, design of testable circuits and design automation. WeiLun Wang（王維倫）received the B.S. degree in electronic engineering from Chung Yuan Christian University in 1985, and the M.S. degree in electrical engineering from Tatung Institute of Technology in 1987. He is now a Ph.D. student in the Department of Electrical Engineering at National Cheng Kung University. His research interests are in the field of VLSI design and test. JhingFa Wang（王駿發）received the Ph.D. degree in electrical engineering and computer science from the Stevens Institute of Technology, Hoboken, in 1983. He is a senior member of IEEE and was elected general chairman of the Chinese Image Processing and Pattern Recognition Society in 1993. He was the director of the Institute of Information Engineering in National Cheng Kung University from 1990 to 1996. He is currently a professor in the department of Electrical Engineering and the Institute of Information Engineering at National Cheng Kung University. He is currently also the Chairman of the Taiwan Information Software Association and the Chairman of the Computer Center of National Cheng Kung University. His current research interests include graph theory, CAD/VLSI, neural nets for image processing, computer speech processing, and optical character recognition. 