SSLFSR

A Sub Shifting Linear Feedback Shift Register (SSLFSR) is a modification to the standard procedure of a Linear Feedback Shift Register (LFSR). Here I will be walking through the modification by comparing and contrasting a 4 bit SSLFSR to a 4 bit LFSR.

Full

Using the taps 0 and 1, a 4 bit LFSR will progress through every possible 4 bit state except for the 0 state. Starting at the above value of 6 and shifting towards the Least Significant Bit (LSB, in the drawing above that’s the farthest right bit), the LFSR will move through the states as such: 6, 11, 5, 10, 13, 14, 15, 7, 3, 1, 8, 4, 2, 9, 12, and back to 6.  These states will always be in this order and will repeat in this cycle indefinitely.

Sub

A 4 bit SSLFSR has a few additions to it’s LFSR counterpart. First there is a simple counter that increments once for each shift the register goes through. When the counter reaches a defined interval the counter is reset back to zero and the register undergoes a subshift instead of the usual shift. A subshift uses the least significant half of the register, called the subregister, as if it were a stand alone LFSR. A 2 bit LFSR uses both of it’s bits as taps. The fact that these two bits are the same bits as the taps of the full 4 bit LFSR seem merely to be a coincidence (this relationship is not observed in registers with more bits). It’s important to note that while the register will never have the value of 0, the subregister on occasion will. If a subshift happens while the subregister is 0, no exception is made.

SSLFSR4

It’s important to note that the value of the register is solely the bits in the register where the state of the register consists of both the bits in the register as well as the value of the count. A maximal length LFSR of n bits has 2^n-1 states. A maximal length SSLFSR with n bits in the full register, with the n/2 LSB bits as the subregister, and an interval i has (2^n-1)*(i+1) states. The maximal length intervals for a 4 bit SSLFSR are 7, 11, and 13. Due to the cyclic nature of LFSRs, 22, 26, and 28 also work due to going through an entire LFSR cycle before subshifting (7+15, 11+15, 13+15). During a maximal length SSLFSR, each register value will be reached exactly i+1 times, once for each possible count value. For instance, above I start at value 6 with a count of 0. The next time a register value of 6 happens, there is a count of 3, then 7, 1, 4, 6, 2, and finally 5 before the cycle starts over back at a value of 6 with a count of 0.

Use of a non-maximal length interval produces a variety of results. A non-maximal length interval will reach some of the states before matching the starting state and repeating the cycle. Depending on what state the SSLFSR is started on, different sets of states are possible. Each set of states will be mutually exclusive and the union of all the sets will include all possible sets.

Research has not yet produced a way to determine maximal length intervals by any method other than brute force.