CRC in USB

Five chapters have taken crc5_ok and has_crc16 as given. This is where they come from — and the interesting part is not the polynomial.

It is that a receiver does not compute the CRC of what it received and compare it with the CRC it was sent. It does something that looks stranger and is simpler, and getting the difference wrong produces a checker that works on every hand-written test vector and fails on the wire.

1. Two Polynomials, Two Jobs

Both are small relative to what they protect, and deliberately so. Chapter 11.1 §2 noted that a token is transmitted before every single transaction — five bits of overhead on eleven is already 45%, and a larger check would be paid millions of times a second for a field that changes slowly and predictably.

The CRC16 has the opposite economics. Sixteen bits over up to 8192 is a fraction of a percent, and the payload is the part that actually carries unpredictable content.

And Chapter 11.5 §4 already noted the gap: a handshake has neither, because it has no body. Its meaning rests on four bits of PID complement.

2. What a CRC Is

A CRC treats the message as a polynomial over GF(2) — coefficients that are 0 or 1, added without carry — and computes the remainder when that polynomial is divided by a chosen generator.

In hardware that is a shift register with feedback taps, and the arithmetic is XOR. Nothing more.

Two properties make it worth doing rather than summing the bytes:

• Every single-bit error is detected, because a single flipped bit changes the remainder by a fixed non-zero amount.
• Every burst error shorter than the CRC's width is detected, which matters because real corruption is bursty — noise, a marginal edge, a hub retiming glitch — rather than independent random flips.

Neither property is an accident of these particular polynomials. They follow from the generator having a non-zero constant term and the register being wide enough, which is what polynomial selection is about — and is a subject this chapter deliberately does not enter, because USB's two are fixed and the engineering question for a device is how to implement them, not which to pick.

3. The Residue

The idea this chapter exists for.

The naive receiver computes the CRC of the received data, compares it with the received check field, and declares a match. It works. It also requires holding the received check field, running a comparison, and getting the bit order of that comparison right.

The actual receiver does something else:

Feed the data and then the received check bits through the same machine. The register lands on a fixed constant — the residue — for every valid packet, regardless of the data.

Then the check is one equality against a constant, and there is no second value to hold and no comparison to get backwards.

4. Initialise to Ones, Complement at the End

Two conventions that look like decoration and are not — though only one of them is observable, which is §7's most interesting finding.

Initialise the register to all ones. A register starting at zero is unchanged by leading zero bits, so 0x00 0x01 and 0x01 would produce the same remainder. Starting at all ones makes the length of a leading run of zeros visible.

Complement the remainder before transmitting. Symmetrically, this makes trailing zeros detectable — without it, appending zero bytes to a valid packet leaves it valid.

5. The CRC Engine, as RTL

One parameterised module serves both CRCs, which is the right structure for a reason beyond code size: the two differ only in width, polynomial and residue, and writing them separately creates two places for the bit order to be wrong.

