Bounds and analysis of aliasing errors in linear feedback shift registers

Aliasing errors in linear feedback shift registers (LFSRs) used as signature analysis registers in self-testing networks are considered. A bound on aliasing is established by a straightforward algebraic analysis of LFSRs. It is calculated as a function of p, the probability of an error occurring at an output of the network under test. This bound is robust but is only good for p close to 1/2. To investigate the question of what happens to aliasing errors in general, the function of LFSRs is modeled by a Markov process and a solution is obtained by the z-transform. It is shown that for p>1/2 the aliasing probability for primitive polynomials converges much faster to the final steady-state value than for nonprimitive polynomials. For values of p<1/2, aliasing probability for primitive polynomials is always less than for nonprimitive ones. These results indicate that, in general, primitive polynomials are much better with respect to aliasing than nonprimitive polynomials. Simulation results for aliasing errors for these polynomials give insight to how aliasing occurs