8 Bit Random Numbers

[Bill Bowden]

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?

-Bill

 

[John Larkin]

On Tue, 27 Jan 2009 18:03:03 -0800 (PST), Bill Bowden
<wrongaddress@att.net> wrote:

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?

-Bill

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

 

[Nobody]

On Tue, 27 Jan 2009 18:03:03 -0800, Bill Bowden wrote:

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, 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:

http://homepage.mac.com/afj/taplist.html

Wikipedia page:

http://en.wikipedia.org/wiki/LFSR

 

[Bob Penoyer]

On Tue, 27 Jan 2009 18:03:03 -0800 (PST), Bill Bowden
<wrongaddress@att.net> wrote:

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 www.bobpenoyer.com/Pseudo_Rand.zip

 

[Bob Masta]

On Tue, 27 Jan 2009 18:03:03 -0800 (PST), Bill
Bowden <wrongaddress@att.net> wrote:

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?

-Bill

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
www.daqarta.com
Scope, Spectrum, Spectrogram, Sound Level Meter
FREE Signal Generator
Science with your sound card!

 

[krw]

In article <pan.2009.01.28.05.13.59.313000@nowhere.com>,
nobody@nowhere.com says...>

On Tue, 27 Jan 2009 18:03:03 -0800, Bill Bowden wrote:

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, 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:

http://homepage.mac.com/afj/taplist.html

Wikipedia page:

http://en.wikipedia.org/wiki/LFSR

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.

 

[John Fields]

On Wed, 28 Jan 2009 14:18:22 GMT, N0Spam@daqarta.com (Bob Masta) wrote:

On Tue, 27 Jan 2009 18:03:03 -0800 (PST), Bill
Bowden <wrongaddress@att.net> wrote:

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?

-Bill

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.

---
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'
state, then forced out of it, with the result that the number of
permutations is 2^n, not (2^n)-1

Here's the schematic:

Version 4
SHEET 1 1140 680
WIRE 1008 -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 944 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 -736 208 -736 -112
WIRE -736 208 -784 208
WIRE -704 208 -736 208
WIRE -496 208 -496 -128
WIRE -496 208 -544 208
WIRE -464 208 -496 208
WIRE -256 208 -256 -144
WIRE -256 208 -304 208
WIRE -224 208 -256 208
WIRE -16 208 -16 -160
WIRE -16 208 -64 208
WIRE 16 208 -16 208
WIRE 224 208 224 -160
WIRE 224 208 176 208
WIRE 256 208 224 208
WIRE 464 208 464 -192
WIRE 464 208 416 208
WIRE 496 208 464 208
WIRE 704 208 704 -224
WIRE 704 208 656 208
WIRE 736 208 704 208
WIRE 1008 208 1008 -496
WIRE 1008 208 896 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 -1216 288 -1216 64
WIRE -1056 288 -1056 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 -1216 384 -1216 368
WIRE -1136 384 -1136 112
WIRE -1136 384 -1216 384
WIRE -1056 384 -1056 368
WIRE -1056 384 -1136 384
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 944 384 944 64
WIRE 944 384 816 384
WIRE -1216 432 -1216 384
FLAG -1216 432 0
SYMBOL voltage -1056 272 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 .001 .002)
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 272 R0
WINDOW 123 0 0 Left 0
WINDOW 39 0 0 Left 0
WINDOW 3 24 104 Invisible 0
SYMATTR InstName V2
SYMATTR Value PULSE(5 0 1e-6)
TEXT -1192 408 Left 0 !.tran 0 .512 0

and here it is in Quick BASIC, so you can see the numerical output
change and the 'pulse stuffer' at work:


'8 bit pseudo-random sequence generator with no lockup state.
'07 September 2007
'John Fields


SCREEN 0
COLOR 0, 7
CLS

q1 = 0
q2 = 0
q3 = 0
q4 = 0
q5 = 0
q6 = 0
q7 = 0
q8 = 0
clk = 0
new$ = "0"
s = 4500000


PRINT " Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 CLOCK"

VIEW PRINT 42 TO 43

PRINT "Press " + CHR$(34) + "f" + CHR$(34) + " to increase
display speed, " + CHR$(34) + "s" + CHR$(34) + " to decrease it, or " +
CHR$(34) + "q" + CHR$(34) + " to quit."


VIEW PRINT 3 TO 40


shift: PRINT q1; q2; q3; q4; q5; q6; q7; q8; " "; clk



nor = q1 OR q2 OR q3 OR q4 OR q5 OR q6 OR q7

IF nor = 0 THEN nor = 1 ELSE nor = 0

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

q8 = q7
q7 = q6
q6 = q5
q5 = q4
q4 = q3
q3 = q2
q2 = q1
q1 = srin

clk = clk + 1
IF clk = 256 THEN clk = 0

FOR t = 1 TO s: NEXT t

a$ = INKEY$
IF a$ = "f" THEN s = s - 100000
IF a$ = "s" THEN s = s + 100000
IF a$ = "q" THEN END



GOTO shift
END

If you don't have a compiler and you want to see it run, I'll post an
executable on abse.
---

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

---
If the taps are located at the same places in the sequence, the vertical
method will yield _exactly_ the same sequence as the horizontal, and if
a pulse stuffer is used to escape from the lockup state, the
initialization sequence can start anywhere.



JF

 

[Bill Bowden]

On Jan 28, 6:18 am, N0S...@daqarta.com (Bob Masta) wrote:

On Tue, 27 Jan 2009 18:03:03 -0800 (PST),
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.

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.

