Maximal-length Sequence Generator (msequence)

Keywords: msequence maximal length sequence generator linear feedback shift register LFSR

The msequence object in liquid is really just a linear feedback shift register (LFSR), efficiently implemented using unsigned integers. The LFSR consists of an \(m\) -bit shift register, \(v\) , and generator polynomial\(g(x)\) . For primitive polynomials, the output sequence has a length \(n=2^m-1\) before repeating. This sequence is known as a maximal-length P/N (positive/negative) sequence, and consists of several useful properties:

  • the output sequence has very good auto-correlation properties; when aligned, the sequence, of course, correlates perfectly to \(n\) . When misaligned by any amount, however, the sequence correlates to exactly \(-1\) .
  • the sequence is easily generated using a linear feedback shift register

Only a certain subset of all possible generator polynomials produce this maximal length sequence.

Table [tab-sequence-genpoly]. Default \(m\) -sequence generator polynomials in liquid

\(m\)\(n=2^m-1\)\(g\) (hex) liquid macro\(g(x)\)
2 3 0x00000003 LIQUID_MSEQUENCE_GENPOLY_M2\( x^{2} + x + 1 \)
3 7 0x00000006 LIQUID_MSEQUENCE_GENPOLY_M3\( x^{3} + x^{2} + 1 \)
4 15 0x0000000c LIQUID_MSEQUENCE_GENPOLY_M4\( x^{4} + x^{3} + 1 \)
5 31 0x00000014 LIQUID_MSEQUENCE_GENPOLY_M5\( x^{5} + x^{3} + 1 \)
6 63 0x00000030 LIQUID_MSEQUENCE_GENPOLY_M6\( x^{6} + x^{5} + 1 \)
7 127 0x00000060 LIQUID_MSEQUENCE_GENPOLY_M7\( x^{7} + x^{6} + 1 \)
8 255 0x000000b8 LIQUID_MSEQUENCE_GENPOLY_M8\( x^{8} + x^{6} + x^{5} + x^{4} + 1 \)
9 511 0x00000110 LIQUID_MSEQUENCE_GENPOLY_M9\( x^{9} + x^{5} + 1 \)
10 1,023 0x00000240 LIQUID_MSEQUENCE_GENPOLY_M10\( x^{10} + x^{7} + 1 \)
11 2,047 0x00000500 LIQUID_MSEQUENCE_GENPOLY_M11\( x^{11} + x^{9} + 1 \)
12 4,095 0x00000e08 LIQUID_MSEQUENCE_GENPOLY_M12\( x^{12} + x^{11} + x^{10} + x^{4} + 1 \)
13 8,191 0x00001c80 LIQUID_MSEQUENCE_GENPOLY_M13\( x^{13} + x^{12} + x^{11} + x^{8} + 1 \)
14 16,383 0x00003802 LIQUID_MSEQUENCE_GENPOLY_M14\( x^{14} + x^{13} + x^{12} + x^{2} + 1 \)
15 32,767 0x00006000 LIQUID_MSEQUENCE_GENPOLY_M15\( x^{15} + x^{14} + 1 \)
16 65,535 0x0000d008 LIQUID_MSEQUENCE_GENPOLY_M16\( x^{16} + x^{15} + x^{13} + x^{4} + 1 \)
17 131,071 0x00012000 LIQUID_MSEQUENCE_GENPOLY_M17\( x^{17} + x^{14} + 1 \)
18 262,143 0x00020400 LIQUID_MSEQUENCE_GENPOLY_M18\( x^{18} + x^{11} + 1 \)
19 524,287 0x00072000 LIQUID_MSEQUENCE_GENPOLY_M19\( x^{19} + x^{18} + x^{17} + x^{14} + 1 \)
20 1,048,575 0x00090000 LIQUID_MSEQUENCE_GENPOLY_M20\( x^{20} + x^{17} + 1 \)
21 2,097,151 0x00140000 LIQUID_MSEQUENCE_GENPOLY_M21\( x^{21} + x^{19} + 1 \)
22 4,194,303 0x00300000 LIQUID_MSEQUENCE_GENPOLY_M22\( x^{22} + x^{21} + 1 \)
23 8,388,607 0x00420000 LIQUID_MSEQUENCE_GENPOLY_M23\( x^{23} + x^{18} + 1 \)
24 16,777,215 0x00e10000 LIQUID_MSEQUENCE_GENPOLY_M24\( x^{24} + x^{23} + x^{22} + x^{17} + 1 \)
25 33,554,431 0x01000004 LIQUID_MSEQUENCE_GENPOLY_M25\( x^{25} + x^{3} + 1 \)
26 67,108,863 0x02000023 LIQUID_MSEQUENCE_GENPOLY_M26\( x^{26} + x^{6} + x^{2} + x + 1 \)
27 134,217,727 0x04000013 LIQUID_MSEQUENCE_GENPOLY_M27\( x^{27} + x^{5} + x^{2} + x + 1 \)
28 268,435,455 0x08000004 LIQUID_MSEQUENCE_GENPOLY_M28\( x^{28} + x^{3} + 1 \)
29 536,870,911 0x10000002 LIQUID_MSEQUENCE_GENPOLY_M29\( x^{29} + x^{2} + 1 \)
30 1,073,741,823 0x20000029 LIQUID_MSEQUENCE_GENPOLY_M30\( x^{30} + x^{6} + x^{4} + x + 1 \)
31 2,147,483,647 0x40000004 LIQUID_MSEQUENCE_GENPOLY_M31\( x^{31} + x^{3} + 1 \)

The default generator polynomials are listed in[ref:tab-sequence-genpoly] , however many more exist.

Notice that both the first and last coefficient of each generator polynomial\(g(x)\) is a \(1\) . This holds true for all \(m\) -sequence generator polynomials. The hexadecimal representation of the generator polynomial drops the trailing 1 as this value is implied in the shift register representation. A default generator polynomial for \(m=2\)\((n=3)\) through \(m=31\)\((n=2,147,483,647)\) are provided in the table, above. These default generator polynomials are included in the global liquid.h header file, as well, for convenience.

#include <liquid/liquid.h>

int main() {
    // create and initialize m-sequence (length 63)
    msequence q = msequence_create_default(6);

    // cycle through values and print state
    unsigned int i;
    for (i=0; i<msequence_get_length(q); i++) {
        printf("%u\n",msequence_get_state(q));
        msequence_advance(q);
    }

    // destroy object
    msequence_destroy(q);
}

Shown above is a short example program demonstrating how to create an msequence object using the default generator polynomial. The program cycles through the entire sequence and prints the internal state of the shift register, a unique sequence for all values in \(1 \ldots n-1\) , but in a pseudo-random order.

doc/msequence/msequence_example.png

Figure [fig-sequence-msequence]. msequence auto-correlation, \(m=7\) (\(n=127\) ), \(g=\) 0x60

The auto-correlation of the \(m\) -sequence with generator polynomial\(g=\) 0x60 can be seen in [ref:fig-sequence-msequence] . The shift register has seven bits (\(m=7\) ) and therefore the output sequence is of length \(n=2^m-1=127\) . Notice that the auto-correlation is equal to unity with no delay, and nearly zero (\(-1/127\) ) for all other delays.