> 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.