Iterative algorithms for computing aliasing probabilities

TitleIterative algorithms for computing aliasing probabilities
Publication TypeJournal Article
Year of Publication1991
AuthorsIvanov, A., C. W. Starke, V. K. Agarwal, W. Daehn, M. Gruetzner, and T. W. Williams
JournalComputer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Pagination260 -265
Date Publishedfeb.
KeywordsALG-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

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


a place of mind, The University of British Columbia

Electrical and Computer Engineering
2332 Main Mall
Vancouver, BC Canada V6T 1Z4
Tel +1.604.822.2872
Fax +1.604.822.5949

Emergency Procedures | Accessibility | Contact UBC | © Copyright 2021 The University of British Columbia