J
John Fields
Guest
On Mon, 02 Feb 2009 16:47:34 +0000, nospam@nospam.com wrote:
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.
---
What NOT gates???
---
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 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