Iterative algorithms for computing aliasing probabilities

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^k), disregarding slight possible start-up and termination improvements, while that of ALG-BL is O(Lf2^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^k), while that of ALG-BL is O(2^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