CRCs

A very common class of circuits you'll see in digital design is based around the Linear Feedback Shift Register (LFSR), which is essentially a chain of clocked registers fed into one another. The output of each register is used as bit in the system's overall value or state, so if you have 4 registers, you have 4 bits...if you have 16 registers, you have 16 states. The last register in the chain is always fed back into the first register in the chain. If this is all that were done, the circuit would be boring, simply cycling the same pattern around in a loop:

For example, if you start Q4, Q3, Q2, and Q1 with values 0001, on each clock cycle you'd get: 0010, then 0100, then 1000, then back to 0001. Great, but not super exciting. To connect some dots in this class, you've already seen this before; this is effectively (a shortened) version of what got synthesized in the seven_segment_controller in Week 02 for controlling the anode line. It has its purpose for sure, but we can do more.

Interestingly, when the output from the final register is not only fed back into the first register, but is also XORed at particular intermediate stages ("taps") with the chain, surprising new behaviors can arise.

Consider the circuit below with four values: Q4, Q3, Q2, and Q1 where the feedback is not simple, but is now made more complicated by the XOR gate. If you were to initialize these four values to to 0001, on each subsequent rising clock edge, the four values would evolve to:

0010, 0100, 1000, 0011, 0110, 1100, 1011, 0101, 1010, 0111, 1110, 1111, 1101, 1001, before cycling back to 0001 where the cycle would repeat itself.

A careful study of this sequence will reveal that it moved through every possible combination of 1's and 0's that can exist in four bits (except for 0000) in a some sort of non-obvious way (i.e. it isn't just going 0001, 0010, 0011, etc...)

To ensure you understand what this circuit is doing, build a Verilog implementation of this LFSR above.

Make an implementation of the circuit above with the following inputs:

• clk_in: your clock signal.
• rst_in: your synchronous reset signal ("synchronous" means the system should be reset only on the clock edge).
• [3:0] seed_in: A value set by the user to seed the LFSR on assertion of the reset signal.

The module should have one output:

• [3:0] q_out: The four taps of the circuit above Q4, Q3, Q2, and Q1

Make sure to test locally using testbenches. Make sure your module can be initialized to any four-bit value with reset and that it behaves properly starting from that state. Also check to see what happens if it does get initialized to 4'b0000.

module lfsr_4 ( input wire clk_in, input wire rst_in, input wire [3:0] seed_in, output logic [3:0] q_out); endmodule

Loading...

This circuit above is a very simple "maximum length" LFSR, meaning it will cycle through all 15 non-zero values in a non-obvious, though deterministic, manner. This makes the LFSR useful for pseudorandom number generation, among other applications we'll see in later labs and psets.

Typically, you'll see LFSRs characterized by polynomials. For now, however, note that the polynomial x^4 + x^1 + 1 corresponds to the feedback pattern above.

To get a better idea of how polynomial characterizations relate to LFSRs, consider another, higher order polynomial:

The LFSR that corresponds to this polynomial is pictured below:

Note the patterns in the feedback taps between the four bit and six bit LFSR. This can be generalized to:

• The x^k and 1 (x^0) corresponds to feeding the biggest register back to the smallest. This will always happen.
• Any intermediate terms of x^n shape will correspond to a XOR tap of the feedback and between register n and n+1.

The bigger your LFSR, the more "random" the output "may" "appear" as you cycle through different states. Note the sequence that a larger LFSR progresses through has no easy-to-see pattern, even when you compare it to a smaller LFSR with a similar seed value. Similarly for a given order the sequence of values one circuit/polynomial generates, will have no easy-to-predict relationship to the sequence of values an LFSR with a different characteristic polynomial will have. All of this means that LFSRs that are sufficiently big can kind of act like halfway-decent pseudorandom number generators. They can (and do) use them for making noise signals in non-cryptographically important situations like signal processing and games all the time and the results are usually "good enough"; bonus that you can make this circuit using such a small number of components.

With this in mind, let's build another LFSR that we'll end up using in some later assignments.

Implement a 16-bit LFSR that implements the polynomial: x^{16}+x^{15}+x^2+1. The inputs should be just like before, just scaled up in size.

• clk_in: your clock signal.
• rst_in: your synchronous reset signal.
• [15:0] seed_in: A value set by the user to seed the LFSR on assertion of the reset signal.

The module should have one output:

• [15:0] q_out: The four values of the circuit Q15 through Q1

It may help to draw out the circuit for this LFSR first! Make sure where you're placing your feedback XOR's match the patterns you see in the four and eight-FF LFSR's shown above as well as the general pattern described. For local testing, feel free to modify the testbench provided for the four-bit LFSR above. It should literally just involve a few resizings of logics.

module lfsr_16 ( input wire clk_in, input wire rst_in, input wire [15:0] seed_in, output logic [15:0] q_out); endmodule

Loading...

The LFSR topology is also used in a slightly modified form of circuit known as a Cyclic Redundancy Check (CRC) which enables error detection in messages. CRC-32 is used in ethernet and has the polynomimal:

If you do anything with ethernet for a final project, you may very well need to end up implementing this.