A generalized algorithm for bounding fault detection probabilities in combinational circuits

With the ease of incorporating a linear feedback shift register (LFSR) within a chip for generating pseudo-random sequence of binary vectors, random pattern testing is popular as a built-in self test (BIST) scheme for combinational circuits for stuck at faults. A combinational circuit is said to be random pattern testable if a certain fault coverage can be achieved with certain confidence when a randomly chosen input pattern sequence of length equal to or less than a fixed number (dictated by practical constraints) is applied to the inputs. In order to determine if a design is random pattern testable it is necessary to examine the fault detection probability of each fault. The exact determination of fault detection probabilities of the modeled stuck at faults in a combinational circuit is an NP complete problem. In this paper, an algorithm for computing bounds for the fault detection probabilities in linear time and which requires almost no memory is introduced