Analysis and Design of Linear Finite State Machines for Signature Analysis Testing

This paper presents a theoretical investigation on the aliasing error probability (AEP) in signature analysis testing by means of linear finite state machines (LFSM’s). The analysis is based on the assumption of statistical independence of successive error vectors. The equations of the resulting Markov chain model of the LFSM are solved to determine an exact expression of the AEP as a function of the main LFSM features (such as its number of flip-flops and feedback network) and of the relevant parameters of the testing environment (namely, test length and input error probabilities). This expression is used to prove criteria for the synthesis of LFSM’s with minimum asymptotic and transient AEP. A fundamental lower bound on the AEP is presented. It represents the performance limit of any LFSM with respect to aliasing minimization, and we show that the AEP in machines realizing counters mod 2^k - 1 is the closest to such a bound, in particular periodically reaching it. Finally, it is proven that the lower bound on the AEP is independent from any linear reencoding of the inputs, so that no linear interface circuit can improve the maximum performance of a LFSM. © 1991 IEEE