Maximal Length Sequences

Various pseudo random codes are generated using LFSR(Linear Feedback Shift Register). The generator polynomial governs all the characteristics of the generator. For a given generator polynomial, there are two ways [2] of implementing LFSR. Galois feedback generator uses only the output bit to add (in Galois field) several stages of the shift register and is desirable for high speed hardware implementation as well as software implementation. The other known as Fibonacci feedback generator can generate several delays of sequences without any additional logic.

Shift-register sequences having the maximum possible period for an r-stage shift register are called maximal length sequences or m-sequences. A primitive generator polynomial [2] always yield an m-sequence. The maximum period of an r-stage shift register can be proven to be 2^r - 1. The m-sequences has three important properties, i.e., balance property, run-length property and shift-and-add property. The periodic autocorrelation function R_a(k) is two-valued and is given by

$$R_a(k) = \left\{ \begin{array}{ll} 1.0 & k = lN \\ -\frac{1}{N} & k \neq lN \end{array} \right.$$ (1)

where l is an integer and N is the period of the m-sequence. The excellent auto-correlation property comes from the first and the third properties. Refer to [2] for details. m-sequences have good auto correlation property and are being used in many applications including IS-95. As the cross-correlation property of these sequences is relatively poor compared to Gold codes, the same sequence with different offset are usually used for different users or for different base stations. With this method, the discrimination property between different spreading codes only depends on partial autocorrelation property.

The software implementation of Galois construction for a given generator polynomial is straight forward and well known [3]. mseq module is written to generate arbitrary m-sequences with the degree of polynomial less than 32. This restriction is due to the fact that the LFSR state is represented by an unsigned long int variable. If an m-sequence generator with the degree of greater than 31 is required, use lmseq module instead of mseq. lmseq handles higher degrees up to 63. mseq module is the foundation module for other PN sequences such as Gold codes, orthogonal Gold codes and Kasami sequences.