A class of good characteristic polynomials for LFSR test pattern generators

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudo-exhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify a class of such polynomials which, by appropriate LFSR cell ordering, guarantees that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage