7.4. Maximal-length Sequences#

  • If we are limited to use BPSK symbols from the alphabet \(\{\pm 1\}\) in our signature sequence, then the maximal-length sequences (\(m\)-sequences) are common choices with “good” auto-correlation functions.

  • The restriction to BPSK symbols may lead to simpler MF (or correlator) implementation correlation w.r.t. an \(m\)-sequence can be calculated by addition and subtraction.

7.4.1. Binary linear feedback shift register sequences#

  • Binary sequences are often generated by feedback shift registers in practice. In particular, linear feedback shift registers, like the one depicted in the figure below, are commonly used

    Linear feedback shift register

  • It is conventional to let the binary sequence \(u=\{u_l\}\) generated by the \(n\)-stage shift register in the above figures and the tap weights \(h_0,h_1,\ldots,h_n\) take on values from the alphabet \(\{0,1\}\). To obtain the BPSK symbol sequence \(x\) from the binary sequence \(u\), we define a map \(\chi\) from the binary alphabet to the BPSK alphabet by

    \[\begin{equation*} x[l] = \chi (u_l) = (-1)^{u_l}, \end{equation*}\]

    i.e., bit value \(0\) is mapped to BPSK symbol \(+1\) and bit value \(1\) is mapped to BPSK symbol \(-1\).

  • Note that \(h_0\) has to be \(1\), otherwise the output sequence \(u\) will be identically zero after \(n\) shifts. Similarly, \(h_n\) has to be \(1\), otherwise we can simply remove the leftmost stage to get a shorter shift register without affecting the output sequence.

  • Alternatively, one can also use the following form of linear feedback shift register that is more amenable to high-speed digital logic implementation:

    Linear feedback shift register in the transposed form

  • From the figures, we see that the shift-register output sequence satisfies

    (7.11)#\[\begin{equation} u_{l+n} = h_n u_l \oplus h_{n-1} u_{l+1} \oplus \ldots \oplus h_1 u_{l+n-1}, \end{equation}\]

    where \(\oplus\) denotes addition modulo \(2\), i.e., the XOR operation.

  • The shift register tap weights \(h_0,h_1,\ldots,h_n\) are usually represented by the binary polynomial

    \[\begin{equation*} h(D)=h_0 D^n+h_1 D^{n-1} + \ldots + h_{n-1}D + h_n. \end{equation*}\]

    The coefficients of \(h(D)\) are often given in octal notation. For example, the polynomial \(D^4+D+1\) is represented by \(\langle23\rangle\) in octal notation.

  • Note that each binary \(h(D)\) corresponds to a binary linear feedback shift register which generates binary sequences. Conversely, we say that a binary sequence \(u\) is generated by \(h(D)\) if the sequence elements satisfy (7.11).

  • A shift register \(h(D)\) can generate different sequences depending on the initial contents of the storage elements. When all the storage elements contain \(0\) initially, the sequences generated is the all-zero sequence. Since the all-zero sequence is of no practical interest, we usually exclude it from the set of sequences generated by \(h(D)\). An \(n\)-stage shift register can be viewed as a state machine with \(2^n-1\) states (the all-zero state is excluded) indexed by the contents of the storage elements. The initial state of the equivalent state machine determines the sequence generated by the shift register. For example, the table below shows all the \(2^4 - 1 = 15\) possible non-zero sequences generated by the polynomial \(D^4+D+1\):

    All non-zero sequences generated by $D^4+D+1$

7.4.2. Properties of binary linear feedback shift register sequences#

  • Binary shift register sequences have been extensively investigated. Here, we state several obvious but important properties of binary shift register sequences. Below, we use \(u\) and \(v\) to denote binary shift register sequences:

    1. Each binary shift register sequence \(u\) is periodic. The period of \(u\) is at most \(2^n -1\), where \(n\) is the degree of the polynomial that generates \(u\).

    2. If \(u\) is generated by \(h(D)\), then \(T^i u\) is a sequence generated by \(h(D)\).

    3. If \(u\) and \(v\) are generated by \(h(D)\), then \(u\oplus v\) is a sequence generated by \(h(D)\).

    4. Let \(u\) be a binary shift register sequence. Then \(T^i \chi(u) = \chi(T^i u)\) and \(\sum_{l=0}^{N-1} \chi(u_l) = N-2w_H(u)\), where \(w_H(u)\) is the Hamming weight of \(u\), i.e., the numbers of \(1\)’s in \(u\) .

    5. Define the periodic cross-correlation function of the binary shift register sequences \(u\) and \(v\) by \(\theta_{u,v}[k] \triangleq \theta_{\chi(u),\chi(v)}[k]\). Then \(\theta_{u,v}[k]= N-2w_H(u\oplus T^k v) = A_k -D_k\), where \(A_k\) and \(D_k\) denote the numbers of places in which \(u\) and \(T^k v\) agree and disagree, respectively.

7.4.3. \(m\)-sequences#

  • From Property 1, we know that an \(n\)-stage shift register can generate sequences with periods up to \(N=2^n-1\). If a shift register sequence has this maximal period, it is called a maximal-length sequence or \(m\)-sequence.

  • It turns out that all \(m\)-sequences with period \(N=2^n-1\) are generated by primitive polynomials of degree \(n\). Conversely, every sequence generated by a primitive polynomial is an \(m\)-sequence.

  • The table below lists primitive polynomials of degrees up to \(8\):

    Primitive polynomials up to degree $8$

  • Note that the reciprocal polynomial (\(D^nh(1/D)\)) of a primitive polynomial is also primitive. Hence, it also generates \(m\)-sequences. For example, the reciprocal polynomial of \(D^4+D+1\) (\(\langle 23 \rangle\)) is \(D^4+D^3+1\) (\(\langle 31 \rangle\)), which is a primitive polynomial. For clarity, reciprocal polynomials are not listed in the table above. One should obtain the reciprocals from the primitive polynomials listed in the table to complete the set of primitive polynomials of a certain degree. More comprehensive tables of primitive polynomials can be found in many standard textbooks on error-control coding.

7.4.4. Properties of \(m\)-sequences#

  • Beside requiring the minimum number of shift register stages to generate, the \(m\)-sequence \(u\) has the following desirable properties:

    1. There are exactly \(N\) non-zero sequences generated by the primitive polynomial \(h(D)\). They are the \(N\) different phases of \(u\), namely, \(u, Tu, T^2u, \ldots, T^{N-1}u\).

    2. A sequence \(u\) of period \(N\) is an \(m\)-sequence if and only if given two distinct integers \(i\) and \(j\), \(0\leq i,j<N\), there is a unique integer \(k \neq i\) or \(j\) such that \(0 \leq k < N\) and \(T^iu \oplus T^ju = T^ku\).

    3. \(w_H(u) = 2^{n-1} = (N+1)/2\)

    4. \(\theta_u(k) = \left\{ \begin{array}{ll} N, & \mathrm{~if~~} l=0 \text{ mod } N \\ -1, & \mathrm{~if~~} l\neq 0 \text{ mod } N. \end{array} \right.\)

  • Note that Properties 2 and 3 imply Property 4, which states that the periodic auto-correlation functions of \(m\)-sequences approach the ideal one described previously as the period \(N\) increases. Therefore, \(m\)-sequences are commonly employed in practice when good autocorrelation functions are required. For example, we can employ an \(m\)-sequence as the signature sequence for acquisition.