PN SEQUENCE (zero values)
in [DSP]
|
Prev: counterphase detection in stereo audio
Next: International Journal of Electronics, Information and Systems (IJEIS) Call for Paper
From: Tim Wescott on 5 Feb 2010 02:32 On Thu, 04 Feb 2010 23:22:42 -0500, Jerry Avins wrote: > glen herrmannsfeldt wrote: >> Tim Wescott <tim(a)seemywebsite.com> wrote: (big snip regarding LFSR, the >> stationary state, and how to get out of it.) >> >>> Or 'clearly very bad'. >> >>> It is a whole lot more gates than a plain ol' LFSR -- see my counter >>> idea for something that is (probably) fewer gates, and works >>> (probably) similar to your pipelined idea. >> >> Now I wonder how many zeros in a row can be generated by an N bit LFSR. >> >> -- glen > > n-1? > > Jerry Or infinite, depending on how you initialize it... -- www.wescottdesign.com
From: glen herrmannsfeldt on 5 Feb 2010 05:45 Tim Wescott <tim(a)seemywebsite.com> wrote: > Or infinite, depending on how you initialize it... and how you power it. Solar powered on a satellite might be best. 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. -- glen
From: Tim Wescott on 5 Feb 2010 10:51 On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote: > Tim Wescott <tim(a)seemywebsite.com> wrote: > >> Or infinite, depending on how you initialize it... > > and how you power it. Solar powered on a satellite might be best. > > 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. > > -- glen 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 :-(. -- www.wescottdesign.com
From: Rob Gaddi on 5 Feb 2010 12:14 On Fri, 05 Feb 2010 09:51:50 -0600 Tim Wescott <tim(a)seemywebsite.com> wrote: > On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote: > > > Tim Wescott <tim(a)seemywebsite.com> wrote: > > > >> Or infinite, depending on how you initialize it... > > > > and how you power it. Solar powered on a satellite might be best. > > > > 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. > > > > -- glen > > 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. 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. -- Rob Gaddi, Highland Technology Email address is currently out of order
From: robert bristow-johnson on 5 Feb 2010 12:21
On Feb 5, 10:51 am, Tim Wescott <t...(a)seemywebsite.com> wrote: > On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote: > > Tim Wescott <t...(a)seemywebsite.com> wrote: > > >> Or infinite, depending on how you initialize it... > > > and how you power it. Solar powered on a satellite might be best. > > > 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. > > > -- glen > > 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 :-(. remember there are two ways of implementing this. the method that seems easier for software is to test the bit that falls off the edge and if that bit is 1, then XOR the register with the "magic bits" (the top N bits of an Nth order primitive polynomial). the method that would be easier for hardware is to XOR together selected taps from the shift register (which taps to draw out match the 1's in the "magic bits") and from that single bit that remains, that gets shifted into the shift register. proving the two methods are equivalent is something i have done about the same time when i was investigating these MLS's 25 years ago. but once that is proven, it should be pretty obvious because the shift register has a single bit getting shifted in and is otherwize unmodified. it must *alway* have at least one bit that is non-zero and, if it is an MLS, must have 2^N - 1 states. one of those states will be 100000000000 (or 00000000001). r b-j |