On the computation of LFSR characteristic polynomials for built-in deterministic test pattern generation

Abstract

In built-in test pattern generation and test set compression, an LFSR is usually employed as the on-chip generator with an arbitrarily selected characteristic polynomial of degree equal, according to a popular rule, to Smax+20, where Smax is the maximum number of specified bits in any test cube of the test set. By fixing the polynomial a priori a linear system only needs to be solved to compute the required LFSR initial states (seeds) to generate the target test cubes, but the disadvantage is that the polynomial degree (length of the LFSR and seed bit size) may be too large and the fault coverage cannot be guaranteed. In this paper we address the problem of computing a polynomial of small degree directly from the given test set without having to solve multiple non-linear systems and fixing a priori the polynomial degree. The proposed method uses an adaptation of the Berlekamp-Massey algorithm and the Sidorenko-Bossert theorem to perform the computation. In addition, the method guarantees (by design) that all the test cubes in the given test set are generated, thereby achieving 100% coverage, which cannot be guaranteed under the 'trial-and-error' Smax+20 rule. Experimental results verify the advantages that the proposed methodology offers in terms of reduced polynomial degree and 100% coverage. © 1968-2012 IEEE.