[simple_series title=”CRC Tutorial”]
| Generator: | 1 | 0 | 0 | 1 | 1 |
| Operation | Register | Message | ||||
| 0 | 0 | 0 | 0 | 0 | 0110111 | |
| <-M | 0 | 0 | 0 | 0 | 0 | 110111 |
| <-M | 0 | 0 | 0 | 0 | 1 | 10111 |
| <-M | 0 | 0 | 0 | 1 | 1 | 0111 |
| <-M | 0 | 0 | 1 | 1 | 0 | 111 |
| <-M | 0 | 1 | 1 | 0 | 1 | 11 |
| <-M | 1 | 1 | 0 | 1 | 1 | 1 |
| XOR | 0 | 1 | 0 | 0 | 0 | 1 |
| <-M | 1 | 0 | 0 | 0 | 1 | |
| XOR | 0 | 0 | 0 | 1 | 0 | |
| <-0 | 0 | 0 | 1 | 0 | 0 | |
| <-0 | 0 | 1 | 0 | 0 | 0 | |
| <-0 | 1 | 0 | 0 | 0 | 0 | |
| XOR | 0 | 0 | 0 | 1 | 1 | |
| <-0 | 0 | 0 | 1 | 1 | 0 | |
Serial hardware CRC: Starting with a zero register, the message is shifted in (<-M), followed by 4 zeros (<-0). Whenever the MSB is 1, the register is XORed with the generator (XOR). The low-order four bits of the register are then the CRC to be added.
The hardware view is to process a bit stream bit-by-bit, resulting in a series of check digits which are appended to the original message. During this process, the CRC engine only needs to keep b+1 bits of state, independent of the message length.
Sending
For the initial generation, the message is first considered to be padded with b zeros. These imaginary appended zeros are then replaced by the calculated CRC. The message (with the check digits appended) is then sent over the transmission channel to the recipient.
Reception
…is even simpler: The entire message including check sequence is passed through the same circuit that was used to generate the check sequence. The result of the circuit should then be all-zeros, indicating that the CRC verification succeeded. [1]This means that the checksum matches the data; it does not say that the data has not been tampered with. But for reasonable CRCs, the probability of accidental changes to the message that retain the validity of the CRC, the probability is negligible. To prevent “intelligent” tampering, cryptographic means are inevitable.
The actual operation is illustrated in the image to the left. We assume an imaginary four-bit CRC, whose generator is 10011. Yes, you are right: These are five bits. But the most significant bit (MSB) is not really of interest, and is therefore not counted. First, the generator MSB is always 1. Second, whenever the register MSB becomes 1, the generator is XORed against the register, clearing the MSB. As a result, the MSB does not need to be transmitted.
Also, magically (at least for now), the resulting message-plus-CRC sequence, when passed through the CRC hardware, will clear the register. As an exercise, try feeding the sequence “01101110110” (this is our message with the CRC attached, so you do not need to push in the four zeros that were used when generating the message!) into the shift register according to the rules. The register will be zero in the end.
When our CRC unit is to be used at very high data rates (today starting in the order of 10…100 Gbit/s), it is very hard to design circuits operating at that speed. Therefore, hardware engineers often process multiple bits at a time (e.g. Dittia 2001, Braun and Waldvogel 2001, Doering and Waldvogel 2004) or use lookup tables like our software engineers described below.