Title :
Analysis and improvement of testability measure approximation algorithms
Author :
Bitner, James ; Jain, Jawahar ; Abraham, Jacob A. ; Fussell, Donald S.
Author_Institution :
Comput. Eng. Res. Center, Texas Univ., Austin, TX, USA
Abstract :
This paper presents a theoretical framework for the study of algorithms for approximating testability measures. To illustrate its application, we consider two well-known algorithms. It is shown empirically that both algorithms perform very poorly on several circuits of realistic size. For some circuits, an equally good approximation to the testability measure can be achieved by a random number generator or a “0th order” approximation algorithm that always returns a constant 1/2. Analytically, we present several circuits for which the performance of these algorithms is arbitrarily bad. The analysis is then used to identify their weaknesses, and procedures are suggested through which such unpredictable performances may be improved. One procedure is discussed in detail and an order of magnitude improvement in accuracy results
Keywords :
design for testability; fault diagnosis; logic testing; random number generation; approximating testability; averaging; higher order approximation; partially symbolic computation; testability measure approximation algorithms; worst case circuits; Algorithm design and analysis; Approximation algorithms; Boolean functions; Circuit analysis; Circuit testing; Contracts; Jacobian matrices; Laboratories; Performance analysis; Polynomials;
Conference_Titel :
Test Symposium, 1994., Proceedings of the Third Asian
Conference_Location :
Nara
Print_ISBN :
0-8186-6690-0
DOI :
10.1109/ATS.1994.367233