One question that I’ve often pondered is how to generate non-maximal length LFSRs or NLFSRs. I decided to see what could be done with an 8b shift register that took 3 taps, and performed a logic operation to generate the shift-in value. The results were interesting, though not necessarily immediately useful.A quick python program was used to generate these results. The python code wasn’t very heavily optimized. For the 3 tap, 8b case the run time was on the order of 1 minute. The same code for a 4 tap, 8b case would take several hours to run.
Interestingly, it turns out that a maximal length sequence can be generated using only 3 taps if the feedback relationship is not a linear function. There were eight such tap-function-init groupings. The feedback expressions for these were (where AB is A and B, and A+B is A or B):
- A=b7, B = b6, C =b2. S = !A!B!C+BC+AC. init = 1
- A=b7, B = b4, C =b3. S = !A!B!C+BC+AC. init = 1
- A=b7, B = b4, C =b0. S = !A!B!C+BC+AC. init = 1
- A=b7, B = b3, C =b2. S = !A!B!C+BC+AC. init = 1
- A=b7, B = b6, C =b2. S = AB!C+!BC+!AC. init = 0
- A=b7, B = b4, C =b0. S = AB!C+!BC+!AC. init = 0
- A=b7, B = b4, C =b3. S = AB!C+!BC+!AC. init = 0
- A=b7, B = b3, C =b2. S = AB!C+!BC+!AC. init = 0
None of the above are very elegant. For an FPGA, it would just be a LUT, so it doesn’t matter too much. At the same time, there probably isn’t a compelling reason to use one of these over a 4-tap LFSR which can also generate the same length sequence.
Using just 3 taps, all sequences of lengths from 1 to 58 can be generated. At 59 and above, there are several lengths that couldn’t be generated. In total, 143 of 256 possible lengths were not attained. The full 256 element sequence was not generated for any of these 3 input functions.
Most of the literature I’ve found on this topic relates to either angle sensors, where multiples of 360 are the goal, and cryptography. It seems there is a method for finding the smallest (in registers) LFSR for a given cycle length. A nonlinear mapping might allow a smaller number of registers. I was able to modify the script to find several specific sequence lengths.