Design and analysis of test schemes for algorithm-based faulttolerance

摘要

The design and analysis of test schemes for algorithm-based faulttolerance (ABFT) are examined. The problem is studied under theassumption that no bound is imposed on the size of a test. Upper andlower bounds are established on the number of tests needed to detect agiven number of errors. These bounds are sharply different from thosepreviously established under the bounded test size model. The testschemes presented are easy to implement. It is also shown that thedesign problem for fault detection is NP-hard even when only one faultneeds to be detected. It is shown that the analysis problem is, ingeneral, co-NP-complete and hence unlikely to be efficiently solvable.Several restricted versions of the problem that can be solvedefficiently are identified. In addition, a new branch-and-boundalgorithm for determining the error detectability of a system ispresented