Error Detection and Correction: CRC and FEC
Compute a CRC by hand for a short message, and say what a block FEC can and cannot correct.
You Will Be Able To
- Compute a short CRC by hand with the shift-and-XOR register.
- Explain what the seed, the inversion, the bit order and the residue are for.
- Predict which errors a CRC catches and which it misses.
- Explain why a Reed-Solomon code corrects a burst in one symbol but not across two.
- Lesson
- P10.11
- Time
- 40 min
- Runs on
- Your browser
- Check
- 5 questions
A new receiver rejects every packet, even on a perfect cable. Its checker runs the CRC over the data and the CRC field, then compares the register with zero. For this CRC a good packet never ends at zero.
| Sender | CRC of "123456789" (check value) | Receiver register at the end | A clean receiver says |
|---|---|---|---|
| Clean CRC-32 | CBF43926 | C704DD7B | accepted |
tx.no_invert = 1: field not inverted | 340BC6D9 | 0000 | rejected |
tx.msb_first = 1: bytes enter bit 7 first | 1898913F | D7C9CA4F | rejected |
tx.seed_zero = 1: register starts at 0 | D202D277 | 79990C74 | rejected |
Both ends with msb_first = 1 | 1898913F | C704DD7B | accepted |
Bench run. A good frame leaves C704DD7B in the register, not zero. The last row passes because both ends share the same mistake, so it fails only against another vendor.
A CRC Is a Remainder
A cyclic redundancy check (CRC) treats the message as one long binary number. It divides that number by a fixed generator and keeps the remainder. The division uses XOR in place of subtraction.
Hardware does the division one bit at a time. USB 2.0 describes the register in §8.3.5:
Compare
XOR the incoming data bit with the top bit of the register.
Shift
Shift the register left by one. A zero enters at the bottom.
Subtract
When the XOR in step 1 was 1, XOR the generator into the register.
00101 and the register starts at 11111.- Cycle 0
Data bit 1 and top bit 1 are equal. The register only shifts:
11111becomes11110. - Cycle 1
Data bit 0 and top bit 1 differ. The register shifts, then XORs
00101:11001. - Cycle 4
Top bit 0 and data bit 1 differ too. Shift, then XOR:
00111. - Cycle 10
After the last bit the register holds the remainder
01000. The sender inverts it and sends10111.
Bench run. The receiver ran the same register over the 11 bits and the 5 field bits. It ended at 01100, the residual that USB 2.0 §8.3.5.1 gives.
The sender appends the CRC to the message. The receiver divides again. A different remainder means the bits changed on the way.
Seed, Inversion, Bit Order and Residue
Four settings turn the plain division into a CRC that a specification can pin down.
The seed is the starting value of the register. With a seed of zero, leading zero bits leave the register at zero. Extra or missing zeros at the front then go unseen. A seed of all ones removes that blind spot.
The sender inverts the remainder before it sends it. Without this, extra zero bits after the CRC field would go unseen.
The bit order says which bit of each byte enters the register first. USB 3.2 feeds each byte in bit 0 first (§7.2.1.2.2). USB 2.0 sends the inverted CRC with its top bit first (§8.3.5).
The residue is what the receiver's register holds after the message and the CRC field. For a good packet it is one fixed constant. The receiver compares against that constant.
| CRC | Generator | Seed | Residual at the receiver | Source |
|---|---|---|---|---|
| USB 2.0 token CRC-5 | x^5 + x^2 + 1 (00101) | all ones | 01100 | USB 2.0 §8.3.5.1 |
| USB 2.0 data CRC-16 | x^16 + x^15 + x^2 + 1 (8005h) | all ones | 800Dh | USB 2.0 §8.3.5.2 |
| USB 3.2 header CRC-16 | 100Bh | FFFFh | F6AAh | USB 3.2 §7.2.1.1.2 |
| USB 3.2 payload CRC-32 | 04C1 1DB7h | FFFF FFFFh | C704 DD7Bh | USB 3.2 §7.2.1.2.2 |
All four invert the remainder before sending it. The bench reproduces the last three residuals on the message "123456789" and the first on the token above.
What a CRC Catches and Misses
A burst is a group of wrong bits that starts and ends with a wrong bit. The bench hit a CRC-32 frame with 600 random bursts of 1 to 32 bits. It missed 0. A CRC of n bits catches every burst of up to n bits.
USB 2.0 states that its CRCs catch all single-bit and double-bit errors (§8.3.5).
A CRC is blind to one family of errors: patterns that are a multiple of the generator. The bench flipped 15 bits in the shape of the generator itself. The receiver accepted the frame.
For random damage, a 32-bit CRC lets about one bad frame in 2^32 through. That is a small number, but it is not zero.
A CRC only detects. It cannot say which bit is wrong, so the link must send the packet again.
A Byte per Clock, and the Distance Rule
A CRC in RTL takes a byte, a word or more per clock. The byte-wide form is the bit-serial one written out for eight steps. On 2,000 random messages they disagreed on 0 CRC-32 values.
Codes are compared by their minimum distance d: the fewest bit or symbol changes that turn one code word into another. A code detects up to d − 1 errors, and corrects up to (d − 1) / 2.
The codes below show the rule. SEC has d = 3: it corrects one error, and two errors often look like one and are miscorrected. SEC-DED has d = 4: it corrects one and detects two. RS(15,13) has d = 3 in symbols.
From Detection to Correction
Forward error correction (FEC) adds check bits so that the receiver can repair the data itself.
The idea is distance. Valid code words are chosen so that any two differ in several bits. One flipped bit leaves the word closest to the original, so the decoder can step back.
The bench has a code with 64 data bits and 8 check bits. It corrected 72 of 72 single-bit errors. It flagged 2,556 of 2,556 double-bit errors and repaired none of them. Such a code is called SEC-DED: single error correct, double error detect.
Reed-Solomon Corrects Whole Symbols
Errors on a fast link come in bursts. A Reed-Solomon (RS) code groups bits into symbols and corrects whole symbols. A symbol with one wrong bit and a symbol with all bits wrong cost the same.
- Neutral
- Datapath
- Result
- Data
- Encode
Two check symbols are added so that two sums over the word, the syndromes, are both zero.
- One wrong symbol
All four bits of symbol 5 flip. The two syndromes give the position and the value of the error. The decoder restores the word.
- The same burst, moved
The same four flips now cover the last two bits of symbol 5 and the first two of symbol 6. That is two wrong symbols.
- Miscorrection
The decoder still finds one position and one value that fit the syndromes. It changes one symbol, reaches a valid but wrong word, and reports success.
Read the diagram as text
- 13 data symbols: 52 bits
- Encoder: adds 2 check symbols
- 15-symbol code word: 60 bits
- Burst in one symbol: 4 wrong bits
- Burst across two: 4 wrong bits
- Decoder: 2 syndromes
- Corrected: original word
- Wrong word: reported as corrected
- 13 data symbols → Encoder
- Encoder → 15-symbol code word
- 15-symbol code word → Burst in one symbol
- Burst in one symbol → Burst across two: shift by 2 bits
- Burst in one symbol → Decoder
- Burst across two → Decoder
- Decoder → Corrected
- Decoder → Wrong word
Bench run on RS(15,13): 225 of 225 single-symbol errors corrected. Of 23,625 two-symbol errors, 3,150 were flagged and 20,475 became a different valid word.
A code with 2t check symbols corrects up to t wrong symbols. The count is in symbols, never in bits.
USB4 uses RS(198,194) on 8-bit symbols, which corrects two symbols per block (§3.1.1.2, §4.3.1.6). Its Gen 4 code is RS(504,480) on 11-bit symbols and corrects 12 (§4.3.2.3).
The bench also has a larger code: 528 symbols of 10 bits, with 14 check symbols. A 70-bit burst is seven wrong symbols to this code. All 14 syndromes went non-zero. The bench does not decode this code. It only shows the detection.
Coding Gain, Latency and Interleaving
An FEC is rated by what it buys and what it costs. It buys coding gain: the same decoded error ratio at a lower signal-to-noise ratio. It costs extra bits and time.
| Code (bench) | Raw BER for 1e-12 decoded | Coding gain |
|---|---|---|
| SEC (136,128) | 1.18e-07 | 2.4 dB |
| RS(15,13) | 1.76e-07 | 2.2 dB |
| RS(528,514), t = 7 | 6.87e-05 | 5.2 dB |
Bench computation: hard decisions on a channel with Gaussian noise. "Decoded" counts failed code words per data bit. The gain is net of the 10 log10(n/k) the check bits cost.
A code that corrects more symbols tolerates a much worse raw link. Here the long code with t = 7 accepts a raw BER near 1e-4, while the single-error codes need about 1e-7.
The cost is latency: a decoder must hold a whole code word before it can correct anything. At 10 Gb/s a 136-bit word is 13.6 ns; a word of 528 ten-bit symbols is 528 ns.
Interleaving spreads a burst over several code words, so each word sees only what it can correct.
| RS(15,13) words on the line | Words right after 300 bursts of 4 symbols |
|---|---|
| One word after another | 884 of 1,200 |
| Interleaved, depth 4 | 1,200 of 1,200 |
Bench run of the library's RS(15,13) decoder, which corrects one symbol per word.
Interleaving adds latency too: depth 4 must collect four whole words before the first one can be decoded.
Try It
CBF43926 is the well-known check value of this CRC-32 for the text "123456789".
The receiver never compares two CRCs. It runs the field through the register and looks for the residue.
Change 8'h01 to 8'h00 in the last block. Nothing is flipped, and the register ends at the residue again.
CRC-32 of 123456789: check value cbf43926 register after message and field: c704dd7b, residue ok 1 one flipped bit: register 052c0393, residue ok 0Read included file: hs_pkg.sv
`timescale 1ns/1ns
// hs_pkg.sv: shared pure functions, and the bench random generator (read-only).
package hs_pkg;
// xorshift32 (Marsaglia 2003): a linear generator over GF(2), period 2^32 - 1. A zero state is
// replaced by 1, because zero maps to itself.
function automatic [31:0] xs32(input [31:0] s);
reg [31:0] x;
x = (s == 32'd0) ? 32'd1 : s;
x = x ^ (x << 13); x = x ^ (x >> 17); x = x ^ (x << 5);
return x;
endfunction
// A Fibonacci PRBS generator x^n + x^m + 1 (PRBS7: 7,6; PRBS9: 9,5; PRBS15: 15,14; PRBS23: 23,18;
// PRBS31: 31,28). The output bit is s[n-1]; the next state shifts the feedback into bit 0.
function automatic [31:0] prbs_next(input [31:0] s, input int n, input int m);
reg fb;
fb = s[n-1] ^ s[m-1];
return ((s << 1) | {31'd0, fb}) & ((n == 32) ? 32'hffffffff : ((32'd1 << n) - 32'd1));
endfunction
function automatic int ones(input [63:0] v);
int n; n = 0;
for (int i = 0; i < 64; i++) n += v[i];
return n;
endfunction
// GF(16) with x^4 + x + 1, and GF(1024) with x^10 + x^3 + 1: shift-and-add multiply, no tables.
function automatic [3:0] gf16_mul(input [3:0] a, input [3:0] b);
reg [3:0] p, x; p = 4'd0; x = a;
for (int i = 0; i < 4; i++) begin
if (b[i]) p = p ^ x;
x = x[3] ? ({x[2:0], 1'b0} ^ 4'b0011) : {x[2:0], 1'b0};
end
return p;
endfunction
function automatic [3:0] gf16_pow(input int e); // alpha^e, alpha = x
reg [3:0] p; int k; p = 4'd1; k = e % 15; if (k < 0) k += 15;
for (int i = 0; i < k; i++) p = gf16_mul(p, 4'd2);
return p;
endfunction
function automatic int gf16_log(input [3:0] a); // -1 for 0
reg [3:0] p; p = 4'd1;
if (a == 4'd0) return -1;
for (int i = 0; i < 15; i++) begin if (p == a) return i; p = gf16_mul(p, 4'd2); end
return -1;
endfunction
function automatic [9:0] gf1024_mul(input [9:0] a, input [9:0] b);
reg [9:0] p, x; p = 10'd0; x = a;
for (int i = 0; i < 10; i++) begin
if (b[i]) p = p ^ x;
x = x[9] ? ({x[8:0], 1'b0} ^ 10'b0000001001) : {x[8:0], 1'b0};
end
return p;
endfunction
function automatic [9:0] gf1024_pow(input int e);
reg [9:0] p; int k; p = 10'd1; k = e % 1023; if (k < 0) k += 1023;
for (int i = 0; i < k; i++) p = gf1024_mul(p, 10'd2);
return p;
endfunction
endpackage
// hs_rng: the bench's random numbers. Same seed, same numbers, on every engine.
module hs_rng;
int unsigned s = 32'h2545f491;
function automatic void seed(input int unsigned v); s = (v == 0) ? 32'd1 : v; endfunction
function automatic int unsigned next(); s = hs_pkg::xs32(s); return s; endfunction
function automatic int below(input int n); s = hs_pkg::xs32(s); return (n <= 0) ? 0 : int'(s % n); endfunction
function automatic bit bit1(); s = hs_pkg::xs32(s); return s[16]; endfunction
function automatic bit chance_ppm(input int ppm); s = hs_pkg::xs32(s); return (s % 1000000) < ppm; endfunction
function automatic [7:0] byte8(); s = hs_pkg::xs32(s); return s[23:16]; endfunction
endmodule
Read included file: hs_code.sv
`timescale 1ns/1ns
// hs_code.sv: line codes, CRCs and scramblers (read-only).
// ---------------------------------------------------------------------------------------------
// hs_8b10b: 8b/10b encoder and decoder with running disparity and the 12 K codes.
// code[9:0] = {a,b,c,d,e,i,f,g,h,j}; bit a (code[9]) goes on the wire first. rd: 0 = RD-, 1 = RD+.
// encode(d, k, rd_in) -> {rd_out, code[9:0]} (11 bits)
// decode(code, rd_in) -> {rd_out, disp_err, code_err, k, d[7:0]} (12 bits)
// enc(d, k) / dec(code): the same, with the running disparity kept in rd_tx / rd_rx
// A K request for a byte that is not one of the 12 K codes is encoded as data and counted in bad_k.
// Decoder: code_err = the code is in neither column of the table; disp_err = it is a valid code
// only in the other column. rd_out follows the sub-block rule on the received bits.
// Faults: no_rd (always the RD- column), a7_never (never the alternate D.x.A7),
// keep_rd_on_unbalanced (the 4b sub-block is chosen with the disparity from before the 6b one),
// no_balanced_flip (D.07 and D.x.3 keep their RD- form at RD+), dec_no_disp_check.
module hs_8b10b;
bit no_rd = 0, a7_never = 0, keep_rd_on_unbalanced = 0, no_balanced_flip = 0, dec_no_disp_check = 0;
bit trace = 0;
bit rd_tx = 0, rd_rx = 0;
int bad_k = 0, symbols = 0, code_errs = 0, disp_errs = 0;
bit last_k = 0, last_code_err = 0, last_disp_err = 0;
bit valid_m [0:1023]; bit valid_p [0:1023]; bit [8:0] kd [0:1023]; bit built = 0;
function automatic [5:0] t6(input [4:0] x); // 5b/6b, RD- column, abcdei
case (x)
5'd0: return 6'b100111; 5'd1: return 6'b011101; 5'd2: return 6'b101101; 5'd3: return 6'b110001;
5'd4: return 6'b110101; 5'd5: return 6'b101001; 5'd6: return 6'b011001; 5'd7: return 6'b111000;
5'd8: return 6'b111001; 5'd9: return 6'b100101; 5'd10: return 6'b010101; 5'd11: return 6'b110100;
5'd12: return 6'b001101; 5'd13: return 6'b101100; 5'd14: return 6'b011100; 5'd15: return 6'b010111;
5'd16: return 6'b011011; 5'd17: return 6'b100011; 5'd18: return 6'b010011; 5'd19: return 6'b110010;
5'd20: return 6'b001011; 5'd21: return 6'b101010; 5'd22: return 6'b011010; 5'd23: return 6'b111010;
5'd24: return 6'b110011; 5'd25: return 6'b100110; 5'd26: return 6'b010110; 5'd27: return 6'b110110;
5'd28: return 6'b001110; 5'd29: return 6'b101110; 5'd30: return 6'b011110; default: return 6'b101011;
endcase
endfunction
function automatic [3:0] t4d(input [2:0] y); // 3b/4b data, RD- column, fghj (y = 7 is P7)
case (y)
3'd0: return 4'b1011; 3'd1: return 4'b1001; 3'd2: return 4'b0101; 3'd3: return 4'b1100;
3'd4: return 4'b1101; 3'd5: return 4'b1010; 3'd6: return 4'b0110; default: return 4'b1110;
endcase
endfunction
function automatic [3:0] t4k(input [2:0] y); // 3b/4b for K codes, RD- form before the flip
case (y)
3'd0: return 4'b1011; 3'd1: return 4'b0110; 3'd2: return 4'b1010; 3'd3: return 4'b1100;
3'd4: return 4'b1101; 3'd5: return 4'b0101; 3'd6: return 4'b1001; default: return 4'b0111;
endcase
endfunction
function automatic bit k_ok(input [7:0] d);
return d[4:0] == 5'd28 || d == 8'hf7 || d == 8'hfb || d == 8'hfd || d == 8'hfe;
endfunction
function automatic int n6(input [5:0] v); return v[0] + v[1] + v[2] + v[3] + v[4] + v[5]; endfunction
function automatic int n4(input [3:0] v); return v[0] + v[1] + v[2] + v[3]; endfunction
// running disparity at the end of a sub-block (more ones: +; more zeros: -; 000111 and 0011: +; 111000 and 1100: -)
function automatic bit rd6(input [5:0] v, input bit rd);
return (n6(v) > 3) ? 1'b1 : (n6(v) < 3) ? 1'b0 : (v == 6'b000111) ? 1'b1 : (v == 6'b111000) ? 1'b0 : rd;
endfunction
function automatic bit rd4(input [3:0] v, input bit rd);
return (n4(v) > 2) ? 1'b1 : (n4(v) < 2) ? 1'b0 : (v == 4'b0011) ? 1'b1 : (v == 4'b1100) ? 1'b0 : rd;
endfunction
// faults: [0] no_rd [1] a7_never [2] keep_rd_on_unbalanced [3] no_balanced_flip
function automatic [10:0] core(input [7:0] d, input bit k, input bit rd_in, input [3:0] f);
reg [5:0] six; reg [3:0] four; reg rd0, r6, rd1, a7, kk; reg [4:0] x; reg [2:0] y; int o6, o4;
x = d[4:0]; y = d[7:5]; kk = k && k_ok(d); rd0 = f[0] ? 1'b0 : rd_in;
six = (kk && x == 5'd28) ? 6'b001111 : t6(x); o6 = n6(six);
if (rd0 && (o6 != 3 || (six == 6'b111000 && !f[3]))) begin six = ~six; o6 = 6 - o6; end
r6 = (o6 > 3) ? 1'b1 : (o6 < 3) ? 1'b0 : (six == 6'b000111) ? 1'b1 : (six == 6'b111000) ? 1'b0 : rd0;
rd1 = f[2] ? rd0 : r6;
if (kk) begin
four = t4k(y); if (rd1) four = ~four;
end else begin
a7 = (y == 3'd7) && !f[1] && ((!rd1 && (x == 5'd17 || x == 5'd18 || x == 5'd20)) || (rd1 && (x == 5'd11 || x == 5'd13 || x == 5'd14)));
four = a7 ? 4'b0111 : t4d(y);
if (rd1 && (n4(four) != 2 || (four == 4'b1100 && !f[3]))) four = ~four;
end
o4 = n4(four);
return {(o4 > 2) ? 1'b1 : (o4 < 2) ? 1'b0 : (four == 4'b0011) ? 1'b1 : (four == 4'b1100) ? 1'b0 : r6, six, four};
endfunction
function automatic [10:0] encode(input [7:0] d, input bit k, input bit rd_in);
if (k && !k_ok(d)) bad_k++;
return core(d, k, rd_in, {no_balanced_flip, keep_rd_on_unbalanced, a7_never, no_rd});
endfunction
function automatic void build();
reg [10:0] c;
for (int i = 0; i < 1024; i++) begin valid_m[i] = 0; valid_p[i] = 0; kd[i] = 9'd0; end
for (int i = 0; i < 268; i++) begin
reg [7:0] d; reg k;
if (i < 256) begin d = i[7:0]; k = 0; end
else begin k = 1; d = (i < 264) ? {3'(i - 256), 5'd28} : (i == 264) ? 8'hf7 : (i == 265) ? 8'hfb : (i == 266) ? 8'hfd : 8'hfe; end
c = core(d, k, 1'b0, 4'd0); valid_m[c[9:0]] = 1; kd[c[9:0]] = {k, d};
c = core(d, k, 1'b1, 4'd0); valid_p[c[9:0]] = 1; kd[c[9:0]] = {k, d};
end
built = 1;
endfunction
function automatic [11:0] decode(input [9:0] code, input bit rd_in);
reg here, there, ce, de, r;
if (!built) build();
here = rd_in ? valid_p[code] : valid_m[code];
there = rd_in ? valid_m[code] : valid_p[code];
ce = !(here || there); de = !ce && !here && !dec_no_disp_check;
r = rd4(code[3:0], rd6(code[9:4], rd_in));
return {r, de, ce, ce ? 9'd0 : kd[code]};
endfunction
function automatic [9:0] enc(input [7:0] d, input bit k);
reg [10:0] r; r = encode(d, k, rd_tx); rd_tx = r[10];
if (trace) $display("s%0d TX %s%0d.%0d code=%b rd=%s", symbols, (k && k_ok(d)) ? "K" : "D", d[4:0], d[7:5], r[9:0], r[10] ? "+" : "-");
symbols++;
return r[9:0];
endfunction
function automatic [8:0] dec(input [9:0] code);
reg [11:0] r; r = decode(code, rd_rx); rd_rx = r[11];
last_disp_err = r[10]; last_code_err = r[9]; last_k = r[8];
if (r[9]) code_errs++; if (r[10]) disp_errs++;
if (trace && (r[9] || r[10])) $display("RX %b %s", code, r[9] ? "code error" : "disparity error");
return r[8:0];
endfunction
function automatic bit comma7(input [6:0] w); return w == 7'b0011111 || w == 7'b1100000; endfunction
endmodule
// ---------------------------------------------------------------------------------------------
// hs_crc: a CRC of 1 to 32 bits with any polynomial, seed, bit order and final inversion.
// The register shifts left; the polynomial omits the x^width term. The field is sent register bit
// width-1 first (USB 2.0, USB 3.2 and Ethernet all send it this way).
// use_crc32(), use_crc16_usb2(), use_crc5_usb2(), use_crc16_usb3(): parameter sets
// reset(), crc_bit(b), crc_byte(v), crc_bits(v, n), field(), field_bit(i), check_value(), crc_residue_ok()
// Faults: msb_first (bytes enter MSB first), no_invert (the field is not complemented), seed_zero.
module hs_crc;
int width = 32;
bit [31:0] poly = 32'h04c11db7, seed = 32'hffffffff, residue = 32'hc704dd7b;
bit lsb_first = 1, invert = 1;
bit msb_first = 0, no_invert = 0, seed_zero = 0;
bit [31:0] r = 32'hffffffff;
function automatic [31:0] mask(); return (width >= 32) ? 32'hffffffff : ((32'd1 << width) - 32'd1); endfunction
function automatic void reset(); r = seed_zero ? 32'd0 : (seed & mask()); endfunction
function automatic void set(input int w, input [31:0] p, input [31:0] s, input [31:0] res, input bit lsb, input bit inv);
width = w; poly = p; seed = s; residue = res; lsb_first = lsb; invert = inv; reset();
endfunction
function automatic void use_crc32(); set(32, 32'h04c11db7, 32'hffffffff, 32'hc704dd7b, 1, 1); endfunction
function automatic void use_crc16_usb2(); set(16, 32'h8005, 32'hffff, 32'h800d, 1, 1); endfunction
function automatic void use_crc5_usb2(); set(5, 32'h05, 32'h1f, 32'h0c, 1, 1); endfunction
function automatic void use_crc16_usb3(); set(16, 32'h100b, 32'hffff, 32'hf6aa, 1, 1); endfunction
function automatic void crc_bit(input bit b);
reg fb; fb = b ^ r[width - 1];
r = ((r << 1) ^ (fb ? poly : 32'd0)) & mask();
endfunction
function automatic void crc_byte(input [7:0] v);
for (int i = 0; i < 8; i++) crc_bit(v[(lsb_first ^ msb_first) ? i : 7 - i]);
endfunction
function automatic void crc_bits(input [31:0] v, input int n); // n bits of v, bit 0 first
for (int i = 0; i < n; i++) crc_bit(v[i]);
endfunction
function automatic [31:0] field(); return (invert && !no_invert) ? (~r & mask()) : r; endfunction
function automatic bit field_bit(input int i); reg [31:0] f; f = field(); return f[width - 1 - i]; endfunction
// the usual published "check" number: the field with its first-sent bit read as bit 0
function automatic [31:0] check_value();
reg [31:0] f, o; f = field(); o = 32'd0;
for (int i = 0; i < width; i++) o[i] = f[width - 1 - i];
return lsb_first ? o : f;
endfunction
function automatic bit crc_residue_ok(); return r == (residue & mask()); endfunction
endmodule
// ---------------------------------------------------------------------------------------------
// hs_scr: additive (frame-synchronous) and multiplicative (self-synchronising) scramblers.
// poly holds the coefficients: bit k is x^k; the +1 term is always used (taps() sets bit 0); len is the degree.
// Additive: a Galois LFSR. The key bit is s[len-1]; each step shifts left and adds the low terms of
// the polynomial when the key bit is 1. The data never enters the register.
// Multiplicative: the line bit is the data bit XOR the register bits at the polynomial's terms;
// the scrambler shifts its own output in, the descrambler shifts the received line bit in.
// scr_add(len, poly, seed), scr_mul(len, poly), use_usb3_gen1(), use_x58(), use_x23_usb3() (see its note)
// scr_bit(b), dscr_bit(b), scr_byte(v), dscr_byte(v) (bit 0 first), scr_reset(), scr_hold() (a skip
// symbol: no step), scr_unscrambled() (a symbol sent in the clear: 8 steps, data untouched)
// Faults: advance_on_skip (scr_hold steps the LFSR 8 times), no_reset (scr_reset does nothing),
// wrong_tap (the lowest term x^k becomes x^(k+1)), seed_zero (scr_reset loads 0).
module hs_scr;
bit mult = 0; int len = 16;
bit [63:0] poly = 64'h10039, seed = 64'hffff;
bit advance_on_skip = 0, no_reset = 0, wrong_tap = 0, seed_zero = 0;
bit [63:0] s = 64'hffff;
int steps = 0;
function automatic [63:0] lmask(); return (len >= 64) ? 64'hffffffffffffffff : ((64'd1 << len) - 64'd1); endfunction
function automatic [63:0] taps();
reg [63:0] p; int k; p = poly | 64'd1; k = 1;
if (wrong_tap) begin
while (k < len && !p[k]) k++;
if (k < len) begin p[k] = 1'b0; p[k + 1] = 1'b1; end
end
return p;
endfunction
function automatic void load(); s = (seed_zero ? 64'd0 : seed) & lmask(); endfunction
function automatic void scr_add(input int n, input [63:0] p, input [63:0] sd); mult = 0; len = n; poly = p; seed = sd; s = sd & lmask(); endfunction
function automatic void scr_mul(input int n, input [63:0] p); mult = 1; len = n; poly = p; seed = 64'd0; s = 64'd0; endfunction
function automatic void use_usb3_gen1(); scr_add(16, 64'h10039, 64'hffff); endfunction // x^16 + x^5 + x^4 + x^3 + 1, seed FFFFh
function automatic void use_x58(); scr_mul(58, (64'd1 << 58) | (64'd1 << 39) | 64'd1); endfunction // x^58 + x^39 + 1
// USB 3.2 Gen 2 (§6.3.2.3) polynomial x^23 + x^21 + x^16 + x^8 + x^5 + x^2 + 1 with seed 1DBFBCh. Only the
// polynomial and seed are the specification's: the register form here is this library's Galois form, and
// the reset and bypass rules of §6.3.2.3 are not modelled, so do not quote its key stream as USB's.
function automatic void use_x23_usb3(); scr_add(23, (64'd1 << 23) | (64'd1 << 21) | (64'd1 << 16) | (64'd1 << 8) | (64'd1 << 5) | (64'd1 << 2) | 64'd1, 64'h1dbfbc); endfunction
function automatic void scr_reset(); if (!no_reset) load(); endfunction
function automatic bit key(); return s[len - 1]; endfunction
function automatic void step();
reg kb; kb = s[len - 1];
s = ((s << 1) & lmask()) ^ (kb ? (taps() & lmask()) : 64'd0);
steps++;
endfunction
// the XOR of the register bits at the polynomial's terms x^1..x^len (bit k-1 of the register for x^k)
function automatic bit fbx(input [63:0] st); return ^(st & (taps() >> 1) & lmask()); endfunction
function automatic bit scr_bit(input bit b);
reg o;
if (!mult) begin o = b ^ s[len - 1]; step(); end
else begin o = b ^ fbx(s); s = ((s << 1) | {63'd0, o}) & lmask(); steps++; end
return o;
endfunction
function automatic bit dscr_bit(input bit b);
reg o;
if (!mult) begin o = b ^ s[len - 1]; step(); end
else begin o = b ^ fbx(s); s = ((s << 1) | {63'd0, b}) & lmask(); steps++; end
return o;
endfunction
function automatic [7:0] scr_byte(input [7:0] v);
reg [7:0] o; for (int i = 0; i < 8; i++) o[i] = scr_bit(v[i]); return o;
endfunction
function automatic [7:0] dscr_byte(input [7:0] v);
reg [7:0] o; for (int i = 0; i < 8; i++) o[i] = dscr_bit(v[i]); return o;
endfunction
// a skip symbol passes unscrambled and the LFSR holds
function automatic void scr_hold(); if (advance_on_skip && !mult) for (int i = 0; i < 8; i++) step(); endfunction
// another symbol that is sent unscrambled (a K code other than COM and SKP): the LFSR still steps 8 times
function automatic void scr_unscrambled(); if (!mult) for (int i = 0; i < 8; i++) step(); endfunction
endmodule
Check Yourself
Common Mistakes
Wrong Compare the receiver's register with zero after the CRC field.
With an inverted field the register of a good packet ends at the residue, which is not zero.
Fix Compare with the residue that the specification gives, such as C704DD7Bh for the USB 3.2 CRC-32.
assign crc_ok = (crc_reg == 32'h0);assign crc_ok = (crc_reg == 32'hc704dd7b);Wrong Feed each byte into the register top bit first because the polynomial is written that way.
The specification fixes the bit order, and USB feeds bit 0 of each byte first.
Fix Take the bit order from the specification and test against a published check value.
for (int i = 7; i >= 0; i--) crc_bit(data[i]);for (int i = 0; i < 8; i++) crc_bit(data[i]);Wrong Drop the CRC because the link has FEC.
Past its limit a decoder can produce a wrong valid word: the bench saw this for 20,475 two-symbol errors.
Fix Keep the CRC after the FEC so that a miscorrection is still caught.
Wrong Read "corrects t = 7" as seven bits.
A Reed-Solomon code counts wrong symbols, and one symbol holds several bits.
Fix Convert a burst to symbols first. Seventy bits that start on a symbol boundary cover seven 10-bit symbols.
Remember
- A CRC is the remainder of a division by a generator. The register shifts, and XORs the generator when the top bit and the data bit differ.
- Seed, inversion, bit order and residue are part of the definition. A good packet ends at the residue, not at zero.
- A CRC of n bits catches every burst of up to n bits. It misses multiples of the generator, and it never corrects.
- FEC corrects by distance between code words. Reed-Solomon corrects whole symbols, so it handles bursts well.
- Past its limit a decoder can miscorrect without a flag. Keep a CRC behind the FEC.