Maximum sequence test pattern generators with irreducible characteristic polynomials

Mechanisms that can generate maximum-length sequences (M-sequences) are of particular interest in pseudoexhaustive or pseudorandom built-in Test Pattern Generation (TPG). The characteristic polynomial of these mechanisms is restricted to be chosen among primitive polynomials only, since the latter require only one initialization state (seed). Recently, it was shown that any non-primitive irreducible polynomial can be used as characteristic polynomial to generate an M-sequence in the minimum number of cycles and with hardware overhead bounded by a low constant irrespectively of the number of seeds. In this paper, we describe and analyze the hardware overhead of two alternative schemes for the same purpose. These schemes offer even lower hardware overhead than the original one for a large majority of non-primitive irreducible polynomials of each degree. We also catalog each non-primitive irreducible polynomial of degree 12–22 according to the least costly of these schemes that can be used with it to generate an M-sequence.