8 Bit Random Numbers

[John Fields]

On Mon, 02 Feb 2009 16:47:34 +0000, nospam@nospam.com wrote:

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.

---
I think you're confused here since, in my first post to this thread, the
first comment line in my BASIC program reads:

" '8 bit pseudo-random sequence generator with no lockup state."

notice I said: "pseudo-random sequence generator", not: "linear feedback
shift register".

Look above and you'll see that you wrote: "Your LTspice circuit isn't an
"XOR-based PRNG" (i.e. LFSR), as it includes 2 (inclusive-) OR gates."

from your "i.e.", the inference is that _you_ considered an EXOR based
PRNG to be the equivalent of an LFSR, while now you're saying it's not,
which then makes my EXOR based PRNG not an LFSR, which should make you
happy.

While I did call the PRSG with the DAC output an LFSR, that was more
brain fart than anything else, since I tend to use PRSG and LFSR
interchangeably. I do, however, tend to use PRSG and "linear counter"
more than any other term.
---

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

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

---
As before, you recall incorrectly.

As I showed earlier, the lockup state can be entirely suppressed with
the use of a simple NOR/EXOR circuit.

With or without the NOR, the sequence is identical in both cases with
the exception that the NOT forces the register into and out of the
lockup state so that becomes the "special additional circuit" you
mention, which then makes the device an LFSR with a special additional
circuit to prevent latchup, which means it's an LFSR.

The end result is that the circuit with the NOR is a true maximal length
PRSG with the number of output states equal to 2^n, while the circuit
without it has only (2^n)-1, the missing state being the lockup state,
of course.

One final thing to note is that while the counter may be _called_ an
LFSR, its output isn't linear since, without the NOR, there'll be one
less zero than ones in its output before it repeats.

JF

 

[Nobody]

On Mon, 02 Feb 2009 07:58:02 -0600, John Fields wrote:

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.

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.

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???

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

 

[Jamie]

John Larkin 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


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

Yum Yum, the Asm code is making me drool!

That's real power man!

http://webpages.charter.net/jamie_5"

 

[John Fields]

On Mon, 02 Feb 2009 08:59:26 -0800, John Larkin
<jjlarkin@highNOTlandTHIStechnologyPART.com> 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

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.

---
Because you don't start off in the hang state?

All EXOR based pseudo-random sequences, amazingly, skip over the hang
state if they're not started in it.

God has a sense of humor, yes?

JF

 

[Bill Bowden]

On Feb 2, 2:05 pm, Nobody <nob...@nowhere.com> wrote:

On Mon, 02 Feb 2009 07:58:02 -0600, John Fields wrote:
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.

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.

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???

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

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
80,00,01.....

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,
00000001..... And that's exactly what the circuit does, without the
lookup table.

-Bill

 

[Nobody]

On Mon, 02 Feb 2009 17:03:00 -0800, Bill Bowden wrote:

The output of the 8 bit LFSR that Fields did

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.

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
80,00,01.....

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.

 

[Nobody]

On Mon, 02 Feb 2009 18:28:02 -0600, John Fields wrote:

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.

---
Because you don't start off in the hang 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.

 

Bill Bowden wrote:

Nobody wrote:

John Fields wrote:

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.

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.

I don't think that anyone 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.

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

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
80,00,01.....

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.

 

[John Fields]

On Tue, 03 Feb 2009 17:59:15 +0000, nospam@nospam.com wrote:

Bill Bowden wrote:

Nobody wrote:

John Fields wrote:

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.

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.

I don't think that anyone 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.

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

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
80,00,01.....

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?

---
How dare you talk to Mr. Bowden in such a disrespectful manner when he's
done nothing but be civil to you?

I suggest you go to:

http://ourworld.compuserve.com/homepages/Bill_Bowden/

and check out his comprehensive library of circuits and circuit
descriptions before you get your foot inextricably stuck in your mouth.

---
Bill, this clown is playing a semantic game of one-upmanship because he
recently learned how to access Wikipedia from Google and learned that
the feedback to the input of the shifter is what's called "linear"
because the EXORs are linear Boolean elements; ergo "Linear _Feedback_
Shift Register": LFSR.

