Browse Prior Art Database

Polynomially Complete Fault Detection Problems

IP.com Disclosure Number: IPCOM000128518D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 15 page(s) / 37K

Publishing Venue

Software Patent Institute

Related People

Oscar H. Ibarra: AUTHOR [+4]

Abstract

We look at several variations of the single fault detection problem for combinational logic circuits and. show that deciding whether single faults are detectable by input-output experiments is pol;ynamially complete ie there is a polynomial time algorithm to decide 3_f these single faults are detectable if and only if there is a. polynomial time algorithm for problems such as the travelling salesman problem,knapsack problem, etc..

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 13% of the total text.

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Polynomially Complete Fault Detection Problems

by Oscar H. Ibarra & Sartaj K. Sahni

0400153 Computer, Information., and Control Sciences Institute of Technology University of Minnesota Minneapolis, Minnesota' 55455 Technical Report 74-3 Def,tuber, 1973 ~Nqr, ~~d~jrune 1374 Cover design courtesy of Ruth and Jay Leavitt

Abstract

We look at several variations of the single fault detection problem for combinational logic circuits and. show that deciding whether single faults are detectable by input-output experiments is pol;ynamially complete ie there is a polynomial time algorithm to decide 3_f these single faults are detectable if and only if there is a. polynomial time algorithm for problems such as the travelling salesman problem,knapsack problem, etc..

1. Introduction

Much attention ~ see e.g. [31and[5]) has been focussed on obtaining fast algorithms to obtain minimal test sets to detect all single stuck-at-zero (s-a-0) and stuck-at-one (s-a--1) faults in combinational logic circuits. The best algorithms known have an asymptotic computing time that is exponential in the number of input lines and gates. Hence these algorithms are computationally feasibl,e only for very small cirucits. In fact it would appear that only algorithms with a computing time linear or at most a square of the number of input lines and gates would be feasible for large combinational circuits (e.g.: large scale intergrated circuits. In this paper we show that several fault detection problems are computationally related to, problems such as: travelling salesman, knapsack, maximal clique of a graph, multiprocessor job scheduling, intricate network .flow problems, etc. Thus, these fault detection problems can be solved in polynomial time if and only if (iff) the travelling salesman, knapsack problem, etc. can also be solved in polynomial time. Specifically, then, we show that several single fault detection problems are polynomially complete (see [1], j4], j7], [9] and j10] for further examples of complete problems). Hence, it would appear very unlikely that the fault detection problems have a polynomial algorithm. This would tend to suggest that circuits be designed in some canonical form for which test sets are easily obtainable. The proof technique used in Lemmas 3.2 and 3.3 indicates that by increasing the number of gates it is possible to covert any circuit into an equivalent circuit for which the test set is easily obtainable. See [6] and j8] for some results on designing easily testable circuits. In section 2 we introduce our notation and then in section 3 we show that the following problems are polynomially complete:

P1: Is the combinational circuit C irrednndar_t (i.e. can all single faults be detected)? P2: Can a fault in a particular input line, xi, be detected by input-output (I/0) experiments? P3: Can all single input faults be detected by I/0 experiments? P4: Can faults in the output...