Score:6

Majority-based feedback shift register

br flag

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.

John Deters avatar
cn flag
While not an answer to your question, ancient CDC mainframes had a "Population Count" instruction, CXi Xk, which would output the number of 1 bits set in register Xk to register Xi. AKA "popcount" or "the NSA instruction", the original primary practical use for this operator was theorized to be cryptanalysis, suggesting this may have been studied or known in the 1960s and 70s. See https://vaibhavsagar.com/blog/2019/09/08/popcount/#:~:text=Most%20CPU%20architectures%20in%20use%20today%20have%20an,%2800100110%29%20is%203%20and%20popcount%20%2801100000%29%20is%202. for more info.
Dominic van der Zypen avatar
br flag
That's really interesting - thanks @JohnDeters for this comment! Also I use a function in [my implementation on GitHub](https://github.com/dominiczypen/Majority_Feedback_Shift_Register/blob/main/mfsr.c) that is actually called popcount(). Maybe using the popcount that is built into the CPU would be much faster
qwr avatar
jp flag
qwr
x86 has a popcount instruction too https://www.felixcloutier.com/x86/popcnt
b degnan avatar
ca flag
btw, in actual hardware, majority circuits take up a lot of space. The simplicity that you see in C is non-existent gate level.
Score:2
ng flag

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.

Dominic van der Zypen avatar
br flag
Thanks a lot for your answer -> it would be awesome to see $b(n)$ increased to become exponential even with a small number of taps cleverly placed, maybe only $3$ taps?
Score:2
ph flag

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

kodlu avatar
sa flag
you say you want to bound minimum cyclelength but your output says "max cycle length"
ph flag
Correct. I'm not sure OP is asking the right question, but so far I'm answering the one that was asked. I do plan to get the other answers too.
poncho avatar
my flag
I did a completely independent search for max cycle length (I haven't even looked at your code), and came with the same results - your code appears to be correct
ph flag
Thanks, @poncho. I guess I'm just really surprised that it's not monotonic.
poncho avatar
my flag
Not that hugely surprising; there are simpler things (such as 'what is the maximum order of a permutation over k objects') that is also not strictly monotonic...
poncho avatar
my flag
Also, I did searching in the other direction "for any width and any set of odd number of taps, what is the minimum cycle length"; for width <= 15, then there is always a cycle of size at most 2*width...
Score:2
ru flag

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.

poncho avatar
my flag
Actually, the next bit that is cycled in is the inverse of the majority of the taps - hence, I don't believe a cycle length of 1 is possible (as a string of identical shifted in bits will eventually become the majority and so shift in the opposite bit). Of course, a cycle length of 2 is quite possible, unless care was taken with tap placement...
Dominic van der Zypen avatar
br flag
Right - and sorry if the question was maybe a bit misleading... I wanted to ask how long a period one could achieve by cleverly place the taps and the starting value of $b$
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.