I located a program to generate 255 pseudo-random numbers in some fixed sequence which repeats after 255 counts. 4 bits of the random register (bits 3,4,5,7) are used as feedback to determine the next "1" or "0" to clock into the shift register. Bits 4 and 5 are xored, and that result is xored with bit 3. The result of that is xored with the last bit 7 to yield a "1" or "0" to shift into the register. This operation produces 255 non-repeating numbers in some scrambled order.

The question is, can this operation be done using fewer bits. Is it possible to produce 255 pseudo-random numbers from an 8 bit shift register using less than 4 bits as feedback?

No. For a reference on this sort of thing, try to find a copy of "Error Correcting Codes," Second Edition, Peterson and Weldon, MIT Press, Cambridge, MA, 1972, Appendix C. Among other things, it lists all 8-bit maximal codes. None is simpler than 4 feedback bits. (Refer only to the "primitive" cases with labels E, F, G, or H as noted on page 473. These are all of the "maximal" cases.)

Also, if you'd like to fool around with this sort of thing in a convenient way, consider downloading my Windows program called Pseudo at

These maximum-length pseudo-random binary sequences have been worked out for shift registers of various lengths. 2-bit feedback is common, but it only works on certain lengths. You can use bits 1 and 7 (1-based numbering) of a 7-bit register to get 128 "random" values, but if you are doing this with real hardware shift registers, just add a few more to get up to longer sequences.

If you are using a processor of some kind, it's natural to use the native register length. With a

16-bit register, the best you can do is a 15-bit generator (bits 1 and 15, for example). For a
32-bit register, you can get a 31-bit generator using bits 7 and 31.

But with a processor there is a much better way to do this same algorithm than actually shifting bits. This requires thinking about it differently. Instead of shifting a register value horizontally, use a list of values. Each value in the list corresponds to one bit-position in the shift register. So to XOR the 1st and 31st "bits" you read the 1st value from the list and XOR it with the 31st value from the list, and use that to form the new 1st value. Essentially, you now have a whole series of shift registers, operating vertically on the list.

If you have an 8-bit processor, you can still use a 31-stage shift register simply by using 31 memory values. In fact, there is nothing to stop you from using MANY more stages, costing only the added memory and no added time to process. (Compare that to shifting long chains of registers horizontally... awkward, since they are always even in length and the desired sequences are always odd.)

You get a full 8-bit value on each turn of the crank, and it is actually less predictable: The old-fashioned "horizontal" register values have the same bit pattern as the prior value, just shifted over by one with one new bit. The "vertical" memory method gives you totally different bit patterns each time. (But you do need to initialize carefully, so that no column contains all zeros, for example.)

Best regards,

Bob Masta DAQARTA v4.51 Data AcQuisition And Real-Time Analysis

formatting link

Scope, Spectrum, Spectrogram, Sound Level Meter FREE Signal Generator Science with your sound card!

IIRC, you can eliminate the zero lockup state, but only by introducing some other state that locks up. What you cannot do is make an XOR-based PRNG that pseudorandomly cycles through all values from 0 to 255.

If you are using a PC or microcontroller rather than logic gates, the RC4/ARCFOUR algorithm is a good alternative to an XOR-based PRNG, is far, far more difficult to predict, and does not cycle unless you are willing to wait many millions of years.

Well, we could argue forever about what constitutes "[E]XOR-based", but it's not an LFSR, and I thought it was clear that's what "nospam" was referring to by "XOR-based PRNG".

I don't think that anone would contest that there exist *other* circuits which will cycle through all 256 8-bit values, or at least don't have the lock-up state.

That is what I was referring to by "XOR-based PRNG." I am willing to stretch the definition of LFSR PRNG to include inverters (NOT), but I am not willing to call something a LFSR if it adds any OR gates. As it says in Wikipedia

formatting link

"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..."

IIRC, the NOT gates can move the lockup state to another bit pattern (which is useful if the underlying technology powers up with all bits set to zero, saving a special additional circuit to initialize the LFSR), but cannot eliminate the lockup state.

The Wikipedia article also has a good discussion of propagation time in Galois LFSRs vs. Fibonacci LFSRs that may lead to a faster running PRNG than the John Fields FSR (FSR, not LFSR).

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here.
All logos and trade names are the property of their respective owners.