May 21, 1998

LFSR counters implement binary polynomial generators

Tom Balph, Motorola Semiconductor

LFSR counters make ideal pseudorandom-number generators, but make sure to provide a reset function to prevent lockup.

You can use linear-feedback shift registers (LFSRs) as alternatives to conventional bi-nary counters (Reference 1). An LFSR reduces the amount of required logic and minimizes routing complexity. A possible disadvantage is that the count sequence is not the normal binary increment or decrement sequence. An LFSR counter, in effect, implements a binary polynomial generator. These generators find common use for pseudorandom-number generation. This article provides some guidelines for implementing LFSR-based counters. Some general points include

• An LFSR with n flip-flops can implement only a (2ⁿ­1)-state counter. The all-zeros state is normally not allowed because the counter locks up.

• Good design practice demands a reset condition that provides start-up in a known condition and also ensures that the counter does not power up in a zero condition and stay locked up.

• The choice of the polynomial used should ensure 2ⁿ­1 states--with no repeated states; such a polynomial is known as a "primitive," or maximal-length polynomial.

To implement a counter with a divide ratio other than 2ⁿ­1, you must first select a primitive polynomial that has the proper degree. The degree, or power of two, must be large enough to allow the desired number range. As an example, a divide-by-35 counter must use a polynomial of the sixth degree (yielding 2⁶­1=63 possible states). You can typically find primitive polynomials in tables in textbooks that deal with testing and pseudorandom numbers. The values in Table 1 derive from Reference 2.

The values in Table 1 are the exponents of terms in primitive binary polynomials. The numbers listed represent the smallest number of terms for a primitive polynomial of each degree. For example, the entry 12: 7 4 3 0 represents the polynomial x¹²+x⁷+x⁴+x³+1. Once you select a polynomial, you first implement a counter for just that polynomial. As a design example, assume you need a divide-by-12 counter. From Table 1, you select the fourth-degree polynomial (x⁴+x+1) because it allows as many as 15 possible states.

You can implement the polynomial in logic as either a "many-to-one" (Figure 1a) or a "one-to-many" (Figure 1b) design. Note that, although either approach implements the same polynomial, the count sequences differ. At this point, you should add a synchronous reset to the design to force an all-ones condition at reset.

Figure 2a shows the one-to-many design example. Through simulation, you can observe the count sequence and verify that the selected polynomial repeats after 2ⁿ­1 states (in this case, 15 states) and that no state repeats within each sequence. Table 2 gives the sequence for this example.

To complete the counter design, you can decode the desired final count and force the normal sequence to truncate back to the reset condition. For the divide-by-12 example, you decode state 12, in which the count value equals two hex. Figure 2b shows the reset-modification hardware.

References

1. Dipert, Brian, "Shattering the programmable-logic speed barrier," EDN, May 22, 1997, pg 37.

2. Bardel, McAnney, and Savir, Built-In Test for VLSI: Pseudorandom Techniques, John Wiley and Sons, 1987.

| EDN Access | Feedback | Table of Contents |