Searching \ for '[PIC] Simple pseudo random code generation' in subject line. ()
Make payments with PayPal - it's fast, free and secure! Help us get a faster server
FAQ page: www.piclist.com/techref/microchip/math/index.htm?key=random
Search entire site for: 'Simple pseudo random code generation'.

Exact match. Not showing close matches.
PICList Thread
'[PIC] Simple pseudo random code generation'
2005\06\22@224144 by Chen Xiao Fan

face
flavicon
face
I am trying to generate some pseudo random code to add
some randomness for the pulse generation. I found the
following code from PICList archive. However it is
generating random code from 1 to 255 and I am trying to
generate something between 1 to 31 (can be 32, etc).
It seems to me I can not simply using three times of
(BCF STATUS,C and RRF RANDOM, F).

Are there any simple code to generate arbitrary pseudo
random number (<=8-bit)?

I am now using TMR1L as the random seed and the code
works for generating 1-255.

Regards,
Xiaofan

>>>> From PICLIST.com archive >>>>>

Andrew Warren [fastfwd at ix.netcom.com] of Fast Forward Engineering
- San Diego, California says
 Load a register called "RANDOM" with any non-zero value, then call this
 routine each time you'd like a new pseudo-random value:
   LFSR:   RLF     RANDOM,W
           RLF     RANDOM,W
           BTFSC   RANDOM,4
           XORLW   1
           BTFSC   RANDOM,5
           XORLW   1
           BTFSC   RANDOM,3
           XORLW   1
           MOVWF   RANDOM
           RETLW   0
Scott Dattalo says:
   [with the double RLF at the start of this routine,] Andy is implementing

   'roll left' where the most significant bit of RANDOM will get copied to
   least significant position. This is how it works. The first RLF will
copy
   the most significant bit of RANDOM into the carry. What ever was in the
   carry prior to the first RLF will get copied into the least significant
bit
   position - but we don't care. Also, since the destination is the W
register,
   the variable RANDOM is unaffected. The second RLF repeats the same
rotate
   operation, but this time the carry has been initialized to the MS bit of

   random. So this second rotate will copy the MS bit into the least
   significant bit. All of the other bits are of course shifted left one
bit
   position. See?

2005\06\22@230134 by Jinx

face picon face
> generating random code from 1 to 255 and I am trying to
> generate something between 1 to 31

> (can be 32, etc)

? thought you said 1-31 ?

> It seems to me I can not simply using three times of
> (BCF STATUS,C and RRF RANDOM, F).

Why not just AND with b'00111111' and add 1 if 0 not OK
or re-generate until <> 0

2005\06\22@230148 by Maarten Hofman

face picon face
Rochester, 22 juni 2005.

Dear Xiao Fan,

Nice to see another random number generator. To get a number from 1-31
from a number from 1-255 you could just AND the result with 0x1F, or
am I mistaken? (Just make sure you keep the old number for the next
time you want to generate a random number).

My current routine is:
 movf Randoma,w
 addwf Randomb,w
 btfsc STATUS,C
 addlw 0x01
 movwf Random
 incf Random,f
 movf Randoma,w
 movwf Randomb
 movf Random,w
 movwf Randoma

Which would be:
random[x]=random[x-1]+random[x-2]+C+1

Of course, I start out by not initialising Randoma and Randomb, and in
routines that have a changing duration (like waiting for a write to
EEPROM to finish, or waiting for user input) I keep increasing Randoma
as long as the loop continues.

The result is random enough for my purposes, but there might be better
ways and I will be following this thread closely.

Greetings,
Maarten Hofman.

2005\06\22@230307 by Jinx

face picon face
> It seems to me I can not simply using three times of
> (BCF STATUS,C and RRF RANDOM, F).

"Why not just AND with b'00111111' and add 1 if 0 not OK
or re-generate until <> 0"

Sorry, fudge fingers -

Why not just AND with b'00011111' and add 1 if 0 not OK
or re-generate until <> 0


2005\06\22@232721 by Chen Xiao Fan

face
flavicon
face
Thanks for the suggestions. I will try that.

By the way, there is another piece of code in the
PIClist archive.

Regards,
Xiaofan


>>>>>>>>> From PICLIST.com archive >>>>>

Or, if you prefer, you can use this routine (written by Marv Isaacman)
 instead:
   MARV:   MOVLW   01DH
           CLRC
           RLF     RANDOM
           SKPNC
           XORWF   RANDOM
           RETLW   0

Linear Congruential Sequence
See also:

www.piclist.com/techref/default.asp?from=/techref/piclist/../microchi
p/math/../&url=http://www.siliconchip.com.au/SOFTWARE/may00/leddice.asm

2005\06\22@233430 by David P Harris

picon face
Maarten Hofman wrote:

>Nice to see another random number generator. ...
>
>My current routine is:
>  
>
Here's a good algorithm:
http://www.piclist.com/techref/microchip/seepicsrc/psbpix/random.htm  ;-)

David


2005\06\23@015815 by Jinx

face picon face
> The result is random enough for my purposes, but there might be better
> ways and I will be following this thread closely.

This is a h/w solution

http://home.clear.net.nz/pages/joecolquitt/white_noise.html

For various reasons a PRNG was not acceptable, so I use one of
these circuits to seed, start, and stop the PIC's timers for totally
random number production

2005\06\23@032811 by William Chops Westfield

face picon face

On Jun 22, 2005, at 8:01 PM, Maarten Hofman wrote:

> To get a number from 1-31 from a number from 1-255 you could just
>  AND the result with 0x1F, or am I mistaken?

You have to be a bit careful applying additional "math" to
pseudo-random numbers, or they can lose some of their randomness
properties.  OTOH, xor/shifting algorithms don't produce very
random numbers anyway, so it depends on what you're looking for.


> (Just make sure you keep the old number for the next
> time you want to generate a random number).

That should help.  since the PRNG cycles through (2^N)-1 bit
patterns, and subset of M bits ought to cycle through all possible
bit patterns 2^(N-M) times, right?

BillW

2005\06\23@045911 by Wouter van Ooijen

face picon face
> Are there any simple code to generate arbitrary pseudo
> random number (<=8-bit)?

The common LFSR pseudo-random generators in fact generate one bit per
step. Just take the number of bits you need.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu


2005\06\23@052152 by Chen Xiao Fan

face
flavicon
face
Sorry but which LFSR? The simple LFSR in the PIClist
archive does not seem to do this.

LFSR:   RLF     RANDOM,W
       RLF     RANDOM,W
       BTFSC   RANDOM,4
       XORLW   1
       BTFSC   RANDOM,5
       XORLW   1
       BTFSC   RANDOM,3
       XORLW   1
       MOVWF   RANDOM
       RETLW   0

Regards,
Xiaofan

{Original Message removed}

2005\06\23@052226 by Chen Xiao Fan

face
flavicon
face
I used the suggestion to generate 1-8 (and with 0x07)
and 1-64 (0x3F) but somehow it loses quite some randomness.
I will check the code again.

Regards,
Xiaofan

{Original Message removed}

2005\06\23@052843 by Peter Onion

