CS150 Lab 5, Spring 1997
Shift Registers and Counters

  1. Objective
  2. Counters and shift registers are commonly-used finite state machines. In this lab, you will build some and use the Xilinx board to observe their operation.

  3. Prelab
  4. Read through this enitrely, enter the circuit described in What To Build, and answer the checkoff sheet questions. This lab requires a bit of design, so think about how the circuits should be assembled and understand what is required before doing anything else.

  5. Linear Feedback Shift Registers

  6. Figure 1: A four-bit linear feedback shift register

    Linear feedback shift registers, such as the one in Figure 1, are n-bit counters exhibiting pseudorandom behavior using little circuitry. They have many applications, including computer graphics and pseudorandom number generation.

    Consider the operation of the LFSR shown in Figure 1. When the latches are all zero, it does nothing. Every Q output is zero, the feedback path from F4 to F1 is zero, and the output of the XOR is zero, so the LFSR stays in this state forever.

    When a 1 is introduced (in F1), the circuit counts through the 24 - 1 = 15 different non-zero bit pattern shown on the right.

    You can build a similar circuit with any number of flip-flops, although more XORs may be needed. The table of primitive polynomials can be used to design these circuits. The section Galois Fields discusses why these circuits do what they do.

    LFSR
    Sequence
    -------
    1 0 0 0
    0 1 0 0
    0 0 1 0
    0 0 0 1
    1 1 0 0
    0 1 1 0
    0 0 1 1
    1 1 0 1
    1 0 1 0
    0 1 0 1
    1 1 1 0
    1 1 1 1
    1 0 1 1
    1 0 0 1
    1 0 0 0

    Using the Table to Build an LFSR

    To build a k-bit LFSR, number the flip-flops, with the leftmost flip flop labeled 1 and the rightmost flip flop k. We'll refer to the flip flops as F1, F2, ..., Fk

    Find the primitive polynomial of the form xk + ... + 1 in the table of primitive polynomials. Wiring up the flip flops to build an LFSR that has 2k different patterns can be done by examining each term of the polynomial. There are two special cases, x0 = 1 and xk, which represent connecting feedback loop from the Q output of Fk to the D input of F1. Each of the other terms in the form of xn corresponds to connecting an XOR between flip-flop Fn and Fn + 1. Where there are no XORs in between flip flops, just connect the Q of the left flip flop to the D of the right flip flop. The assembled 4-bit LFSR is shown in Figure 1. The meaning of the primitive polynomial x4 + x + 1 = x4 + x1 + x0 is described below:

    To build an eight-bit LFSR, use the primitive polynomial x8 + x4 + x3 + x2 + 1 and connect XORs between F2 and F3, F3 and F4, and F4 and F5.

  7. What to Build
  8. You will build a configurable linear-feedback shift register on the Xilinx Design Demonstration Board. The DIP switches will control whether to place an XOR or just a wire between adjacent flip flops. The eight LEDs will display either the contents of the shift register or an eight-bit binary counter depending on the display mode selected by the SPARE buton. Also, the RESET button will reset the counter.

    We must clock the shift register slowly to see its operation. The 1 MHz clock from the XChecker cable is much too fast, so we will divide it by 215 = 32768 to obtain a 30.5 Hz clock. We will use this 30.5 Hz signal as a clock enable input to the other flip-flops in the design, rather than using a separate clock signal. A single-clock design is more robust than one with multiple clocks.

    Our shift register will consist of eight flip-flops. Between each flip-flop will be a small circuit you will have to design: it will either emulate an XOR gate or a wire, depending on the position of the dip switch that controls it.

    Since flip-flops in the Xilinx start in the reset state (all 0s), and the LFSRs stay in the same all-zero state, building Figure 1 exactly will not work. Thus, you will have to invert both the input and output of each flip flop to get a good sequence of patterns. This modification will make the flip flops behave normally, but when reset, the inverters will insure that it will output a 1 instead of a 0.

    We will visually compare the operation of the shift register to an eight-bit binary counter clearable with the RESET button. In one display mode, seven of the eight LEDs will display the seven most significant bits of this counter, and the eighth LED will light up if the flip-flops are in the all-zeros state.

    In the other display mode, the LEDs will display the contents of the shift register. Use two-input multiplexers controlled by the SPARE button to choose the between the two display modes for the LEDs.

    All interfaces built into the Xilinx board (buttons, switches, and LEDs) can be connected to your circuit by components in the cs150 library (RESET, SPARE, DIPS, LEDS, etc), so they can be used to save some time. Remember, though that the LEDS are lit when low and the left LED is on the right side of the symbol. After placing the components, you can "push" into the schematic by right-clicking on the symbol and click on Schematic to see how the components are connected to the I/O pins. As with the lock from Lab 3, the clock will come from Pin 8, the RESET button from Pin 56, and the SPARE button from Pin 68. Remember to use a PULLUP with the SPARE button, as in the Lab 3 schematic (this is already done for you if you use the SPARE component). The DEBOUNCE circuit is unnecessary, except for extra credit. To use the XChecker debugging facilities, include the READBACK circuit.

    Here is a summary of what you need to do:

    1. Build a divide-by-32768 counter with a CC16CE. AND together the least significant fifteen bits with four AND4s and an AND3 to produce the clock enable signal for the other flip-flops in the design.

    2. Use a CC8CE eight-bit counter with its CE input connected to the clock enable signal from the CC16CE's outputs, its CLR connected to the RESET button. Think about the polarity of this signal.

    3. Build the shift register using eight FDCEs with their CE inputs connected to the clock enable signal. Put an XOR with a multiplexer, and control the multiplexer with the DIP switches, whose pins are listed in Table 1, to select between the output of the previous flip flop (or ground for the left most FF) and the previous flip flop XOR the feedback. Be sure to invert the inputs and outputs of the flip flops.

    4. Use eight two-input multiplexers (M2_1s) controlled by the SPARE button to select the two display modes for the LEDs. Think about what you want the default (SPARE released) to be. The LED pin numbers are listed in Table 1.

      • In one mode, display the Q outputs of the eight shift register flip-flops.

      • In the other mode, display the seven most significant bits of the CC8CE and have the last LED be lit only when the rightmost flip flop is the ONLY flip-flop high.

    left right
    switch1920232425 262728
    LED6162656657 585960

    Table 1: DIP switch and LED pins

  9. What to Do
    1. Make sure the eight-bit counter is working. Make the LEDs display the counter and verify the counter's LEDs are flashing at half the speed of their neighbor. Try resetting the counter with the RESET button.

    2. Observe the shift register contents on the LEDs. Set the switches so that all bits become zero (all switches in the same direction). Flip the leftmost switch. The display should change to a sweeping all-on to all-off pattern.

    3. Use the table of primitive polynomials to set the switches to make a seven-bit, period 127 LFSR. Verify this period by waiting for the eighth LED to flash briefly, pressing the RESET button, and noting that the next flash happens in about the same time it takes the second-slowest counter bit to pulse on and off. Show a TA.

    4. Use the table to set the switches to make an eight-bit, period 255 LFSR. Verify the period as before; use instead the slowest counter bit. Show a TA.

    5. Change one of the other switches so that you still have an eight-bit LFSR, but with a different period. Time it as before. Show a TA.

  10. Galois Fields (Optional Reading)
  11. This circuit behaves as it does because it is performing multiplication on a field, a set with two operations defined on it: ``addition'' and ``multiplication.'' The set is closed under these operations, the associative and distributive laws hold, there is both an additive and multiplicative identity element, there is an additive inverse for every element, and a multiplicative inverse for every non-zero element.

    Familiar infinite fields include the set of rational numbers, the set of real numbers, and the set of complex numbers. The set of integers is not a field, since most integers do not have a integer multiplicative inverse.

    Finite fields are called Galois (gal-WAH) fields. Binary numbers form a simple Galois field with two elements called GF(2). The XOR function is ``addition,'' and the AND function is ``multiplication.''

    Consider polynomials whose coefficients come from GF(2), that is, each term of the form xn is either present or absent. For example, 0, 1, x, x2, and x7 + x6 + 1 are all GF(2)-coefficient polynomials.

    Adding these polynomials is easy. "Add" (XOR) each element individually - there is no carry:
    Multiplying these polynomials is alo easy. Multiplying by a monomial of the form xn is like shifting to the left:

    If we use this addition and take the results of this multiplication modulo a prime polynomial p(x) (a polynomial that cannot be written as the product of two non-trivial polynomials q(x) r(x)), these polynomials form a Galois field. For any degree, there is at least one prime polynomial. By using it, we can form GF(2n), the Galois field with 2n elements, for any positive integer n.

    Every Galois field has a primitive element: an element such that every non-zero element can be expressed as a power of . So if we know a primitive field element and can raise it to any power, we can obtain all non-zero elements of a field.

    Certain choices of p(x), the prime generating polynomial for a field (i.e., multiplication is taken modulo this polynomial), make the simple polynomial x a primitive element. It turns out there is such a p(x), called a primitive polynomial, of every degree.

    For example, the polynomial x4 + x + 1 is primitive. So = x is a primitive element, and successive powers of will generate all non-zero elements of GF(16):

    The pattern of coefficients shown above matches the bits in the table that shows the counter sequence of a four bit LFSR. In general, finding these primitive polynomials is difficult. Looking them up in a table, such as the one on the right, is easiest.

    The equivalences between Galois fields and hardware are:

    Primitive Polynomials

    x2 + x + 1
    x3 + x + 1
    x4 + x + 1
    x5 + x2 + 1
    x6 + x + 1
    x7 + x3 + 1
    x8 + x4 + x3 + x2 + 1
    x9 + x4 + 1
    x10 + x3 + 1
    x11 + x2 + 1
    x12 + x6 + x4 + x + 1
    x13 + x4 + x3 + x + 1
    x14 + x10 + x6 + x + 1
    x15 + x + 1
    x16 + x12 + x3 + x + 1
    x17 + x3 + 1
    x18 + x7 + 1
    x19 + x5 + x2 + x + 1
    x20 + x3 + 1
    x21 + x2 + 1
    x22 + x + 1
    x23 + x5 + 1
    x24 + x7 + x2 + x + 1
    x25 + x3 + 1
    x26 + x6 + x2 + x + 1
    x27 + x5 + x2 + x + 1
    x28 + x3 + 1
    x29 + x + 1
    x30 + x6 + x4 + x + 1
    x31 + x3 + 1
    x32 + x7 + x6 + x2 + 1

    Galois Field
    Hardware



    Multiplication by x <==> Shift right
    Taking the result mod p(x) <==> XORing with the coefficients of p(x) when the most significant coefficient is 1
    Obtaining all 2n - 1 non-zero elements by evaluating xk for k = 1, ..., 2n - 1 <==> Shifting and XORing 2n - 1 times

    This is a small fraction of the power of Galois fields, which are used throughout the large, rich field of error control (error-correcting) codes.

  12. Checkoffs
    1. Use the table of primitive polynomials to draw a schematic for an LFSR with 29 - 1 = 511 unique states. How many flip-flops do you need? How many XORs?









    2. None of the counter and LFSR lights flash at exactly the same rate. Why are they not identical?





  13. Divide-by-32768 and eight-bit counters working, displaying

  14. TA: ___________ (30%)
  15. Seven-bit LFSR with period 127

  16. TA: ___________ (20%)
  17. Eight-bit LFSR with period 255

  18. TA: ___________ (20%)
  19. Eight-bit LFSR with another period

  20. TA: ___________ (20%)
  21. Extra Credit:
    Make the SPARE button toggle between the two display modes

  22. TA: ___________ (10%)
  23. Turned in on time

  24. TA: ___________ (10%)