Prev: counterphase detection in stereo audio
Next: International Journal of Electronics, Information and Systems (IJEIS) Call for Paper
From: glen herrmannsfeldt on 5 Feb 2010 17:27
Tim Wescott <tim(a)seemywebsite.com> wrote:
> On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote:

>> OK, so is the longest finite run of zeros, one on each end, really n-1?
>> Not so obvious to me, but maybe it is right.

> Yes. Not obvious to me, either, and I can't remember how I know -- a
> proof is demanded here, but I can't supply it off the cuff :-(.

It isn't a proof, but the wikipedia LFSR page gives the whole
distribution. It seems that for a true LFSR (all XOR, no XNOR)
If you count the runs of zeros and ones, half the runs will be one
bit long (it doesn't say 0's and 1's separately), one quarter will
be two bits long, up to a single run of (n-1) zeros and a single
run of (n) ones. That is, that an n bit LFSR will have 2**(n-1)
runs of zeros or ones.

One the other hand, adding XNOR makes it non-linear in the
mathematical sense, though most of the important properties
are still there. Linearity allows for deeper mathematical
analysis than would otherwise be possible. (Math that I
am not very good at doing.)

-- glen
From: glen herrmannsfeldt on 5 Feb 2010 17:38
Rob Gaddi <rgaddi(a)technologyhighland.com> wrote:
> On Fri, 05 Feb 2010 09:51:50 -0600
> Tim Wescott <tim(a)seemywebsite.com> wrote:
(snip)

>> Yes. Not obvious to me, either, and I can't remember how I know -- a
>> proof is demanded here, but I can't supply it off the cuff :-(.

> I might could. Start by keeping in mind that the next N bits that
> you're going to get out of an LFSR are the N bits currently loaded; all
> of the results of the feedback are injected at the very beginning, and
> so you won't start seeing them until N+1.

To do that, you have to be able to see the equivalence of the
Galois form (see the wikipedia entry) and the Fibonacci form.

The equivalence is there, but the math is less than obvious to me.
The Fibonacci form has a shift register with input the XOR of
some of the taps. The Galois form is the form you implement
in software with bitwise XOR operators, or in hardware feeding
the output of the shift register to XOR gates between some of
the FF's.

> All zeros is the hang state, so clearly if you emit N zeros
> you've hung; game over. Therefore the maximum finite number
> of zeros you can get is the maximal run that can be present
> on the register, which is a one as far away from you as possible
> (beginning) followed by N-1 zeros.

It seems, though, that the maximal run (one each) are (N-1) zeros
and (N) ones for the linear form. For the non-linear (with XNOR)
where the all zeros state isn't the hang state, then N zeros
could occur. I don't know about even more non-linear versions.

-- glen
First  |  Prev  | 
Pages: 1 2 3 4 5 6 7 8 9
Prev: counterphase detection in stereo audio
Next: International Journal of Electronics, Information and Systems (IJEIS) Call for Paper