Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

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 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 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 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:

  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 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.

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    
share|improve this question
1  
If input is in format 2, are the first and last bits always set, and is there at most one other bit set? – Neil Mar 20 at 19:59
    
@Neil First: yes. Last: I hadn't thought of that, but also yes, otherwise the last stages would be useless. I've edited that into the challenge. Thanks! – Luis Mendo Mar 20 at 20:20
    
can we shift to the left and therefore take the feedback configuration in reverse order, e.g. you second test case as [1,1,0,0,1]? – nimi Mar 20 at 22:19
    
@nimi Yes, if you indicate that in your input format specification – Luis Mendo Mar 20 at 22:43
    
Thanks, but I'm still unclear as to how many stages might be connected to the adder. – Neil Mar 20 at 22:54
up vote 2 down vote accepted

Jelly, 18 bytes

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

This takes a single integer, encoding a0 in its MSB and aL-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.
share|improve this answer

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    
share|improve this answer

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
share|improve this answer
    
I've edited the challenge (following Neil's comment): the input list will always end in 1. Just in case it helps – Luis Mendo Mar 20 at 20:21

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 (2L-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
share|improve this answer
    
Does MATL compile to Matlab? – cat Mar 21 at 3:34
    
@tac Yes, to Matlab or Octave. In the answer you have the link to the compiler and documentation – Luis Mendo Mar 21 at 10:25

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.

share|improve this answer

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
share|improve this answer
    
Hardcoding in the source code doesn't seem to be one of the accepted input methods. Also, the cyclic shift in the output amounts to starting the sequence in a different state, which is not allowed by the challenge – Luis Mendo Mar 30 at 21:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.