@article {Ivanov1991Iterative-algor,
title = {Iterative algorithms for computing aliasing probabilities},
journal = {Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on},
volume = {10},
number = {2},
year = {1991},
month = {feb.},
pages = {260 -265},
abstract = {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(L2k), disregarding slight possible start-up and termination improvements, while that of ALG-BL is O(Lf2k+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(2k), while that of ALG-BL is O(2k+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},
keywords = {ALG-MK, aliasing probabilities, built-in self test, compaction techniques, computational complexities, computational complexity, floating-point multiplications, integrated circuit testing, iterative algorithm, iterative methods, logic testing, Markov process model, Markov processes, probability, shift/add operations, signature analysis, space complexity, time complexity},
issn = {0278-0070},
doi = {10.1109/43.68413},
url = {http://dx.doi.org/10.1109/43.68413},
author = {Ivanov, A. and Starke, C.W. and Agarwal, V.K. and Daehn, W. and Gruetzner, M. and Williams, T.W.}
}