flavicon
face
On Thu, 2005-06-23 at 10:57 +0200, Wouter van Ooijen wrote:
> > Are there any simple code to generate arbitrary pseudo
> > random number (<=8-bit)?
>
> The common LFSR pseudo-random generators in fact generate one bit per
> step. Just take the number of bits you need.

And the longer you make the shift register, the more bits you'll get
before the sequence repeats.

Peter



2005\06\23@053458 by David P Harris

picon face
Chen Xiao Fan wrote:

>I used the suggestion to generate 1-8 (and with 0x07)
>and 1-64 (0x3F) but somehow it loses quite some randomness.
>I will check the code again.
>  
>
1. Were you using a shift register method, they generate one random bit
per cycle, so you would need to do several cycles.
2. Make sure you kept the random number generated, and did not use the
modified number in the next cycle.

David


2005\06\23@053806 by David P Harris

picon face
Chen Xiao Fan wrote:

>Sorry but which LFSR? The simple LFSR in the PIClist
>archive does not seem to do this.
>
>LFSR:   RLF     RANDOM,W
>        RLF     RANDOM,W
>        BTFSC   RANDOM,4
>        XORLW   1
>        BTFSC   RANDOM,5
>        XORLW   1
>        BTFSC   RANDOM,3
>        XORLW   1
>        MOVWF   RANDOM
>        RETLW   0
>
>Regards,
>Xiaofan
>  
>
Yes it does.  You shift the random number to the left.  Then you XOR the
first bit depending on the other bits.  So only the first bit gets
changed.

You will need to run through 3 times for 0-7, and 5 times for 0-31.

David

>{Original Message removed}

2005\06\23@054356 by Alan B. Pearce

face picon face
>I used the suggestion to generate 1-8 (and with 0x07)
>and 1-64 (0x3F) but somehow it loses quite some randomness.
>I will check the code again.

Don't forget that with so few possible numbers then the result will not
appear to be very random at all.

2005\06\23@054837 by David P Harris

picon face
Peter Onion wrote:

{Quote hidden}

I found a website that described this algorithm and had a table of
register length and tap points.  There is a good one that is 39 bits
long and has two tap points, so its quick.

I used one from Dave vanHorn's site for a flickering fire:
http://www.dvanhorn.org/AvrSoftware/
Here's the exact url: http://www.dvanhorn.org/Downloads/T11-Noisy.zip

Here's a site with the table in it:
http://direct.xilinx.com/bvdocs/appnotes/xapp052.pdf

Lots of fun,
David

2005\06\23@072643 by Wouter van Ooijen

face picon face
> Sorry but which LFSR? The simple LFSR in the PIClist
> archive does not seem to do this.
>
> LFSR:   RLF     RANDOM,W
>         RLF     RANDOM,W
>         BTFSC   RANDOM,4
>         XORLW   1
>         BTFSC   RANDOM,5
>         XORLW   1
>         BTFSC   RANDOM,3
>         XORLW   1
>         MOVWF   RANDOM
>         RETLW   0

It does. Each time you call this routine it shifts the (in this case
16-bit) value on step and generates one new pseudo-random bit, which is
inserted into the just vacated bit. If you want it to generate for
instance a random byte you must call it 8 times, otherwise there will be
a very strong correlation between successive bytes.

OMHO 16 bit is often a bit short, I would opt for a 24-bit SR. The Jal
library contains one:

var byte _random_b1
var byte _random_b2
var byte _random_b3

-- make sure there is at least one bit set!
asm bsf _random_b1, 0

procedure _random_shift is
  -- from the art of electronics, p657:
  -- 24 bits LFSR needs xor feedback from taps at 17, 22 and 23
  assembler
          movlw 0
     bank btfsc _random_b3, 1
             xorlw 0xFF
          btfsc _random_b3, 6
             xorlw 0xFF
          btfsc _random_b3, 7
             xorlw 0xFF
          addlw 1
     bank rlf   _random_b1, f
     bank rlf   _random_b2, f
     bank rlf   _random_b3, f
  end assembler
end procedure

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu


2005\06\23@074238 by olin piclist

face picon face
Chen Xiao Fan wrote:
> I am trying to generate some pseudo random code to add
> some randomness for the pulse generation. I found the
> following code from PICList archive. However it is
> generating random code from 1 to 255 and I am trying to
> generate something between 1 to 31 (can be 32, etc).

So just AND the 0-255 value with 31.

> Are there any simple code to generate arbitrary pseudo
> random number (<=8-bit)?

I don't know if you would consider it simple, but the HAL_RAND.ASPIC module
contains a pseudo-random number generator.  It is available in the HAL PIC
project from http://www.embedinc.com/pic.  Remeber that Embed Inc software
releases must be installed in oldest to newest order.  I don't think this
release has been updated in a long time.  If you install it, you must go
back and re-install any newer releases you wish to function correctly.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

2005\06\23@104622 by Denny Esterline

picon face
> I am trying to generate some pseudo random code to add
> some randomness for the pulse generation.

Some time last week I was thinking about randomness and such and I came up
with an idea. I haven't had time to research it, but I do find it
intriguing. What if you took two separate oscillators (possibly drifty RC
oscillators with widely different tempcos) and fed them into a shift
register -one as data the other as clock. Since they're not directly related
to each other, their relative phase will continually drift - producing a
continuous stream of uncertainty on the shift register. If a third clock was
used to decide when to sample the data...

Maybe this weekend I'll have some time to try this and run it through some
randomness testing. Does anyone know of any 'standard' randomness tests?
(hmm... a quick google *only* produced 246,000 results - Anybody have any
favorites before I wade through them?)

-Denny

2005\06\23@105313 by Michael Rigby-Jones

picon face


>-----Original Message-----
>From: spam_OUTpiclist-bouncesTakeThisOuTspammit.edu [.....piclist-bouncesKILLspamspam@spam@mit.edu]
>Sent: 23 June 2005 15:48
>To: Microcontroller discussion list - Public.
>Subject: Re: [PIC] Simple pseudo random code generation
>
>
>> I am trying to generate some pseudo random code to add
>> some randomness for the pulse generation.
>
>Some time last week I was thinking about randomness and such
>and I came up with an idea. I haven't had time to research it,
>but I do find it intriguing. What if you took two separate
>oscillators (possibly drifty RC oscillators with widely
>different tempcos) and fed them into a shift register -one as
>data the other as clock. Since they're not directly related to
>each other, their relative phase will continually drift -
>producing a continuous stream of uncertainty on the shift
>register.

The relative frequencies of the two oscillators will have a constant frequency difference in the short term so the output bit stream will be very predictable and most unrandom IMHO.

The BE junction of a bipolar transistor in reverse breakdown is a strong noise generator that has been traditionaly used as a RNG.

Regards

Mike

=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================

2005\06\23@110315 by Maarten Hofman

face picon face
> Maybe this weekend I'll have some time to try this and run it through some
> randomness testing. Does anyone know of any 'standard' randomness tests?
> (hmm... a quick google *only* produced 246,000 results - Anybody have any
> favorites before I wade through them?)

A simple way I would probably use is to use a compressor, like (g)zip,
to try and compress the output. The more random the output is, the
less likely (g)zip will be able to compress it. Apart from that, you
would want to make sure that a histogram of all the output values
looks like a reasonably flat line (i.e. all values are equally
represented).

Greetings,
Maarten Hofman.

