Sorry I didn't respond to you right away RB. Been busy-ish, and this thread is a bit technical to just pop in and drop a few lines. I wrote quite a lot here for you, but feel free to skip all you want. No obligation to read any of it.
I don't think you would save much RAM trying to manually handle all the top bits and at first glance it looks like a coding nightmare.
That's pretty much exactly what I figured. I just wanted to point out the possibility. But yeah, not worth it really.
[Your idea is] interesting and would be a cool experiment.
Sure.
Though we may need to choose a different platform if we want to really test this. It's hard to get data out of the sim, at least it is for me. I have to put markers in my source, output the trace to a text file, then process that file with a batch script to extract useful data. It's fairly tedious.
Really we're entering the realm of statistics anyway, not PIC programming. The firmware realization should probably come after the math is down pat. But such things would be out of my sphere of knowledge. This probably needs the attention of some real "mathmagicians".
Generally modifying the data within a LFSR is considered bad form as the LFSR is a single maximal length repeating pattern, so to change any bit when it is working just skips it to a different part of the pattern, which in most cases gives a shortened repeat.
Hummm... I don't really know myself, but the way I figure it is as follows...
In all their pattern complexity and glory, LFSRs are really just an odd form of binary counter[SUP]
[1][/SUP]. So, we should be able to statistically simplify them to a basic nBit counter, as they both cover the same space in the same number of iterations. LFSRs just use a different pattern to get to the same destination. We will conveniently overlook the all zero state, which should only have a very small bias on the statistics of all this (I hope).
Now, analyzing a standard counter we find that clearing any one bit that was previously set will always jump back in the sequence, and setting any bit that was previously clear jumps forward. It follows from this that if we toggle any randomly chosen bit, at any random time, we would have a 50/50 chance of going back or forward, since such random choice should have a 50/50 chance of hitting a 1 or 0, in accordance with the expected value theory
[SUP][2][/SUP].
Truthfully, an LFSR isn't exactly the same as a simple counter in the above regard. For example you could see an instance where clearing a bit would actually go forward, or setting one ends up sending you back, the opposite behavior of a typical counter. But in reality this doesn't actually matter, because the distribution of these "opposite behaving instances" should also be 50/50, canceling any bias out.
So because the expected value for a single binary bit in an LFSR is 0.5=1/2=50/50, and an LFSR should more or less behave just like an ordinary counter when any randomly chosen bit is flipped. It follows that any random LFSR bit being toggled really should also statistically have 50/50 chances of either skipping ahead, *OR* skipping back, just like a counter does.
Q: OK, assuming you are correct, what does this really mean?
A: The biggest advantages of LFSRs is that they are reasonably fast, and they cover maximum space for a given amount of memory. The biggest problem of LFSRs, as with any maximal length counters with simple feedback system, is that they are 100% deterministic. For example, the Berlekamp–Massey algorithm can "crack" any single LFSR working with just it's output stream
[SUP][3][/SUP]. LFSRs however have the distinct advantage over standard counters of being quite
statistically random, and that is just the ticket out of their easy to define deterministic nature. Using one LFSR to change another, whether directly or just affecting it's output stream, breaks up patterns. So, the above theory may or may not short change the space that a given LFSR would have covered if left alone, like you are more or less suggesting. But even so it still doesn't do it in a deterministic way. It may short change it a whole lot for one or two iterations, then another modification does something else altogether, "un-short changing it's self" so to speak.
Another way to examine the problem, one that is significantly easier to explain, is to point out that the transition from all 1s to the next state is in fact a perfectly valid and acceptable number that one may find in a truly random sequence. It has the same exact weight as any other LFSR transition you could come across in a truly random sequence in fact. And even before you see it like this, you may realize that an LFSR is a loop with no real beginning or end. Thus there is really nothing to get short changed as debated. Yes, if you alter bits in an LFSR outside of it's feedback function, you will be making big leaps from one point in the circle to another that wouldn't have happened otherwise. But there is absolutely no way for an attacker to know, when you are doing this, where you started, where you will end up, how big the jump was, or how big it will be. This remains true even if the jump brings you really close to or over the all 1s boundary. Mashing bits of multiple LFSRs with each other before using them intrinsically obscures any particular transitions that would scream LFSR sequence. Which is generally how you are going to use LFSRs anyway.
So, bad form or not, I still want to believe that using any well designed "exo-LFSR feedback function" to change an LFSRs current state can generate good entropy. And I feel another LFSR is a decent way to do this. But feel perfectly comfortable to object with a better explanation of your own point of view, because I may be totally wrong. It wouldn't be the first time the other shoe has dropped on one of my crazy ideas.
If you want to try that I would suggest XORing a bit from LFSR A with LFSR B, that gives better entropy than just eliminating and replacing a bit. Also it might be good to only do that process infrequently, not do it every bit. That gives time to build more entropy in the individual LFSRs before they "mash" a bit and affect each other, giving longer and more complex patterns in their interaction and disallowing short pattern locks. Building on that, if you can "randomly" select a time to mash the bits that is generally better than doing it at a fixed time, provided there is little predictability to when you randomly do the event.
You are pretty much describing the
shrinking generator. It's a little different because one ANDs the output of LFSR A with the output of LFSR B, rather than XOR. But the exact logic function doesn't really matter I don't think, two LFSRs properly interacting generate entropy. The second part of what your saying is describing the
alternating step generator, which is the other major LFSR based PRNG.
There is nothing really wrong with either of these implementations. The only thing is they are well known and relatively inflexible. Also note that if implemented wrong they both will fail miserably, but the same is true for just about anything. That being said, the other side of the coin is that "custom" and "secret" PRNG algos tend to have more flaws than what has been well established. That's why the general conciseness is keep such things open. Then again, if you know what you're doing, and you thoroughly check your work, you could have your cake and eat it too. So the reward o'ta be there.
And obviously, the old technique of generating the output bit by XORing a number of non-polynomial bits from different LFSRs will give a much better output than just outputting the last bit from the last LFSR in the line.
This is another technique mentioned in the Wiki article for solving the deterministic problem of LFSRs. It doesn't go into detail though and there are no references to go by. But it seems pretty strait forward. So, not much to say about this really.
It's fun seeing someone making RNGs in software and hopefully someone else might speak up who has experience. My understanding is pretty rudimentary and I'm mainly a brute force kind of guy, ie big buffers and lots of data mashing based on unrelated things. LFSRs are more mathematical in nature and (to me) are best used as a single part of a RNG process, not form the entire process.
It's fun making them... when I can get the code to behave properly.
It should be obvious that my understanding is also fairly rudimentary. Though I like to use the less harsh word "intuitive". This highlights the contrast to some kind of hard science and mathematics without implying one has absolutely no idea of what they are doing. And although LFSRs are quite mathematical, I do think they can be used with a intuitive mindset well enough to be the core of a good PRNG, though I can't exactly prove this. And of course, even if LFSRs are not 100% usable this way by themselves, there will always remain the opportunity to add other methods to supplement their weaknesses. Your brute force methods wouldn't be bad for this.
Anyway, that's all I got right now. Thanks for your help RB, I couldn't have done it with you. Honestly, you solved my original reason for creating this thread, so the case is pretty much closed as far as I am concerned. I'll still probably get back on this sooner or later, just maybe not in this thread. Now that I have Galois LFSRs, I need to play with them and see what I can come up with.