http://home1.gte.net/res0658s/electronics/LFSRtaps.html

-Bill

 

[John Fields]

On Wed, 28 Jan 2009 11:52:47 -0600, John Fields
<jfields@austininstruments.com> 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

 

[Bill Bowden]

On Jan 28, 9:52 am, John Fields <jfie...@austininstruments.com> wrote:

and here it is in Quick BASIC, so you can see the >numerical output change and the 'pulse stuffer' at work:

'8 bit pseudo-random sequence generator with no lockup state.
'07 September 2007
'John Fields

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

 

[Bill Bowden]

On Jan 31, 5:59 pm, Bill Bowden <wrongaddr...@att.net> wrote:

On Jan 28, 9:52 am, John Fields <jfie...@austininstruments.com> wrote:



and here it is in Quick BASIC, so you can see the >numerical output change and the 'pulse stuffer' at work:

'8 bit pseudo-random sequence generator with no lockup state.
'07 September 2007
'John Fields

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

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

 

Bill Bowden wrote:

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.

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.

 

[John Fields]

On Sun, 01 Feb 2009 14:35:55 +0000, nospam@nospam.com wrote:

IIRC, you can eliminate the zero lockup state, but only by introducing
some other state that locks up.

---
You recall incorrectly.
---

What you cannot do is make an XOR-based
PRNG that pseudorandomly cycles through all values from 0 to 255.

---
Not true.

If you run the LTspice circuit list or the BASIC program I posted
earlier (or build it, even) you can see all 256 states exercised.

JF

 

[John Fields]

On Sat, 31 Jan 2009 17:59:47 -0800 (PST), Bill Bowden
<wrongaddress@att.net> wrote:

On Jan 28, 9:52 am, John Fields <jfie...@austininstruments.com> wrote:

and here it is in Quick BASIC, so you can see the >numerical output change and the 'pulse stuffer' at work:

'8 bit pseudo-random sequence generator with no lockup state.
'07 September 2007
'John Fields


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.

---
Thanks.
---

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

---
True.

JF

 

[Nobody]

On Sun, 01 Feb 2009 10:17:46 -0600, John Fields wrote:

What you cannot do is make an XOR-based
PRNG that pseudorandomly cycles through all values from 0 to 255.

---
Not true.

If you run the LTspice circuit list or the BASIC program I posted
earlier (or build it, even) you can see all 256 states exercised.

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.

 

[John Fields]

On Sun, 01 Feb 2009 22:36:15 +0000, Nobody <nobody@nowhere.com> wrote:

On Sun, 01 Feb 2009 10:17:46 -0600, John Fields wrote:

What you cannot do is make an XOR-based
PRNG that pseudorandomly cycles through all values from 0 to 255.

---
Not true.

If you run the LTspice circuit list or the BASIC program I posted
earlier (or build it, even) you can see all 256 states exercised.

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

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

It's EXOR _based_ because the basic polynomial is generated by A4, A10,
and A11 (EXOR gates) with taps along the register located at Q3,Q5,Q6,
and Q8.

Furthermore, A12 and A13 don't comprise 2 inclusive-OR gates, they
resolve to a single inclusive NOR
---

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

---
Duh.

The point was that with the addition of the extra circuitry, (A12, A13,
and A14) slipping into the lockup state by accident becomes impossible,
even if, on purpose, the counter is cleared on power-up.

JF

 

[Nobody]

On Sun, 01 Feb 2009 17:24:40 -0600, John Fields wrote:

What you cannot do is make an XOR-based PRNG that pseudorandomly cycles
through all values from 0 to 255.

---
Not true.

If you run the LTspice circuit list or the BASIC program I posted
earlier (or build it, even) you can see all 256 states exercised.

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

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

It's EXOR _based_ because the basic polynomial is generated by A4, A10,
and A11 (EXOR gates) with taps along the register located at Q3,Q5,Q6, and
Q8.

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.

 

[John Fields]

On Mon, 02 Feb 2009 04:03:27 +0000, Nobody <nobody@nowhere.com> wrote:

On Sun, 01 Feb 2009 17:24:40 -0600, John Fields wrote:

What you cannot do is make an XOR-based PRNG that pseudorandomly cycles
through all values from 0 to 255.

---
Not true.

If you run the LTspice circuit list or the BASIC program I posted
earlier (or build it, even) you can see all 256 states exercised.

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

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

It's EXOR _based_ because the basic polynomial is generated by A4, A10,
and A11 (EXOR gates) with taps along the register located at Q3,Q5,Q6, and
Q8.

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

He was, and you're both wrong.

What you're saying, in effect, is that if an 8 cylinder ICE fitted with
a 7 cylinder ignition system was fitted with a system winch allowed all
8 cylinders to work it would no longer be an ICE, which is total
nonsense.
---

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.

---
Your point being???

JF

 

Nobody wrote:

John Fields wrote:

What you cannot do is make an XOR-based PRNG that
pseudorandomly cycles through all values from 0 to 255.

Not true.

If you run the LTspice circuit list or the BASIC program I posted
earlier (or build it, even) you can see all 256 states exercised.

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

Sorry, but that's not right.

It's EXOR _based_ because the basic polynomial is generated by A4, A10,
and A11 (EXOR gates) with taps along the register located at Q3,Q5,Q6, and
Q8.

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 (http://en.wikipedia.org/wiki/LFSR)
"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).

 

[John Larkin]

On Tue, 27 Jan 2009 18:03:03 -0800 (PST), Bill Bowden
<wrongaddress@att.net> wrote:

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?

-Bill

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