2005\06\23@114011 by Jan-Erik Soderholm

face picon face
Just a thought about "randomness"...

A pseudo RNG made up from a shift
register
with feedback will never produce two the same
value in
sequence, right ? Is it that
that is "pseudo" with it ?

>From a *true*
RNG you'd expect that
there will be sequences (of any lenght if the
generator is run "forever") of repeated values, not ?

Jan-Erik.



2005\06\23@120949 by Michael Rigby-Jones

picon face


>-----Original Message-----
>From: piclist-bouncesspamKILLspammit.edu [.....piclist-bouncesKILLspamspam.....mit.edu]
>Sent: 23 June 2005 16:40
>To: EraseMEpiclistspam_OUTspamTakeThisOuTmit.edu
>Subject: RE: [PIC] Simple pseudo random code generation
>
>
>Just a thought about "randomness"...
>
>A pseudo RNG made up from a shift
>register
>with feedback will never produce two the same
>value in
>sequence, right ? Is it that
>that is "pseudo" with it ?
>

It's "pseudo" primarily because the output is easily predictable.

Regards

Mike

=======================================================================
This e-mail is intended for the person it is addressed to only. The
information contained in it may be confidential and/or protected by
law. If you are not the intended recipient of this message, you must
not make any use of this information, or copy or show it to any
person. Please contact us immediately to tell us that you have
received this e-mail, and return the original to us. Any use,
forwarding, printing or copying of this message is strictly prohibited.
No part of this message can be considered a request for goods or
services.
=======================================================================

2005\06\23@121601 by Mike Hord

picon face
> Just a thought about "randomness"...
>
> A pseudo RNG made up from a shift
> register
> with feedback will never produce two the same
> value in
> sequence, right ? Is it that
> that is "pseudo" with it ?

Not so sure about that...although that might be part of the
"pseudo", I think the bigger part is the fact that if you load
the register with the same starting value, the sequence it
produces will always be the same, even though the output
(without knowledge of the internal workings) appears to be
unpredictable.

And, for that matter, it is possible to produce a shift
register based PRNG that will spit out short stints of
identical sequences.  All one needs to do is to not use
every bit in the register (use, say, 8 non-sequential bits of
a 32-bit register), and the possibilty occurs of a repeating
sequence of bits without the register being hung in a
predictable state.

> >From a *true*
> RNG you'd expect that
> there will be sequences (of any lenght if the
> generator is run "forever") of repeated values, not?

For truly random, yes, you could expect interludes of
repeated sequences.

Mike H.

2005\06\23@121653 by Denny Esterline

picon face
> A simple way I would probably use is to use a compressor, like (g)zip,
> to try and compress the output. The more random the output is, the
> less likely (g)zip will be able to compress it. Apart from that, you
> would want to make sure that a histogram of all the output values
> looks like a reasonably flat line (i.e. all values are equally
> represented).
>
> Greetings,
> Maarten Hofman.

Hmm.. I like that, quick and easy. I was thinking in binary -there
should be about the same number of zeros and ones, and the length of
strings of the same bit should fit a bell shaped curve. But definitly
more research is in order.

-Denny

2005\06\23@121853 by Denny Esterline

picon face
> >Some time last week I was thinking about randomness and such
> >and I came up with an idea. I haven't had time to research it,
> >but I do find it intriguing. What if you took two separate
> >oscillators (possibly drifty RC oscillators with widely
> >different tempcos) and fed them into a shift register -one as
> >data the other as clock. Since they're not directly related to
> >each other, their relative phase will continually drift -
> >producing a continuous stream of uncertainty on the shift
> >register.
>
> The relative frequencies of the two oscillators will have a constant frequency difference in the short term so the output bit stream will be very predictable and most unrandom IMHO.
>

But the frequencies isn't where the data is coming from. The data
comes from the phase relationship, which should be much less
predictable. And yes, this is all just conjecture until I test it :-)


-Denny

2005\06\23@125351 by Bradley Ferguson

picon face
On 6/23/05, Maarten Hofman <cashimorspamspam_OUTgmail.com> wrote:
> > Maybe this weekend I'll have some time to try this and run it through some
> > randomness testing. Does anyone know of any 'standard' randomness tests?
> > (hmm... a quick google *only* produced 246,000 results - Anybody have any
> > favorites before I wade through them?)
>
> A simple way I would probably use is to use a compressor, like (g)zip,
> to try and compress the output. The more random the output is, the
> less likely (g)zip will be able to compress it. Apart from that, you
> would want to make sure that a histogram of all the output values
> looks like a reasonably flat line (i.e. all values are equally
> represented).

Using a zip routine would probably be a pretty quick and effective
method, but I think a histogram may not work as any full period of
(for example) a sinusoidal signal will have a flat histogram.

I think the usual method to determine (or at least give an indication
of) randomness is to use the autocorrelation of the data.  You might
look that up.  I may be wrong, though.

Bradley

2005\06\23@135401 by Peter Onion

flavicon
face
On Thu, 2005-06-23 at 02:48 -0700, David P Harris wrote:

> Here's a site with the table in it:
> http://direct.xilinx.com/bvdocs/appnotes/xapp052.pdf

That's certainly going to be added to my "PIC bookmarks"

Peter

2005\06\23@145544 by Dave Tweed

face
flavicon
face
Bradley Ferguson <@spam@bradleyeeKILLspamspamgmail.com> wrote:
> On 6/23/05, Maarten Hofman <KILLspamcashimorKILLspamspamgmail.com> wrote:
> > A simple way I would probably use is to use a compressor, like (g)zip,
> > to try and compress the output. The more random the output is, the
> > less likely (g)zip will be able to compress it. Apart from that, you
> > would want to make sure that a histogram of all the output values
> > looks like a reasonably flat line (i.e. all values are equally
> > represented).
>
> Using a zip routine would probably be a pretty quick and effective
> method, but I think a histogram may not work as any full period of
> (for example) a sinusoidal signal will have a flat histogram.

Not even close! A sinewave spends far more time at the extremes than at
the intermediate values. In fact, a standard test for an ADC is to see
whether its histogram forms a well-defined bathtub-shaped curve when fed
a sinewave.

See figure 4c (and the associated text) in this article:

HTML: www.circuitcellar.com/pastissues/articles/Tweed99/article.htm
PDF:  http://www.circuitcellar.com/pastissues/articles/Tweed99/tweed99.pdf

That's not to say that there aren't waveforms that have a flat histogram
(e.g., triangle, sawtooth), but a sinewave isn't one of them.

-- Dave Tweed

2005\06\23@154329 by Dave VanHorn

flavicon
face
At 01:55 PM 6/23/2005, Dave Tweed wrote:
>Bradley Ferguson <RemoveMEbradleyeeTakeThisOuTspamgmail.com> wrote:
> > On 6/23/05, Maarten Hofman <spamBeGonecashimorspamBeGonespamgmail.com> wrote:
> > > A simple way I would probably use is to use a compressor, like (g)zip,
> > > to try and compress the output. The more random the output is, the
> > > less likely (g)zip will be able to compress it. Apart from that, you
> > > would want to make sure that a histogram of all the output values
> > > looks like a reasonably flat line (i.e. all values are equally
> > > represented).

