Pseudorandom Bitstreams

Pseudorandom Bitstreams

Post by Achim Gra » Fri, 01 Feb 2002 05:28:02



Hello,

I'm looking for a) any information on the creation of pseudorandom
bitstreams with a predetermined density of 1's or 0's. Preferably a
method would allow to construct several uncorrelated bitstreams with
different densities. I only need low densities (but with good
resolution), the band in the middle which I already know to be prone
to patterning is not of much interest. Now for b) which is an m
efficient implementation in an FPGA for high clockrates in the MHz
range.

If you have any leads or ideas, thanks in advance.

Achim.

 
 
 

Pseudorandom Bitstreams

Post by TTK Cia » Fri, 01 Feb 2002 07:34:39



Quote:>   Date: 30 Jan 2002 12:28:02 -0800

>I'm looking for a) any information on the creation of pseudorandom
>bitstreams with a predetermined density of 1's or 0's. Preferably a
>method would allow to construct several uncorrelated bitstreams with
>different densities. I only need low densities (but with good
>resolution), the band in the middle which I already know to be prone
>to patterning is not of much interest. Now for b) which is an m
>efficient implementation in an FPGA for high clockrates in the MHz
>range.

  Look into Linear Feedback Shift Registers (LFSR).  They have been
long popular on FPGA's for their low gate requirements and bitstream
determinism, used as either reproducible pseudorandom bit generators
or as alternatives to numeric counters.

  Given an output stream (or significant fraction thereof), you can
mathematically calculate the LFSR seed and mixing function which
will generate that output stream.  It should be possible to calculate
a seed + mixer which will generate a specific ratio of 1's and 0's.

  -- TTK

 
 
 

Pseudorandom Bitstreams

Post by Terje Mathise » Fri, 01 Feb 2002 18:20:43



>   Given an output stream (or significant fraction thereof), you can
> mathematically calculate the LFSR seed and mixing function which
> will generate that output stream.  It should be possible to calculate
> a seed + mixer which will generate a specific ratio of 1's and 0's.

I don't believe this is possible, not using unbiased operations (shifts
and xor)?

It seems to me that you would need some kind of post-processing step to
intentionally bias the outputs!

Terje

--

"almost all programming can be viewed as an exercise in caching"

 
 
 

Pseudorandom Bitstreams

Post by Peter Dickerso » Fri, 01 Feb 2002 18:54:39


If ine uses a LFSR and compare the result against a programmable register
( less than) shouldn't the density be the ratio of the register value to the
LFSR max value (or some subset if less bits are used for the comare)?

Peter



> >   Given an output stream (or significant fraction thereof), you can
> > mathematically calculate the LFSR seed and mixing function which
> > will generate that output stream.  It should be possible to calculate
> > a seed + mixer which will generate a specific ratio of 1's and 0's.

> I don't believe this is possible, not using unbiased operations (shifts
> and xor)?

> It seems to me that you would need some kind of post-processing step to
> intentionally bias the outputs!

> Terje

> --

> "almost all programming can be viewed as an exercise in caching"

 
 
 

Pseudorandom Bitstreams

Post by Rob Warno » Fri, 01 Feb 2002 19:53:23


+---------------
| I'm looking for a) any information on the creation of pseudorandom
| bitstreams with a predetermined density of 1's or 0's...
+---------------

You should probably re-ask this question on "sci.crypt". There are a
bunch of people with the particular kind of math skills you need that
hang out there. E.g., look at the recent threads on "Perez unbiasing".
What you're asking for sounds like doing the reverse of such unbiasing,
actually...  ;-}

-Rob

-----

SGI Network Engineering         <http://www.meer.net/~rpw3/>
1600 Amphitheatre Pkwy.         Phone: 650-933-1673
Mountain View, CA  94043        PP-ASEL-IA


 
 
 

Pseudorandom Bitstreams

Post by Nick Maclar » Fri, 01 Feb 2002 20:37:19




