Fault-Simulation Methods—Extensions and Comparison By Y. H. LEVENDEL and P. R. MENON (taruscrit recived Decerber 16, 1980) In this paper, we compare four different methods of fault simulation in terms of their hailing of arbitrary numbers of logic values, modeling levels, and detailed timing. The methods considered are parallel, deductive, mullils, and concurrent simulation methods Since some of the methods, in thor current forme, are unable fo handle all the problems under consideration, ise have proposed fxtensiona to the methode wherever necessary before making the ‘comparisons. While all the methods considered are capable of solting the problems with the same degree of accuracy, the concurrent sim lation method appears to be the simplest and moe flexible, 1. wtRopucTioN Different techniques forthe office! simulation of fouls in digital cireuits have been published. Among thar, the bet kowwrn are paca ‘imation, deductive simlation,*and concurrent simulation” A few Irapers analyzing some aspocte ofthese methods have alsa heen pub Thea ™* ‘This paper end two othere" comprise a serge attempting & com prebernive analysis of fault simulation methods (ti hoped that they ‘will provide a basis forthe eelection of faultsimnlaton methods to ‘SUisy sprite requirements Inthia paper, we consider theee nspeets of circuit modeling and thir ffecta on the faule-sinulation method wed. Pits, we consider the ‘numberof logie values needed co accurately move! Tog devices and jeg impact on tho simulation methed. Nex, che effectiveness of the different methods for simulating at different levela (ex, wale level, functional level, subsystem level, et) iconsidered. Finally, we dienes the modeling of timing effects, such as rise and fall times and high roquoncy rjection. (Our itady covers four methods of ft simlation: parallel, deduc ‘ive, mulls, and concurrent. Tn their eurrent forms, ame of the ‘methods are not capable of handling ll the problems we consider. 2205 “Therefore, we have atcempted to extend the existing methods, wher cer neteseary, before making the compairinone between methods Before proceeding to the analyse of the methods, we present brief description of each method, "Historically, parallel sislaion eas the fat metbod thal simulated 1 matther of faults simultaneously” Thie method, which is perhaps che fot widely amd, taken advantage of word-orien operation in he fost eompater ai acs together several fuly ereit values into ont fr more computer words. Although this method ia quit offcien|, ‘lite posts are required for ximlating large numbers of faults ‘Deductive simulation attempts to eliminate the need for multiple passes by computing norinal signal values in the eicuie end deducing the faulty values by manipalating lies of Calis Asaociated wich each ‘gna is Ful ist, eich ia sot of full, any one ef which wil cause {he signal value €o be different fom the normal value, Th effects of fault ere propagate Uhrough the circuit by un algebra of wet "The mulls method associate two oF more lists of fouls with each signal" Conceptually, the umber of lists associated with signal is teal to the number of logic valuas simulated. Thus for two logic Sales, chene mill be a O18 and a Let wseeinted oth each signal, the former being the gel of fle fn whose presence (individualls) the tinal wll have the valu 0, nl the lsttar those that result in a value ff, Sec algetra ie necessary for manipulating thow:Tists also. However, Unlike the deductive rathod, the equations for compating che output Tats of «device from iu input lata are dependent only on the function performed by the device and net on the syn values. In concurrent simulation, any fat that causes che inputs, ontpuls, orinternal state ofa davioo tobe differeat fom their normal values is represented conceptually by 9 copy of the device. During wimulation, if the inputs, ootpuee, and state of faulty’ copy become identical 1 those of the fnul-fee eapy, th faulty vopy i deleted. Thus, fly Copice are erated and deleted during simulation ‘The evaluation of fully copii is essendally the same aa faul-free copies, and no set alzcbra iv involved. Concurreot simulation can also handle a lage ‘uber of faults eimulianensly. "tis interesting to note that all the above methow, except parallel simulation, use come fran of data compression fae acring faulty signal ‘Salus Gn the other hand, parallel sation actmpta to compute “Simultaneously the flt-tree signal value and a umber of faulty signal ‘les associated with eac lead in the circu. 1, NUMBER OF LOGIE VALUES ‘Three-valued logic systems have een widely used for analyzing essentially binary aya." Three logic values are also used in logic 2238 THE BELL SYSTEM TECHNICAL JOURNAL, NOVENBER 1881 mulation, where O and 1 represent the two diserete values being Iolled and a third value, u, denotes that a particular value is tinknown, "Recently, e-sate busing has become » widespread technique used in many ust deigns, Diffelien in modeling olfects associated with fewus lechnology have been reported” One effect is the memory Secoriated with dialed buss ‘That is the disabled hus remembers fhe previous logic value on Use bus A solution consists of adding pedal circuitry to regular gates, making poasible tho use of simulator with only three logie values" Au alienate aalution is Uh addition of Three more logic ves, namely 2,2, forreprocentng the states tf disabled buses with previous value equal to 0,1, anv unknown, respectively: Transistor iunsisiow logic (xT) trkslate technology equine the addition of only one logie value, 2." ‘Bus contention, anotber (9pical, potentially destructive tri-state cficet, cannot be modeled by added ezeuilzy, A solution consists of ‘ding one more logie value representing a confit slate, a, a8 shown {nthe following example. ‘Consider a driver snvertar wd a bus configuration in Te. tri-state technology (Pig). When line is enabled, the gate operates as an inverler, when e ie disabled the ourput of the gate Is in a highs impedance stato, When used in a bux configuration, wwe enabled inverters create » confice (bus contention}, If they are in opposite satan Te got of logie values (0. 1,1 2) 8 suicent Lo mel these tfc, since timate devions in is technology do not have the ‘memory property mentioned sbwve. "Table [shows how the bus eonfiguraion of Fig, 1 cam be simulated ‘sing th above st of fve loge values Since the bus will be connected to che oats of drivers, whieh ean produce four out of the five logic ‘eles only four loge values are used for modeling the bus. ig 1-917. brwweaverer (Bu onfiuation FAULT SIMULATION 2257 Table (a) Tristate invortr output @) Slate of tisste bus RTs: earaeaea Tran ordinary gn could be connected directly toa bus, che model should allow five logic values for the gate inputs, but requires oaly ‘three logic values for ia ouput, Table TI shows the behavior of such an AND gace with ipuca sand 3, and output ‘The use of larger sei of legic wales, hough necessary to correctly model modern technology, Bas 4 serous impact on the racthed of Simla used. The following seetions dea with Us problem, ‘will ene Tine in the ere O value on line in che full free circuit und the remaining bts represent values on the seane line in she presence of diferent single full. Table II-AND gate with five input rogle values “Table I—Coding fr ieee logic When a three-valied system ix ute, each af the circuits simula in parulel must be coed uning lwo binary digits A commonly used ‘method consis of sesacnting so word with tach line, namely the O-word aan the 16ord a" The voding used is showin Table TH, ‘where the subeript refers wo the ath bit ofeach word. ‘Baaimples of ite use are shown in Fig. 2 Here, and elsewhero in this, paper, lower-onse roman letters are used co denote leads and Greek Tetters zepresent words, Pur the gal of Fig 2, we ave where « and + represent the bitwive ANT and OR operations on complete words This method can bo extended for any number of logic values, For fnmtance, consider the AND gate of Fig. , usin the et of loge values (0.1, a, @, 2). The binary cling scheme requires three computor ‘words foreach line, and three codes (out of eight) are not used. For FAULT SIMULATION 2299 ig. 2 AND pee speciation fr lp aan any choice of code, i it possible co ealeulate the gts ourpa from ‘ching expressions ofthe flowing form: Pm Mao BA Y= ao PP Fm also A “The orginal et of lope values and operations do not conatiute @ ‘Boolean algebra. "The coding scheme establishes «mapping of now "Boolean functions into swiehing operations that canbe applied om fll comporer war, thu, llowing pall precering. "BS uring a coding of n~ 1 warables to represent n loge value, it ia posible to obtain simpler equations for computing the ootpois of fst, For example, consider che gate of Fig. @ and a coding using four Sore a and to reprosunt ive logic vals. The coo i suck Gavel = 1,5 = 01,0500 a= AN the variable wl b ert and only if ar = a, With this eine, the following equations are thane for the gto of i, yore ae yao. “This type of coding cam be used for any numberof logic values 22 Mutt simulation 1 haa been showa that for « threv-valuel loge aston, Uhre Tacs 3°, X', and X° ean be associated with euch line x.” Bach Tis, X% (0, 1,4) roprecenc che faults which cause Line x to have the value 4. Far each Line x, all the Vets X° ure dogjoint and any list i the ‘complement ofthe union of the uther two fie, the union ofthe three Tits isthe ect of al faults being siralased, or the gatas of Fig, 2, we have 12240 THE BELL SYSTEN TECHNICAL JOURNAL, NOVEMBER 1081 (:4gp eo (Gitnt w-mon le nar (Sth 2 FoR, se“ a emp ne etn, Terpectively ‘When five logic valine are wie, we need five lit; for instance, A’ A‘ Ava and A ore associated with line For the AND gate of Fig. 3, we have caatuR casos end onc) Os CUCUCUS = FURUATR. For the inverter of Fig 2, we have Bapoa egos Ber BUR UEUEIN TOA woud and forthe bus configuration of Fig. 1 Abe un Bb U Una Ue BD Ab (Bina Uw BAU UA BO ATW BIUBE AP= Bin B= (BIO BD) UB BR ‘This method can be generalized to any gate (ype an any number of logic values as follows: Let us assume thal we wish (o simulate 3 function fly Xe +p) where each input and the output may fsoume any one of A valves, dono hy 1, 2,0, % and that the Tuncron is defined by a table which specifies the values of (forall combinations of wali of x 1) We msooclate » variable x with each variable x, auch that = & Simlany, we escocate variables la difadonly is = jl Pi with f Ui) For esch i, 1-54 A, we obtain an expression PadPs ‘where P;aze proc of Hierals 2, representing all combinations af values for which f= £ Far exazuple ifthe table bas an entry nehanQue2 fol, ‘the expression fr {will contain the torm as (ii) Replace all wer-case lectern in the equation for f* by the corresponding uppercase letra, vepresencing lists, and retain the ‘superscripts and subverts, Replace produetaby intersection and aura byunion. ‘Dedluctive ticmuation is wel define forte logic vals an ie aso applicable to three logic valuus with some loss of information. Speci {cally ifthe ignal eahae inthe normal iret ix known, (he (1 0F 1, ‘bat the value inthe presence oft ful x unknown (denoted By 1), ‘the full is included in tho full Listas sl fits" Dra ie ‘unknown schether the particular signal value in The peotonce af the ful wl be eiffernt fom Ue full vali. Te wa shown in Ri Wand 12 that chere are enses where the eine valine in he normal céeouit may be unknown, but the value in the presence of 9 fal may De kinnrn, Since he deductive method canoe represen thia case, the ‘esas nbisined may be law aocurata than with other methods." "A modification ofthe deductive method chat leads o accurate three vlved felt simulation was presented in Ref. 10. It uses the coding of ‘Table TT for representing each signal value by a pair of binary variables. A psi of equations can then he derved, aa in Section 21, for computing the coded outputs for each gato cype. These oquations can be viowed aa defining a transformation ofthe original eicuit with three signal vals nts tr rel Ut wil have only inary signal. ‘These two circa ca be stated sing the Grorvalued deductive method. The foull-ree and faulty signal values on any lead in the ‘original ere ea be determine fromm the sigaal vt an foul ists associated with the corresponding puir of leads in the (runsfurmed iret. 2242 THE BLL SYSTEM TECHNICAL JOURNAL, NOVEMBER 1081 The same approach can be used for performing deductive fault simulation with any umber of loge values I logic values are co be ‘mulated, flopak] binary variables will he wed to nepresent them, ‘where [x1 denotes the emallest integer greater than or equal co x.‘The ‘uations for the coded outputs of differen. gale types can be devived ‘rom their truth tables, and used in deductive siuaatin, "Aaas example, conser the bus driver of Pig. 4 tobe simulated with four loge valves, namely, 0 1,2 (high impedance) and w (unknown) ‘The behavior of the device in speciied in Table LV. ‘Using the ceding af Table V, we shall represent tbe signals ae, and b of the bus driver by a: and a, e and e, and by and by Te output ‘equations by and B, can be derived from Tables IV and V. b= end + anton, deed tanivee, For any combination of input vilues and faue iets, che output values ad fae lists ean be enmputed an in Ret. 19 Denoting the fault list sseociated with each variable by che core sponding uppercase leer, le che input vals sl fale Tite forthe ‘reat of Pig. be as follows: anos a 1.91 ant A= 19) 2,4) eek Ba 5) Table Behavior of bus aver ic FAULTSIMULATION 2243, Table ¥—Coding tr trstate devices ‘Let us sasume that al th faults being considered are external co the vice, and we wish to propgale the effects of eho faults Unrough the ‘device. The input conditions are: a ~ |, @ ~ 1. Since the fault Lis ‘contained only in the fruit Fst Ag. t will cause a, to become 1, and therefore a to becom >On the other hand, fault is contained both fn dyand A,, and will cause both anand a, to be inverted the value of (in tho presence of fale 3 willbe 0. Similarly, fault 2 wil repu in (=z faulting ~0, and foul in =u FPorthe above act of valucs the ourpue values and faut lists cun be ‘computed ung the equntons fu Dy and dy and the method presented ii Ref. 19 as follows nao bet Bo= (do 1 Be Bi) U Fn Bd = (0, 8,4) B= (A URLU BI AED ~ 28,5} Denoting the value aft in the presence of full « by Bia, we can obtain the following faulty values fom tho valuos by and By ad foul lists Be al ba) =a WA= a HIS) —0; BAD= Zz BIG) =u “These can be verifiad by computing the ourput for each faulty come bination of inpuia using "Table LV. ‘The modified deductive method dissed above does not lose any information sbout the normal wl Faulty cvcuits and i as accurate as tny ofthe other methods, Tl requires ony logo ist compared tothe flats needa or uli simulation. However, ful ist computations Alepend on signal vdtes nmin he more complex than in the multiist mathe. 24 Concurrent simulation “There is no imitation on the numberof logic values in this cine tion method! sine fully ni fat-free citcuts ae treated independ tently. A lon he primitive elements ofthe eveit are well defined, the evaluation of faulty cizeuis presents no diliculty ‘2244 THE BELL SYSTEM TFCIINICAL JOURNAL, NOVEMBER 1981