The state 00000...000 usually won't happen on these machines either,
but as long as you're looking at N-1 bits of the register, then you
should, over time, see all states equally as often.


2005\06\23@161721 by William Chops Westfield

face picon face

--Apple-Mail-6--483280587
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
       charset=US-ASCII;
       format=flowed

On Jun 23, 2005, at 4:24 AM, Wouter van Ooijen wrote:

> If you want it to generate for instance a random byte you must call
> it 8 times, otherwise there will be a very strong correlation
> between successive bytes.

It depends on what you're doing.  Calling the LFSR 8 times does not
result in an output value that is any less predictable than calling
it once (and ALL the bits change, even if you've only generated one
new random bit, so it looks pretty good if you're simulating a
flickering
fire, or generating noise, or something like that.)

Here's some "shuffle" code I was hoping to publish in one of those
electronics magazines as a "design note."  It gives you the numbers
1 through N in a random order, for any N (need not be power of two.)
All in C...

Enjoy
BillW

--Apple-Mail-6--483280587
Content-Transfer-Encoding: base64
Content-Type: application/zip;
       x-mac-type=5A495020;
       x-unix-mode=0755;
       x-mac-creator=53495421;
       name="shuffle.zip"
Content-Disposition: attachment;
       filename=shuffle.zip

UEsDBBQAAAAIACu2uTCqWbIiagQAAMUIAAALAAAAc2h1ZmZsZS50eHRlVU1v3DYQvetXDHLJLqpd
xDbsQ4Ie0sQIeqgRND6noKSRxFoiFQ7ptfrr+4aSvNl2gf0SyTdvZt4b/k4nI/Qj2cjUWDHT5K2L
3NCpZ0fjTI5P9MfXG/r0mabBzBzo5NPQuLeR3kif2nbgN7TTpUK864S8q5nY1D1ZR8G4xo/kQ8Nh
T8LPHMwgABPAhNiTbzP6cnQnZi7p6t27X1asCeEQuPVBEfPu2DPdKsDxeNwTfaTKRn0eGEzqaL2j
2rtn62okMXIRexPzoSn4Lphx5CDINCfw5PyJeryjp9Egb7zJ0JIWjg9WFHvjvZLKe0ZbB49AMfhh
0KL0XhjxRh9mLamGq0w1zNSmYaCKkQMrj5lM03ADXtg+3VDDtUdxjkS/pUizT9R45fZwf//5gpck
FMAsnP5O+MAigjSp5uLMGVx/JEbyx6J4RAj8HLzguUYB9W3jX4OtjjWdLMgFjikgqf+DaPLGzYVL
Y8VB/0Eno1CaNPrd7e3NbUlJrOvQduR6R9UcWQj9Glgk1y76YDpGfh+LSTg1/rCKYgXt2KG4EUd2
X/98+LKn2jjUC7Agcs4R9Jx3h8ATm4iAxU8cVygpqUrabD2czEB2nAYeGfVTXeRkt3C8EDY/w4Cz
66DJ6+8PhyvaqepA5UEVtkZQxT1CUG8FZCKZ3GWEKLVxBYgvnWntELVcCVsQEoQ2hvht8DCwLopt
siTUJV0moNYLLPGYe+exFrYQYB+1/6gR2RUH6+dW2Sg8tLQUSD7Q1TWCn8wsRQuJ+pPQ9c11qa05
4Sw/Z819szn1FBT3C4CX+uQKq9hM6Dgs/DSkK04MdbuoqgB2iYc4s3QMab+gZdWsth1ThjinDouP
DK+tViiWGmHPJiCDVCajrVnPm83MEhERZB811sjGLekrbcR0MKYZOh9QnxEZ5ECxV8jBPvH7oiC8
NmmDzG40L3v6de2S/ivXiLybgut2qs/A3f71ceaw33/IllqcxC8G4jr7S+UqmkPEYRMaBLRtPGjT
Di8+HFrmpjL1E0ndQ5I60nQE5LKXJFmpsHgVg8lDTDcgy4talARsxIj8ggZ0GAqSNVAgBTumkYzo
3zWxEqPjSatg4zrfWyNaxh26oO0vdcWBl6jNqmW9sMuIvXT8uuM8ILQROo9kNDr+sjYWOdp/VMmZ
luaGeDjaccRYX6A2IV/dZWNhU3YP2M6oZqOz5VUb6hIdM9e3xWqgLIOz5PwU7YiQKruzjnofcD5D
K5caQhFW7z74uNwIur0G524TqTZeUIvMZVnK3tSGhizlyYvVLmzZXdwSefLoTNCl/GT1Ywm32YFf
g/23p8Wmb4Lv0xDz9dLgnsJqjdrOuKvaFkMBOzarC2b7/aa7FugCkV/M9feEr2CC3j4u6ynj9n5i
vY5mFLuGQ/hgXYN5gQ/Af8rKfgWKmEOK1PCoFEOmu92iSAt+i7zoNDkLD+kBEMKmbx6Dw8qZk+8U
SRbLhOTKM2quLSPFOspy1wLjWS5qRJevrWRrm6T4F1BLAwQUAAAACAAstrkwUapEBz8FAAAMDQAA
DQAAAHNodWZmbGVfbGliLmOFVllvGzcQfo5+xUAPheRKsuQcCOK4QFsUrYHAKZIUQV9qULuzEmEu
ueUhWQ3y3ztDcnd1Gd4HGyLn4jffHJcXA7gAtw5VpfBeyeWs4INfTbOzcrX2cDWfX03pzytY7uAX
qRR8RecriaokQZb9WYNQK2OlX9dQGQuNNWUopF6BACt0aWpw+G9AXSBUln7dgfRYOwiOhWqpZS1U
jMMbK1YIo5dXsJTejQG+rLHX3rJ/bTxYbFD4ZGYCy+ChEBqWmC+wZGtmg1aQwnKXPXm2JWo2iKUD
Cg1MVTn0bkbyl4NBQkNqj1YL1YbDj2LdFqb+uSTNATo6snQdmsY4LMEbDmXxJr4BUBTra3hAbMgj
4A7BaNiZYKEwdSMV2uTdeeFlAUE7udJYkjdjfQTQ4uoa4nfJuZIVA7CSjsKEPz/dxec8baFBWwe+
Mfq+MJqEtL+Optpf/MB9MbbVgtE4DKVJaaTf5NgHqyMcGh99vp/mPOtQLymoEUU1zqALgpEuhS2h
Fo+yDjWwHYV65dfwaOy0ovCXonggxKaE2NELZwlk6bJrx76zo0SnBQP+5vXrl68pdeSvko9YRlKI
pqHEaK92ZOSYizOAO0O5aI1l7rjocBQ9yuRs2L5gCEpqFPY4CVuZngLtUzgt15GDpJ+StEJNdCRG
OcI9qJIpEogts/HT2T9An/g02hhZjgffBkSFY1GNWwbvBubXg3gvKxhl9sANHY+B9PLXncPiOh5+
P1H5AeaPb+dzUkuWW9lTqVf7Uv88KbZIYs+JkdTbU7E+4l76/XtYjOHHLBvFMke6qhl8zzzu6I2p
wsHYkhLjTZsXhDooLxuFGfSeLRiILS5xTQCTWrGVlvpHghPYIiVKWCmWajeG0pDS4t0CamIj6VLL
iaSqpHWezERyeBIiC1SQJf3zRM3PYemtKGI5bo19cKSgybhw9JPpI8pS8u2EiTdhQxRH5hu1ISeX
UpEARj4/1xso4qMbqZvgI9V6VEfxEKZnW8qYwWa0u++577kvz5cvDJZRymwZvYowZr+OW24EEh9T
u1Y72Eh6tsLUwStRkIBhGTJz2rwZl+577nvu6+dHP01prvn0Bs5pjLUFy8XSp8m0P1fK3Ij6VjHL
6reMu3t3kj2r72Pvn0Yz7E/S2NoIFbqhddh72Fj+SPzMbCBTvTqdeEvIE+77kjmo0d8m8NglL1I/
ZFo7CiMGS3VSN2rHfPVbQwA0giLIo5f4/YfZ4gYTcaFYC72KtaFVhKR/Wi12RD9HtUmGu97NfZnm
fxkaJQvh6TeZ946NUSCpCjphcjeK4tJNqN3w7E0esfPXjdEJDBfDuGdEW1Sy3O7ZlawqtMiYKcEB
yDgEOydpC/H7XG3T2VtTW7Fz1Pi7TSQ2f777GHxKsabYSTdn/nLAHf+AUTB6ggWTsxlta7hvoJ1C
6piXF/FfjOFoUuV9i/LULnUI/6E13VsPloavtx8+tKaCpu5Kb7E18bGQtgg18T7lAn7TLlhMGdxi
i8pabGjSJpVs5lBzyOVSSicyvDGU2WyWhS+7aXICQRp/gxdnLtr5cq6l0fXpcexyx5XOm9CItpsx
H/4uN6j3lxRTtYtqI4sHatN7e0m7lAzZRBSbDdnIX7xTnl+uRFpKlsLJgjRSqmJKuKl0RE2z5eOn
L7cf7z7n6nxyZAmeOw+yicWfqys2WBPYDqtbLpi2IX1Kq1gU72ohibDsfDZjOKaLceqLh4w9gI2H
iufN8Pxak2s/rTQ8S78NXsSj/eTg6HBPGo3HeauB7VoqGm5Z5aeb6OlgVYhXMa3/A1BLAwQUAAAA
CAAstrkwMotUgp0CAABsBQAADgAAAHNodWZmbGVfdGVzdC5jhVNRb9MwEH6Of8WpaFPadVs7tqeu
SMADICF4AImXSZUTXxqL2C62s65M++/cOUm7DiEsq6rj7/vu7rvz5UTABL7VbVU1uIoY4kXJX967
zc7rdR3haja7Oqefayh28E43DfwgVKWxUQRk7FsLslk7r2NtoHIeNt6pttR2DRK8tMoZCPirRVsi
VJ5OX0BHNAHawCCjrTayYakQnZdrhPz1FRQ6hjHA9xoP7C3Hty6Cxw3K2MlMoWgjlNJCgf0FKlZz
9+glEYpdHymyljQsiCoApQauqgLGcNHVQtF0ANoSFBpnQ/Qyame5pLWXhhQoKj6U6EsdMCTFRhde
+h1oC6EzMnl4KYR4pW3ZtArhNkSl3UX9Rgh8iOgttDbotUVFHOfjwFxZus61jWDkw3gxgO+dVnsI
2RXzYzrlZ1dc1JSyoBN608aU+arkKqSNJCZE0uEuQz4WjwJoMV4vsizjw+UEPju3gdK1lgJTEXtM
7bZG2t1iD/zotsBfwLamQE9euCHFnveyRm/VgT6KZPWon4+kcRSvb8yUW3VgdY3jIUvOr9EiNcgl
YmIqB48io6nOYEIyGxoMJaNkxnFHCUCcbOMpVpWP+uqmR2Hv7IhcywKNFkFOFKQ9msLpHn464E+Z
wGhdQd5fw+0SZmORci88yp8Lsc/tEzVRy0b/Rq5kb5zBspZWB9Pnd9RzDjFkOH6m9QFjmuVUTJLz
/GBCpJnvnSXWEEMNDXthwZ0d0l5SlVPK+WuK1B85OP9lV6ZE7dZfvg02sOG5Xs4WoOF2gNHh7GwM
jx3dWxI8HvweRwIJMaR2ckOuM364YJM1nMD8BpZLmF8nzWeVjAbgk8hov7g4HM//sf637mwnlULA
ttbUunxOH56EMFLb/fNKjy3vLv4AUEsDBBQAAAAIACy2uTAnbZBSHwIAAPwFAAAPAAAAc2h1ZmZs
ZV9sb2cudHh0hZRNj5swEIbv/hWjlXJjqW0wJJH20ktP/VDbW7WqWDABLbFTMO3uv69nEGZTleBI
r8aeseN5ZvC3sm8vDgZX9E5XYA18HzV8LF5BKhDZUSVHpUBynrLRtC9iB6eyhKEZ67rTP50eXLxM
u/bJz+7tlZ/2yR3E765W2Y+hOF86Df1oHhlr7J9zYV4jsHU9aBfBoHXFJAcBInjhwd8kAoDPFOSn
YgpEi4EfAiVByXGWoSgUjiJRUhTyHjBujxYKpCi0ljFcpGMkCp1AR3PG7lfG1vAZl01hTq05gWs0
fPn66cN0eVrWA0xVQP/FDq1rrYngaXRgrPOBv0ZtSh0DvLeuYT627ToorXFFa0D4pHOfr8/W5xrH
8eNNohyRbiHFMKKxCuOK+BZxtop8Ybo1tphedH8eXYHoEI3naRyc2t8ebgHnsWygauta99osRG82
H7/dffyf9ssnXphfgJaEfiOHCgR46DdCRTtSorKgkgEnbZE3UW2hqm0PhbEeVA/6xX99Opq/VI/n
rtLlsycAZdFXw53voVUySvqrJCmoLN+/xaPkWzwUMwOaYjE5iSJCCyy9ckCHCqBQJErC0bGf+UqB
U2onFSgnRJ4CaXNyRVSGZkvC15/S33FcSxiqnAuT0oEC92GM4mjlcyHSdK6LpLhsanNUnCqGHonm
AS0qN1l0DN1hv17FrbFWEQ7+Ry9tsmPD9KZX1uj/POjqKLLpQf8LUEsBAhQDFAAAAAgAK7a5MKpZ
siJqBAAAxQgAAAsAAAAAAAAAAAAAAKSBAAAAAHNodWZmbGUudHh0UEsBAhQDFAAAAAgALLa5MFGq
RAc/BQAADA0AAA0AAAAAAAAAAAAAAKSBkwQAAHNodWZmbGVfbGliLmNQSwECFAMUAAAACAAstrkw
J22QUh8CAAD8BQAADwAAAAAAAAAAAAAApIHGDAAAc2h1ZmZsZV9sb2cudHh0UEsBAhQDFAAAAAgA
LLa5MDKLVIKdAgAAbAUAAA4AAAAAAAAAAAAAAKSB/QkAAHNodWZmbGVfdGVzdC5jUEsFBgAAAAAE
AAQA7QAAABIPAAAAAA==

