Electronics > Projects, Designs, and Technical Stuff
Algorithm for calculating previous states of LFSR counters ?
bsccara:
'someone', my main goal going with the LFSR is not absolute maximum Fmax. I need it to be fast enough to not impede timing closure but also as light as possible on resources as I have 16 of them on the design. As it is the FPGA is already almost maxed out, particularly on LUTs...
There's also some misunderstanding going on, as the LFSR counter does not self-reset; after being enabled from other logic it steps from a loadable initial state until zero, at which time that other logic will disable it. The loading is done while the timer is reset but I wouldn't call it self-reseting, as it doesn't continue on by itself.
Nominal Animal:
--- Quote from: hamster_nz on July 05, 2019, 05:29:08 am ---- Pseudo-random binary sequences
--- End quote ---
I don't know much about the hardware (just about zero on VHDL, Verilog, or FPGAs), but I do scientific work (computational materials physics; simulators and such), and the two PRNG families I use, Mersenne Twister and Xorshift, are both based on linear feedback shift registers. Xorshift is pure XOR LFSR with optional output twizzling through multiplication that does not affect the state at all (it just provides better distribution in the output bits), and Mersenne Twister is a twisted generalized feedback shift register.
MT19937 in particular is used everywhere; it's the default PRNG in Python (random module), for example.
It might be important to note here that OP is actually interested in two different aspects of XNOR LFSRs: One is hardware implementation for a fast counter, towards an all-zero state; and another is a generic C implementation run on a desktop-type computer, to calculate the initial state needed for the hardware implementation to reach the all-zero state in a specific number of steps.
A 9-bit XNOR LFSR can have 511 distinct states (excluding the all-ones halt state). This is such a small number of states that the generic C implementation can tabulate all values according to the number of steps to the all-zero state.
A 35-bit XNOR LFSR can have 235-1 = 34,359,738,367 distinct states (again excluding the all-ones halt state). It is not feasible to tabulate all of these in a desktop program; that'd take gigabytes of memory.
My example program above shows that for any XNOR LFSR implementation, you can easily create (and shows how) a complementary XNOR LFSR, that produces the same sequence, but in the reverse direction. Since I wrote it for illustration only, it is also just about the slowest way to go about it, though; but to show much faster implementations, one should use a fixed characteristic polynomial (fixed taps and LFSR size).
My suggestion for the desktop program is to precalculate the reverse sequence once, saving suitable states and their distances from the zero state. To find the desired start state, one picks the saved state furthest from the zero state not further than the desired distance, and continue from that point using the complementary XNOR LFSR. A few tens of thousands of saved states means every distinct state can be reached with fewer than a million iterations, which should be plenty fast enough for a desktop configuration application.
My earlier post attempted to explain that if the desktop application needs to be even faster, one can find any distinct state based on their distance from the zero state, in logarithmic time. It is just much more complicated to implement, as it usually involves functions that produce the same result in fixed time as iterating the XNOR LFSR a fixed number of times would. In other words, you can implement the functionality to find a specific state for the hardware counter to reach all-zero state in a specific number of steps, even on a weak microcontroller; it just takes somewhat more mathy programming work, i.e. human programmer time and effort.
xhamster_nz above showed an alternate method, using precalculated look-up tables, to implement a fast state finder for a specific distance from the all-zero state. I found them fascinating; I have never explored that approach before. (Then again, I haven't explored skipping ahead in an LFSR before, either.) Thanks!
The Xilinx XAPP 052 from 1996 states that for a 9-bit XNOR LFSR, taps 9 and 5 (corresponding to characteristic polynomial of x9+x5+1) produces a maximal-length sequence; and taps 35 and 33 (corresponding to x35+x33+1) for 35-bit XNOR LFSR. Two taps is the minimum number of taps needed for a maximal-length XNOR LFSR, so these taps seem optimal to me for OP's use case.
Perhaps OP could confirm these are the XNOR LFSRs they're particularly interested in? If so, we could easily whip up example programs/C functions to generate the desired states for the hardware to reach the all-zero state in the specified number of steps. Otherwise, I am afraid this thread is at serious risk of derailing...
Navigation
[0] Message Index
[*] Previous page
Go to full version