8 Bit Random Numbers

My references all suggest 4 taps for an 8-bit reg, although they can be different taps.

Many longer registers generate maximal-length sequences with just one xor gate.

John

No, there isn't an 8-bit maximal linear feedback shift register with 2 taps.

Complete lists of maximal LFSRs from 3 to 32 bits can be found at:

Wikipedia page:

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

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

Xilinx has a pretty good LFSR application note (XAPP052) on maximum length LFSRs with a tap table for LFSR lengths from 3 to 168 bits.

--
If you decode the state just before lockup and exor that with the exor
of the taps, the register is forced into the now permitted \'lockup\'

Thanks, I found a tap list here that shows only 2 taps (15,14) for a

15 bit register, or a sequence of about 32767.

I guess there is more than one way to do it.

-Bill

On Wed, 28 Jan 2009 11:52:47 -0600, John Fields wrote:

. . . Just for fun...

8 bit LFSR with no lockup state and output DAC:

Version 4 SHEET 1 1340 964 WIRE 976 -496 -320 -496 WIRE -384 -480 -432 -480 WIRE -432 -448 -432 -480 WIRE -432 -448 -480 -448 WIRE 464 -432 -320 -432 WIRE -544 -400 -880 -400 WIRE -432 -384 -480 -384 WIRE 224 -368 -320 -368 WIRE -432 -352 -432 -384 WIRE -384 -352 -432 -352 WIRE -256 -304 -320 -304 WIRE 704 -224 96 -224 WIRE -880 -192 -880 -400 WIRE -880 -192 -928 -192 WIRE 464 -192 464 -432 WIRE 464 -192 96 -192 WIRE 32 -176 -784 -176 WIRE -16 -160 -784 -160 WIRE 224 -160 224 -368 WIRE 224 -160 96 -160 WIRE -992 -144 -1056 -144 WIRE -256 -144 -256 -304 WIRE -256 -144 -784 -144 WIRE -848 -128 -928 -128 WIRE -496 -128 -784 -128 WIRE -736 -112 -784 -112 WIRE 1104 64 -1216 64 WIRE -864 112 -1136 112 WIRE -624 112 -864 112 WIRE -384 112 -624 112 WIRE -144 112 -384 112 WIRE 96 112 -144 112 WIRE 336 112 96 112 WIRE 576 112 336 112 WIRE 816 112 576 112 WIRE -864 160 -864 112 WIRE -624 160 -624 112 WIRE -384 160 -384 112 WIRE -144 160 -144 112 WIRE 96 160 96 112 WIRE 336 160 336 112 WIRE 576 160 576 112 WIRE 816 160 816 112 WIRE -1056 208 -1056 -144 WIRE -944 208 -1056 208 WIRE -752 208 -784 208 WIRE -736 208 -736 -112 WIRE -736 208 -752 208 WIRE -704 208 -736 208 WIRE -512 208 -544 208 WIRE -496 208 -496 -128 WIRE -496 208 -512 208 WIRE -464 208 -496 208 WIRE -272 208 -304 208 WIRE -256 208 -256 -144 WIRE -256 208 -272 208 WIRE -224 208 -256 208 WIRE -32 208 -64 208 WIRE -16 208 -16 -160 WIRE -16 208 -32 208 WIRE 16 208 -16 208 WIRE 208 208 176 208 WIRE 224 208 224 -160 WIRE 224 208 208 208 WIRE 256 208 224 208 WIRE 448 208 416 208 WIRE 464 208 464 -192 WIRE 464 208 448 208 WIRE 496 208 464 208 WIRE 688 208 656 208 WIRE 704 208 704 -224 WIRE 704 208 688 208 WIRE 736 208 704 208 WIRE 928 208 896 208 WIRE 976 208 976 -496 WIRE 976 208 928 208 WIRE -976 256 -1056 256 WIRE -944 256 -976 256 WIRE -704 256 -736 256 WIRE -464 256 -496 256 WIRE -224 256 -256 256 WIRE 16 256 -16 256 WIRE 256 256 224 256 WIRE 496 256 464 256 WIRE 736 256 704 256 WIRE -976 352 -976 256 WIRE -736 352 -736 256 WIRE -736 352 -976 352 WIRE -496 352 -496 256 WIRE -496 352 -736 352 WIRE -256 352 -256 256 WIRE -256 352 -496 352 WIRE -16 352 -16 256 WIRE -16 352 -256 352 WIRE 224 352 224 256 WIRE 224 352 -16 352 WIRE 464 352 464 256 WIRE 464 352 224 352 WIRE 704 352 704 256 WIRE 704 352 464 352 WIRE -864 384 -864 304 WIRE -624 384 -624 304 WIRE -624 384 -864 384 WIRE -384 384 -384 304 WIRE -384 384 -624 384 WIRE -144 384 -144 304 WIRE -144 384 -384 384 WIRE 96 384 96 304 WIRE 96 384 -144 384 WIRE 336 384 336 304 WIRE 336 384 96 384 WIRE 576 384 576 304 WIRE 576 384 336 384 WIRE 816 384 816 304 WIRE 816 384 576 384 WIRE 1104 384 1104 64 WIRE 1104 384 816 384 WIRE -704 464 -832 464 WIRE -464 464 -704 464 WIRE -224 464 -464 464 WIRE 16 464 -224 464 WIRE 256 464 16 464 WIRE 496 464 256 464 WIRE 736 464 496 464 WIRE 976 464 736 464 WIRE -704 496 -704 464 WIRE -464 496 -464 464 WIRE -224 496 -224 464 WIRE 16 496 16 464 WIRE 256 496 256 464 WIRE 496 496 496 464 WIRE 736 496 736 464 WIRE 976 496 976 464 WIRE -1216 624 -1216 64 WIRE -1056 624 -1056 256 WIRE -832 624 -832 464 WIRE -704 624 -704 576 WIRE -464 624 -464 576 WIRE -224 624 -224 576 WIRE 16 624 16 576 WIRE 256 624 256 576 WIRE 496 624 496 576 WIRE 736 624 736 576 WIRE 976 624 976 576 WIRE -752 640 -752 208 WIRE -512 640 -512 208 WIRE -272 640 -272 208 WIRE -32 640 -32 208 WIRE 208 640 208 208 WIRE 448 640 448 208 WIRE 688 640 688 208 WIRE 928 640 928 208 WIRE -1216 768 -1216 704 WIRE -1136 768 -1136 112 WIRE -1136 768 -1216 768 WIRE -1056 768 -1056 704 WIRE -1056 768 -1136 768 WIRE -832 768 -832 704 WIRE -832 768 -1056 768 WIRE -752 768 -752 688 WIRE -752 768 -832 768 WIRE -512 768 -512 688 WIRE -512 768 -752 768 WIRE -272 768 -272 688 WIRE -272 768 -512 768 WIRE -32 768 -32 688 WIRE -32 768 -272 768 WIRE 208 768 208 688 WIRE 208 768 -32 768 WIRE 448 768 448 688 WIRE 448 768 208 768 WIRE 688 768 688 688 WIRE 688 768 448 768 WIRE 816 768 688 768 WIRE 928 768 928 688 WIRE 928 768 816 768 WIRE 816 816 816 768 WIRE 928 816 928 768 WIRE -704 928 -704 704 WIRE -464 928 -464 704 WIRE -464 928 -704 928 WIRE -224 928 -224 704 WIRE -224 928 -464 928 WIRE 16 928 16 704 WIRE 16 928 -224 928 WIRE 256 928 256 704 WIRE 256 928 16 928 WIRE 496 928 496 704 WIRE 496 928 256 928 WIRE 736 928 736 704 WIRE 736 928 496 928 WIRE 816 928 816 880 WIRE 816 928 736 928 WIRE 928 928 928 896 WIRE 928 928 816 928 WIRE 976 928 976 704 WIRE 976 928 928 928 WIRE -1216 944 -1216 768 FLAG -1216 944 0 SYMBOL voltage -1056 608 R0 WINDOW 3 24 104 Invisible 0 WINDOW 123 0 0 Left 0 WINDOW 39 0 0 Left 0 SYMATTR Value PULSE(0 5 0 1e-6 1e-6 .0005 .001) SYMATTR InstName V1 SYMBOL Digital\\\\dflop -864 160 R0 SYMATTR InstName A5 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\xor -976 -96 R180 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A14 SYMBOL Digital\\\\dflop -624 160 R0 SYMATTR InstName A1 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\dflop -384 160 R0 SYMATTR InstName A2 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\dflop -144 160 R0 SYMATTR InstName A3 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\dflop 96 160 R0 SYMATTR InstName A6 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\dflop 336 160 R0 SYMATTR InstName A7 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\dflop 576 160 R0 SYMATTR InstName A8 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\dflop 816 160 R0 SYMATTR InstName A9 SYMATTR SpiceLine Td=10n tripdt=10n trise=30n vhigh=5 SYMBOL Digital\\\\xor -528 -352 R180 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A4 SYMBOL Digital\\\\xor -368 -528 M0 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A10 SYMBOL Digital\\\\xor -368 -400 M0 WINDOW 3 16 112 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A11 SYMBOL Digital\\\\or 64 -128 R180 WINDOW 3 -8 128 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A12 SYMBOL Digital\\\\or -816 -208 M0 WINDOW 3 -8 128 Invisible 0 SYMATTR Value trise 10e-9 vhigh 5v SYMATTR InstName A13 SYMBOL voltage -1216 608 R0 WINDOW 123 0 0 Left 0 WINDOW 39 0 0 Left 0 WINDOW 3 24 104 Invisible 0 SYMATTR Value PULSE(5 0 1e-6) SYMATTR InstName V2 SYMBOL sw 976 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S1 SYMBOL res 960 480 R0 SYMATTR InstName R1 SYMATTR Value 1000 SYMBOL sw 736 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S2 SYMBOL res 720 480 R0 SYMATTR InstName R2 SYMATTR Value 2000 SYMBOL sw 496 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S3 SYMBOL res 480 480 R0 SYMATTR InstName R3 SYMATTR Value 4000 SYMBOL sw 256 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S4 SYMBOL res 240 480 R0 SYMATTR InstName R4 SYMATTR Value 8000 SYMBOL sw 16 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S5 SYMBOL res 0 480 R0 SYMATTR InstName R5 SYMATTR Value 16k SYMBOL sw -224 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S6 SYMBOL res -240 480 R0 SYMATTR InstName R6 SYMATTR Value 32k SYMBOL sw -464 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S7 SYMBOL res -480 480 R0 SYMATTR InstName R7 SYMATTR Value 64k SYMBOL sw -704 720 M180 WINDOW 0 32 15 Left 0 WINDOW 3 32 44 Left 0 SYMATTR InstName S8 SYMBOL res -720 480 R0 SYMATTR InstName R8 SYMATTR Value 128k SYMBOL voltage -832 608 R0 WINDOW 123 0 0 Left 0 WINDOW 39 0 0 Left 0 WINDOW 3 24 104 Invisible 0 SYMATTR Value PULSE(0 13.115 1e-6) SYMATTR InstName V3 SYMBOL res 944 912 R180 WINDOW 0 36 76 Left 0 WINDOW 3 36 40 Left 0 SYMATTR InstName R9 SYMATTR Value 10 SYMBOL cap 800 816 R0 WINDOW 0 -41 31 Left 0 WINDOW 3 -53 59 Left 0 SYMATTR InstName C1 SYMATTR Value 100e-9 TEXT -1192 808 Left 0 !.tran 0 .275 0 TEXT -1200 856 Left 0 !.model SW SW(Ron=1 Roff=10Meg Vt=0.5Vh=0)