--Apple-Mail-6--483280587
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit

2005\06\23@163625 by Dave VanHorn

flavicon
face

>
>It depends on what you're doing.  Calling the LFSR 8 times does not
>result in an output value that is any less predictable than calling
>it once (and ALL the bits change, even if you've only generated one
>new random bit, so it looks pretty good if you're simulating a flickering
>fire, or generating noise, or something like that.)

Isn't a flicking fire a strange attractor?

2005\06\23@164611 by Wouter van Ooijen

face picon face
> > If you want it to generate for instance a random byte you must call
> > it 8 times, otherwise there will be a very strong correlation
> > between successive bytes.
>
> It depends on what you're doing.  Calling the LFSR 8 times does not
> result in an output value that is any less predictable than calling
> it once (and ALL the bits change, even if you've only generated one
> new random bit, so it looks pretty good if you're simulating a
> flickering
> fire, or generating noise, or something like that.)

That output value "an sich" is indeed not less random than any other
value. In fact it is as random as 0b00000000. Randomness is all about
correlation.

When you call just once and grab 8 bits you will have 7 bits of the
previous value (shifted one position) + one (pseudo) random bit. That
will not look very random when shown on 8 LEDs.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu


2005\06\23@171254 by Peter Onion

flavicon
face
On Thu, 2005-06-23 at 13:17 -0700, William Chops Westfield wrote:
>   Calling the LFSR 8 times does not
> result in an output value that is any less predictable than calling
> it once

