Kuen-Jong Lee, Wei-Lun Wang and Jhing-Fa Wang
Department of Electrical Engineering
National Cheng Kung University
Tainan, Taiwan 701, R.O.C.
A mixed-type feedback shift register (MFSR) is similar to a linear feedback shift register (LFSR) except that the connection between two consecutive flip-flops (F/F's) may be through the Q or output, and an extra inverter may exist at the input to the first flip-flop (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 built-in 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 16-stage MISA, the probability that a feasible MFSR does not exist is less than 2-32768.
Keywords: mixed-type feedback shift register, linear feedback shift register, pseudorandom pattern generator, multiple input signature analyzer
Retrieve Word file (199809_07.doc : 286,208 bytes)
Received November 19, 1996; revised July 16, 1997.
Communicated by Youn-Long Lin.