On Sun, 31 Jan 1999 22:08:31 -0500 dave vanhorn <dvanhorn@CEDAR.NET>
writes:
>>Generating a Random Number
>>
>>             copyright, Peter H. Anderson, Dept of Electrical
>>Enginnering,
>>             Morgan State University, Baltimore, MD 21239, August 9,
>'97
>>
>
>
>This is a broken implementation of a PN generator. The need for a trap
>for
>the all zeroes condition tells you that it's broken. In a good
>implementation, unless you start it at all zero, it will never get
>there on
>it's own.


>The hack to keep it from locking, also shortens the sequence. :(

It shouldn't unless the sequence generator (bits that are xor'd) is
wrong.  Normal operation will not allow the register to shift to all zero
unless it starts at all zero.  Generators that give maximum length are
given in reference texts (I think Lin and Costello's _Error Control
Coding_ has a page of them).   I don't know offhand if the one given is
correct.

The possibility of locking up at all zero is a normal property of any
linear feedback shift register regardless of the implementation.

The author's xoring process can be optimized *a lot*.  This code or some
variation would work:

;Use RAND_HI.7 to accumulate new bit (RAND_HI.7 xor RAND_HI.6 xor
;  RAND_HI.4 xor RAND_LO.3
        movlw   h'80'
        btfsc   RAND_HI,6
        xorwf   RAND_HI,f
        btfsc   RAND_HI,4
        xorwf   RAND_HI,f
        btfsc   RAND_LO,f
        xorwf   RAND_HI,f

        rlf     RAND_HI,w       ;Get new bit into C
        rlf     RAND_LO,f
        rlf     RAND,HI,f

It helps to choose a register length so the generation of the sequence
only requires xoring two bits.  That leads to shorter xoring code, but
may require more RAM to hold the register.  One classic example is a
17-stage register with stages 14 and 17 xor'd to produce the new bits.

An important point not mentioned in the description is that each call to
"random" only gennerates one new psuedo-random bit.  If you use more than
one bit of the registers as the result, the resulting numbers will be
correlated to each other.  For example, if you use the low 3 bits and a
value of 011 occurs, the next value can only be 110 or 111.  To prevent
this, call "random" n times, then isolate n bits fromt he register to use
as your random number.


___________________________________________________________________
You don't need to buy Internet access to use free Internet e-mail.
Get completely free e-mail from Juno at http://www.juno.com/getjuno.html
or call Juno at (800) 654-JUNO [654-5866]