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

Abstract

Interlacing properties of shift-register sequences with generator polynomials irreducible over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p)</tex> -herein called elementary sequences--are analyzed. The most important elementary sequences are maximal-length sequences ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> -sequences). If the period <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> of an elementary sequence is not prime, the sequence can always be constructed by interlacing shorter elementary sequences of period <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q_{i}</tex> , provided <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q_{i}</tex> divides <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> . 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-speed <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> -sequences is presented.