Reseeding using compaction of pre-generated LFSR sub-sequences

Built-In Self-Test (BIST) techniques are often based on pseudo-random pattern generators, which represent simple structures that can generate necessary test stimuli for a device under test (DUT). For some designs, however, additional measures of fault coverage improvement have to be applied. LFSR reseeding is a popular technique due to its ability to considerably improve both the fault coverage and test application time by embedding specific vectors into the pseudorandom sequence. Proper selection of LFSR seeds is the key aspect in a successful reseeding scheme. In this paper, we present our approach to reseeding optimization that is based on compaction of pre-generated LFSR sub-sequences in order to select a minimal subset of to be included into the final solution. The proposed approach relies on the branch-and-bound search technique, which can provide the optimal compaction for a given test setup. Alternatively, it can run for a limited time in a heuristic mode, producing intermediate results. Experiments show that applied heuristics can yield optimal or quasi-optimal solutions in polynomial time. These solutions outperform previously published results for a similar reseeding approach.