Maximum-length sequences, usually known as m-sequences, are binary sequences with some interesting properties (pseudo-noise appeareance, optimal periodic autocorrelation) which make them suitable for many applications in telecommunications, such as spread-spectrum transmission, measurement of impulse responses of propagation channels, and error-control coding. As a specific example, they are the basis for the synchronization signals used in the (4G) LTE mobile communication system.
These sequences are best understood as generated by means of an L-stage binary shift register with linear feedback. Consider the following figure (from the linked Wikipedia article), which shows an example for L=4.
The state of the shift register is given by the content (
1) of each stage. This can also be interpreted as the binary expansion of a number, with the most significant bit at left. The shift register is initiallized with a certain state, which we will assume to be
[0 ... 0 1]. At each discrete-time instant, the contents are shifted to the right. The value of the rightmost stage is the output, and gets removed from the register. The successive values of the rightmost state constitute the output sequence. The leftmost part is filled with the result of the feedback, which is a modulo-2 (XOR) combination of certain stages of the register (in the figure they are the two rightmost stages). The stages that are actually connected to the modulo-2 adder will be referred to as the feedback configuration.
A sequence produced by a shift register is always periodic. Depending on the feedback configuration, different sequences result. For certain configurations the period of the resulting sequence is the maximum possible, that is, an m-sequence results. This maximum is 2L-1: the register has 2L states, but the all-zero state can't be part of the cycle because it is an absorbing state (once it is reached it is never abandoned).
A shift-register sequence is defined by the number of stages L and the feedback configuration. Only certain feedback configurations give rise to m-sequences. The example above is one of them, and the sequence is
[1 0 0 0 1 0 0 1 1 0 1 0 1 1 1], with period 15.
It can be assumed that the last stage is always part of the feedback, otherwise that stage (and possibly some of the preceding) would be useless.
There are several ways to describe the feedback configuration:
- As a binary array of size L:
[0 0 1 1]in the example. As indicated, the last entry last will always be
- As a number with that binary expansion. But since it would not be possible to distinguish for example
[0 1 1]and
[0 0 1 1], a dummy leading
1is added. In the example, the number defining the feedback configuration would be
- As a polynomial (over the field GF(2)). Again, a leading 1 coefficient needs to be introduced. In the example, the polynomial would be x4+x+1. The exponents increase to the left.
The description in terms of polynomials is interesting because of the following characterization: the sequence generated from the shift register will be an m-sequence if and only if the polynomial is primitive.
TL;DR / The challenge
Given a feedback configuration with L>0 stages, generate one cycle of the resulting sequence, starting from the
0···01 state as described above. The feedback configuration will always correspond to an m-sequence, so the period will always be 2L-1.
Input can be given by any means, as long as it is not pre-processed:
- Binary array. In this case L is not explicitly given, because it is the length of the vector.
- You can choose to include a dummy leading
1in the above array (and then L is the length minus 1).
- Number with dummy leading
1digit in its binary expansion.
- Number without that dummy
1and a separate input explicitly giving L.
- Strings representing any of the above.
...or any other reasonable format.
The input format used must be the same for all possible inputs. Please indicate which one you choose.
For reference, A058947 gives all possible inputs that give rise to m-sequences, in format 2 (that is, all primitive polynomials over GF(2)).
The output will contain 2L-1 values. It can be an array of zeros and ones, a binary string, or any other format that is easily readable. The format must be the same for all inputs. Separating spaces or newlines are accepted.
Code golf. Fewest best.
Input in format 2, input in format 3, output as a string:
[1 1] 3 1 [1 0 0 1 1] 19 100010011010111 [1 0 1 0 0 1] 41 1000010101110110001111100110100 [1 0 0 0 0 1 1] 67 100000100001100010100111101000111001001011011101100110101011111