If you only call an M bit LFSR  once next value V(N+1) be

EITHER

V(N+1) = 2 V(N) + 1 mod 2^^M

OR

V(N+1) = 2 V(N) + 0 mod 2^^M

So there's only 1 bit of randomness.  You do need to call it P times to
get P random bits.

Peter

2005\06\23@183940 by olin piclist

face picon face
Michael Rigby-Jones wrote:
>> Some time last week I was thinking about randomness and such
>> and I came up with an idea. I haven't had time to research it,
>> but I do find it intriguing. What if you took two separate
>> oscillators (possibly drifty RC oscillators with widely
>> different tempcos) and fed them into a shift register -one as
>> data the other as clock. Since they're not directly related to
>> each other, their relative phase will continually drift -
>> producing a continuous stream of uncertainty on the shift
>> register.
>
> The relative frequencies of the two oscillators will have a constant
> frequency difference in the short term so the output bit stream will be
> very predictable and most unrandom IMHO.

Short term is OK if it's used as an external perterbation of a digital
random number generator.  Imagine the reverse.  What would it take to create
a 1/0 digital stream using analog oscillators that is accurate enough to
cause even an 8 bit CRC to repeat consistently?  What about a 16, 24, 32, or
more bit CRC?  You couldn't design such a system even with atomic clocks,
and a CRC is pretty simple to compute in a PIC and only requires 4-8 bytes
of state.

The more state and therefore longer repeat sequence (assuming a reasonable
algorithm) of the digital random number generator, the less often it needs
an external random input to make the output indistinguishable from a truly
random 1/0 stream.

I'd be more worried that the two analog oscillators might have a little
coupling between them and sync up at a sub-harmonic.  That makes them no
longer two independent events.  Of course, if the PIC oscillator is separate
and not coupled, that can be the second independent clock.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

2005\06\23@184808 by olin piclist

face picon face
Maarten Hofman wrote:
> A simple way I would probably use is to use a compressor, like (g)zip,
> to try and compress the output. The more random the output is, the
> less likely (g)zip will be able to compress it. Apart from that, you
> would want to make sure that a histogram of all the output values
> looks like a reasonably flat line (i.e. all values are equally
> represented).

Another easy quick test is a 2D histogram.  Plot the frequency of occurrence
of sample N versus sample N-1.  In other words, this makes many correlations
from one sample to the next visually obvious.  You might be surprised how
readily many "simple" random number generators fail this test.  It relies on
the pattern recognition processor in your brain.

For example, suppose your random number generator generates random 8 bit
bytes.  Clear a 256x256 monochrome image to black (0).  If the next sample
is 107 and the previous was 49, then increment the pixel value at (49, 107)
by one.  Stop the first time a pixel value reaches 255 (white).  Display
result.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

2005\06\23@185241 by olin piclist

face picon face
Jan-Erik Soderholm wrote:
> A pseudo RNG made up from a shift
> register
> with feedback will never produce two the same
> value in
> sequence, right ?

If the output bit is fed directly as the next input bit, then no.  Both
0....00 and 1....11 will repeat indefinitely.

I believe your statement is correct only if the input bit is the inverted
output bit and the shift register is an odd number of bits long.  Even then
the minimum guaranteed sequence is only 2 values, which is still not very
useful.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

2005\06\23@204520 by Chen Xiao Fan

face
flavicon
face
Thanks a lot for the explanation.

The problem is that I can not afford to call the routine 8 times:
I can only afford to call the routine at most two times.

I am doing this on a 12F629 with 4MHz internal oscillator (1us per
instruction) and my normal loop time can not exceed 125us (with a
filter depth of 8, which lead to 1ms response time for the program).
The fixed loop time is about 70us and I want to generate a delay of
24-52us (20us overhead + 4-32 us of delay) leading to a loop
time of 94-122us ( average 108us). So I have very limited
time to do this.

Regards,
Xiaofan

{Original Message removed}

2005\06\23@205709 by Chen Xiao Fan

face
flavicon
face
Actually this is the first piece of code I checked. Unfortunately
it is too long for me to use. However maybe I can take the
idea of using a table of random number instead of a
generator and generate the random delay time needed.


Regards,
Xiaofan



{Original Message removed}

2005\06\23@215600 by David P Harris

picon face
Chen Xiao Fan wrote:

>Actually this is the first piece of code I checked. Unfortunately
>it is too long for me to use. However maybe I can take the
>idea of using a table of random number instead of a
>generator and generate the random delay time needed.
>  
>
Yes, you can almost always substitute memory for speed, so if you have
room for a table that would work, then you just step through it.

David


2005\06\23@223123 by Chen Xiao Fan

face
flavicon
face
Yes I have more than enough of space (only used up
40% of the space, this is really a simple application)
to do things but not the time.

Regards,
Xiaofan

-----Original Message-----
From: David P Harris
Sent: Friday, June 24, 2005 9:56 AM

Yes, you can almost always substitute memory for speed, so if you have
room for a table that would work, then you just step through it.

2005\06\23@223347 by Chen Xiao Fan

face
flavicon
face
Sorry but I think 3 bit of random number is not
the same as 0-7 and 5 bit of random number is not
the same as 0-31. Do I miss something obvious?

Regards,
Xiaofan

{Original Message removed}

2005\06\23@230842 by Chen Xiao Fan

face
flavicon
face
That is true. The requirement is that every two or three
units (same firmware) will have different pulse sequence
(as different as possible) so that the pulse will not
overlap so much that it defeats the digital filter.

The application is a family of low cost optic proximity
switch sensor (the sensor's emitter sends out a short pulse
of light and check the signal level of the photo diode
receiver to detect if there is a target which blocks the
light path). The digital filter is very simple. If the
signal is above the threshold, it will add 1 to the
filter counter and minus 1 if below the threshold.
Once the filter counter reach 0, the output will be switched
off. Once the filter counter reach 0, the output
will be switched off.

