CRC, Checksums and m-Out-of-n Codes

Compute a CRC by long division with XOR and with a shift register. Add a checksum with an end-around carry, and check an m-out-of-n code.

You Will Be Able To

  • Divide a message by a generator with XOR and read the CRC as the remainder.
  • Build the serial shift register that computes the same CRC one bit per clock.
  • Say which errors a CRC always catches, and compute an Internet checksum.
  • Check a word of an m-out-of-n code, and name the errors it misses.
Lesson
G1.10
Time
30 min
Runs on
Your browser
Check
6 questions

An Ethernet frame carries a 32-bit CRC. Parity would miss half of all error patterns. The CRC misses none of the single bursts up to 32 bits long, and it costs one shift register per link. This lesson builds the same machine with three bits.

Divide 11010011 by 1011
27
26
25
24
23
22
21
20

Weights show bit magnitudes. For signed values, the leftmost bit has a negative weight.

Hexadecimal
0xD3

Generator 1011 (degree 3). Append 3 zeros and divide, subtracting with XOR and never borrowing.

Message + 3 zeros11010011000
XOR 1 at bit 01011
Remainder01100011000
XOR 2 at bit 11011
Remainder0111011000
XOR 3 at bit 21011
Remainder010111000
XOR 4 at bit 31011
Remainder00001000
XOR 5 at bit 71011
Remainder0011

CRC (the remainder): 011. Codeword: message then CRC, 11010011 011.

Received codeword. Select a bit to flip it in transit (M = message, C = CRC).

M
M
M
M
M
M
M
M
C
C
C

The receiver divides the whole codeword: remainder 000 — no error detected.

Next XOR step walks the division. Flip received bits below it: a nonzero remainder means the error is caught.

Division with XOR

Treat a bit string as a polynomial: 1011 is x^3 + x + 1. Arithmetic on the coefficients is done mod 2, so adding and subtracting are both XOR, and there are no carries.

To compute a CRC with a generator of degree r, append r zeros to the message. Divide by the generator: under every leading 1, XOR in the generator. The r bits left at the end are the remainder, the CRC.

The sender appends the CRC to the message. The receiver divides the whole codeword. A remainder of 0 means no error was seen.

One Bit per Clock

Hardware does not store the whole message. A shift register of r flip-flops holds the running remainder. Each clock takes in one message bit, most significant first.

The bit that leaves the top, XORed with the bit that enters, is the feedback. It goes into every position where the generator has a 1, except the top. For 1011 that is position 1 and position 0.

CRC-3 One Bit per Clock
CRC-3 One Bit per Clockxfb · XORfb=0xt1 · XORt1=1a0 · ANDd0=0a1 · ANDd1=1a2 · ANDd2=1DQf0 · DFFq0=1DQf1 · DFFq1=1DQf2 · DFFq2=0din=0run=1clk=0
din=0 run=1 clk=0
xfb · XORq2=0, din=0 → fb=0
xt1 · XORq0=1, fb=0 → t1=1
a0 · ANDrun=1, fb=0 → d0=0
a1 · ANDrun=1, t1=1 → d1=1
a2 · ANDrun=1, q1=1 → d2=1
f0 · DFFd0=0, clk=0 → q0=1
f1 · DFFd1=1, clk=0 → q1=1
f2 · DFFd2=1, clk=0 → q2=0
Read the connections
GateKindInputsOutput
xfbXORq2, dinfb
xt1XORq0, fbt1
a0ANDrun, fbd0
a1ANDrun, t1d1
a2ANDrun, q1d2
f0DFFd0, clkq0
f1DFFd1, clkq1
f2DFFd2, clkq2

Outputs: q2, q1, q0. MUX inputs: d0, d1, select. Latch/flip-flop inputs: data, enable/clock. Unknown values are marked x; high impedance is folded into x in this model.

Gate delay 55. Settled after 55 gate delays from t = 0.

Output values at each gate delay012345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455q2xxx00000000000011111100000000000000000011111100000000000q1xxx00000011111100000000000000000011111100000000000011111q0xxx00000011111111111111111111111100000000000000000011111
Scroll horizontally ↔
Every computed frame
Timeq2q1q0
0xxx
1xxx
2xxx
3000
4000
5000
6000
7000
8000
9011
10011
11011
12011
13011
14011
15101
16101
17101
18101
19101
20101
21001
22001
23001
24001
25001
26001
27001
28001
29001
30001
31001
32001
33010
34010
35010
36010
37010
38010
39100
40100
41100
42100
43100
44100
45000
46000
47000
48000
49000
50000
51011
52011
53011
54011
55011

  1. Step 3 · Clear. With run at 0 the AND gates feed 0s, so the first edge clears the register to 000.
  2. Step 9 · First bit. The first message bit, 1, enters. The feedback fb = q2 XOR din is 1, and it lands in q0 and, through the second XOR, in q1.
  3. Step 54 · The remainder. After eight edges the register holds 011, the remainder of the long division above.
MessageLong divisionShift register
11010011011011
10110000000000
11111111011011
00000110001001

Measured on the simulator: the lab computes the CRC both ways. 10110000 is 1011 times x^4, so its remainder is 000.

This form needs no appended zeros. It gives the remainder of the message times x^r, the same as the long division.

What a CRC Always Catches

An error is a pattern e added to the codeword by XOR. The receiver sees no error only when e itself divides by the generator. Good generators make that rare for the errors that happen most.

