Majority-based feedback shift register

Question

Linear feedback shift registers (LFSR's) work by taking a fixed-length bit-string $b\in\{0,1\}^n$, as well as fixed "taps" (bit positions) and applying XOR to the taps, giving one output bit, which is appended at the $b$ after shifting it.

Now XOR is a linear function. A natural non-linear function that can be used on the fixed set of taps is a kind of "majority vote", which works as follows: if the majority of the taps is $0$, then we output $1$, and vice versa. (For this, it is best to have an odd number of taps.)

A simple implementation of a majority-based feedback shift register can be found here.

Of course, applying this "majority vote" procedure over and over again, this eventually gets periodical.

Question. Given fixed bit-length $n$, what is a lower bound of the maximal length of a period that can be achieved choosing a suitable start string $b\in \{0,1\}^n$ and a suitable set of taps?

Also, I wasn't able to find out if and where this concept has been studied.

Answer 1

I'm reading the question as asking for $b(n)$, the largest possible, such that we can exhibit distinct tap points (in odd number), and $n$-bit state, leading to a periodic sequence of (shortest) period at least $b(n)$ steps.

I have a construction with $b(n)=2n-2$ for $n\ge3$. The taps are the next three bits that will drop out of the MVFSR. The state is all-zeroes, except for the next bit that will drop out of the MVFSR. Here is an illustration with $n=8$: time elapses from left to right, the MVSFR shifts down, the next bit enters on top, the three taps are marked with *.

   0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0
   0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0
   0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0
   0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0
   0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0
*  0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0
*  0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
*  1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1

If we allow a single tap, we get to $b(n)=2n$.

I hope that $b(n)$ can be improved (increased), perhaps to become exponential, but it's already more than $1$ of this answer, and $2$ of this comment.

Answer 2

I would hesitate to claim a better lower bound than 1.

We note that for a majority vote feedback shift register (hereafter MVFSR) if there are $2k+1$ taps and if at any point the fill of the register has at most $k$ zeros (respectively at most $k$ ones) then the register will subsequently fill up with ones (respectively with zeros) and hit a cycle of 1.

Likewise, one feels that there is a lot of substantialism in that MVFSR with sparse fills with lots of zeros are likely to produce zero feedbacks and dense fills with lots of ones are likely to produce one feedbacks. Heuristically this would drive the fill density away from 1/2 and towards the above degeneracy.

It's possible to produce MVFSRs with taps set in arithmetic progression that degenerate into interleavings of smaller registers and so which hit stable cycles of length equal to the number of smaller registers, but this does not feel like a good idea.

One can also note that the map from fill-to-fill for an MVFSR has many two-to-one maps which places a poor upper bound on the final cycle length. In general fills where $k+1$ of the first $2k$ taps are zero or one (i.e. where there are not exactly $k$ zeros and $k$ ones in the first $2k$ tap positions) are fills where the oldest tap bit is irrelevant to the feedback and so we create a two-to-one.

Answer 3

I've written some code to just brute force tap configurations and starting values for small register sizes. So I have some values, rather than an analytic result. Of course the results are conditional on there not being any bugs in the code (https://github.com/bmm6o/MVFSR).

for width 4, max cycle length is 8
for width 5, max cycle length is 10
for width 6, max cycle length is 12
for width 7, max cycle length is 14
for width 8, max cycle length is 48
for width 9, max cycle length is 48
for width 10, max cycle length is 80
for width 11, max cycle length is 108
for width 12, max cycle length is 140
for width 13, max cycle length is 270
for width 14, max cycle length is 270
for width 15, max cycle length is 270
for width 16, max cycle length is 480
for width 17, max cycle length is 752
for width 18, max cycle length is 1520

It can be risky to generalize from small values, but it does to seem to approximately double when the width increases by 2. This sequence is not present in the OEIS.

You've probably realized this, but your MVFSR evolves in a way such that most states have exactly 2 pre-images. I'm not sure how to use that to make a probabilistic estimate of the cycle length distribution, but it seems like it would be helpful.

For most cryptographic purposes, putting a lower bound on the maximum cycle length is not the most important question. Much more important is the minimum length, or at least a way to characterize and avoid short cycles. In that way, there is a serious problem with MVFSR. Under optimal tap selection, there are cycles of length just $2n$.