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.
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.
- I/O
- Datapath
- Neutral
- Channel / handshake
- Data
- Send
The remainder of 11010011000 divided by 1011 is 011. The codeword is 11010011011.
- Receive
The codeword itself divides exactly. So the remainder at the receiver depends only on the error pattern e.
Read the diagram as text
- Message: 11010011
- Divide by 1011: three zeros appended
- Codeword: message, then the CRC 011
- Channel: may XOR in an error e
- Divide again: the whole codeword
- Remainder: 0: accept; not 0: reject
- Message → Divide by 1011: eight bits
- Divide by 1011 → Codeword: remainder 011
- Codeword → Channel: eleven bits
- Channel → Divide again: codeword XOR e
- Divide again → Remainder: remainder of e alone
An error is missed only when e is a multiple of the generator.
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.
| Message | Long division | Shift register |
|---|---|---|
| 11010011 | 011 | 011 |
| 10110000 | 000 | 000 |
| 11111111 | 011 | 011 |
| 00000110 | 001 | 001 |
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 patterns | Missed | Of |
|---|---|---|
| single errors | 0 | 11 |
| double errors | 4 | 55 |
| bursts of 2 or 3 bits | 0 | 28 |
| bursts of 4 bits | 8 | 32 |
| three errors | 26 | 165 |
| odd numbers of errors | 0 | 2048 |
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 added | Ones'-complement sum | Plain sum |
|---|---|---|
| 1234 | 1234 | 1234 |
| f00d | 0242 | 0241 |
| beef | c131 | c130 |
| 0f0f | d040 | d03f |
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.
| Codewords | Single errors caught | A 1 and a 0 swapped, caught |
|---|---|---|
| 00011 00101 00110 01001 01010 01100 10001 10010 10100 11000 | 50 of 50 | 1 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
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.
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.
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.
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 001Check Yourself
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.
sum = sum + w;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.