Evaluate a Linear Feedback Shift Register

Question

Introduction

The Fibonacci Linear Feedback Shift Register (LFSR) is a digital circuit which generates a stream of random-looking bits. It consists of several 1-bit flip-flops in a row, with certain positions designated as 'tapped'. In each iteration, the values in the tapped positions are XORed together (i.e., summed modulo 2) and the result is held in reserve. Then the bits are shifted to the right. The rightmost bit falls off the register and becomes the output, while the reserve bit is input on the left.

Maximal LFSR

The output stream of a LFSR is periodic; it repeats after some number of iterations. A maximal LFSR has a period of 2^n - 1, where n is its number of bits. This only occurs if the tapped positions are correctly chosen; otherwise the period will be less. If the LFSR is maximal, it will cycle through all possible internal states (except all zeroes) exactly once before repeating.

For more information about maximal Fibonacci LFSRs (primitive polynomials), see this article: https://en.wikipedia.org/wiki/Linear_feedback_shift_register#Fibonacci_LFSRs

Task

You must write a function that takes as its arguments a list representing the initial internal state of an n-bit LFSR (a list of length n made of 0 and at least one 1), and a list of tapped positions. The tapped positions are input as a list with either of these general formats (brackets, commas, and spaces are shown for convenience and are entirely optional):

Format A: [0, 0, 1, 1]

Format B: [3, 4]

Both formats declare that the 3rd and 4th positions are tapped.

The function must produce exactly one complete cycle of output of the LFSR (either as function output, or printed to the screen), as well as a Boolean evaluation of whether or not the LFSR period is maximal.

If you prefer, you may use two functions to produce the LFSR output and maximality evaluation.

Scoring

Per usual code golf rules, your score is the number of characters in your code. Make sure your code evaluates these examples correctly:

Example 1

State: [1, 0, 1, 0]

Taps: [3,4]

Output: [0,1,0,1,1,1,1,0,0,0,1,0,0,1,1] and True (since the period is 2^n - 1 = 15)

Example 2

State: [1, 0, 1, 0, 1]

Taps: [3, 5]

Output: [1,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1] and True (since the period is 2^n - 1 = 31)

Example 3

State: [1, 0, 1, 0, 1]

Taps: [4, 5]

Output: [1,0,1,0,1,1,1,1,1,0,0,0,0,1,0,0,0,1,1,0,0] and False (since the output has period 21, which is not equal to 2^n - 1)

Answer 1

GolfScript, 38 characters

:f;:i[{0{(2$=^}f/\+)\.i=!}do;].,)2i,?=

You may declare it as a named function if you enclose the code in {<code>}:F. It takes the top two arguments from the stack and pushes the results back to the stack, e.g. (test it online):

[1 0 1 0 1] [3 5]

:f;:i[{0{(2$=^}f/\+)\.i=!}do;].,)2i,?=

# => yields [1 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1] 1

Annotated code:

:f;          # save tap positions (1 indexed) to variable f
:i           # and the initial state to variable i
[{           # the [{...}do;] loop generates an array using the loop
             #   top of stack is the current state
  0          #   push zero (accumulator)
  {          #   {...}f/ loops over all tap positions
    (        #     make the current position zero-indexed
    2$=      #     take the corresponding bit from the current state (2$)
    ^        #     xor with the accumulator
  }f/        #   end of loop
  \+         #   prepend the new bit to the current state
  )\         #   and shift out the last bit (output)
  .i=        #   compare the current state to input
  !          #   if not equal then loop
}do;]        # end of loop - discard the state
.,)          # length of the output + 1
2i,?         # 2^length of initial state
=            # are those two numbers equal?

Answer 2

Perl - 78 bytes

sub f{($_,$t)=@_;s//($_&$t)%9&1/e,@o=(@o,chop)until$o{$_}++;@o,$/,@o+1>>y///c}

Input is expected as two binary strings, one representing the current state, and the other the taps. For example, the input ('10101', '00011') corresponds to an initial state with the 1st, 3rd, and 5th bits set (one indexed), with taps on the 4th and 5th bit.

For the truth condition, a 0 or 1 is returned, separated by a newline.

Note: The bit counting logic above, ($_&$t)%9&1, will fail if the total number of bits is more than 16, and/or the number of taps is greater than 8. This can be replaced by ($_&$t)=~y|0||c&1 at the cost of 6 bytes.

Test Case 1
Input:

print f('1010', '0011');

Output:

010111100010011
1

Test Case 2
Input:

print f('10101', '00101');

Output:

1010100001001011001111100011011
1

Test Case 3 Input:

print f('10101', '00011');

Output:

101011111000010001100
0

Answer 3

Javascript (E6) 144 157 169

Edit Output as string instead of array

F=(s,t)=>(P=>{b=s.length,i=s=P(s,2),t=P(t,2);for(o='';!o||i-s;){for(p=q=s&t;q>>=1;p^=q);o+=s&1,s=s>>1|(p&1)<<b-1}})(parseInt)||[!!o[(1<<b)-2],o]

Ungolfed

F=(s,t)=> 
( P => { // Inner block, spare a final 'return'
  b = s.length,
  i = s = P(s,2), t=P(t,2);
  for (o='';!o||i-s;) {
    for (p=q=s&t;q>>=1;p^=q);
    o += s & 1,
    s = s >> 1 | (p&1) << b-1
  }
} ) (parseInt)
|| [!!o[(1<<b)-2], o]  

Usage

State and Tapped position input as strings of bits (format A) Return an array with true/false and a string of output bits

Test

Javascript console in firefox,

F('1010', '0011') [true, "010111100010011"]

F('10101', '00101') [true, "1010100001001011001111100011011"]

F('10101', '00011') [false, "101011111000010001100"]