On Thu, 04 Feb 2010 23:22:42 -0500, Jerry Avins wrote:> glen herrmannsfeldt wrote: >> Tim Wescott <tim@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? > > JerryOr infinite, depending on how you initialize it... -- www.wescottdesign.com
PN SEQUENCE (zero values)
Started by ●February 4, 2010
Reply by ●February 5, 20102010-02-05
Reply by ●February 5, 20102010-02-05
Tim Wescott <tim@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
Reply by ●February 5, 20102010-02-05
On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote:> Tim Wescott <tim@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. > > -- glenYes. 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
Reply by ●February 5, 20102010-02-05
On Fri, 05 Feb 2010 09:51:50 -0600 Tim Wescott <tim@seemywebsite.com> wrote:> On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote: > > > Tim Wescott <tim@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
Reply by ●February 5, 20102010-02-05
On Feb 5, 10:51�am, Tim Wescott <t...@seemywebsite.com> wrote:> On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote: > > Tim Wescott <t...@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
Reply by ●February 5, 20102010-02-05
On Feb 5, 12:21�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> On Feb 5, 10:51�am, Tim Wescott <t...@seemywebsite.com> wrote: > > > On Fri, 05 Feb 2010 10:45:54 +0000, glen herrmannsfeldt wrote: > > > Tim Wescott <t...@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). >oh, you can see it in the software case. we have 2^N - 1 states, all possible bit combinations except 00000000000. (let's say we're right shifting.) one of those states will be 10000000000. as those N-1 zeros get shifted out, there will be no XOR operations to mask in other 1 bits, so the only 1 bit is the one you see getting shifted to the right: (e.g. 00001000000). that's why we know there can be no more than N-1 contiguous zeros and why there is one place in the sequence that there *are* N-1 zeros. now, how to prove that there are N contiguous 1 bits? easy in the hardware case, but not so obvious in the software case. r b-j
Reply by ●February 5, 20102010-02-05
On Feb 4, 11:22�pm, Jerry Avins <j...@ieee.org> wrote:> glen herrmannsfeldt wrote: > > Tim Wescott <t...@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?If it is maximal length, every possible n bit combination will be generated, other than the all zero lock-up pattern of course. So it would be n-1 contiguous zeros. Rick
Reply by ●February 5, 20102010-02-05
rickman wrote:> On Feb 4, 11:22 pm, Jerry Avins <j...@ieee.org> wrote: >> glen herrmannsfeldt wrote: >>> Tim Wescott <t...@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? > > If it is maximal length, every possible n bit combination will be > generated, other than the all zero lock-up pattern of course. So it > would be n-1 contiguous zeros.And N successive ones. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●February 5, 20102010-02-05
if the XORed result is further XORed with a constant 1 then there are some cases if every time the sequence is XORed then again all 1 state will go inactive. so if we XOR our XORed result alternately or maybe after 3 or 4 chips then we can have all states -------------------------------------------------------------------------- what do you think about this ???????????? secondly another method as disscussed in posts i will add one thing if we use a NOR gate to check any 1 in registers ( connect all LFSR to NOR---if no one then nor= 1) there we got the all zero state in hand ,,,,,,and now i do a XOR between the NOR value and the output XOR vlaue of PN sequence in case NOR=0 means there are 1 in LSFRs output would be 0 XOR (value of PN sequence XOR)=value of PN sequence XOR for NOR=1 means no one in LFSRs 1 XOR 0(it will be 0 as all LFSRs are in zero)=1
Reply by ●February 5, 20102010-02-05
In article <z4OdnXYazOLiE_HWnZ2dnUVZ_sudnZ2d@giganews.com>, Avier <shahanwarkhan@hotmail.com> wrote:> >what do you think about this ???????????? > > >secondly another method as disscussed in posts i will add one thing > >if we use a NOR gate to check any 1 in registers ( connect all LFSR to >NOR---if no one then nor= 1) > >there we got the all zero state in hand ,,,,,,and now i do a XOR between >the NOR value and the output XOR vlaue of PN sequence > >in case NOR=0 means there are 1 in LSFRs output would be > >0 XOR (value of PN sequence XOR)=value of PN sequence XOR > > > >for NOR=1 means no one in LFSRs > >1 XOR 0(it will be 0 as all LFSRs are in zero)=1 >You use a NOR of all bits EXCEPT the MSB (if shifting left). So the NOR kicks in for two states - one to kick it into the all zeros state, one to kick it out of the all zeros state. Regards, Mark