|> +---------------
|> | I'm looking for a) any information on the creation of pseudorandom
|> | bitstreams with a predetermined density of 1's or 0's...
|> +---------------
|>
|> You should probably re-ask this question on "sci.crypt". There are a
|> bunch of people with the particular kind of math skills you need that
|> hang out there. E.g., look at the recent threads on "Perez unbiasing".
|> What you're asking for sounds like doing the reverse of such unbiasing,
|> actually...  ;-}

Also sci.math.stat.  It is a well-studied problem with known
solutions.

LSFRs have known, serious, problems but have advantages as well.
So do multiplicative congruential generators.  So does every other
known, good, method of generating pseudo-random numbers.

The problem with 'true' random numbers (noisy diodes etc.) is to
clean the data up enough to get true independence.  A balance of
probabilities is easy - just generate a pair of bits, ignore two
ones or two zeroes and map {0,1} and {1,0} to 0 and 1.  That is
probably what "Perez unbiasing" does, by the sound of it.

To generate a predetermined, non-uniform density, just filter the
output using any one of the known techniques.  They will vary
with how fixed the proportion is (i.e. setup time etc.) and how
you want to implement it.

If you aren't too woried about performance, you can convert enough
bits to a fixed-point number and compare that against your proportion.
This is trivial to implement, of course, but will waste a lot of bits.

There are much more efficient methods, but you need to juggle
probabilities to work them out.

Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QH, England.

Tel.:  +44 1223 334761    Fax:  +44 1223 334679

 
 
 

Pseudorandom Bitstreams

Post by TTK Cia » Sat, 02 Feb 2002 05:07:52



>   Date: Thu, 31 Jan 2002 10:20:43 +0100


>>   Given an output stream (or significant fraction thereof), you can
>> mathematically calculate the LFSR seed and mixing function which
>> will generate that output stream.  It should be possible to calculate
>> a seed + mixer which will generate a specific ratio of 1's and 0's.

>I don't believe this is possible, not using unbiased operations (shifts
>and xor)?

  Considering that an LFSR can be calculated from a fraction of
its output, then at the very least it is possible to synthesize an
output with the desired ratio, and then calculate the appropriate
LFSR.  But it should also be possible to calculate an appropriate
LFSR without first synthesizing its precise output stream (and it
should be noted that not all small output streams map to a small
LFSR).

  It is definitely possible for LFSR's to generate biased output
using unbiased operations.  Consider, for instance, the degenerate
case of a two-bit LFSR, whose output/replacement bit a function of
the XOR of both bits, and the initial value of the LFSR is "00".  
It will generate an output stream of all "0"'s.

Quote:>It seems to me that you would need some kind of post-processing step to
>intentionally bias the outputs!

  That's possible, if the math is impractical to implement in his
technology.  Such a post-processing step would not even necessarily
be very complex.  Simply taking two bits from a "square" LFSR (or,
if speed is more important than complexity, one bit from each of
two square LFSR's) and AND'ing them together will generate 25% 1's
and 75% 0's.  More precise ratios could be obtained by extracting
multi-bit words of "square" bits and multiplying them together to
get a word's worth of biased bits (the degree of bias would depend
on the lengths of the words).  Depending on his specific needs,
implementing a biasing post-processor may or may not be practical.

  I second the motion that he re-ask his question in sci.crypt,
though.  All that I know about LFSR's was learned in the context of
cryptography, and there are probably other better solutions for his
problem which the crypto guys would know.

 
 
 

Pseudorandom Bitstreams

Post by del cecch » Sat, 02 Feb 2002 11:41:45




> >   Given an output stream (or significant fraction thereof), you can
> > mathematically calculate the LFSR seed and mixing function which
> > will generate that output stream.  It should be possible to
calculate
> > a seed + mixer which will generate a specific ratio of 1's and 0's.

> I don't believe this is possible, not using unbiased operations
(shifts
> and xor)?

> It seems to me that you would need some kind of post-processing step
to
> intentionally bias the outputs!

> Terje

> --

> "almost all programming can be viewed as an exercise in caching"

One could perform a combinatorial operation that would change it.  For
example wouldn't "or"ing two bits together to form the output increase
the density?  Anyway, there are whole books on LFSRs.

del cecchi

 
 
 

Pseudorandom Bitstreams

Post by Paul Hsi » Sat, 02 Feb 2002 13:42:06