Consequently, he disallows my circuit from being part of the set of
LFSRs because the NOR is a non-linear element. Boo-Hoo...
---

What Fields posted was *NOT* an 8 bit LFSR. It was *NOT* XOR based.

---
Well I'll go along with your little "LFSR" definition, but it certainly
_is_ EXOR based.

After all, it's a shift register with EXORs connected to the same taps
as your "LFSR", no?

And the data pattern is identical for the two, with the exception that
mine has and cannot have a lockup state.

If it's not EXOR based, what do you think those gates are that look like
ORs, but with the extra curved line on the input side?
---

(BTW, why does Fields keep calling XOR "EXOR?" Does he have some
sort of problem using standard terminology?)

---
http://www.google.com/search?sourceid=navclient&ie=UTF-8&rlz=1T4GFRC_en&q=EXOR+gate

you pompous little cocksucker.
---

Simply saying "you are both wrong" does not change reality.

---
It most certainly does, since had I not said it, reality would have
taken a different turn and you wouldn't have posted:

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

---
So, because we don't, you've got your tit caught in the wringer?

The problem is, you don't want agreement, you want agreement on _your_
terms.

Well, you're not going to get it.

Since it's the EXORs which are responsible for generating the data
pattern, my circuit is an EXOR based Pseudo Random Sequence Generator
and is referred to by many names, including Pseudo Random Number
Generator, so your idiotic claim that it's not an EXOR based PRNG is
unfounded.

Just for fun, though, if you had a choice what would you call it?
---

There is nothing wrong with his design.

---
Oh, thank you God, I was beginning to think I'd made a mistake.
---

You are simply calling it by the wrong
name.

---
So what would you call it?
---

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.

---
Then admit that what you consider to be wrong terminology, i.e."EXOR
based PRNG" is right.
---

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.

---
Fuck you _and_ the horse you rode in on, since that's not what anyone's
talking about and all you're trying to do is sidestep the issue by
changing the focus of the thread.

JF

 

[John Fields]

On Tue, 03 Feb 2009 15:59:45 -0600, John Fields
<jfields@austininstruments.com> wrote:

And the data pattern is identical for the two, with the exception that
mine has and cannot have a lockup state.

---
Schrodinger's cat kinda funny, but Aarghhh!!!

Should read:

"mine doesn't have and cannot have a lockup state."

JF

 

[John Fields]

On Mon, 02 Feb 2009 22:05:13 +0000, Nobody <nobody@nowhere.com> wrote:

On Mon, 02 Feb 2009 07:58:02 -0600, John Fields wrote:

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.

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.

---
Well, I can't argue with that since it's the _feedback_ that's linear,
so I concede.
---

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???

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

---
And yet the LFSR lives within whatever it's called if it's EXOR feedback
based...

I suggest, since the non-linear portion of the counters' sequence is so
small, that they be dubbed Mostly Linear Feedback Shift Registers;
MLFSRs.

Got a problem with that?

JF

 

[Bill Bowden]

On Feb 3, 9:59 am, nos...@nospam.com wrote:

Bill Bowden wrote:

Nobody wrote:

John Fields wrote:

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.

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.

I don't think that anyone 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.

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

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
80,00,01.....

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?

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
1024 "1s" and only 1023 zeros which is slightly non-linear.

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

What am I missing?

-Bill

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.

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

 

John Fields wrote:

you pompous little cocksucker.

Fuck you _and_ the horse you rode in on

If you had logic or evidence supporting your arguments, you would have posted
them. Not having either and having clearly lost the argument, you now resort
to personal attacks.

Plonk.

 

[Bill Bowden]

On Feb 3, 9:59 am, nos...@nospam.com wrote:

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?

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?

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.

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

 

[John Larkin]

On Tue, 03 Feb 2009 06:02:47 +0000, Nobody <nobody@nowhere.com> wrote:

On Mon, 02 Feb 2009 18:28:02 -0600, John Fields wrote:

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.

---
Because you don't start off in the hang 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.

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

 

[Bill Bowden]

