OnFinding aNearly Minimal SetofFault Detection Tests forCombinational Logic Nets

Abstract

A procedure isdescribed forfinding, byshortcut Inthis paperthefault table approach isagaininvoked; methods, anear-minimal setoftests fordetecting all single faultshow,-ever, only averysmall fraction ofallpossible tests inacombinational logic net.Theprocedure should proveuseful for netswhicharetoolarge tobetreated bymoreexactmethods (2).are e dintetab.etess e r arearily Thesetoftests sofound also appears useful fordiagnosing (i.e., thosewhichdetectlargenumbersoffaults, andthe locating) faults. Theclass offaults considered isthat which causesmainproblem attacked hereisthederivation ofashort- connections tobestuck atlogical oneorlogical zero. Thenetscutprocedure forfinding thesedesirable tests. Thispro- considered mayinclude AND,OR,NAND,NOR,andNOTgates. cedure alsoappears toensure finding asufficient setof Thebasesoftheprocedure arethepathsensitizing concept, tests todetect alldetectable faults. Thispoint isdis- andreduction ofanettoitsequivalent normal form, abbreviated cusseddeter in tect faph of S on t is enf. Itisshown that ifasetoftests canbefound which detects an cussed further inthelast paragraph ofSection II.Itis appropriate subset offaults intheenf, this setwill detect all faults notguaranteed thatthesetofteststhusderived will intheoriginal net. Theenfalso provides avehicle forsystematically contain atruly minimal subset, butitislikely tocon- finding themostdesirable tests, namely those which eachdetecttain onethatisnearminimal. Theprocedure maybe- manyfaults inthenet.Theprocedure isillustrated indetail byan example. ~~~~~~~~come cumubersome whenthenumberofpathsthrough example. thenetislarge. Thistendstobethecasewhenmany I.INTROD-UCTION gateshaveahigh-fanout index.