A Multi-valued Algebra for Capacitance Induced Crosstalk Delay Faults

Capacitive crosstalk can slowdown transitions which can propagate to outputs and cause erroneous operation. Test generation methods such as XGEN and XGEN-E were proposed to generate tests for such failures. However, a drawback of these test generation methods is that a large proportion of faults are aborted. In this paper, we systematically derive a multi-valued algebra. We first show that a composite value system must be derived considering all operations performed by the algorithm that will use the value system. In particular, we identify that for our test generation algorithm it is imperative to consider its timing operations and their impact on what composite values can exist in our algebra. We also identify the fact that even some key procedures - namely the backtrace procedure as well as the search procedure - need to be modified to work with the composite value system. We derive a new 57-valued algebra and modify the key ATPG procedures to obtain a test generation methodology which we call XGEN-M (´M´ for multi-valued). We present experimental results that demonstrate the superiority of XGEN-M compared to previous methods.