On Feb 3, 1:59 pm, John Fields <jfie...@austininstruments.com> wrote:

Bill, this clown is playing a semantic game of one-upmanship because he
recently learned how to access Wikipedia from Google and learned that
the feedback to the input of the shifter is what's called "linear"
because the EXORs are linear Boolean elements; ergo "Linear _Feedback_
Shift Register": LFSR.

Consequently, he disallows my circuit from being part of the set of
LFSRs because the NOR is a non-linear element. Boo-Hoo...
---

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

 

[Nobody]

On Tue, 03 Feb 2009 19:31:09 -0800, Bill Bowden wrote:

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?

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.

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.

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?

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 <stdio.h>

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 << 7;
return t;
}

byte g(byte *x)
{
byte t = *x & 1;
byte k = (-t) & g_taps;
*x >>= 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;
}

 

[John Fields]

On Tue, 3 Feb 2009 23:18:56 -0800 (PST), Bill Bowden
<wrongaddress@att.net> wrote:

On Feb 3, 1:59 pm, John Fields <jfie...@austininstruments.com> wrote:


Bill, this clown is playing a semantic game of one-upmanship because he
recently learned how to access Wikipedia from Google and learned that
the feedback to the input of the shifter is what's called "linear"
because the EXORs are linear Boolean elements; ergo "Linear _Feedback_
Shift Register": LFSR.

Consequently, he disallows my circuit from being part of the set of
LFSRs because the NOR is a non-linear element. Boo-Hoo...
---

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

---
Thinking about it a little more, it occurred to me that my circuit (it's
not really mine, I came across it in the late 60's when I worked for
Racal-Milgo in Miami) is in a class of devices called "feedback shift
registers" and, since its output has as many ones as it has zeroes, it's
a linear device.

Consequently, it's truly a linear feedback shift register and the ones
with lockout states aren't.


JF

 

[John Fields]

On Wed, 04 Feb 2009 10:14:30 +0000, Nobody <nobody@nowhere.com> wrote:

On Tue, 03 Feb 2009 19:31:09 -0800, Bill Bowden wrote:

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?

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.

---
No, it doesn't.

You don't understand.

In an LFSR without NOR feedback there exist two modes of operation: the
trivial lockup state which, if entered into at startup or forced into by
noise, is eternal, and the normal Fibonacci (or Galois) mode where a
maximal length sequence has a length equal to (2^n)-1, where n is the
number of stages in the shifter.

With the NOR feedback there is no lockup state, the length of the
sequence is equal to 2^n, and the output of the device is truly linear.
Why would that be undesirable?

BTW, since we're talking about shift registers employing feedback (i.e.
"feedback shift registers") and mine has a linear output, I'd say that
qualifies it as a linear feedback shift register, so I rescind my
earlier concession.

JF

 

Bill Bowden wrote:

John Fields wrote:

Bill, this clown is playing a semantic game of one-upmanship because he
recently learned how to access Wikipedia from Google and learned that
the feedback to the input of the shifter is what's called "linear"
because the EXORs are linear Boolean elements; ergo "Linear _Feedback_
Shift Register": LFSR.

Consequently, he disallows my circuit from being part of the set of
LFSRs because the NOR is a non-linear element. Boo-Hoo...

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.

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:

http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm
(Scroll down to "Galois Field Mathematics and M-Sequences")

http://www.edacafe.com/books/ASIC/Book/CH14/CH14.7.php
(Using a LFSR for Built-in Self-test in an ASIC)

http://www.yikes.com/~ptolemy/lfsr_web/index.htm
(LFSRs for Engineers)

http://en.wikipedia.org/wiki/Linear_feedback_shift_register
(Scroll down to "Polynomials for Maximal LFSRs")

http://www.physics.otago.ac.nz/px/research/electronics/papers/technical-reports/lfsr_table.pdf
(Table of maximum-cycle LFSR taps)

http://homepage.mac.com/afj/taplist.html
(Another table of maximum-cycle LFSR taps)

http://home1.gte.net/res0658s/electronics/LFSRtaps.html
(Yet another table of LFSR taps)