On Feb 4, 6:36�pm, Jerry Avins <j...@ieee.org> wrote:> robert bristow-johnson wrote: > > On Feb 4, 3:19 pm, "Avier" <shahanwark...@hotmail.com> wrote: > >> just for check > > >> IS there any way to produce a PN sequence from all zero �intial state. > > >> that is all zeros in shift regiters > > > long ago (in the eighties, and it was on a 68K, like my first Mac) i > > did a sorta MLS in which i inverted the logic whether to XOR the > > accumulator or not. �i think i XORed if the bit shifted out was a 0, > > not a 1. > > > and i ran experiments to see that it did 2^N - 1 states before getting > > back to all zeros. �that meant that there was some non-zero state that > > it never hit, and i think i found it, but i don't remember if the word > > representing the skipped state was something i could derive. > > All ones.no, it wasn't that, Jerry. 0xFFFF becomes 0x7FFF. it was weird. assuming right-shifting, it had to be an even number. it would get right-shifted, XORed and afterward it would be the same number. hmmmm. r b-j
PN SEQUENCE (zero values)
Started by ●February 4, 2010
Reply by ●February 4, 20102010-02-04
Reply by ●February 4, 20102010-02-04
On Thu, 04 Feb 2010 22:51:03 +0000, Al Clark wrote:> "Avier" <shahanwarkhan@hotmail.com> wrote in news:1- > KdnQfbRfxWtvbWnZ2dnUVZ_vOdnZ2d@giganews.com: > >> just for check >> >> >> IS there any way to produce a PN sequence from all zero intial state. >> >> that is all zeros in shift regiters >> >> > The all zero state is a the 2n - (2n-1) state. Its next state is itself. > > You could use an N input NOR connected to each output state. The output > of the NOR would be 0 for all situations except the all 0 state. You > could take this value and OR with any one of the output states. This > would cause an all 0 condition to be changed to one with a single 1 > state. At this point the states would change to the 2n-1 sequence. Once > in a 2n-1 sequence, the OR function would never cause a change in the > next state since you would always be ORing a 0. > > This is clearly a very bad solution. > > In software, you just initialize a seed to be non zero. > > In hardware, the VLV solution adds an inverter to the output of a flip > flop. If you then perform a RESET, you have a seed with a single 1, > which will avoid the all zero state.But when do you perform the reset? Clearly it's easy to initialize a LFSR so it will 'never' go to all zeros. The only reasons that I can see for making sure it doesn't stem from paranoia: paranoia about power glitches, paranoia about cosmic rays, paranoia about a temporary fault from over- or under-temperature operation turning permanent, etc. Granted, if that's an issue then most processor-based systems are screwed, because if the zap hits the stack pointer or program counter your system is a whole lot deader than if you lose the state of one lousy PN sequence generator. -- www.wescottdesign.com
Reply by ●February 4, 20102010-02-04
On Feb 4, 7:56�pm, "Avier" <shahanwark...@hotmail.com> wrote:> one way as i see > > 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 say ????Avier, not that i have any time to do any work for you, but give me a week and i'll dig this up (or re-derive it). i'm intrigued about it and this is a quarter century old, so i can't remember it and i sure- as-hell do not know where the floppy disks are with this code. r b-j
Reply by ●February 4, 20102010-02-04
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
Reply by ●February 4, 20102010-02-04
Tim Wescott <tim@seemywebsite.com> wrote: (someone wrote)>> In hardware, the VLV solution adds an inverter to the output of a flip >> flop. If you then perform a RESET, you have a seed with a single 1, >> which will avoid the all zero state.> But when do you perform the reset? Clearly it's easy to initialize a > LFSR so it will 'never' go to all zeros. The only reasons that I can see > for making sure it doesn't stem from paranoia: paranoia about power > glitches, paranoia about cosmic rays, paranoia about a temporary fault > from over- or under-temperature operation turning permanent, etc.If a system is running close to its maximum clock rate, then it can be very sensitive to some of those. If you get out of reset before starting the clock then it is easy, but you can't always do that.> Granted, if that's an issue then most processor-based systems are > screwed, because if the zap hits the stack pointer or program counter > your system is a whole lot deader than if you lose the state of one lousy > PN sequence generator.Yes, but one reason to use dedicated (non-soft) hardware is to avoid those possibilities. Then again, watchdog reset on processors to get out of any of the possible software failure modes is not so unusual. -- glen
Reply by ●February 4, 20102010-02-04
robert bristow-johnson <rbj@audioimagination.com> wrote: (snip)> no, it wasn't that, Jerry. 0xFFFF becomes 0x7FFF.> it was weird.> assuming right-shifting, it had to be an even number. it would get > right-shifted, XORed and afterward it would be the same number.If the state register is x, and the XOR value is a, then (x>>1)^a==x, or in verilog form x[n-1:1]^a[n-2:0]==x[n-2:0] x[0]==0 (the condition for the XOR). I think a[n-1] has to be 1, otherwise it is an n-1 bit LFSR. x[1]^a[0]=x[0]=0 x[1]=a[0] x[2]^a[1]=x[1]=a[0] x[2]=a[0]^a[1] x[3]^a[2]=x[2]= x[3]=a[0]^a[1]^a[2] etc. -- glen
Reply by ●February 4, 20102010-02-04
On Feb 4, 10:01�pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> robert bristow-johnson <r...@audioimagination.com> wrote: > > (snip) > > > no, it wasn't that, Jerry. �0xFFFF becomes 0x7FFF. > > it was weird. > > assuming right-shifting, it had to be an even number. �it would get > > right-shifted, XORed and afterward it would be the same number. > > If the state register is x, and the XOR value is a, > then �(x>>1)^a==x, or in verilog form > > x[n-1:1]^a[n-2:0]==x[n-2:0] > x[0]==0 (the condition for the XOR). > I think a[n-1] has to be 1, otherwise it is an n-1 bit LFSR.yes, same as with the top n bits of an nth-order primitive polynomial (which is i think what i used.> x[1]^a[0]=x[0]=0 � � � x[1]=a[0] > x[2]^a[1]=x[1]=a[0] � �x[2]=a[0]^a[1] > x[3]^a[2]=x[2]= � � � �x[3]=a[0]^a[1]^a[2]well, somebuddy other than me (maybe the OP) gets to check this out. i don't have time, but i think it works. the issue is, just like a regular MLS, there is a state that, if you somehow find yourself in that state (like if the alpha particle comes in and flips a bit) you're stuck in it (until the next alpha particle comes along and knocks you out of it). but you could start with a cleared register and go through all other states, and i'll bet if you picked out a single bit out, it would qualify as an MLS of sorts (psuedo-white noise). r b-j
Reply by ●February 4, 20102010-02-04
On Feb 4, 9:42�pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> 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.why wouldn't that be N-1? r b-j
Reply by ●February 5, 20102010-02-05
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. > > -- glenn-1? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●February 5, 20102010-02-05
Tim Wescott <tim@seemywebsite.com> wrote in news:dKydnam7PZFR8vbWnZ2dnUVZ_gZi4p2d@web-ster.com:> On Thu, 04 Feb 2010 23:05:18 +0000, glen herrmannsfeldt wrote: > >> Al Clark <aclark@danvillesignal.com> wrote: (snip) >> >>> You could use an N input NOR connected to each output state. The output >>> of the NOR would be 0 for all situations except the all 0 state. You >>> could take this value and OR with any one of the output states. This >>> would cause an all 0 condition to be changed to one with a single 1 >>> state. At this point the states would change to the 2n-1 sequence. Once >>> in a 2n-1 sequence, the OR function would never cause a change in the >>> next state since you would always be ORing a 0. >> >>> This is clearly a very bad solution. >> >> Why is it so bad? If you compare the cost of being in the wrong state >> to the cost of the OR gate, is it all that bad? >> >>> In software, you just initialize a seed to be non zero. >> >>> In hardware, the VLV solution adds an inverter to the output >>> of a flip flop. If you then perform a RESET, you have a >>> seed with a single 1, which will avoid the all zero state. >> >> And if an alpha particle comes through and it does get into the wrong >> state then you are stuck. >> >> -- glen> Because that wide wide NOR gate is _expensive_. >Exactly. I only suggested it as a method that eliminates the zero state. As an engineer, I think it is overly complicated. The inverter method is probably much better since a stray reset will still cause the sequence to go back to a long sequence. If the sequence is reasonably long, the alpha particle will need to be very lucky to cause the all zero state. I think the probabity of circuit failure is much much higher. Al
