I have an application where I need to generate several seconds
of delay from an internal 32KHz oscillator. If I use a ripple counter,
it will require 17-18 flip-flops. Since this is repeated several times
inside an IC, I would like to reduce the number of FF's in each counter.
By using an LFSR instead of a ripple counter, can I reduce the number of
FF's
and still achieve the same same total delay?
As I recall, The LFSR taps/locations are based on the primitive polynomial
for the selected length of shift register. Selecting the taps properly will
insure there are no repeated codes as the LFSR is clocked through it's
entire
code-space. But, I'm not concerned about about repeated codes, I just
want to
generate a fixed delay using a reduced number of FF's.
Any ideas whether this is do-able or not?
or
references to IEEE periodicals or text books would be appreciated.
thanks,
steve
LSFR to make long counters
Started by ●July 30, 2004
Reply by ●July 30, 20042004-07-30
On Thu, 29 Jul 2004 23:09:31 -0500, Junk0 <junkaddress@comcast.net> wrote:> >I have an application where I need to generate several seconds >of delay from an internal 32KHz oscillator. If I use a ripple counter, >it will require 17-18 flip-flops. Since this is repeated several times >inside an IC, I would like to reduce the number of FF's in each counter. > >By using an LFSR instead of a ripple counter, can I reduce the number of >FF's >and still achieve the same same total delay? > >As I recall, The LFSR taps/locations are based on the primitive polynomial >for the selected length of shift register. Selecting the taps properly will >insure there are no repeated codes as the LFSR is clocked through it's >entire >code-space. But, I'm not concerned about about repeated codes, I just >want to >generate a fixed delay using a reduced number of FF's. > >Any ideas whether this is do-able or not?No, this can't be done. N ffs will make a state machine with 2^N states *regardless of how those states are ordered*. The LFSR might use less combinatorial logic than a binary counter, but decoding it may be harder. If the resolution of your delay is coarse, you could use a prescaler, e.g. divide the 32kHz down to 1kHz or so. This will take 5 ffs, and each of your delay counters will need 5 fewer ffs to get the same delay. The resolution will be 1ms instead of 30 us though. Regards, Allan.
Reply by ●July 30, 20042004-07-30
Allan Herriman wrote:> On Thu, 29 Jul 2004 23:09:31 -0500, Junk0 <junkaddress@comcast.net> > wrote: > > >>I have an application where I need to generate several seconds >>of delay from an internal 32KHz oscillator. If I use a ripple counter, >>it will require 17-18 flip-flops. Since this is repeated several times >>inside an IC, I would like to reduce the number of FF's in each counter. >> >>By using an LFSR instead of a ripple counter, can I reduce the number of >>FF's >>and still achieve the same same total delay? >> >>As I recall, The LFSR taps/locations are based on the primitive polynomial >>for the selected length of shift register. Selecting the taps properly will >>insure there are no repeated codes as the LFSR is clocked through it's >>entire >>code-space. But, I'm not concerned about about repeated codes, I just >>want to >>generate a fixed delay using a reduced number of FF's. >> >>Any ideas whether this is do-able or not? > > > No, this can't be done. N ffs will make a state machine with 2^N > states *regardless of how those states are ordered*.OK, I was afraid this would be the case, but I thought I might be overlooking something.> The LFSR might use less combinatorial logic than a binary counter, but > decoding it may be harder.that makes sense, to decode a particular state on an LFSR you would need to do logic on all N outputs of the LFSR, but with a ripple counter you can just add an extra (N+1) FF, clocked off of the Nth FF. When the (N+1) FF finally get clocked, you have then detected 2^N clocks, without having to do logic on all "N"(or any) outputs. thanks, -steve
Reply by ●July 30, 20042004-07-30
"Allan Herriman" <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in message news:soijg0dmq3tmvuujgslc068282n4bahk7h@4ax.com...> On Thu, 29 Jul 2004 23:09:31 -0500, Junk0 <junkaddress@comcast.net> > wrote: > > > >I have an application where I need to generate several seconds > >of delay from an internal 32KHz oscillator. If I use a ripple counter, > >it will require 17-18 flip-flops. Since this is repeated several times > >inside an IC, I would like to reduce the number of FF's in each counter. > > > >By using an LFSR instead of a ripple counter, can I reduce the number of > >FF's > >and still achieve the same same total delay? > > > > No, this can't be done. N ffs will make a state machine with 2^N > states *regardless of how those states are ordered*. > > The LFSR might use less combinatorial logic than a binary counter, but > decoding it may be harder.LFSR uses less combinatorial logic than a binary counter, but a ripple counter uses even less (none actually). But in my experience, the "ripple" nature of when the outputs change make it unsuitable for integrating with the rest of your logic in many situations. But if it works for you, by all means use it as it is very efficient. BTW, IIRC a N flip-flop LFSR can only generate at most 2^N-1 states. There is one state (usually all zeros) that isn't allowed as the LFSR "sticks" when it hits that.
Reply by ●July 30, 20042004-07-30
Jon Harris wrote:> "Allan Herriman" <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in > message news:soijg0dmq3tmvuujgslc068282n4bahk7h@4ax.com... > >>On Thu, 29 Jul 2004 23:09:31 -0500, Junk0 <junkaddress@comcast.net> >>wrote: >> >>>I have an application where I need to generate several seconds >>>of delay from an internal 32KHz oscillator. If I use a ripple counter, >>>it will require 17-18 flip-flops. Since this is repeated several times >>>inside an IC, I would like to reduce the number of FF's in each counter. >>> >>>By using an LFSR instead of a ripple counter, can I reduce the number of >>>FF's >>>and still achieve the same same total delay? >>> >> >>No, this can't be done. N ffs will make a state machine with 2^N >>states *regardless of how those states are ordered*. >> >>The LFSR might use less combinatorial logic than a binary counter, but >>decoding it may be harder. > > > LFSR uses less combinatorial logic than a binary counter, but a ripple counter > uses even less (none actually). But in my experience, the "ripple" nature of > when the outputs change make it unsuitable for integrating with the rest of your > logic in many situations. But if it works for you, by all means use it as it is > very efficient. > > BTW, IIRC a N flip-flop LFSR can only generate at most 2^N-1 states. There is > one state (usually all zeros) that isn't allowed as the LFSR "sticks" when it > hits that.A ripple counter is useful for dividing by a power of two. Don't try to use a long one to decode a particular combination of ones and zeros of the individual stages unless the combinatorial logic incorporates the same delays as the ripple chain. The state you want doesn't exist in its entirety at any one instant. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 30, 20042004-07-30
"Jerry Avins" <jya@ieee.org> wrote in message news:410ac53b$0$2840$61fed72c@news.rcn.com...> Jon Harris wrote: > > > "Allan Herriman" <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in > > message news:soijg0dmq3tmvuujgslc068282n4bahk7h@4ax.com... > > > >>On Thu, 29 Jul 2004 23:09:31 -0500, Junk0 <junkaddress@comcast.net> > >>wrote: > >> > > > > LFSR uses less combinatorial logic than a binary counter, but a ripplecounter> > uses even less (none actually). But in my experience, the "ripple" natureof> > when the outputs change make it unsuitable for integrating with the rest ofyour> > logic in many situations. But if it works for you, by all means use it asit is> > very efficient. > > A ripple counter is useful for dividing by a power of two. Don't try to > use a long one to decode a particular combination of ones and zeros of > the individual stages unless the combinatorial logic incorporates the > same delays as the ripple chain. The state you want doesn't exist in its > entirety at any one instant.Yes, that's a great example of "unsuitable for integrating with the rest of your logic"!
Reply by ●July 31, 20042004-07-31
On Fri, 30 Jul 2004 13:23:35 -0700, "Jon Harris" <goldentully@hotmail.com> wrote:>"Allan Herriman" <allan.herriman.hates.spam@ctam.com.au.invalid> wrote in >message news:soijg0dmq3tmvuujgslc068282n4bahk7h@4ax.com... >> On Thu, 29 Jul 2004 23:09:31 -0500, Junk0 <junkaddress@comcast.net> >> wrote: >> > >> >I have an application where I need to generate several seconds >> >of delay from an internal 32KHz oscillator. If I use a ripple counter, >> >it will require 17-18 flip-flops. Since this is repeated several times >> >inside an IC, I would like to reduce the number of FF's in each counter. >> > >> >By using an LFSR instead of a ripple counter, can I reduce the number of >> >FF's >> >and still achieve the same same total delay? >> > >> >> No, this can't be done. N ffs will make a state machine with 2^N >> states *regardless of how those states are ordered*. >> >> The LFSR might use less combinatorial logic than a binary counter, but >> decoding it may be harder. > >LFSR uses less combinatorial logic than a binary counter, but a ripple counter >uses even less (none actually). But in my experience, the "ripple" nature of >when the outputs change make it unsuitable for integrating with the rest of your >logic in many situations. But if it works for you, by all means use it as it is >very efficient.A ripple counter may also be very efficient in terms of power dissipation.>BTW, IIRC a N flip-flop LFSR can only generate at most 2^N-1 states. There is >one state (usually all zeros) that isn't allowed as the LFSR "sticks" when it >hits that.There's a simple mod that allows an "LFSR" to cycle through all 2^N states, however the feedback is a little more complicated (it involves an N-1 input OR or AND gate). Since the feedback is non-linear, it's not really an LFSR any more. I think there's a theorem that says that any N ff machine with purely linear feedback can't cycle through 2^N states. This is an important result that I've used a few times in design of (e.g.) CRC error detection circuits, but I have yet to find a formal proof for this theorem. I've only come up with hand-waving proofs in the past (I'm not a mathematician). Any pointers? Regards, Allan
Reply by ●July 31, 20042004-07-31
Allan Herriman wrote: ...> I think there's a theorem that says that any N ff machine with purely > linear feedback can't cycle through 2^N states. This is an important > result that I've used a few times in design of (e.g.) CRC error > detection circuits, but I have yet to find a formal proof for this > theorem. I've only come up with hand-waving proofs in the past (I'm > not a mathematician). > Any pointers?Isn't no feedback at all linear? If so, a ripple-carry counter is a counterexample. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 31, 20042004-07-31
Jerry Avins wrote:> Allan Herriman wrote: > > ... > >> I think there's a theorem that says that any N ff machine with purely >> linear feedback can't cycle through 2^N states. This is an important >> result that I've used a few times in design of (e.g.) CRC error >> detection circuits, but I have yet to find a formal proof for this >> theorem. I've only come up with hand-waving proofs in the past (I'm >> not a mathematician). >> Any pointers? > > > Isn't no feedback at all linear? If so, a ripple-carry counter is a > counterexample. > > JerryWell, if you take "feedback" to mean feedback from the N flip-flops back to themselves then a counter does depend on feedback, and it's not linear in a mod-2 sense. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●August 2, 20042004-08-02
