[sdiy] Pseudo randoms in software

[Neil Johnson]

On Thu, 21 Nov 2002, David Hughes wrote:
> My solution was as follows. I wrote a quick noddy program in Javascript to
> produce a series of random numbers in the range of 1..255 using the browser's
> Random() call. I then cut and pasted the browser output into the CodeVision text
> editor and turned the results into a large look up table.

Interesting.  I applied your table idea to the classical
shift-register-based PRBS generator, so as to calculate all random bits in
parallel, rather than serially generating 16 bits of data (can also be
applied to 8-bit data by changing the data type from unsigned short to
unsigned char).  The code is as follows:

----------- CUT HERE ----------------------------------------

#include <stdio.h>

#define LENGTH	(16)
#define TAP(n)	((n+i)%LENGTH)

int main( void )
{
    unsigned short PRBS[LENGTH];
    int i = 0;
    int j = 0;

    for( j = 0; j < 66000; ++j )
    {
        PRBS[i] = PRBS[TAP(4)] ^ PRBS[TAP(13)] ^ PRBS[TAP(15)];

        printf( "%d\n", (int)PRBS[i] );

        i = ( i + 1 ) % LENGTH;
    }
    return 0;
}

----------- CUT HERE ----------------------------------------

The important line is the "PRBS[i] = ... ", which generates all sixteen
random bits in parallel, then stores them in the shift register
(implemented as ring buffer).

The "% LENGTH" does the wrap-around for the buffer/shift-register.  In
practice, "% 16" can be accomplished with "AND 15", so no integer division
is necessary.

Coding this up in PIC or some other assembler shouldn't take too many
lines:
	PRBS calculation:
		three byte additions
		three byte ANDs
		three 16-bit table lookups
		two 16-bit XORs (or 8-bit for narrower numbers)
		one 16-bit table write

	Index increment:
		one byte increment
		one byte AND

If using byte-wide data, then I reckon this could be done in, say, 14
instructions.  16-bit wide data would need a few more instructions to do
the XORing and table accesses.

Oh, and I got the tap info from one of Magbus's emails from some time
back; you should get a maximal length sequence of 65535.

Neil

--
Neil Johnson :: Computer Laboratory :: University of Cambridge ::
http://www.njohnson.co.uk          http://www.cl.cam.ac.uk/~nej22
----  IEE Cambridge Branch: http://www.iee-cambridge.org.uk  ----