In order to facilitate side by side mounting of two or
more sensors, you need to prevent them from seeing each
other as much as possible (within the limitation of
the optics, the speed of the front end trans-impedance
amplifier and the MCU speed and the creativeness of
the firmware). The solution is to add some random
delay to the pulse period. The pulse width is fixed
by the design of the amplifier (4us here). The minimum
period is limited by the speed of the MCU and the allowed
power consumption. The maximum period is decided by the
filter depth and the response time.

So now the problem is how to generate the random delay
after the fixed processing loop so that each sensor
has a as different as possible pulse period.

I just realized that Timer 1 value and Timer 0 value
is not a good random seed since all sensors will
have the same sequence if powered up at the same time
since I am using the same firmware for them and I
do not want to use a serial number for each sensor.
Maybe the OSCCAL value is a possible candidate.

Regards,
Xiaofan

-----Original Message-----
From: Alan B. Pearce [TakeThisOuTA.B.PearceEraseMEspamspam_OUTrl.ac.uk]
Sent: Thursday, June 23, 2005 5:44 PM
To: Microcontroller discussion list - Public.
Subject: Re: [PIC] Simple pseudo random code generation

>I used the suggestion to generate 1-8 (and with 0x07)
>and 1-64 (0x3F) but somehow it loses quite some randomness.
>I will check the code again.

Don't forget that with so few possible numbers then the result will not
appear to be very random at all.

2005\06\23@235455 by Hector Martin

flavicon
face
2^5=32. So 0-31.
2^3=8. So 0-7.

I.e. for 3 bit:

000 - 0
001 - 1
010 - 2
011 - 3
100 - 4
101 - 5
110 - 6
111 - 7

Chen Xiao Fan wrote:
> Sorry but I think 3 bit of random number is not
> the same as 0-7 and 5 bit of random number is not
> the same as 0-31. Do I miss something obvious?
>
> Regards,
> Xiaofan
>

--
Hector Martin (RemoveMEhectorspamTakeThisOuTmarcansoft.com)
Public Key: http://www.marcansoft.com/hector.asc

2005\06\23@235521 by Chen Xiao Fan

face
flavicon
face
OOPs, that is wrong.

I think Timer 1 value and Timer 0 value
could be used since they are specified as
unknown during startup.

Regards,
Xiaofan

-----Original Message-----
From: Chen Xiao Fan
Sent: Friday, June 24, 2005 11:09 AM
To: 'Microcontroller discussion list - Public.'
Subject: RE: [PIC] Simple pseudo random code generation
...
I just realized that Timer 1 value and Timer 0 value
is not a good random seed since all sensors will
have the same sequence if powered up at the same time
since I am using the same firmware for them and I
do not want to use a serial number for each sensor.
Maybe the OSCCAL value is a possible candidate.

2005\06\24@023511 by Chen Xiao Fan

