Generate m-sequences

Question

Introduction

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 (0 or 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 2^L-1: the register has 2^L 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 1.
• 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 1 is added. In the example, the number defining the feedback configuration would be 19.
• As a polynomial (over the field GF(2)). Again, a leading 1 coefficient needs to be introduced. In the example, the polynomial would be x⁴+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 2^L-1.

Input can be given by any means, as long as it is not pre-processed:

1. Binary array. In this case L is not explicitly given, because it is the length of the vector.
2. You can choose to include a dummy leading 1 in the above array (and then L is the length minus 1).
3. Number with dummy leading 1 digit in its binary expansion.
4. Number without that dummy 1 and a separate input explicitly giving L.
5. 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 2^L-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.

Test cases

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    

Answer 1

Haskell, 88 82 bytes

r@(h:t)%m=h:(t++[mod(sum[v|(v,1)<-zip r m])2])%m
l#x=take(2^l-1)$(1:(0<$[2..l]))%x

I'm using input method 1 (but in reverse order, because I'm shifting to the left) together with L as an explicit parameter.

Usage example (test case #2): 4 # [1,1,0,0] -> [1,0,0,0,1,0,0,1,1,0,1,0,1,1,1].

How it works: % does the work. First parameter is the content of the shift register, second parameter is the feedback configuration. # starts the whole process by building the initial register content, calling % and taking the first 2^L-1 elements.

main function #:

                1:0<$[2..l]      -- initial register content: one 1 followed
                                 -- by L-1 0s
                            %x   -- call the helper function with the
                                 -- feedback configuration
take(2^l-1)                      -- and take the first 2^L-1 elements

helper function % (bind r to the whole register set, h to the first register a0
and t to register a1..aL. Bind m to the feedback config): 

h:                               -- next element is h, followed by
                         %m      -- a recursive call of %, where the new register is
   t++                           -- t followed by
           [v|(v,1)<-zip r m]    -- the elements of l, where the corresponding
                                 -- elements of m are "1"
      mod(sum ...          )2    -- xored    

Answer 2

Pyth, 19 bytes

eM.u+xF*VQNPN+m0tQ1

Try it online: Demonstration or Test Suite

Explanation:

eM.u+xF*VQNPN+m0tQ1   implicit: Q = input list in format 1
              m0tQ    create a list with len(Q)-1 zeros
             +    1   and append a one at the end
                      this is the starting sequence
  .u                  apply the following statement repeatedly to the starting seq. N:
       *VQN              vectorized multiplication of Q and N
     xF                  xor all this values
    +      PN            remove the last value of N and prepend the new calculated one
                      .u stops, when it detects a cycle and returns a list of
                      all intermediate states of N
eM                    take the last element of each state and print this list

Answer 3

Jelly, 18 bytes

æḟ2µ&³B^/+ḤµḤ¡BḣḤṖ

This takes a single integer, encoding a₀ in its MSB and a_L-1 in its LSB.

The test cases become 1, 12, 18 and 48 in this format. Try it online!

How it works

æḟ2µ&³B^/+ḤµḤ¡BḣḤṖ  Main link. Argument: n (binary-encoded taps)

æḟ2                 Round n down to k = 2 ** (L - 1), the nearest power of 2.
   µ                Begin a new, monadic link. Argument: r = k
    &³              Bitwise AND r with n.
      B             Convert to binary.
       ^/           Bitwise XOR all binary digits.
          Ḥ         Unhalve; yield 2r.
         +          Add the results to left and right.
           µ        Convert the previous chain into a single link.
            Ḥ       Unhalve; yield 2k = 2 ** L.
             ¡      Execute the link 2k times, updating r in each iteration.
              B     Convert the final value of r to binary.
               ḣḤ   Keep only the first 2k binary digits.
                 Ṗ  Pop; discard the last digit.

Answer 4

MATL, 26 bytes

g`tGZ&Bs2\2GBnq^*+H#2\tq]x

This works in current version (15.0.0) of the language.

Input is a number describing the feedback configuration, using format 3 as described in the challenge. Output is separated by newlines.

Try it online!

Explanation

This uses numbers to represent the register contents, and a bitwise XOR operation to compute the feedback bit.

At each iteration the fed-back bit is introduced at an "extra stage" at the left of the leftmost stage. A divmod operation by 2 then gives the new contents (division quotient) and the output (division remainder). The stack holds the already produced output and the current state on top.

Instead of looping a fixed number (2^L-1) of times, a "do...while" loop is used, which in this case requires fewer bytes. The loop exits when the 1 state is reached again.

g         % take input. Convert to logical: gives 1, because input is nonzero.
          % This is the initial state. The input has been copied into clipboard G
`         % do...while
  t       %   duplicate
  G       %   push input
  Z&      %   bitwise XOR
  Bs2\    %   convert to binary, sum, compute parity. The result is the feedback bit
  2GBnq^  %   compute next power of two that exceeds the register size. This is used
          %   for introducing the fed-back bit in a leftmost stage "outside" the
          %   register, which will be immediately shifted right
  *+      %   multiply by feedback bit and add to register state
  H#2\    %   divmod by 2. Gives output bit and new state on top
  tq      %   duplicate and subtract 1. This is falsey if state is 1 (loop will be
          %   exited in that case)
]         % end do...while. Exit if top of stack is falsey
x         % delete current state. Implicitly display sequence

Answer 5

JavaScript (ES6), 100 bytes

(l,f)=>[...Array((1<<l)-1)].map((_,i)=>(v=i?(x=v&f,[1,2,4,8,16].map(n=>x^=x>>n),x&1)<<l-1|v>>1:1)&1)

Takes type 4 input (length and feedback without the leading 1; well, the 1 is optional.) Returns an array of 0s and 1s. The parity calculation is annoying; I wanted to use reduce but that turns out to be 2 bytes longer, because the precedence of << is wrong for my use case.

Answer 6

Kotlin, 93 bytes

^{(91 + len(str(Number)))}

Input Number is hardcoded in the source, without leading 1 and in reverse bit order (like @Dennis' answer). Input L is not needed!

The test cases become 1, 12, 18, 48.

fun main(a:Array<String>){var v=1
do{print(v and 1)
v=(v shr 1)xor 48*(v and 1)
}while(v!=1)}

Try it online!

Result appears rotated left by L bits:

100001100010100111101000111001001011011101100110101011111100000

Compare with original:

      100001100010100111101000111001001011011101100110101011111100000
100000100001100010100111101000111001001011011101100110101011111    

      1010111011000111110011010010000
 1000010101110110001111100110100

      100110101111000
  100010011010111