Interlacing properties of shift-register sequences with generator polynomials irreducible overGF(p)(Corresp.)

Interlacing properties of shift-register sequences with generator polynomials irreducible over GF(p)-herein called elementary sequences--are analyzed. The most important elementary sequences are maximal-length sequences (m-sequences). If the periodqof an elementary sequence is not prime, the sequence can always be constructed by interlacing shorter elementary sequences of periodq_{i}, providedq_{i}dividesq. It is proved that all interlaced elementary sequences are generated by one and the same irreducible polynomial. Some relationships between equal-length elementary sequences are derived, including some rather unexpected crosscorrelation properties. As an example of an application of the theory, a new time-division multiplex technique for generating high-speedm-sequences is presented.