Untestable fault identification using recurrence relations and impossible value assignments

This paper presents two novel and low cost techniques that can be used for the purpose of untestable fault identification. First, we present a new theorem and a practical method using static implications to identify unexcitable nets using recurrence relations in sequential circuits. Since each unexcitable net generally infers to more than one untestable fault, this theorem helps us to quickly identify significantly more sequentially untestable faults. In addition to discovering unexcitable nets using recurrence relations, we propose a second approach that aims at quickly identifying non-trivial multiple-node conflicts, which can then be used to identify additional untestable faults in both combinational and sequential circuits. Unlike previous techniques that concentrate on identifying local conflicts in the circuit, our approach efficiently extends the conflicting value analysis across multiple levels in the circuit to identify more untestable faults. Application of our techniques to both combinational and sequential benchmark circuits showed that significantly more untestable faults can be identified using the proposed approaches, with low overhead in terms of both memory and execution time.