Simple bounds on serial signature analysis aliasing for random testing

It is shown that the aliasing probability is bounded above by (1+ε)/L≈1/L (ε small for large L ) for test lengths L less than the period, L_c, of the signature polynomial; for test lengths L that are multiples of L_c, the aliasing probability is bounded above by 1; for test lengths L greater than L_c and not a multiple of L_c, the aliasing probability is bounded above by 2/( L_c+1). These simple bounds avoid any exponential complexity associated with the exact computation of the aliasing probability. Simple bounds also apply to signature analysis based on any linear finite state machine (including linear cellular automaton). From these simple bounds it follows that the aliasing probability in a signature analysis design using β intermediate signatures is bounded by ((1+ε)^ββ^β)/L ^β, for β<L and L/β<L_c. By using intermediate signatures the aliasing probability can be substantially reduced