face
flavicon
face
It is not that simple. :(

If you feed 1 to the LFSR routine, the sequence will
be like 1,2,4,8, 0x11,0x23,0x47,0x8E,0x1C,0x38,
0x71,0xE2,... Just like what Peter Onion mentioned.

So my understanding is that when you call the routine
once, one random bit will be generated. If you call it
three times, 3 random bits will be changed. It is not
that you will get 0 to 2^n-1 when you call it n times.

Regards,
Xiaofan


{Original Message removed}

2005\06\24@034302 by Chen Xiao Fan

face
flavicon
face
I found the following from the PIClist archive
and it claims to be better than Andrew Warren's
LFSR. Why?

Regards,
Xiaofan

;*****************************************
;PRNG 8 bits
;by Nikolai Golovchenko
;Seed RANDOM with a number different to 0
;during initialization.
;This code gives less sequential repetitions
;at edges  (0 to 32, 224 to 255)
;than Andrew Warren's
LFSR:
    CLRC
    RLF     RANDOM, 1
    SWAPF   RANDOM, 0
    ANDLW   0XE0
    RRF     RANDOM, 1
    ADDWF   RANDOM, 0
    ADDWF   RANDOM, 0
    ADDWF   RANDOM, 0
    SUBLW   0X35
    MOVWF   RANDOM
    RETURN

2005\06\24@041458 by Alan B. Pearce

face picon face
>I am using the same firmware for them and I
>do not want to use a serial number for each sensor.
>Maybe the OSCCAL value is a possible candidate.

I would worry that within a single production batch of chips the OSCCAL
value would probably not change much.

2005\06\24@042156 by Alan B. Pearce

face picon face
>I found the following from the PIClist archive
>and it claims to be better than Andrew Warren's
>LFSR.

Probably because it is written by Nikolai.

>Why?

I thought the answer to that is in the past lines of the opening comment.

2005\06\24@043729 by Chen Xiao Fan

face
flavicon
face
You may be correct. But it seems to me that most of them
are actually different. I have used quite some of them.
Anyway I will not use this value as the random seed now.
I am now using the start up value of TMR1L. Do not know
if it is better or not.

Regards.
Xiaofan

-----Original Message-----
From: Alan B. Pearce [A.B.PearceEraseMEspam.....rl.ac.uk]
Sent: Friday, June 24, 2005 4:15 PM
To: Microcontroller discussion list - Public.
Subject: Re: [PIC] Simple pseudo random code generation


>I am using the same firmware for them and I
>do not want to use a serial number for each sensor.
>Maybe the OSCCAL value is a possible candidate.

I would worry that within a single production batch of chips the OSCCAL
value would probably not change much.

2005\06\24@045026 by Alan B. Pearce

face picon face
>>Why?
>
>I thought the answer to that is in the past lines of the opening comment.

                                       ^^^^
Whoops, I meant to say "last lines"

2005\06\24@075315 by olin piclist

face picon face
David P Harris wrote:
> Yes, you can almost always substitute memory for speed, so if you have
> room for a table that would work, then you just step through it.

A good trick to make a large virtual table is to use multiple tables if you
can afford the time.  If each table is a prime number in size, then the
entire resulting sequence is as if it comes from a virtual table the size of
the product of the individual tables.

For example, suppose you used two table, one 19 entries long and the other
17.  The total repeating sequence is 323 long.  The table sizes are roughly
squared at the cost of twice the lookup cycles plus a little to combine the
two table results.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

2005\06\24@081422 by Jinx

face picon face
> For example, suppose you used two table, one 19 entries long and
> the other 17.  The total repeating sequence is 323 long.  The table
> sizes are roughly squared at the cost of twice the lookup cycles plus
> a little to combine the two table results

Can you explain that a little further please

2005\06\24@085103 by Hector Martin

flavicon
face
Chen Xiao Fan wrote:
> OOPs, that is wrong.
>
> I think Timer 1 value and Timer 0 value
> could be used since they are specified as
> unknown during startup.

Don't trust the unknowns. They may be unknown, but that does not
guarantee that it will be a random value. It might as well be 0x00 all
the time, or tend to have the same value always. As long as it is not
0x00 "always", it will be specified as unknown. But it might not be
very random.

--
Hector Martin (EraseMEhectorspammarcansoft.com)
Public Key: http://www.marcansoft.com/hector.asc

2005\06\24@121925 by olin piclist

face picon face
Jinx wrote:
>> For example, suppose you used two table, one 19 entries long and
>> the other 17.  The total repeating sequence is 323 long.  The table
>> sizes are roughly squared at the cost of twice the lookup cycles plus
>> a little to combine the two table results
>
> Can you explain that a little further please

Let's say I have a basic table-based pseudo random number generator.  All it
does is return successive table entries.  These are produced when the code
is written, presumable by a high quality random number generator.  The
result will appear random for any sequence up to the size of the table,
after which it repeats.  All digital pseudo random number generators repeat
due to having finite state.  In this case the state is the table index.
Such table-based random number generators are fast, produce high quality
values over short sequences, and are good enough for many applications.

The big problem of this approach is the relatively short length of the
repeating sequence.  The brute force way to make it longer is to use a
longer table.  Another approach is to in effect use two separate table based
random number generators.  Both generators are run each time you want a new
random value, and the results of both are combined to make the final output.
If each table is a different prime number in length, then the resulting
combined random output will have a repeating length of the product of the
two primes.  If one is 17 entries long and the other 19, then the combined
output will repeat every 17 x 19 = 323 values.  In other words if you start
both table indexes at 0, it will take 323 iterations before both indexes
return to 0 simultaneously.  The cost of this is two table lookups and a
combine.  Note that this can be applied to more tables.  If a third table is
added with 23 entries, then the repeating sequence is 17 x 19 x 23 = 7429
values long.


*****************************************************************
Embed Inc, embedded system specialists in Littleton Massachusetts
(978) 742-9014, http://www.embedinc.com

2005\06\24@125633 by Peter

picon face


On Thu, 23 Jun 2005, Denny Esterline wrote:

{Quote hidden}

Look into chi-squared analysis. Look for a program called ent.exe (by
John Walker) on the Internet.

Peter

2005\06\24@130028 by Robert Rolf

picon face
Unless you have a way to generate a truly random
seed for the PRNG, all units with the same firmware
will have the same 'random' sequence if powered up at
the same time. And regardless of the starting seed,
the PRNG will repeat the exact same sequence so eventually
the sensor sequences will track as their clocks drift
past each other over the long term.

Why do you not want to 'serialize' the units
by having different firmware (or more specifically 'data')
 for each?
It seems that having a different random sequence
in a lookup table for each device would be the simplest
and fastest code execution.

Robert

Chen Xiao Fan wrote:

{Quote hidden}

2005\06\24@141231 by Bradley Ferguson

picon face
On 6/23/05, Dave Tweed <RemoveMEpicEraseMEspamEraseMEdtweed.com> wrote:
{Quote hidden}

Of course, you're right.  I don't know what I was thinking.  That
started out as a straight line/sawtooth, which would have a flat
histogram and not be random.  I just didn't think on that one.

Bradley

2005\06\24@141657 by Peter

picon face

On Fri, 24 Jun 2005, Hector Martin wrote:

>> Sorry but I think 3 bit of random number is not
>> the same as 0-7 and 5 bit of random number is not
>> the same as 0-31. Do I miss something obvious?

The randomness affects the order in which the numbers come out of the
algorythm, not their domain. A 3 bit full sequence random number
sequence is simply a permutation of the vector 0,1,2,3,4,5,6,7 which
repeats indefinitely (and identically).

Peter

2005\06\24@164716 by Ben Hencke

picon face
Wow, this thread is growing!

The problem I saw with any generator is that some patterns show up,
and the sequence is predictable.

Most that I have seen fluctuate from a high values to low values
somewhat predictably. The actual value is pseudo-random, but there is
a noticeable pattern that flip-flops. This is especially true of 8 bit
generators.

To "appear" more random to users, I take 2 different random algorithms
and use them in sequence to generate the output. The first stage must
keep its random register so that you don't get a short feedback cycle.

ie:

keep 2 regs for a 16 bit generator,  store back in first regs to use
as seed for next run.
copy 2 regs to another 2 regs
use a different generator algorithm either a 16 bit or two 8bit on the
2nd stage. in effect use the output of the first stage as the seed for
the second stage.
take the outputs from the 2nd stage. It is pretty random and doesn't
flip-flop noticeably. For my 8bit needs, i xor the results together
for a 3rd stage..

The output appears very random and still has many possible values. for
8 bit values, you are not limited to a static sequence of 255 that
keeps repeating, instead you get a sequence of 65k so it is harder to
predict the next value.

ie given any 8 bit generator, if you get 123 you can always predict
the next number.

With the above method, if you get 123, there are 255 possible values
that would follow. From a byte to byte viewpoint this appears very
random even though there is a larger sequence.

- Ben

2005\06\24@170702 by Dave VanHorn

flavicon
face

>
>ie given any 8 bit generator, if you get 123 you can always predict
>the next number.

What I've done in the past, is to implement something like a 24 bit
LFSR, and only use 8 bits of it.
So, you get the advantage that the next state is not readily apparent
from the current state.
You don't have to take the 8 bits from the same byte either, and you
can invert some of them, or even use an LUT to translate them to
something else entirely, so that the left-shifting isn't apparent.


2005\06\24@174056 by Wouter van Ooijen

face picon face
> What I've done in the past, is to implement something like a 24 bit
> LFSR, and only use 8 bits of it.
> So, you get the advantage that the next state is not readily apparent
> from the current state.
> You don't have to take the 8 bits from the same byte either, and you
> can invert some of them, or even use an LUT to translate them to
> something else entirely, so that the left-shifting isn't apparent.

When you use the LFSR properly (shift at least the same number of steps
as you take bits) the shifting will not be visible.

Wouter van Ooijen

-- -------------------------------------------
Van Ooijen Technische Informatica: http://www.voti.nl
consultancy, development, PICmicro products
docent Hogeschool van Utrecht: http://www.voti.nl/hvu


2005\06\24@181853 by Jinx

face picon face
> > Can you explain that a little further please
>
> Let's say I have a basic table-based pseudo random number generator.  All
it
> <snip>
> added with 23 entries, then the repeating sequence is 17 x 19 x 23 = 7429
> values long.

Thanks

2005\06\24@204016 by Jinx

face picon face
> I think Timer 1 value and Timer 0 value
> could be used since they are specified as
> unknown during startup.

I'd try to work WDT in there somewhere. Perhaps measure it with
a high-precision timer (eg 1/10,00th or 1/100,000 sec) and take
some LSBs. It's the only thing close to analogue/variable in all PICs.
I wonder if those PICs with a s/w changeable oscillator configuration
can use that feature as a seed somehow (eg switch from xtal to RC,
use settling time difference to next WDT ?)

2005\06\25@062412 by dr. Imre Bartfai

flavicon
face
part 1 1041 bytes content-type:TEXT/PLAIN; charset=US-ASCII; format=flowedHi,

attached is an awk script which calculates - under more other statistics -
the relative entropy. The closer is this measure to 1, the higher is the
randomness. E. g. a text has a Hrel=0.75, and a .JPG file Hrel=0.9978.
I hope this helps.

Regards,
Imre

On Thu, 23 Jun 2005, Maarten Hofman wrote:

{Quote hidden}

> --

More... (looser matching)
- Last day of these posts
- In 2005 , 2006 only
- Today
- New search...