What are your expectations regarding SEUSSF and SEUSSR ?

Conga

cgracey wrote: »

I added in SEUSSF and SEUSSR which were from the Prop2-Hot. They don't take much logic and they provide a forward and reverse bit-position-and-polarity-change function. These are kind of silly instructions, but they'll provide simple means to obfuscate data or create pseudo-random numbers from counters, etc

Hi Chip, hi all,

What are your expectations regarding SEUSSF and SEUSSR ?

I do not expect a proper PRNG, much less a cryptographically secure PRNG.

Just that it would be nice to have a period (cycle length) of 2**30 or greater --- given that SEUSSF and SEUSSR operate on a 32-bit register (the PRNG state), that should be possible, right?

Getting somewhat evenly distributed 32-bit values would also be nice, even if (maybe) the resulting sequence would fail some statistical tests on randomness.

Determinism is not a limitation, is a feature: it's useful to have the ability to replicate an output sequence or a simulation run by using same seed 32-bit value.

But the best part, that I have not seen outside P2, is having a pair of PRNG-like instructions, giving us the ability to "go back" in a pseudo-random sequence (using SEUSSR after SEUSSF, or vice-versa).

Thanks!

cgracey

Making a pseudo-random number generator, at least an LFSR, is just two instructions and one data long:

TEST x,mask WC
RCL x,#1

In the Prop2 hub, along with CNT, there's RND, which is a 32-bit LFSR that's been reordered and selectively inverted for different output to each cog. It's updated every clock and can be read using the GETRND {D} {WC,WZ}, meaning that you don't even need to affect D, but could just get a pseudo-random bit into C and/or Z, if you want.

Something that can move every bit into a new position, while inverting half of them, is a function that would take many instructions, otherwise. That's what I was thinking, anyway, about SEUSSF/SEUSSR. It does something that would be impractically expensive to do discreetly. It's in the toolbox if any wants to pull it out. Plus, as you said, it's reversible. And it takes very little silicon.

This brings up a topic which I've found fascinating: What useful unary functions can be achieved? At the simple end of the spectrum there's "one's-complement", while at the other end there's "is-it-prime?", which would be clearly impractical to implement in a single clock.

Heater.

How about a PRNG for the Prop with a cycle of 2^121 ?

http://forums.parallax.com/discussion/136975/jkiss32-high-quality-prng-with-realrandom-seed-save-a-cog

cgracey

Heater. wrote: »

How about a PRNG for the Prop with a cycle of 2^121 ?

http://forums.parallax.com/discussion/136975/jkiss32-high-quality-prng-with-realrandom-seed-save-a-cog

I could use that as the hub's PRNG, but I don't have any experience with it and I feel like it might be inviting unknowns, at this point. Would be simple to do, though.

He made a version that works on 32-bit values that a processor might handle, as there are shifts and adds. Easy to implement in hardware, but I wonder if there is even a more efficient way, since we have real logic, not constrained by typical processor abilities.

Conga

cgracey wrote: »

Something that can move every bit into a new position, while inverting half of them, is a function that would take many instructions, otherwise. That's what I was thinking, anyway, about SEUSSF/SEUSSR.

OK, so the idea was about a simple pseudorandom scrambler and descrambler that can be done well in silicon (and would be impractically expensive in software).

I understand that SEUSSF/SEUSSR were not designed specifically to be used as a reversible PRNG, but of course they can be used this way too.

cgracey wrote: »

This brings up a topic which I've found fascinating: What useful unary functions can be achieved? At the simple end of the spectrum there's "one's-complement", while at the other end there's "is-it-prime?", which would be clearly impractical to implement in a single clock.

The focus on useful operations that can be done in very little silicon is an important part of the appeal of the P2 design (for me).
Looking forward to the P2 chip.

Thanks!

Seairth

Here's another use for SEUSSx: improving wireless communications. While talking to a co-worker about the challenges of infrared communications, we started talking about ways to implement FEC (forward error correction). One aspect of effective error correction is that lost/damaged bits must be sparse. In other words, if you have a significant amount of error in one spot, error correction may not work. Whereas, if you have the same amount of error spread out over the length of your packet, you are more likely to be able to recover the lost/damaged information. This is where SEUSSx comes in. The basic process is:

1. Encode packet with error correction information
2. For each 32-bit block, scramble the bits with SEUSSF.
3. Transmit
4. Receive
5. For each 32-bit block, unscramble the bits with SEUSSR.
6. Apply error correction

The reason that you scramble the bits is so that an environmental interference that would cause significant local error would end up being sparsely distributed when the bits were unscrambled. Of course, this doesn't guarantee successful error correction. I just improves the odds.

Heater.

Searith,

A very good point. How I wished we had such bit juggling instructions back in the 1980's on a military wireless project.

We had 7 bit characters with 5 ECC bits. That detected and corrected all 1 bit errors and could detect 2 bit errors. Those 12 bits were taken 8 at a time and dispersed into 12 byte blocks. All 8 LSB's in the first byte, all second bits in the second byte etc.

With that a noise burst on the wireless link could take out 8 bits in row and the data recovered successfully. Noise tends to follow the Poisson distribution so this greatly increases the probability of a block being received correctly.

Hmm...thinking about it now I don't know why I did not suggest putting all that logic in the ASIC they built that was the wireless modem...