8 Bit Random Numbers

No, I'm saying that if you modify an LFSR so that its input is no longer an N-input XOR of (some of) its outputs, it's no longer an LFSR.

There are circuits which don't have the lockup state, but an LFSR isn't one of them.

Yum Yum, the Asm code is making me drool! :)

That's real power man!

The output of the 8 bit LFSR that Fields did is exactly the same as the standard version using 4 taps. The only addition is the zero state appears between the values hex 80 and 01. The new sequence goes

Another solution (with a processor) might be to use a lookup table where the desired values are read in order. And if you did that, why not just add the extra forbidden zero into the table? And if you did add it, where should it be located?

Seems logical to me to add the forbidden zero state where it might normally occur, which is right after the 10000000 state and just before the 00000001 state, so the sequence is 10000000, 00000000,

-Bill

Oh, Jeebus. My entire point, my only point, is that what John Fields posted ISN'T AN LFSR.

This isn't a value judgement about the merits of the circuit; it's simply a matter of not misusing terminology.

Right. Which makes it not an LFSR. The word "linear" actually means something in this context, and inherent in that meaning is that there is a "zero" state which is invariant, i.e. f(0) = 0. IOW, a "lockup" state.

Note that the "zero" state doesn't have to be the one with all bits zero. If you use XNOR gates, the all-ones state is the "zero" state.

FWIW, the hang state is FFFFF4C4:

d0 = 0xFFFFF4C4 d0>>1 = 0x7FFFFA62 (d0>>1) ^ 0x80000EA6 = 0x7FFFFA62 ^ 0x80000EA6 = 0xFFFFF4C4

Derivation:

(x>>1)^0x80000EA6 = x => x^(x>>1) = 0x80000EA6

In binary:

x^(x>>1)= 10000000000000000000111010100110

(x >> 1) will always have bit 31 clear, 0x80000EA6 has bit 31 set, so x must have bit 31 set:

=> x = 1............................... => x>>1 = 01..............................

So x>>1 has bit 30 set, 0x80000EA6 has bit 30 clear, so x must have bit 30 set:

=> x = 11.............................. => x>>1 = 011.............................

And so on.

What part of

"A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. The only linear functions of single bits are xor and inverse-xor..."

are you having trouble understanding?

What Fields posted was *NOT* an 8 bit LFSR. It was *NOT* XOR based. (BTW, why does Fields keep calling XOR "EXOR?" Does he have some sort of problem using standard terminology?) Simply saying "you are both wrong" does not change reality. If the two of you would simply stop calling whatever his circuit is a "LFSR" or a "XOR Based PRNG", then everyone here could agree. There is nothing wrong with his design. You are simply calling it by the wrong name. Just because someone is an engineer, that doesn't mean that he has to be stubborn and refuse to admit any error. The world will not end if you admit to using the wrong terminology.

BTW, for most applications a standard Galois LFSR is superior to what Fields posted. When implemented using logic gates, The XOR gates are run in parallel rather than in serial, reducing propagation delay and allowing for faster cycling. When implemented in software, it is is more efficient because the XOR can computed a word at a time. Code it or breadboard it and see.

I'm having trouble with the linear part. Linear suggests to me an equal amount of "1s" and "0s" over a long period, which should be 1024 of each for an 8 bit counter. The LFSR without Fields mod produces

Using Fields approach produces equal amounts of "1" and "0" or 1024 of each, which seems closer to linear.

What am I missing?

-Bill

Yes, I know about that, but haven't figured out the 8 bit number to xor with the random register to get the desired result.

Maybe you know what it is?

-Bill

I'm having trouble with the linear part. From what I understand a linear output would suggest an equal number of ones and zeros over a long period of time, or about 1024 of each for an 8 bit register during each complete cycle. This is the case for Fields circuit using the extra 7 input nor, and extra xor.

The standard LFSR with the missing "0" state yields 1024 "ones" but only 1016 "zeros" for each complete cycle, since 8 zeros are left out.

So, which approach would you say is more linear?

Yes, I know about that, but haven't figured out the exact 8 bit word to xor against the 8 bit random word in a parallel fashion to get the desired result. Maybe you know what it is?

-Bill

Thanks. After consideration, I was going to try to find if it actually had a hang state last night, but Zeitgeist has Chimay on tap.

Incidentally, there's a typo in my code. The first instruction should be LSR.L, a longword rotate.

This sequence obviously includes both the all 1's and all 0's states, interestingly only 32 clocks apart.

John

Yes, I know how these people operate. They can't appreciate anything new and unique that conflicts with existing ideas. Some won't even take the time to look over new stuff, because they already know it won't work. They can't see the beauty in something simple and original that negates old ideas.

-Bill

The mathematical notion of linearity implies that the transformation has a "zero" element such that f(0)=0.

If all you want is a generator of pseudo-random bits, none of this matters. It may even be undesirable, as it effectively mandates a lock-up state.

For your original sequence of 3,4,5,7, use 0xB8 or 0x1D, depending upon the shift direction. The following C code generates the same bit sequence using both Fibonacci and Galois implementations.

Note that the two versions generate the same bit sequences, but the sequence of 8-bit states differs.

#include

typedef unsigned char byte;

byte f_taps = 0x1D; /* 0001 1101 */ byte g_taps = 0xB8; /* 1011 1000 */

byte xor(byte x) { x = (x & 0x0F) ^ (x >> 4); x = (x & 0x03) ^ (x >> 2); x = (x & 0x01) ^ (x >> 1); return x; }

byte f(byte *x) { byte t = xor(*x & f_taps); *x >>= 1; *x |= t >= 1; *x ^= k; return t; }

int main(void) { byte x = 1, y = 1; int i;

for (i = 0; i < 0x100; i++) { byte tx = f(&x); byte ty = g(&y); printf("%d %d\\n", tx, ty); }

return 0; }

I strongly disagree. I certainly do appreciate new and unique ideas. It's calling the new and unique idea by the exact same name as an existing tried and true idea that I object to. Such lack of rigor leads to things like JF writing "you are wrong" concerning a correct statement about a PRNG that uses only XOR feedback (AKA a LFSR) and pointing to an alleged counterexample that uses other (nonlinear) logic elements in the feedback.

His decision to resort to personal attacks rather that arguing his case on the merits is suggestive that he himself knows that his "you are both wrong" was and still is incorrect.

His idea has a lot going for it (no lockup state, balanced 1s and 0s...) and at least one disadvantage (slower than a Galois LFSR) and is a worthy addition to any list of easy-to-impiment PRNGs as long as it is properly classified rather than misnamed. I certainly have not seen anyone here claim that it won't work or refuse to look at it. I don't know where you got that.

More info on the existing "tried and true" approach:

There is an extensive literature on LFSR's, dating back decades, with lots of formal theory. There's plenty of stuff on the web.

John