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 did, 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. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
PN SEQUENCE (zero values)
Started by ●February 4, 2010
Reply by ●February 4, 20102010-02-04
Reply by ●February 4, 20102010-02-04
In article <T8ednaRDyYKmqvbWnZ2dnUVZ_vadnZ2d@giganews.com>, Vladimir Vassilevsky <nospam@nowhere.com> wrote:> > >John 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 >> >> >> I believe the all-zeros state is never legal because it would cause >> all subsequent outputs to be zero. > >You can modify LSFR by sticking an additional invertor into it. This >will take care of all zero state however the sequence will stil have 2^N >- 1 "normal" states.You can also make the sequence max length (all 2**n) states with a little logic. It makes the sequence non-linear - but it's pretty much the same sequence. You modify the "feedback term" by comparing the least signficant N-1 bits with all zero. Take this bit and XOR it with the feedback line to generate a modified feedback term. This modifies the sequence from: MSB bit high, rest of bits zero -> All zeros -> Continue with sequence If this is done in hardware, this changes the critical path from a single XOR to an (n-1) bit compare with all zeros. Rereading that not sure it's clear. If you need more clear examples, let me know... Regards, Mark
Reply by ●February 4, 20102010-02-04
robert bristow-johnson <rbj@audioimagination.com> wrote:> 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 did, and i think i found it, but i don't remember if the word > representing the skipped state was something i could derive.It should be easy, though I don't think I ever tried. Write down the recursion function and set the new state equal to the previous state. -- glen
Reply by ●February 4, 20102010-02-04
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 ????
Reply by ●February 4, 20102010-02-04
On Thu, 04 Feb 2010 12:45:18 -0800, John 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 > > I believe the all-zeros state is never legal because it would cause all > subsequent outputs to be zero.PN yes. PN from a linear shift register, no. -- www.wescottdesign.com
Reply by ●February 4, 20102010-02-04
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. > > -- glenBecause that wide wide NOR gate is _expensive_. -- www.wescottdesign.com
Reply by ●February 4, 20102010-02-04
On Thu, 04 Feb 2010 14:19:23 -0600, Avier wrote:> just for check > > > IS there any way to produce a PN sequence from all zero intial state. > > that is all zeros in shift regitersPresumably you're implementing this in an LFSR. You have to add logic. By definition a truly _linear_ feedback shift register has multiple modes. If you choose a feedback polynomial that is prime then you get your one maximal-length mode and your zero mode, instead of several shorter ones and a zero one. So you add logic to your LFSR to make it a _non_ linear FSR. The easiest way I can think of to do this is to put a counter on the output of the thing that counts up any time it sees a zero, and resets any time it sees a 1. If the count gets up to 2^N, you've just detected the all-zeros state, and you inject a one into your feedback. Then your FSR isn't in the all-zero state anymore, and life is wonderful. -- www.wescottdesign.com
Reply by ●February 4, 20102010-02-04
Tim Wescott <tim@seemywebsite.com> wrote:> 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.(snip)>>> 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?(snip)>> And if an alpha particle comes through and it does get into the wrong >> state then you are stuck.> Because that wide wide NOR gate is _expensive_.As I said, it depends on the cost of being in the wrong state. If it is part of a car engine control system (no suggestion that anyone does that) then the cost could be high. If you mean expensive in critical path, then pipeline it. That delays the number of cycles to get out of the bad state, but much of the time you can live with that. Many FPGA designs aren't so full that the extra logic would be that bad. Not enough to be 'clearly bad' to me. -- glen
Reply by ●February 4, 20102010-02-04
On Fri, 05 Feb 2010 01:31:02 +0000, glen herrmannsfeldt wrote:> Tim Wescott <tim@seemywebsite.com> wrote: >> 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. > (snip) > >>>> 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? > (snip) > >>> And if an alpha particle comes through and it does get into the wrong >>> state then you are stuck. > >> Because that wide wide NOR gate is _expensive_. > > As I said, it depends on the cost of being in the wrong state. If it is > part of a car engine control system (no suggestion that anyone does > that) then the cost could be high. > > If you mean expensive in critical path, then pipeline it. That delays > the number of cycles to get out of the bad state, but much of the time > you can live with that. > > Many FPGA designs aren't so full that the extra logic would be that bad. > Not enough to be 'clearly bad' to me. > > -- glenOr '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. -- www.wescottdesign.com
Reply by ●February 4, 20102010-02-04
glen herrmannsfeldt wrote:>>>And if an alpha particle comes through and it does get into the wrong >>>state then you are stuck. > > As I said, it depends on the cost of being in the wrong state. > If it is part of a car engine control system (no suggestion that > anyone does that) then the cost could be high. > > If you mean expensive in critical path, then pipeline it. > That delays the number of cycles to get out of the bad state, > but much of the time you can live with that. > > Many FPGA designs aren't so full that the extra logic would be > that bad. Not enough to be 'clearly bad' to me.Military grade encryption hardware runs self checks at every cycle. The amount of circutry related to that is much higher then required by the basic functionality. And then there is always a problem of who is going to guard the guards. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
