Properties of an LFSR
To properly understand an SSLFSR, you must understand some basic properties of the LFSR. A Linear Feedback Shift Register is a set of bits whose current state determines the next state. This is achieved by XORing particular bits, called taps, of the register together and shifting the result into the register. When proper taps are used, the register will result in every possible state except for the zero state (the state in which all bits in the register are zeros), thus the value of the register is zero. A register of value zero, after XORing the taps, will always result in a zero bit being shifted in, resulting in a register that is still of value 0. A non-zero value will never shift to become a zero value register due to the position of the taps. Every shift happens the same way in an LFSR. The tap positions (i.e. relative to the least significant bit or the most significant bit) determine which way the register shifts. For a register of n bits and knowing that it can never hold the zero state, the register will shift through2^n-1
states. At that point, the register will continue to shift through the same states in the same order repeating forever. Different size registers will result in a different order of states as well as different raw states e.g. a 4 bit register can never have the state of 20, yet any register larger than 4 bits can. The order of states for a particular register size are circular in that when the register holds the last state, another shift will begin the cycle over again. With this circular nature in mind, it’s worth noting that the starting state is not relevant to any relevant properties of an LFSR.
At its core, a SubShifting Linear Feedback Shift Register is an LFSR with an additional integer to help represent the full state, and this additional integer is used to modify the clocking cycle. SSLFSRs use the same taps as LFSRs but the state is manipulated in one of two ways depending on the integer that is external to the register, called the counter. Those two ways are shifts and subshifts. A shift is exactly as described above for an LFSR: the taps of the full register are XORed together and the resulting value is shifted into the register. Subshifting is slightly different. Only the second half of the register (the half that the register is shifted towards, e.g. the least significant bits) is shifted using proper taps for the sub-register’s size. The sub-register is also shifted in the same direction as the full register e.g. towards the least significant bit. The subshift still takes place even if the subshift register contains the value of 0. This will, as expected, result in the same state as it was before the subshift. A subshift does not affect the other half of the register in any way.
When to shift and when to subshift is decided by the additional integer, the counter, which counts to an interval. This value initially starts at 0 and as the register performs shifts, this counter is incremented until reaching a limit, i. When the value reaches i, then the next time the register would normally shift, it subshifts instead and the counter value is returned to 0. This continually repeats to modify the normal LFSR cycle by subshifting at constant intervals. Because of the fact it’s only used to space the difference between two subshifts, the interval can be started at i and counted down to zero and, upon reaching zero, be reset back to i to achieve the same register values and will maintain all the properties that separate an SSLFSR from an LFSR. Note the usage of state and value. The value of an SSLFSR is the register while the state is the combination of the value and the interval.
These changes alter many characteristics to how a non-subshifting, normal LFSR works. First, each state is more than just the value of the register; it also contains the value of the counter. For example if the register value is 8 and the counter is 3, that state is unique from any other time the register value is 8 such as when the counter is at 2 or 4. An SSLFSR has a different number of states than an LFSR. For a register of n bits, knowing that the value still cannot hold 0, and with the counter counting up to the interval i the register will shift through(2^n-1)*(i+1)
An SSLFSR does not work for all intervals i. Different size registers have different intervals that produce these optimal results. A single register size does have multiple working intervals, the number of which is seemingly proportional to the size of the register. Intervals larger than the max size of the register imply that a full cycle of LFSR states happen before another subshift. For an 8 bit SSLFSR, 11 is a working interval, therefore so is any i in n(2^8-1)+11 such as 266 for n=1 and 521 for n=2. Intervals producing optimal results are deemed “working intervals” or “full length intervals.” Just like LFSRs, the starting state is not relevant to any of these properties of SSLFSRs when using a full length interval. It is important to note that, for a full length interval, every value is achieved as a result of a subshift once and only once before the cycle is restarted, and every value is achieved exactly i times as a result of a shift, therefore every value is achieved exactly i + 1 times before the loop starts over. As in an LFSR, in one full cycle, each state only happens once. Although the register’s value might repeat, the counter will be different each time until the cycle repeats. Also like an LFSR, once an SSLFSR completes it’s cycle, it will restart the cycle and continue forever repeating the cycle specific for it’s size and interval. Different intervals will result in a different order of states, as well as a different number of possible states. Working intervals seem randomly distributed. Working intervals for one size of SSLFSRs do not inherently work in SSLFSRs of other sizes. There is currently no way to predict working intervals that are smaller than the max size of the register. Working intervals have only been found through trial and error.
When a non-working interval is used with an SSLFSR, different properties are exhibited. The most notable property is that not every state will be achieved by shifting and subshifting. Dependent on the starting state, an SSLFSR with a non full length interval will produce different subsets of all the possible states for that interval. The union of all subsets of states includes every achievable state once and only once, showing that the subsets are mutually exclusive. The number of sets, the sizes of the sets, and the contents of the sets do not seem to follow a pattern.
Changing intervals throughout the life cycle of an SSLFSR has not been tested. Registers with an odd size number of bits have not been testing, although sub-registers can be odd sized. Sub-registers that are not exactly half the size of the full register have not been tested. Sub-registers at any location other than the second half of the full register (usually the side containing the Least Significant Bit) have not been tested. Sub-registers shifting the opposite direction of the full register have not been tested. Combinations of LFSR-2 and LFSR-4 (when available for the register size) shifting and subshifting styles were briefly looked into and showed that any combination will have a set of working intervals, but will not produce the same set of working intervals. Galois SSLFSRs have not been tested.