CRC stands for Cyclic Redundancy Check which is a technique used to detect and correct errors in data transmission over a network. It is used in digital communication systems to ensure the integrity of data during transmission.
This algorithm generates a fixed length value related to the data called the checksum, which is sent along with the data. At the receiving end, the checksum is calculated, and if it matches, the data is determined to be error-free.
In this article, we will learn how to implement the CRC algorithm using Python.
Refer to this article to learn about the things you should know before working with Python.
What Is CRC?
CRC is an algorithm based on the polynomial technique meaning, it considers the data as a form of a polynomial and performs polynomial division with a fixed divisor which is also a polynomial. The remainder obtained is the checksum which is appended to the data and is used to determine if the data has any errors.
Related: Encryption Program in Python
At the receiver’s side, a polynomial division is taken place, and if the remainder is zero, the data is errorless. If the remainder is not zero, the data is corrupted during the transmission.
There are various types of CRC, such as CRC-16, CRC-32, CRC-64, etc., based on the size of the checksum they use. CRC-16 uses a 16-bit checksum.
Let us see the working of CRC to understand better.
To briefly explain the scenario, the sender appends a length of zeros to the data or message. The number of zeros added depends on the data and the checksum algorithm. The divisor is decided to be the value of the number of zeros+1 bits. This divisor is used to perform polynomial division on the data, whose remainder is the CRC. The checksum is later appended to the original data and is set for transmission.
At the receiver’s end, once he obtains the data appended with CRC, he performs polynomial division with a divisor. If the remainder is zero, the message is proved to be error-free else, it is rejected.
Now let us learn how to implement CRC-16 in Python.
CRC-CCITT
CRC-CCITT is a variant of the checksum algorithm, which uses the CCITT standard(Consultative Committee for International Telephony and Telegraphy). It is often used in various communication protocols and data transmission systems, particularly in telecommunications applications.
There are two variants of this algorithm. One approach initializes the CRC polynomial value to be 0x0000. While the other one uses 0xFFFF.It means nothing, but the first approach initializes to zeros(0000000000000000), and the other one uses ones(1111111111111111).
Let us see the possible approaches to calculate the CRC value.
Defining a Function to Calculate CRC
We are going to create a function to calculate the CRC using the CCITT standard.
def crc_ccitt_16(data):
crc = 0xFFFF
for byte in data:
crc ^= (byte << 8)
for _ in range(8):
if crc & 0x8000:
crc = (crc << 1) ^ 0x1021
else:
crc <<= 1
crc &= 0xFFFF
return crc
data = b'Hello, World!'
crc_ccitt_16 = crc_ccitt_16(data)
print(f"CRC-CCITT (16-bit) of '{data}' is: 0x{crc_ccitt_16:04X}")
The method crc_ccitt_16 method accepts the data for which we need to generate a CRC value. The initial value is set to 0xFFFF(all ones), and for each byte in the data, we perform XOR with the initial value of CRC. This function iterates 8 times and determines if the leftmost bit of the current CRC value is 1 or 0. This bit represents the coefficient of the highest degree term in the polynomial used for the CRC-CCITT term of the polynomial.
If the leftmost bit is 1, it shifts the crc one bit to the left (crc << 1) and then performs XOR with the CRC-CCITT polynomial value (0x1021). The XOR operation effectively performs a binary division with the polynomial.
But if the leftmost bit is 0, it simply shifts the crc one bit to the left without performing the XOR operation. Finally, the data we pass(Hello, World!) is used to generate a CRC value and is printed in the last line.
Let us see the output.
Using a Look up Table to Compute CRC
To perform the same operation, we are going to use a look up table.
def generate_crc_ccitt_table():
table = [0] * 256
polynomial = 0x1021
for i in range(256):
crc = i << 8
for _ in range(8):
if crc & 0x8000:
crc = (crc << 1) ^ polynomial
else:
crc <<= 1
crc &= 0xFFFF
table[i] = crc
return table
def calculate_crc_ccitt_16(data, table):
crc = 0xFFFF
for byte in data:
crc = (crc << 8) ^ table[(crc >> 8) ^ byte]
crc &= 0xFFFF
return crc
crc_ccitt_table = generate_crc_ccitt_table()
data = b'Hello, World!'
crc_ccitt_16 = calculate_crc_ccitt_16(data, crc_ccitt_table)
print(f"CRC-CCITT (16-bit) of '{data}' is: 0x{crc_ccitt_16:04X}")
The approach is same. But instead of using for loop to go back and forth in the data, we just use a table which stores all the values and we can access a particular value based on its index. The crc generated is also the same because the initial value of crc used is same.
Through these two approaches, we understood how to calculate the CRC. However, we do have other approaches which are much easier and more direct. There is a third-party library called crcmod of the PyPi, which can do this computation automatically.
The crcmod package
The crcmod package of the PyPi library is sued to generate computations for Cyclic Redundancy Check.
It can be installed using the following command
pip install crcmod
Let us see how we can calculate crc using this package.
import crcmod.predefined
data = b'Hello, World!'
crc_ccitt_16 = crcmod.predefined.Crc('crc-ccitt-false').new(data)
crc_ccitt_16.update(data)
crc_hex = format(crc_ccitt_16.crcValue, '04X')
print(f"CRC-CCITT (16-bit) of '{data}' is: 0x{crc_hex}")
In the first line, we are importing the package we installed earlier.
The message we want to generate crc for is stored in a variable called data.
The approach we used in this code crc-ccitt-false uses all ones in the initialization, which generates a value different than the last two approaches. The crc value calculated is stored in crc_hex and is printed in the last line.
Conclusion
The CRC is an algorithm used to detect and correct data while transmission. It appends a fixed-length arbitrary value to the data called the checksum, which is verified at the receiver’s end to make sure the data is not corrupted.
It is based on polynomial division, and the data is appended with the checksum, and a polynomial divisor is used to perform division.
There are many variants of this algorithm based on the size of the checksum produced. In this article, we have seen the CRC-16 implementation which uses 16-bit checksum.
We have seen three approaches to implement the CRC-16 algorithm- using a function to calculate the checksum, using a look-up table to reduce the complexity of the previous approach, and finally, using a third-party package called crcmod.