Welcome to the World of CDMA 

Linear Feedback Shift Registers Ideally the spreading codes used in direct sequence spread spectrum systems
would be truly random binary sequences, as might be produced by consecutive
tosses of an unbiased, memoryless coin. This is not practical. Both transmitter
and receiver must generate the same sequence, timealigned, in order to communicate
with one another. Receivers thus must perform synchronization searches by changing
their time offset hypothesis until the transmitter timing is located. Achieving
high capacity in the CDMA environment also requires that the spreading rate
be high: 1.2288 MHz in IS95A CDMA. If truly random sequences were to be used
then they would have to be pregenerated and prestored in all transmitters,
with a matching copy in all receivers. Deterministic methods of generating the
pseudorandom sequences are preferable. The CDMA air interfaces use linear feedback
shift register (LFSR) generators for this purpose.
Linear feedback shift registers can be implemented in two ways (Figure 1). The socalled Fibonacci implementation consists of a simple shift register in which a binary weighted modulo 2 sum of the taps is fed back to the input. There are actually two sequences produced by each of these generators. One is the trivial one, of length one, that occurs in both cases when the initial state of the generator is all zeros. The other, the useful one, has length 2^{m}1. Together these two sequences account for all 2^{m} states of the mbit state register. The mathematics of these generators is equivalent to the operation of ordinary algebra applied to abstract polynomials over an indeterminate X, with binaryvalued coefficients. This is a finite (Galois) field of order 2^{m} . Each sequence is based on a generator polynomial whose coefficients are binary, and are the weights shown in the figures. The polynomial is said to be primitive if it does not factor and it divides X^{r}+1, where r=2^{m}1. A primitive polynomial of degree m necessarily has g_{m} = g_{0} = 1. If the generator polynomial in a LFSR is primitive then the sequence produced by that generator has maximum length, which is 2^{m}1. Maximal length sequences are sometimes called msequences. For a discussion of the mathematics of finite fields see, for example, Golomb. Properties Some properties of msequences:1. An mbit register produces a sequence of period 2^{m}1. 2. An msequence contains exactly 2^{m1} ones and 2^{m1} 1 zeros. 3. The sum, modulo 2 of an msequence and another phase of the same msequence yields a third phase of the sequence. 3a. (A corollary of 3) Each node of the generator of an msequence runs through some phase of the sequence. 4. A sliding window of length m, passed along an msequence for 2^{m}1 positions, will span every possible mbit number except all zeros once and only once. 5. Define a run of length r to be a sequence of r consecutive identical symbols, bracketed by nonequal symbols. Then in any msequence there are:
If the sequence is mapped to a binary valued waveform
by mapping a binary zero to 1 and binary 1 to +1, then the autocorrelation
is unity for zero delay, and 1/N at all other times. Example Consider as an example, polynomials of degree 3, so that maximal length sequences are 7 bits long. The primitive polynomials of degree 3 are found as the nontrivial factors of X^{r}+1, where r=2^{m}1=7:produces {1110100} starting from the state [001]. Offsets and Time Shifts of mSequences The linearity of the msequence generators and their properties as a representation of a finite field make it rather simple to offset a state by some prescribed number of states, or to create a transformation matrix that will produce a delayed version of the sequence from an undelayed state register. The Galois generator, in particular, can be regarded as a counter in a Galois field. Counting is equivalent to multiplication of the generator state by a primitive element of the field. The multiplication is equivalent to ordinary matrix multiplication of the state, regarded as a column matrix, by a transformation matrix T.
 Back to Long Code  Back to Short Code 
 Index  Topics  Glossary  Standards  Bibliography  Feedback  Copyright © 19961999 Arthur H. M. Ross, Ph.D., Limited 