4
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)
Is there any leniency regarding the input format? For example, would requiring state input be in the form
10101
rather than[1, 0, 1, 0, 1]
be acceptable? – primo – 2014-06-06T05:21:24.350Certainly, the list with square brackets was only a suggested input format. Spaces and commas should only be used if they are convenient in your language. – phosgene – 2014-06-06T05:22:51.333
May we use 0-indexed taps rather than 1-indexed? – Peter Taylor – 2014-06-06T07:23:28.743
Sure, any unambiguous input format is fine. – phosgene – 2014-06-06T07:48:55.423