// ─────────────────────────────────────────────────────────────────────────
// usb_crc
//
// Classification: SIMPLIFIED SYNTHESIZABLE TEACHING RTL. One bit-serial
// engine, parameterised to serve both of section 1's codes.
//
// WHAT IT MODELS. Section 2's shift-and-XOR division, section 3's residue
// test, and section 4's two conventions.
//
// WHAT IT DOES NOT MODEL. The framing that decides which bits belong to the
// field (Module 14); the selection of WHICH crc to run, which comes from
// Chapter 11.5's group decode; the parallel (per-byte or per-word)
// formulation a real controller uses at high speed -- this is bit-serial
// for clarity, and the parallel version is the same polynomial unrolled;
// and the packet-level consequences of a failure, which are Chapters 11.1
// and 11.3.
//
// ── WHY ONE MODULE FOR BOTH ─────────────────────────────────────────────
// CRC5 and CRC16 differ in three parameters and nothing else. Two separate
// modules would be two places for the bit order, the initial value and the
// final complement to be wrong -- and section 8 measures a defect in
// exactly those conventions that NO self-consistent test can see. Sharing
// the implementation means a known-answer test on either code validates
// the conventions for both.
// ─────────────────────────────────────────────────────────────────────────
module usb_crc #(
  parameter int unsigned W       = 5,
  // CRC5: x^5 + x^2 + 1      -> 16'h0005
  // CRC16: x^16 + x^15 + x^2 + 1 -> 16'h8005
  parameter logic [15:0] POLY    = 16'h0005,
  // Section 3, DERIVED not quoted: the value the register lands on after a
  // valid field followed by its check bits.
  //   CRC5  -> 5'b01100
  //   CRC16 -> 16'h800D
  parameter logic [15:0] RESIDUE = 16'h000C
)(
  input  logic clk,
  input  logic rst_n,

  input  logic start,      // begin a new field
  input  logic bit_valid,
  input  logic bit_in,     // LSB first -- the order USB transmits in

  // What a TRANSMITTER appends, sent MSB first. Section 3: that asymmetry
  // is what makes the residue a constant.
  output logic [W-1:0] crc_tx,

  // What a RECEIVER tests, after feeding the data AND the received check
  // bits. Note it is NOT a comparison against a held value -- section 3.
  output logic         residue_ok
);

  logic [W-1:0] reg_q;

  // Section 2: the incoming bit mixes into the feedback. Dropping this term
  // (section 7's C3) leaves a machine that ignores its input entirely and
  // still produces a plausible-looking value.
  logic fb;
  assign fb = reg_q[W-1] ^ bit_in;

  // Section 4: the final complement, applied on transmit only -- which is
  // why it does NOT cancel, and why section 7's C4 is visible where C1 is
  // not.
  assign crc_tx = ~reg_q;

  assign residue_ok = (reg_q == RESIDUE[W-1:0]);

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      reg_q <= {W{1'b1}};
    end else if (start) begin
      // Section 4: all ones, so that leading zeros in the message are
      // visible. This value CANCELS in the residue -- see section 8.
      reg_q <= {W{1'b1}};
    end else if (bit_valid) begin
      reg_q <= {reg_q[W-2:0], 1'b0};
      if (fb) reg_q <= {reg_q[W-2:0], 1'b0} ^ POLY[W-1:0];
    end
  end

endmodule

What it models. Bit-serial polynomial division, in both its transmit and receive uses.

Engineering reason. Because the two uses are the same machine, and separating them is how the conventions drift apart.

Inputs. A start pulse, and a stream of bits with valid.

State retained. W flip-flops — 5 or 16.

Outputs. The value to transmit, and the receiver's verdict. Both are combinational views of the same register, which is what guarantees they cannot disagree about the convention.

Hardware implied. A shift register with two or three XOR taps. A CRC5 is five flip-flops and two XOR gates.

Reset behaviour. All ones, matching start, so a field begun without a start pulse after reset still behaves.

Assumptions. That bits arrive LSB-first for the message and MSB-first for a received check field — and that assumption is checkable, which is §3's point; that start precedes every field; and that the caller knows which parameterisation to use, from Chapter 11.5's group decode.

Omissions. Framing, code selection, the parallel formulation, and the packet-level consequences — in the header.

What DV should verify. That a clean field plus its check always yields the residue, for any data; that every single-bit error fails it; that the transmitted CRC matches absolute known values — not merely its own receiver; that the residue constant is right; and that the initial value and final complement are the specified ones.

6. Mutation Test

Five mutations. The bench has two independent kinds of check, and which mutations each kind catches is the finding:

• Self-consistency — 56 CRC5 tokens and 6 CRC16 payloads fed through compute-then-check, confirming the residue; plus 161 single-bit errors confirming detection.
• Known-answer — the transmitted CRC compared against absolute values from an independently written model: 6 CRC5 vectors and 4 CRC16 vectors.

Look at the two extreme rows before the individual entries. C1 fails only the known-answer tests. C5 fails only the self-consistency tests. §8 is about why that pairing is not a coincidence.

C1 — initialise the register to zero

Measured: all 10 known-answer vectors wrong. Every self-consistency check passed — the residue held on all 62 fields and all 161 single-bit errors were still detected.

§4's callout, realised. The initial value contributes identically to the compute pass and the check pass, so it cancels. A device with this defect is perfectly self-consistent and cannot interoperate with anything.

C2 — drop a polynomial tap

Measured: 6 of 6 and 3 of 4 known answers wrong; the residue failed on every field.

Changing the generator changes everything downstream, and — importantly — the residue constant no longer matches the parameter, so the design fails its own check. Loud, immediate, caught by everything.

The one CRC16 vector it got right is the zero-length payload, whose CRC is 0x0000 because nothing is fed through the register at all. A test vector that exercises no data cannot detect a defect in the datapath — which is a small, sharp reminder that a known-answer suite needs vectors that actually move bits.

C3 — do not mix the input into the feedback

assign fb = reg_q[W-1];   // MUTANT C3: the data is ignored

Measured: 5 of 6 and 2 of 4 known answers wrong; the residue failed on every field.

The register free-runs on its own contents. The CRC becomes a function of the message length alone — which is why it still gets some vectors right: two messages of the same length produce the same value, and a vector whose correct answer happens to coincide is not a pass in any meaningful sense.

It is the mutation that most resembles working code, because the output still changes as bits are clocked and still looks scrambled.

C4 — omit the final complement

Measured: all 10 known answers wrong; the residue failed on every field; and 10 single-bit errors went undetected.

§4's second convention. Unlike C1 it is applied once, on transmit only, so it does not cancel — and the extra 10 undetected single-bit errors are the concrete cost of losing trailing-zero sensitivity.

C5 — compare against the wrong residue constant

Measured: every self-consistency check failed. All 10 known-answer vectors passed.

The mirror of C1. crc_tx is untouched, so everything the device transmits is perfectly correct — it simply rejects every packet it receives, including its own.

A device with C5 is a correct transmitter and a broken receiver, and a bench that only checked transmitted values would report it as flawless.

7. The Assertions

// ─────────────────────────────────────────────────────────────────────────
// Classification: TEACHING ASSERTIONS about the CRC engine.
// R-properties are the residue contract; D the detection guarantee;
// K the known-answer anchors. Note that K cannot be expressed as a property
// over this design's own signals -- section 8, in assertion form.
// ─────────────────────────────────────────────────────────────────────────

// R1 -- A VALID FIELD PLUS ITS CHECK YIELDS THE RESIDUE. The core contract.
// Written over a sequence because the claim is about the END of a field,
// and `field_complete` is a bench/monitor signal marking it.
property p_residue_on_valid;
  @(posedge clk) disable iff (!rst_n)
    (field_complete && field_was_uncorrupted) |-> residue_ok;
endproperty
assert property (p_residue_on_valid);   // via bind

// R2 -- AND NOT OTHERWISE, FOR A SINGLE-BIT ERROR. Section 2's guarantee,
// as an assertion rather than an assumption. Restricted to single-bit
// because that is what the code actually guarantees -- writing it for ALL
// corruptions would be false, and a property that is false gets weakened
// until it says nothing.
property p_single_bit_detected;
  @(posedge clk) disable iff (!rst_n)
    (field_complete && (corruption_weight == 1)) |-> !residue_ok;
endproperty
assert property (p_single_bit_detected);   // via bind

// D1 -- THE REGISTER ONLY MOVES ON A VALID BIT OR A START. Catches a shift
// enable that leaks, which would silently consume idle cycles as data.
property p_no_spontaneous_shift;
  @(posedge clk) disable iff (!rst_n)
    (crc_state != $past(crc_state)) |-> $past(bit_valid || start);
endproperty
assert property (p_no_spontaneous_shift);   // via bind

// D2 -- START LOADS THE SPECIFIED INITIAL VALUE. Section 4's first
// convention. This is the ONLY property here that can catch section 6's C1,
// and it can only do so by naming the constant -- which is to say, by
// importing a fact from outside the design.
property p_start_loads_init;
  @(posedge clk) disable iff (!rst_n)
    start |=> (crc_state == {W{1'b1}});
endproperty
assert property (p_start_loads_init);   // via bind

// D3 -- THE TRANSMITTED VALUE IS THE COMPLEMENT OF THE REGISTER. Section
// 4's second convention, and section 6's C4.
property p_tx_is_complement;
  @(posedge clk) disable iff (!rst_n)
    crc_tx == ~crc_state;
endproperty
assert property (p_tx_is_complement);   // via bind

// K -- THE KNOWN ANSWERS. There is NO property over this design's own
// signals that can express these, because the design has no access to the
// truth: it would have to compute the expected value, and computing it is
// the thing being checked. They are checks in the BENCH, not assertions on
// the DUT, and section 8 is the argument for why that distinction is worth
// making explicitly rather than glossing over:
//
//     CRC5 (0x000) == 5'b01000       CRC5 (0x715) == 5'b10111   <- spec example
//     CRC5 (0x7ff) == 5'b00010       CRC16(empty)  == 16'h0000
//     CRC16(8'h00) == 16'h02fd       CRC16(0..7)   == 16'h9da1

Every assertion here needs a bind, and several need signals that do not exist in the design — whether the field was corrupted, how many bits were flipped, what the truth was. That is not an inconvenience to be engineered away.

The K block is the point, and it is deliberately not written as a property. A known-answer check cannot be an assertion on the DUT, because an assertion can only reference the DUT's own signals, and the DUT does not know the right answer — if it did, the check would be circular. §6's C1 is the measured proof: it satisfies every property that can be written over this design's signals except one that names a constant from outside.

8. Verification

This chapter's commit point is the check agreed with the specification, not merely with itself.

Stimulus.

• 56 CRC5 tokens spanning the address and endpoint space, computed then checked;
• all single-bit errors in the 11 data bits and in the 5 check bits — 85 cases;
• 6 CRC16 payloads from 1 to 40 bytes, plus 76 single-bit errors across them;
• 10 known-answer vectors whose expected values came from an independently written model, two of which are externally anchored.

Observation. The residue verdict, and — separately and crucially — the transmitted CRC value, which a self-consistent bench never examines.

Reference model. Two, and they do different jobs. A bit-level model of the division, used to generate the known answers. And the design itself, used as its own receiver for the residue tests. §6 is the measurement showing that neither is sufficient.

Coverage — crosses:

• data length: minimum, typical, maximum, and zero — the empty payload is a real case and §6's C2 shows it is also a weak vector
• corruption position: in the data × in the check field — both, because a checker can be right about one and wrong about the other
• corruption weight: 0, 1, and 2 — with the expectation that weight 2 may pass, which is the guarantee's honest boundary
• both parameterisations, sharing the stimulus generator

Negative cases with defined outcomes: every single-bit error fails the residue; a valid field always passes regardless of content; the transmitted value matches the known answers; and the register never advances without a valid bit.

9. Debugging: the Device Nothing Will Talk To

A device enumerates on no host. A protocol analyser shows the device transmitting packets that the analyser itself flags as CRC errors. The device's own loopback self-test passes perfectly, every time, at every data rate.

What does self-test passes, everything else fails tell you? That the device is internally consistent and externally wrong — which is a narrow and very informative category. Something both ends of its self-test share is not what the rest of the world uses.

What do both ends of a loopback share? Every convention: the polynomial, the bit order, the initial value, the final complement. A self-test cannot detect an error in any of them, because the error cancels.

Which is the most likely? §6 ranks them by what a self-test hides. C1 — the initial value — is the only one that passes a self-test completely, so it is the first thing to check, not the last.

How do you check it without a reference implementation? Compute one known answer by hand. CRC5(0x715) = 0b10111 is in the specification with its working shown. If the device produces anything else, the conventions are wrong and the self-test was never going to say so.

What if the CRC value is right and packets are still rejected? Then it is the bit order on the wire rather than the computation — the value is correct and being transmitted LSB-first when it should be MSB-first. §3's residue derivation is the test: under the wrong order there is no constant, so a receiver built the same way would also fail, and the self-test would then not pass. The fact that the self-test passes is evidence against this hypothesis, which is worth noticing because it narrows the search.

And why does the analyser's verdict matter so much here? Because it is the only participant that did not get its conventions from this project. An external checker is the entire content of §8 — arriving, as it usually does, as a piece of test equipment rather than as a design decision.

The signature to keep: self-test passes, the world rejects it, means a shared convention is wrong — and the search should start with whichever convention cancels.

10. Common Misconceptions

11. Reason It Through

A team ports a working USB device from full speed to high speed. The CRC engine is reused unchanged, but the datapath is widened to process 8 bits per clock instead of 1. The parallel CRC is derived by unrolling the serial one, and verified by comparing it against the serial version on ten thousand random payloads. All agree.

Is that verification sound? For the question it asks, yes — the parallel engine computes the same function as the serial one, and ten thousand random payloads is strong evidence for that.

What question does it not ask? Whether the serial one was right. §6's C1 is the case: if the original had a wrong initial value, the parallel version inherits it, agrees perfectly, and the comparison confirms nothing about correctness.

But the device worked at full speed — doesn't that prove the serial engine? It does, and this is the part worth being careful about. A device that interoperated was externally validated, whether or not anybody intended it. The bug cannot be C1.

So what is actually at risk in this port? The things that changed: bit ordering within the byte, the handling of payloads that are not a whole number of words, and the initial and final conditions at the boundaries of a widened datapath. None of those is exercised by comparing against the serial version on whole-byte random payloads.

What is the missing stimulus? Payload lengths that are not multiples of the datapath width — including zero — and payloads whose length straddles a word boundary. §6's C2 showed a zero-length vector validating nothing; here the opposite risk applies, since a widened engine has its most delicate logic exactly at partial words.

And what should the bench gain? The known answers, carried over. They validated conventions in the serial engine and they validate the same conventions in the parallel one, for free — and unlike the serial-versus-parallel comparison, they cannot be satisfied by two implementations sharing a mistake.

The transferable point: comparing a new implementation against an old one verifies the port, not the function. It is the right check and it is not sufficient, because it inherits every property the old one had — including the wrong ones. Any anchor to something external survives the port and should be carried across it.

12. Understanding Check

13. Summary

USB has two CRCs: five bits over a token's eleven, sixteen over a payload's up to 8192. Both are shift registers with XOR taps, guaranteeing every single-bit error and every burst shorter than the register.

A receiver does not recompute and compare. It feeds the data and the received check bits through the same machine and tests that the register lands on a residue — 0b01100 for CRC5, 0x800D for CRC16. Both derived here rather than quoted, cross-checked between an independent model and the RTL, and anchored externally by CRC16(empty) = 0x0000 and the specification's own worked example CRC5(0x715) = 0b10111.

The derivation proves the bit order. Data goes LSB-first and the remainder MSB-first, and under the other convention there is no constant at all — 56 tokens produced four different values instead of one.

Two conventions look alike and behave oppositely. The final complement is applied once, on transmit, and does not cancel. The initial value cancels completely — the residue is identical whether the register starts at all ones or at zero.

§6 measured five mutations against two independent kinds of check, and the two extremes are the chapter:

• Initialising to zero passed every self-consistency test — residue held on all 62 fields, all 161 single-bit errors still detected — and failed all 10 known-answer vectors. A device that is perfectly self-consistent and cannot talk to anything.
• A wrong residue constant failed every self-consistency test and passed all 10 known-answer vectors. A correct transmitter and a broken receiver.

A self-consistency test proves the design agrees with itself. A known-answer test proves it agrees with the world. Neither catches what the other does.

And §8 collects Module 11's whole verification thread: across six chapters, seven distinct ways a passing bench was wrong — an unreachable state, a reset applied to already-reset state, a bench driving what the design should cause, a model sharing the design's misunderstanding, a failure mode the environment model excluded, an empty negative space, and no anchor outside the design. Not one was a wrong expected value, every one was a question the bench did not ask, and no coverage report would have shown any of them.

14. Where Module 11 Leaves You

Every packet on a USB bus is now accounted for. A token names a destination; a data packet carries a payload and a sequence bit; a handshake carries a one-byte verdict; an SOF broadcasts a number to nobody. All four are one structure — a PID whose nibbles check each other, an optional body, an optional CRC — and the group bits of that PID say which.

What the module deliberately did not build is the sequencing. Every chapter described a packet in isolation and stopped at its boundary. A token is followed by a data packet, which is answered by a handshake — and not one of those relationships has been specified here.

Module 12 is the Transaction Model, where the three-packet rhythm becomes a state machine with timeouts, and the questions this module kept deferring get answered: how long a device may take to respond before the host gives up, what happens when a packet arrives in the wrong phase, and how the handshake in Chapter 11.3 and the toggle in Chapter 11.2 combine into a transaction that either completed or did not.

Browse the full path on the USB tutorials index.