[sdiy] Simplest random source

[Magnus Danielson]

From: Seb Francis <seb at is-uk.com>
Subject: Re: [sdiy] Simplest random source
Date: Mon, 18 Nov 2002 01:49:30 +0000

> Hi Magnus,
> 
> I couldn't find too much in the archives ..
> http://www.buchi.de/sdiy/Search1.ASP?914
> 
> And a search on google for PRBS didn't help me too much either.  But I am interested if you can give me a link to a schematic or algorithm.

If you look in the archives either of September 2000 or May of this year you
ought to find plenty written about it. Titles makes it kind of obvious and it
was pretty big-volume stuff at it's time.

> Magnus Danielson wrote:
> 
> > If you look way back in time, you will be able to find a thread about random
> > generators and there I posted PRBS generator polynoms all the way up to 64 bits
> > of length. You will also find me arguing for the use of longer polynomial
> > lengths. Inside a PIC, AVR or anything like it, there is no excuse not to use
> > up the hardware better and go for a long polynomial.
> 
> The question for me would be how many instructions does it take to get a 16bit 'random-enough' number.

Not many. Really depends on the architecture, which funny tricks you play with
arthmetics/logics and exactly which polynomilal you are attempting to realize.

One trick is to wrap them into backward order, same properties, but may be
simpler to implement.

> > You get both cycletimes
> > beyond lifetime of the apparatous and thick noise-spectrum, which you do want
> > That comes hand-in-hand when you go for the longer polynoms. a 64 bit polynom
> > requires only 8 byte of storage and we're still only talking one or two XOR
> > gates, so processing is still fairly simple.
> >
> 
> The previously posted algorithm should be an exact replica of this circuit:
> http://www.analog-synth.de/synths/mod2/trigdiv/dig_noise.gif
> Now this looks very much to me like a long shift register with some XOR taps .. could it be a similar thing?

Yes, long shift register and some XOR taps for the linear feedback term.
It's linear since you are in a Galois field and... no, don't ask!

Cheers,
Magnus