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 |