A transitive closure based algorithm for test generation
Srimat Chakradhar, Vishwani D. Agrawal · 1991
We present a transitive closure (TC) based test generation algorithm.A test k obtained by determining signal values that sattsfy a Boolean expression constructed from the ctrcuit netltst and the fault.The atgorithm is a sequenceof two main stepsthat are repeatedly executed: TC computation and dectsion- maldng.To compute the TC of the ctrcuit, we construct an hnpltcation graph whose vertices are labeled as the true and fatse states of alt signals.A directed edge (z, y) tn this graph represents the controlling htfluence of the true state of signal z on the true state of signal y that are connected through a wire or a gate.Since the implication graph only includes pairwtse (or btnary) relations, it is a partial representation of the netlist.The TC of the bnplication graph contatns pairwise logical relationships among all signats.When signal relationships describing fault activation and path sensittzatton are included, TC determines signal fixations and logical contradictions that dtrectly identify many redundancies.Sensitization of physical and logical dominators, unique path sensitization, static and dynamic learntng and other techniques that are useful in determiatng necessary stgnal assignments are implicit tn the preeess.If signals thus determined satisfy the Boolean formula, we have a test.Otherwtse, we use the decision-making step, fix an unasstf+ned signal, and update the TC to find further logical consequences.