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: robert bristow-johnson on 5 Feb 2010 12:38 On Feb 5, 12:21 pm, robert bristow-johnson <r...(a)audioimagination.com> wrote: > 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). > 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
From: rickman on 5 Feb 2010 13:09 On Feb 4, 11:22 pm, Jerry Avins <j...(a)ieee.org> wrote: > glen herrmannsfeldt wrote: > > Tim Wescott <t...(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? 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
From: Jerry Avins on 5 Feb 2010 15:34 rickman wrote: > On Feb 4, 11:22 pm, Jerry Avins <j...(a)ieee.org> wrote: >> glen herrmannsfeldt wrote: >>> Tim Wescott <t...(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? > > 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. �����������������������������������������������������������������������
From: Avier on 5 Feb 2010 16:32 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
From: Mark Curry on 5 Feb 2010 17:00
In article <z4OdnXYazOLiE_HWnZ2dnUVZ_sudnZ2d(a)giganews.com>, Avier <shahanwarkhan(a)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 |