Error patternsMissedOf
single errors011
double errors455
bursts of 2 or 3 bits028
bursts of 4 bits832
three errors26165
odd numbers of errors02048

Measured on the simulator: every error pattern on an 11-bit CRC-3 codeword. The last row uses the generator 11101 on 12 bits.

Three rules follow. A generator with more than one term catches every single error. A generator of degree r with an x^0 term catches every burst of r bits or fewer. A generator with x + 1 as a factor catches every odd number of errors: 11101 is (x + 1)(x^3 + x + 1).

CRC-3 also shows the limits. Two errors exactly 7 apart pass it, and so does the burst 1011, the generator itself.

Checksums with an End-Around Carry

A checksum is cheaper than a CRC: add the words up. The Internet checksum adds 16-bit words in ones' complement (lesson G1.2). A carry out of bit 15 is added back in at bit 0. The checksum is the inverse of the sum.

Word addedOnes'-complement sumPlain sum
123412341234
f00d02420241
beefc131c130
0f0fd040d03f

Measured on the simulator. The checksum is 2fbf, and the receiver's sum of all five words is ffff.

A checksum misses more than a CRC. Swapping two words does not change the sum, and two errors that cancel pass unseen.

m-Out-of-n Codes

In an m-out-of-n code every codeword has exactly m 1s among n bits. The checker counts the 1s. The 2-out-of-5 code has exactly ten codewords, one per decimal digit.

CodewordsSingle errors caughtA 1 and a 0 swapped, caught
00011 00101 00110 01001 01010 01100 10001 10010 10100 1100050 of 501 of 0

Measured on the simulator over all 32 words of five bits.

Any error that only turns 1s into 0s, or only 0s into 1s, changes the count. Such unidirectional errors are always caught. An error that swaps a 1 and a 0 keeps the count and passes.

Asked in interviews
  1. How does a serial CRC circuit work?

    A shift register of r flip-flops holds the running remainder. Each clock, the bit leaving the top XOR the incoming bit is the feedback. It goes into the taps where the generator has a 1.

  2. Which errors does a CRC of degree r always catch?

    Every single-bit error, and every burst of r bits or fewer when the generator has an x^0 term. With x + 1 as a factor of the generator, also every odd number of errors.

  3. How is the Internet checksum computed?

    Add the 16-bit words in ones' complement, adding each carry out back in at bit 0, then invert the sum. The receiver adds everything and expects ffff.

Try It

Each line computes CRC-3 of one message twice: by long division and by the serial register. The two always agree.

10110000 is the generator 1011 shifted left, so it divides exactly and its CRC is 000.

Change the generator in both places to 1001 (x^3 + 1), with the feedback only into position 0. Then compare the two columns again.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: message 11010011 division 011 shift register 011 message 10110000 division 000 shift register 000 message 11111111 division 011 shift register 011 message 00000110 division 001 shift register 001

Check Yourself

Predict the outputThe program adds two 16-bit words with an end-around carry. What exact line does it print?
module tb;
  logic [16:0] wide;
  logic [15:0] sum;
  initial begin
    wide = 16'hffff + 16'h0003;
    sum = wide[15:0] + 16'(wide[16]);
    $display("%h", sum);
  end
endmodule
Spot the bugEach option sets nxt, the next state of the serial CRC-3 register r for the generator 1011 and the input bit din. The bench checks all 256 messages against the long division. Which option fails?
ConceptA CRC generator has degree 16 and an x^0 term. Which errors does it always catch?
ConceptTwo 16-bit words of a packet are swapped in transit. What does the Internet checksum see?
ConceptA 2-out-of-5 checker sees the word 00111. What does it report?
ConceptWhy does the generator 11101 catch every odd number of errors, when 1011 does not?

Common Mistakes

Wrong Drop the x^0 term of the generator.

Writing 1010 drops the x^0 term. The CRC still catches single errors, but it now misses bursts. Measured: 8 of the 28 bursts of 2 or 3 bits pass.

Fix Write every coefficient, including the 1 at the right end.

Wrong Add checksum words with a plain adder that drops the carry.

The Internet checksum is a ones'-complement sum. A lost carry makes the sum one too small. Measured: d03f in place of d040.

Fix Add the carry out back in at bit 0: the end-around carry.

Before
sum = sum + w;
After
wide = sum + w;
sum = wide[15:0] + 16'(wide[16]);

Wrong Forget to invert the final ones'-complement sum.

The checksum is the inverse, so that the receiver's sum over everything comes out as all 1s.

Fix Send ~sum. The receiver checks for ffff.

Wrong Expect a CRC to catch every error.

An error pattern that is a multiple of the generator leaves no remainder. Measured: 8 of the 32 bursts of 4 bits pass CRC-3.

Fix Pick a generator whose degree covers the longest burst you expect, and add other checks above it.

Remember

  • A CRC is the remainder of the message times x^r divided by the generator, with XOR for subtraction.
  • A shift register of r flip-flops computes it one bit per clock, feeding back into the generator's taps.
  • A degree-r CRC with an x^0 term catches every single error and every burst of r bits or fewer. With x + 1 as a factor, it also catches every odd error.
  • The Internet checksum is a ones'-complement sum with an end-around carry, then inverted.
  • An m-out-of-n checker counts the 1s; it catches unidirectional errors and misses a swapped 1 and 0.

Practice

Report a problem with this page