An algorithm, ALG-MK, for computing exact aliasing probabilities in signature analysis is derived from a Markov process model of signature analysis. A previous algorithm, ALG-BL, which was derived from a Boolean expressions formulation of the problem, is reformulated so that it can also be reviewed as being based on a Markov process. Both algorithms compute exact aliasing probabilities in signature analysis. The computational complexities of the two models are compared. It is shown that the time complexity of the iterative algorithm ALG-MK is O(L2/sup k/), disregarding slight possible start-up and termination improvements, while that of ALG-BL is O(Lf2/sup k+f/), where k is the size of the signature register, f is the number of feedback taps, and L is the test sequence length. ALG-BL requires more shift and add operations, but requires half the number of floating-point multiplications that ALG-MK requires. The space complexity of ALG-MK is O(2/sup k/), while that of ALG-BL is O(2/sup k+f/). It is also shown that ALG-MK and ALG-BL are formally related through a linear transformation of their state vectors. Both algorithms may be used to study aliasing under generalized error models.>

Aliasing errors in linear feedback shift registers (LFSRs) used as signature analysis registers in self-testing networks are considered. A bound on aliasing is established by a straightforward algebraic analysis of LFSRs. It is calculated as a function of p, the probability of an error occurring at an output of the network under test. This bound is robust but is only good for p close to 1/2. To investigate the question of what happens to aliasing errors in general, the function of LFSRs is modeled by a Markov process and a solution is obtained by the z-transform. It is shown that for p>1/2 the aliasing probability for primitive polynomials converges much faster to the final steady-state value than for nonprimitive polynomials. For values of p>