JF

the 'pulse stuffer' at work:

That's interesting John. I changed your tap sequence to what I had from the other program so the xor sequence is:

tap1 = q5 XOR q6 tap2 = q4 XOR tap1 tap3 = tap2 XOR q8 srin = nor XOR tap3

This seems to represent what I had earlier with bits 5,6 exored, and that result xored with bit 3, and that result xored with bit 8.

Worked well and produced the expected results with the addition of the zero lockup state on count 25.

Not sure how the zero gets eliminated, but the sequence continued with the correct values after the zero state.

I'll give it some more though and maybe figure it out.

Nice job. Some people say it's impossible to eliminate the zero lockup state, but looks like that's not the case.

-Bill

and the 'pulse stuffer' at work:

More info:

Forget to mention I changed your starting qx values to all "1" or 255 which produces the zero condition on count 25. The sequence goes like this:

FF, FE, FC, F8, F0, E1, C2, 85, 0B, 17, 2F, 5E, BC, 78, F1, E3, C6,

8D, 1A, 34, 68, D0, A0, 40, 80, 00, 01, 02, 04, 08, 11

-Bill

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.

--
You recall incorrectly. :-)

and the 'pulse stuffer' at work:

--
Thanks.

Your LTspice circuit isn't an "XOR-based PRNG" (i.e. LFSR), as it includes

2 (inclusive-) OR gates.

If you're limited to XOR gates, the all-zeros state is bound to be invariant. That's the "linear" part of LFSR.

--
Sorry, but that\'s not right. 

It\'s EXOR _based_ because the basic polynomial is generated by A4, A10,

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.

--
He was, and you\'re both wrong.

What you\'re saying, in effect, is that if an 8 cylinder ICE fitted with

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

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

The bitwise-xor-shift thing is sort of a nuisance to code in a processor, or rather it's slow. One thing I've done (in 68K assembly) is...

; SUBBIE TO SEQUENCE THE PSEUDORANDOM VALUE IN D0

PRAM: LSR.W # 1, D0 ; THIS IS A 32-BIT MAXIMAL BCC.S PROM ; PSEUDORANDOM THING SOMEHOW. RTS

PROM: EORI.L # 80000EA6h, D0 RTS

which is right-shift one bit and, if the carry is clear, xor with that mess. This has no hang state. I have no clue why it works.

John