Generating an MLS sequence

Generation of an MLS signal can be done using a feedback shift register [68,65]. The shift register consists of a group of $m$ binary memory elements in a line. At each time unit the numbers held in the memory elements are passed on one step to the right and the vacated element on the left is generated by a recursion relation which depends on the number of memory elements, $m$. The values which exit the element group on the right hand side form the output sequence.

There are several recursion relations that may be used to generate an MLS. We will not derive these, rather we will use the simplest (and therefore most computationally efficient) available. As an example, consider a shift register of $m=4$ elements. The recursion relation we use is directly related to the primitive polynomial [69]

$$h(x) = x^4 + x + 1.$$ (7.3)

The memory elements corresponding to the terms in $h(x)$ are added and the result taken modulo 2 (ie. the remainder when divided by two) to give the left entry on the following time step. As is shown in figure 7.10, the term 1 in $h(x)$ corresponds to the value held in $a_i$, the term $x$ refers to the term $a_{i+1}$ and the term $x^4$ is not part of the sum because there are only 4 memory elements. The primitive polynomial therefore corresponds to the recursion relation $a_{i+4}=a_{i+1}+a_{i}$. The last and second last elements are therefore used to calculate the new left hand element, and since the sum is taken modulo 2 the operation is equivalent to the exclusive OR gate as shown in the figure.

Figure 7.10: Feedback shift register and recurrence relation for $m$ = 4

In order to generate an MLS in practice we have to specify an initial state for the memory elements. Here we will use 1111. The last and second last elements are both 1, so the sum is 2, which when taken modulo 2 gives a result of 0 for the left hand element at the next step. The other elements shift one step to the right, giving 0111 as the next state of the four elements, and the 1 which exited on the right is the first term in the output sequence.

Table 7.1 shows the state of the memory element group at each time step and the MLS can be seen building up vertically down the right hand column. The MLS sequence appears random, but repeats with a period of 15. In fact, the element group takes every binary value possible except 0000 which would be a dead end for the sequence since a 1 would never be generated. The number of possible values for a binary number with $m$ digits is $2^m$ so the maximum length for an MLS signal must therefore be $2^m-1$, hence the name maximum length sequence. It follows that the initial state is unimportant to the properties of the MLS signal (as long as 0000 is not taken) since the sequence covers all non-zero states and is periodic.

Table 7.1: MLS element sequence for $m=4$

Time step, $i$	Elements, $(a_{i+3},a_{i+2},a_{i+1},a_i)$	MLS signal, $a_i$
0	1111	1
1	0111	1
2	0011	1
3	0001	1
4	1000	0
5	0100	0
6	0010	0
7	1001	1
8	1100	0
9	0110	0
10	1011	1
11	0101	1
12	1010	0
13	1101	1
14	1110	0
15	1111	1
16	0111	1
:	:	:

For other values of $m$, the only difference in the method for generating an MLS is that we use $m$ memory elements and we must use a different primitive polynomial, of order $m$. The polynomials up to $m=168$ are listed by Stahnke [69] and are shown in recursion relation form up to $m=20$ in table 7.2. The length of an $m=20$ sequence is $2^{20}-1 = 1048575$ samples which corresponds to over 23 seconds of sound when played as an acoustic signal at 44.1 kHz.

Table 7.2: Recursion relations for MLS of length $2^m-1$

$m$	Recursion relation
1	$a_{i+1} = a_{i}$
2	$a_{i+2} = a_{i+1} + a_i$
3	$a_{i+3} = a_{i+1} + a_i$
4	$a_{i+4} = a_{i+1} + a_i$
5	$a_{i+5} = a_{i+2} + a_i$
6	$a_{i+6} = a_{i+1} + a_i$
7	$a_{i+7} = a_{i+1} + a_i$
8	$a_{i+8} = a_{i+6} + a_{i+5} + a_{i+1} + a_i$
9	$a_{i+9} = a_{i+4} + a_i$
10	$a_{i+10} = a_{i+3} + a_i$
11	$a_{i+11} = a_{i+2} + a_i$
12	$a_{i+12} = a_{i+7} + a_{i+4} + a_{i+3} + a_i$
13	$a_{i+13} = a_{i+4} + a_{i+3} + a_{i+1} + a_i$
14	$a_{i+14} = a_{i+12} + a_{i+11} + a_{i+1} + a_i$
15	$a_{i+15} = a_{i+1} + a_i$
16	$a_{i+16} = a_{i+5} + a_{i+3} + a_{i+2} + a_i$
17	$a_{i+17} = a_{i+3} + a_i$
18	$a_{i+18} = a_{i+7} + a_i$
19	$a_{i+19} = a_{i+6} + a_{i+5} + a_{i+1} + a_i$
20	$a_{i+20} = a_{i+3} + a_i$