> I'm looking for a) any information on the creation of pseudorandom
> bitstreams with a predetermined density of 1's or 0's. Preferably a
> method would allow to construct several uncorrelated bitstreams with
> different densities. I only need low densities (but with good
> resolution), the band in the middle which I already know to be prone
> to patterning is not of much interest. Now for b) which is an m
> efficient implementation in an FPGA for high clockrates in the MHz
> range.

> If you have any leads or ideas, thanks in advance.

Well, just getting some random numbers, you should use one of the
Marsaglia random number generators, but I assume you are up on the
latest in just generic random number generators.

The only issue (that I don't think has been adequately addressed with
the responses this far) is the pickable density that you are looking
for.  I assume in general you just want:

    SampleBit[i] = (RandFloat(0.0, 0.1) > Density);

and that your issue is how do you actually do the above with
reasonable performance.  Obviously for certain special cases its easy:

    Density = 0.25
    SampleWord[i] = RandWord() & RandWord();

    Density = 0.125
    SampleWord[i] = RandWord() & RandWord() & RandWord();
    etc.

    Density = 0.75
    SampleWord[i] = RandWord() | RandWord();

    Density = 0.875
    SampleWord[i] = RandWord() | RandWord() | RandWord();
    etc.

    Density = 0.625
    SampleWord[i] = (RandWord() & RandWord()) ^ (RandWord() |
RandWord())

    Density = 0.1875
    SampleWord[i] = RandWord() & RandWord() & (RandWord() |
RandWord());

    etc.

So in general, starting with x = 0.5, (x*y), (x+y-x*y) and (x+y-2*x*y)
can be constructed.  So if you can approximate your desired density
with this kind of thing to your degree of satisfaction, then you can
generate your random stream in this way.  I'm too lazy to look at this
right now, but it looks like it might be possible to generate any
x/2^n in at most n+1 calls to RandWord().

--
Paul Hsieh
http://www.pobox.com/~qed/

 
 
 

Pseudorandom Bitstreams

Post by Terje Mathise » Sun, 03 Feb 2002 18:25:48




> > I don't believe this is possible, not using unbiased operations
> (shifts
> > and xor)?

> > It seems to me that you would need some kind of post-processing step
> to
> > intentionally bias the outputs!

> One could perform a combinatorial operation that would change it.  For
> example wouldn't "or"ing two bits together to form the output increase
> the density?  Anyway, there are whole books on LFSRs.

This is exactly what I meant.

As several others have suggested, sci.crypt is the proper place for this
kind of question.

Personally, I've written just enough crypto code to be dangerous, i.e. I
know some of the basics, but not nearly enough to avoid the kind of
critical glitch that recently broke the WLAN WEP protocols.

Terje

--

"almost all programming can be viewed as an exercise in caching"

 
 
 

1. JPEG Group bitstream -> JPEG Cosmo bitstream ?

                        Hello, people!

From the Cosmo release notes:

My JPEG bitstreams have been created via the fourth public release
of the Independent JPEG Group's free JPEG software :
release 4 of 10-Dec-92

It is a problem to re-create the JPEG bitstreams with the Cosmo.
(It will take a lot of time - the original data are on the Exabytes
and many other obstacles)

Is it possible to obtain this helpful information and add the SGI APP1
segment to the already existing JPEG bitstream ?

Any information is greatly appreciated!

Thank you,
Gena

--

Technion - Israel Institute of Technology,              fax:    972-4-294353
Computer Science Dept, Technion City,                   voice:  972-4-294528
Haifa 32000 Israel

2. access-list filters IP classes question ?

3. Is Bitstream Letter Gothic on Bitstream 500 CD?

4. apache ssl on NT

5. Converting Bitstream Fontware to Bitstream Facelift.

6. Clustered Servers Crashing HELP!!!!!

7. JPEG Group bitstream -> JPEG Cosmo bitstream ?

8. !Job: Software Windows NT Developer -TX-AUS (recruiter)

9. Random VS Pseudorandom

10. Generating Pseudorandom Numbers

11. Need help in producing a PN (pseudorandom noise) sequence

12. Pseudorandom-number generator