Electronics > Projects, Designs, and Technical Stuff

Algorithm for calculating previous states of LFSR counters ?

<< < (5/9) > >>

duak:
Could you break the 35 bit LFSR into smaller segments that would be easier to un-hash?  eg., if I wanted to count to 100 in decimal, I could use a 7-bit binary counter and convert to decimal or I could use two 4-bit BCD counters.  Here, two 18 bit LFSRs could be cascaded.  The more significant LFSR would only shift when the least significant LFSR is in state 0.  It might make more sense to use even smaller segments to speed up the un-hash conversion.

bsccara:
'duak', that would reduce the maximum number of steps (and inherently maximum count) for the same bit size, as a 36 bit LFSR would have a maximum period of 236-1, while two 18 bit ones would have a (218-1)2 maximum period. Also having the most significant LFSR being enabled through a multi-LUT zero detection would make for a lower Fmax and increased propagation delays, making timing closure much harder.

duak:
bsccara: yes, you are correct that the segmented LFSR counter scheme is not as efficient, however if my algebra is correct the maximum period is 2^36 - 2*2^18 + 1.  This is greater than 2^35 which is your minimum requirement.

If I remember correctly, LFSRs can be described using Galois Fields.  I know nothing more although I understand that the French cigarettes are named after Evariste Galois, the mathematician that developed the theory behind them.

I don't know what device(s) you are planning to use to implement the counters - FPGAs or gate arrays or ?.  I agree there will likely be another gate delay that has to be compensated for.

I think the limiting speed of the entire counter chain is determined by two factors (in addition to the clock rate of the flips-flops):

1.) detecting zero - depending on the resources of the device, this could be as simple as a wired-OR or something as complicated  as a multilevel tree.  It may be possible to pipeline the zero detect and have it spread over two clock cycles.  This could be compensated for by adjusting the preload pattern by one.  Alternately, you could also detect the state before all zeros.  However, these schemes will limit the minimum count.

2.) the second LFSR segment will need to be enabled for one clock cycle at a time - basically the 'carry' or zero detect out of the first segment.  Again, I don't know what resources your device has, but what is needed is either a 'D' flip-flop with an enable input or a gateable clock.

hamster_nz:

--- Quote from: bsccara on July 03, 2019, 02:25:36 pm ---Thank you all for your replies, particularly 'hamster_nz'. As to the why... I'm implementing a design that requires multiple counters working as timers. I need them to take a programmable number of clock cycles to reach all-zeros, which signals end-of-count. These counters are implemented on a FPGA along with a lot more logic, so I need the counters to be as fast as possible (the feedback network needs to be simple) to be able to achieve timing closure and as nimble as possible on the resources. Hence LFSRs.
I don't care about which states the counters go through as long as the number of them match the programmable setting. So I need to calculate which value to program into the counters as a starting state in order for them to go through that number of states prior to reaching all-zeros. These values will be provided from outside the FPGA, from software running on a PC.
Since each counter may run consecutively with different starting states, up to thousands of count cycles back to back, I need the calculation to be fast.
Presently I'm using brute force along with a pre-computed sparse table but the original question was if a better way existed.
'hamster_nz', I'm now looking into your reply to figure out if those pre-computed tables are feasable.

--- End quote ---

If you tell me enough to know what you are doing I might end up doing most of the work for you...  ;D

e.g. which polynomial  - Maybe I should just assume 35,33 & 9,5.

ejeffrey:
IIRC LFSR can be trivially reversed.  I think what you do is mirror the taps and then it will cycle through mirrored state registers in reverse order.  I don't exactly remember the details but it should be easy to figure out.

Navigation

[0] Message Index

[#] Next page

[*] Previous page

There was an error while thanking
Thanking...
Go to full version
Powered by SMFPacks Advanced Attachments Uploader Mod