I plan to build a transmitter and receiver station which is able to transmit data with the help of light signals (“Visible Light Communication” – VLC). In order for the data transmission to be possible, the clock frequency of the transmitter and the receiver must be precisely synchronized. I have already explained in previous posts how to set a precise clock frequency for the Arduino and the Raspberry Pi, to which I link below.
A cyclic redundancy check is a simple and elegant way to verify that the data arriving at a receiving station is correct. For example, if bits have been swapped in a received data packet or a 1 has been received instead of a 0, this can be detected by the cyclic redundancy check (CRC for short). The CRC identifies that a data packet has an error and the receiving station will drop the packet.
This might also be interesting for you: Setting a precise clock frequency for an Arduino
Also closely related to this article: Setting a precise clock frequency for the Raspberry Pi
Cyclic redundancy check – How it works:
The CRC is a mathematical trick. In principle, the calculation is a polynomial division. For example, the data packet 10010101 corresponds to the following polynomial:
A so-called generator polynomial is required for the calculation of the CRC. The generator polynomial can be chosen freely, but some polynomials have proven to be particularly suitable. It is important that the generator polynomial for sending the data and for receiving the data is identical. I have chosen the polynomial 1011 for the sake of simplicity:
The procedure is the same for each data packet. An additional CRC value is appended to each data packet that is to be sent. This CRC value is one digit smaller than the generator polynomial. In the current case, the generator polynomial 1011 has a total of 4 digits, which means that the CRC value has 3 digits. At the beginning of the calculation the CRC value is still unknown, therefore simply 3 times (since the CRC value has here 3 digits) the 0 is appended to the data package. Thus the data packet 10010101 now becomes 10010101000.
Then the polynomial division starts. 10010101000 is divided by 1011. I have summarized the step-by-step process of the division in a graphic. At the end of the polynomial division the remainder 110 remains on the transmitter. This remainder is the desired CRC value. The CRC value is appended to the actual data packet 10010101 and transmitted to the receiver. If the data transmission is correct, the receiver receives the packet 10010101110.
At this point the mathematical trick happens. The calculated CRC was appended to the data packet and transmitted to the receiver. The receiver can now also perform a polynomial division with the generator polynomial 1011, but since this time the CRC value 110 was appended to the data packet 10010101 instead of 3 times 0, no remainder is left when the polynomial division is repeated.
No remainder on the receiver side means that the data packet was transmitted correctly. However, if a remainder is left, then an error has crept in during the transmission. The faulty data packet can be discarded and the receiver can ask for a retransmission of the data packet.
2 thoughts on “Cyclic Redundancy Check in C code”