Scott Seidman <namdiesttocs@mindspring.com> wrote in news:Xns981899D412A01scottseidmanmindspri@130.133.1.4:> Jerry Avins <jya@ieee.org> wrote in news:GIOdneiE98-G5ErZnZ2dnUVZ_v- > dnZ2d@rcn.net: > >> Scott Seidman wrote: >> >>> Oops-- missed the 8-bit part. Sorry. >> >> We're evidently on the same page. տ� >> � >> Jerry > > > I suppose you can run eight of these guys and seed them separately, but > there would be some concerns. Still, a great way to get a pseudo random > bit stream, but that's about it. >Now that I think about it, you could shift in 8 bits of the output to a single with bit sets, and use that, dump it, shift in 8 more bits .... -- Scott Reverse name to reply
8 bit white noise algorithm
Started by ●August 4, 2006
Reply by ●August 7, 20062006-08-07
Reply by ●August 7, 20062006-08-07
Scott Seidman wrote:> Scott Seidman <namdiesttocs@mindspring.com> wrote in > news:Xns981899D412A01scottseidmanmindspri@130.133.1.4: > >> Jerry Avins <jya@ieee.org> wrote in news:GIOdneiE98-G5ErZnZ2dnUVZ_v- >> dnZ2d@rcn.net: >> >>> Scott Seidman wrote: >>> >>>> Oops-- missed the 8-bit part. Sorry. >>> We're evidently on the same page. տ� >>> � >>> Jerry >> >> I suppose you can run eight of these guys and seed them separately, but >> there would be some concerns. Still, a great way to get a pseudo random >> bit stream, but that's about it. >> > > > Now that I think about it, you could shift in 8 bits of the output to a > single with bit sets, and use that, dump it, shift in 8 more bits ....Knuth writes that even that has some flaws, but I don't remember why. Probably good enough for noise, though (but watch zero mean). Except for memory access, it's hardly slower in software to shift 8 registers once, than 1 register 8 times. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 7, 20062006-08-07
Martin Eisenberg wrote:> Jerry Avins wrote: >> Scott Seidman wrote: > >>> I've always like the linear feedback shift register approach. >>> It's dirt simple to implement with simple bit ops. See >>> http://en.wikipedia.org/wiki/Linear_feedback_shift_register >> According to Knuth, the bits _within_ the SR aren't very random, >> even though successive _output_ bits exhibit little correlation. >> An SR is nice, but you need to advance it once for each output >> bit. Running parallel SRs of different characteristics is a good >> hardware speedup, but does nothing for a single processor. > > It may do something when the processor has multiple execution units > and/or deep pipelines, no?I should have written "execution unit" where I wrote "processor". Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 7, 20062006-08-07
Jerry Avins wrote:> Scott Seidman wrote: > >> Oops-- missed the 8-bit part. Sorry. > > > We're evidently on the same page. տ� > � > JerryI'd start with a 9 bit algorithm, then dither and quantise it down to 8 :-) Steve
Reply by ●August 8, 20062006-08-08
"Scott Seidman" <namdiesttocs@mindspring.com> wrote in message news:Xns981899D412A01scottseidmanmindspri@130.133.1.4...> Jerry Avins <jya@ieee.org> wrote in > news:GIOdneiE98-G5ErZnZ2dnUVZ_v- > dnZ2d@rcn.net: > >> Scott Seidman wrote: >> >>> Oops-- missed the 8-bit part. Sorry. >> >> We're evidently on the same page. տ� >> � >> Jerry > > > I suppose you can run eight of these guys and seed them > separately, but > there would be some concerns. Still, a great way to get a > pseudo random > bit stream, but that's about it. > > -- > Scott > Reverse name to replyFrom the header of a function I wrote many years ago: /* ** ** RandLP.c ** ** Being a C implementation of a random number generator described ** in a 1973 paper by T. G. Lewis and W. H. Payne: ** ** "Generalized Feedback Shift Register Pseudorandom Number Algorithm" ** ** Journal of the ACM, Vol. 20, No. 3, July, 1973, pp 456-468. ** */ What Lewis and Payne did was transpose the LFSR's shift register so that instead of running horizontally across a byte or word, it runs vertically down an array of your choice of byte, short, integer, long, etc. They initialized the arrays with data that was as uncorrelated as possible, but then processed all the shift registers using the same polynomial. This allowed them to produce sequences of PRNs with extremely long periods in whatever widths they needed. In effect, they are running many LFSRs in parallel. The LFSR sucks for certain applications such as cryptography because one only needs something like 2n+1 points (n is the order of the polynomial) to model and predict all future outputs. It does have certains charms for people who aren't willing to expend the effort to do the job right. Since the OP has failed to describe what he really needed, you can assume whatever you want when proposing a solution.
Reply by ●August 8, 20062006-08-08
John E. Hadstate wrote: ...> The LFSR sucks for certain applications such as cryptography > because one only needs something like 2n+1 points (n is the > order of the polynomial) to model and predict all future > outputs. It does have certains charms for people who aren't > willing to expend the effort to do the job right.As you implied exceptions when you wrote "some", I suppose you'll agree that it's perfectly adequate for some applications.> Since the OP has failed to describe what he really needed, > you can assume whatever you want when proposing a solution.Since the OP has failed to describe what he really needed, you can probably sell him anything reasonable. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●August 8, 20062006-08-08
John E. Hadstate wrote:> The LFSR sucks for certain applications such as cryptography > because one only needs something like 2n+1 points (n is the > order of the polynomial) to model and predict all future > outputs. It does have certains charms for people who aren't > willing to expend the effort to do the job right.What is the right way to do the job? I've never found a form of pseudo random generation that doesn't some day waste lots of my time investigating something that turn out to be a quirk of the generator.> Since the OP has failed to describe what he really needed, > you can assume whatever you want when proposing a solution.I assume he probably doesn't know exactly what he needs. Steve
Reply by ●August 9, 20062006-08-09
"Steve Underwood" <steveu@dis.org> wrote in message news:ebbi75$dlb$1@home.itg.ti.com...> > What is the right way to do the job?As I suggested above, take any vetted, modern block cipher algorithm: DES, 3DES, AES, Skipjack (designed for embedded implementations), Twofish, Blowfish, IDEA, there are more. Key the cipher with the key of your choice (since security is not a concern, key management is not a concern). Create a multi-byte counter the same size as the cipher's block. Encrypt the counter and get a set of pseudo-random bytes. Each time you run out of bytes, increment the counter and encrypt again.> I've never found a form of pseudo random generation that > doesn't some day waste lots of my time > investigating something that turn out to be a quirk of the > generator.The nice thing about this approach is you don't have to take the word of some bozo on USENET. You've got the NSA to back this one up. There are proofs of security behind it. To this point, security has not been mentioned as a requirement, however, security is based to a large extent on the guarantee that you can't predict the next byte with any probability greater than sheer guessing (1/256) no matter how much history you have available. This is not true for streams generated by LFSRs or LCGs. There are PRNGs, and then there are crypto-quality PRNGs. As a practical matter, you're not going to distinguish a crypto-quality PRNG from random white noise in trillions of years, no matter how much computing power you have. As an aside, some "generator quirks" are really the result of the observer not having a good understanding of the properties of random sequences.
Reply by ●August 9, 20062006-08-09
John E. Hadstate wrote:> "Steve Underwood" <steveu@dis.org> wrote in message > news:ebbi75$dlb$1@home.itg.ti.com... >> What is the right way to do the job? > > As I suggested above, take any vetted, modern block cipher > algorithm: DES, 3DES, AES, Skipjack (designed for embedded > implementations), Twofish, Blowfish, IDEA, there are more. > Key the cipher with the key of your choice (since security > is not a concern, key management is not a concern). Create a > multi-byte counter the same size as the cipher's block. > Encrypt the counter and get a set of pseudo-random bytes. > Each time you run out of bytes, increment the counter and > encrypt again. > >> I've never found a form of pseudo random generation that >> doesn't some day waste lots of my time >> investigating something that turn out to be a quirk of the >> generator. > > The nice thing about this approach is you don't have to take > the word of some bozo on USENET. You've got the NSA to back > this one up. There are proofs of security behind it. To > this point, security has not been mentioned as a > requirement, however, security is based to a large extent on > the guarantee that you can't predict the next byte with any > probability greater than sheer guessing (1/256) no matter > how much history you have available. This is not true for > streams generated by LFSRs or LCGs. > > There are PRNGs, and then there are crypto-quality PRNGs. > As a practical matter, you're not going to distinguish a > crypto-quality PRNG from random white noise in trillions of > years, no matter how much computing power you have. As anThis greatly overestimates the quality of these algorithms. Most crypto algorithms only achieve high security when used in a rolling mode, initially seeded with something truly random. Most computers these days have a random generator based on genuine sources of entropy. The generator cannot generate numbers quickly, but it is adequate to generate an initial seed for a crypto stream. Without that, most crypto is breakable in a realistic time.> aside, some "generator quirks" are really the result of the > observer not having a good understanding of the properties > of random sequences.True, but I was referring to things like LCGs. In a commonly used one the LSB goes 1,0,1,0 forever. More subtly, in some, bit X of every Yth sample is always zero. Most fast PRNGs have some kind of pattern things going on, though most are less obvious than the 1,0,1,0 thing. Regards, Steve
Reply by ●August 10, 20062006-08-10
"Steve Underwood" <steveu@dis.org> wrote in message news:ebe1el$v9$1@home.itg.ti.com...>> There are PRNGs, and then there are crypto-quality PRNGs. >> As a practical matter, you're not going to distinguish a >> crypto-quality PRNG from random white noise in trillions >> of years, no matter how much computing power you have. >> As an > > This greatly overestimates the quality of these > algorithms. Most crypto algorithms only achieve high > security[snip rest of bullshit] Mr. Underwood, You are holding forth on a subject about which you obviously have no expertise. I suggest you spend a decade or so in the study of this subject. You may find the effort both illuminating and rewarding.
