Cyclic redundancy check (CRC) is a common data transmission error detection technique commonly used in the data communication field. The transmit end calculates a check code for the data in a data frame based on a certain algorithm, appends the check code to the data frame, and sends the data frame to the receive end. The receive end verifies the correctness and integrity of the received data by repeating the calculation using the same algorithm.
Introduction to CRC
Bit errors (0 changed to 1 or 1 changed to 0) may occur in transmitted data due to transmission media faults or external interference, causing incorrect data on the receive end. To resolve this problem, the receive end needs to perform error detection on the received data and accepts the data only when it is correct.
There are many error detection methods, such as parity check, checksum check, and CRC check. Their implementation is similar: The transmit end calculates a check code for data using a certain algorithm, and sends the check code and data to the receive end. The receive end performs the same calculation to check whether the data changes.
CRC was first proposed by W. Wesley Peterson, a mathematician and computer scientist, in 1961. CRC has advantages over other error detection methods in terms of speed, cost, and correctness. Therefore, CRC has become the most commonly used error detection method in the computer information and communications fields. For example, a standard Ethernet frame ends with a 4-byte frame check sequence (FCS) for error detection.
Ethernet frame format
How Is CRC Calculation Implemented?
CRC enables the transmit end to append an R-bit check code to the K-bit data to be sent, generate a new frame, and send the frame to the receive end. When receiving the new frame, the receive end checks whether the received data is correct based on the received data and check code.
Example of data and check code
The check code needs to ensure that the generated new frame is divisible by a specific number that is selected by both the transmit end and receive end (modulo-2 division). The receive end divides the received new frame by the selected divisor. Because a number has been added before the data frame is sent to remove the remainder, there should be no remainder. If there is a remainder, an error occurs during the transmission of the frame.
An R-bit check code is appended to the K-bit data, and the entire code length becomes N bits. This type of code is also referred to as (N,K) code. For a given (N,K) code, it can be proved that there is a polynomial g(x) whose highest power is N–K=R, and an R-bit check code can be generated based on g(x). The algorithm is based on the GF(2) polynomial arithmetic, as shown in the following figure.
CRC calculation formula
