Understanding Linear Feedback Shift Registers in FPGAs
adiuvoengineering.com
adiuvoengineering.com
FYI conversion between normal binary and grey code is to simply XOR successive pairs of bits.
Grey code would at most oscillate between the two values e.g. from 010 (three in Grey Code) to 110 (four in Grey Code).
Three of the combinations are used for the "authentication" portion (as used by s/w), the other combination for the "encryption" portion.
I ignored polynomials, implemented a "jump" function via bit-matrix exponentiation (unsupported by most BLAS-like libraries!), then did prime factorization via the Cunningham tables, and checked for partial periods of their inverses.
Some minor points I remember:
* there are several boolean choices in how you implement the LFSR. Left-vs-right, forward-vs-backward, xor-vs-xnor ... in particular you have a choice of "no all-zero state" or "no all-one state".
* when comparing that advancing by a given number is a period, it's much more efficient to advance both sides to minimize the number of 1 bits.
* an informative period failure is 15 = 6 + 6 + 3. Doesn't this conflict with something in the article?
* the info you need for 4096 bits is not in the Cunningham tables but is available elsewhere on the internet. But due to some of the simplification rules, some much-larger periods are easily derived from the Cunningham tables (assuming you can properly parse them, of course).
* tradition makes people produce LFSRs with very few taps but if you're doing it in software there's no real reason you have to do anything other than keep them even and use the end bits. I never collected statistics on how long it takes to guess a good one though.
I’m missing something here… what do you mean by “advance both sides?”
> an informative period failure is 15 = 6 + 6 + 3. Doesn't this conflict with something in the article?
You’re talking about, say, P(x) = x^4 + x^2 + 1, for a four-bit LFSR? This will have three nontrivial cycles, with length 6, 6, and 3. Rather than talk about this specific polynomial / specific set of taps, we can consider that the initial (non-zero) state is in one of those three cycles. There are three possibilities for the length of a cycle:
1. Maximum period 2^k-1. In this case, 15.
2. Period which is a factor of 2^k-1, such as 3.
3. Period which is not a factor of 2^k-1, such as 6.
We can distinguish these case by picking an initial state and then doing a series of checks, where we advance the LFSR by N steps, and then see if it is in the initial state again.
For exactly the LFSRs with maximum period, the LFSR will be in the initial state after advancing 2^k-1 steps, but it will not be in the initial state after advancing (2^k-1)/p steps for prime factors p of 2^k-1. In the case of a 4-bit LFSR, we check N=15, N=5, and N=3. The cycles of length 6 will fail the test because they will be in a different state after advancing 15 steps. The cycles of length 3 will fail because they will be in the same state after advancing 3 steps. The end result is that the LFSR with cycles of length 6, 6, and 3 will be rejected, no matter which cycle the initial state is in.
> tradition makes people produce LFSRs with very few taps but if you're doing it in software there's no real reason you have to do anything other than keep them even and use the end bits.
The reason I was looking at this in the first place was out of a kind of retrocomputing interest, and using something like 0x100001b as your polynomial for a 24-bit LFSR can make the implementation slightly shorter / faster, on some older CPUs and with memory constraints.
It was easy to find a lot of handwaving and code / numbers copied from place to place, and I wanted to know how to generate the polynomials / pick the taps in the first place. The program I wrote just goes through the polynomials in lexicographic order, so it’s not actually trying to pick the fewest number of taps, but it will prefer sets of taps where the taps are all clustered on one side.
Instead of checking `state == advance(state, 2*32-1)`, which takes 32 multiplies, it's cheaper to do `advance(state, 1) == advance(state, 2*32), which only takes 2 multiplies (they both still take 32 squares unless you cache those). And actually the special case of 1 didn't require constructing the matrix at all, allowing a cheaper direct computation.
> The cycles of length 6 will fail the test because they will be in a different state after advancing 15 steps.
Okay, now this rings a bell. It has been quite a while since I actually played with this all.
The only other thing that was surprising was that you wrote out your taps including both ends (thus they look to have an odd rather than even), but that's purely a matter of convention.
Ah! That makes sense. But for N=2^32-1, there are also checks for N/3, N/5, N/17, N/257, and N/65537.
This only fails to decrease the needed work for the N/3 and N/5 cases here, which form small regular patterns. For larger regular patterns, or for irregular patterns (2^odd-1), chances are that there will be at least some simplification (unless the pattern is mostly zeros in which case it isn't needed anyway).
Iiuc what you're describing is using different sets of factors, which would guarantee low correlation, if differing spectra.
A minor point, but they are called Gold codes -- after Robert Gold, who developed the technique in the 60s.