Cyclic Redundancy Check

Cyclic Redundancy Check (crc)

Looking at polynomial calculations and implementation

Abstract

During the transmission between devices on a network there is the potential for interference thanks to transmission impairments caused by attenuation, noise, and other external factors. These impairments can cause data to become corrupted. CRC is one of several methods that can be used in the context of error detection, and thereby avoidance.

This report looks at a brief overview before discussing how these calculations are used to calculate a CRC value, and decode this. The end of the report includes a Python3 implementation of CRC from both the perspective of the sender and receiver.

CRC in the Context of Networks

What is an error?

An error is a scenario where the data the receiver consumes, is corrupted and does not match what the sender transmitted. Interference that introduces errors, causes a distortion in the signal whereby a 0 bit can become a 1 bit and vice versa.

Where is this implemented?

This error detection is implemented in the data link layer, alongside encoding, and is applied to the raw data being transmitted.

History

CRC, as acknowledged by (Peterson, W. W.; Brown, D. T. January 1961) was invented by W. Wesley Peterson in 1961, and expanded on by CCIT (Comité Consultatif international Télégraphique et Telephone) - now called ITU-T (ITU Telecommunication Standardisation Sector).

CRC Calculations

CRC is a hash function that is used to detect these errors in a transmission. This is achieved by appending a set quantity of bits on to the end of the message being sent, the checksum. On the receiving end these check bits that make up the checksum are analysed for errors. The Cyclic part of CRC implies the use of Cyclic Codes, the Redundancy part of CRC is the checksum that is appended, and Check is the verification that is made on the receiving end of the transmission.

In its simplest form the data being transmitted is a number represented as a string of bits, using a CRC polynomial (a divisor), divide this data by the CRC polynomial, and calculate the remainder. The remainder of this division is the CRC.

Base 10 Example

An example using base 10:

Given data = 1098764355, and a CRC polynomial of 9, 1098764355 % 9 = 3 (CRC)

Polynomial Selection

When determining a polynomial as the divisor, as Messender, B. (2013) suggests it’s important to consider the ramifications of the division, and the potential for failure if a simple polynomial is selected. For instance if our CRC polynomial is 2 any odd value will have a CRC of 1, any even value will have a CRC of 0.

Another example might be the value 3:

Given data = 1098764345, and a CRC polynomial of 3, 1098764355 % 3 = 2 (CRC)
Given data = 1098764348, and a CRC polynomial of 3, 1098764348 % 3 = 2 (CRC)

Given that we are taking data D and calculating the remainder by dividing against the CRC polynomial c, there is a chance that if enough of the string of bits is corrupted it can still pass the error check (1/c). Therefore it’s important to select a CRC polynomial that is big enough to limit this as much as possible.

Binary Polynomial Arithmetic

First let’s consider that an integer is made up of coefficients of a base 10 polynomial, for instance 123 is equivalent to: (1)102 + (2)101 + (3)100

Now let’s consider a binary number in the same way, for instance 1011 (11 in base 10): (1)23 + (0)22 + (1)21+ (1)20

We can alsos express this as: x3 + x1+ 1

If this were our CRC polynomial c, the remainder will always fit into c-1 bits, so in this case this is a “3 bit CRC”.

As Ritter T (1986) expresses binary polynomial arithmetic can be done by ignoring the carries - this is essentially an XOR operation: 0101 + 1110 = 1011

This can be expressed as: Given our numbers

(0x3 +  1x2+ 0x1+ 1)
(1x3 +  1x2+ 1x1+ 0)

Perform addition

(1x3 +  2x2+ 1x1+ 2)

Set the least significant value to 1, and perform modulo 2 against each of the coefficients ((1%2)x3 + (2%2)x2+ (1%2)x1+ 1) Result (1x3 + 0x2+ 1x1+ 1) = (1011)

CRC Encoding / Decoding

Upto this point we have determined that CRC involves adding check data to the data sender is transmitting (a redundancy). This is used to detect if any bits have been flipped during transmission through some form of interference. The receiver is going to divide the received data, the bits, by a divisor, a key, and from this use the remainder to determine if the CRC value matches the CRC that the sender calculated.

Prior to sending the sender calculates a CRC from the remainder of the division between the data and a CRC generator value (a polynomial generator such as (x3 + x2+ x1)).

To perform this division take the dividend (the data), and from the most significant bit, take a slice the width of the divisor, and perform XOR comparison against the divisor with this slice of bits.

Update the original data by replacing the modified bits, shift to the next significant bit in the result, and continue. At each step, if the leftmost digit is 0, XOR the slice against 0, if it’s 1 then XOR the slice against the divisor.

The resulting remainder is the CRC.

Let’s consider an example:

Given the data: 1101011011
And a polynomial generator of: 10011

Sender

To ensure the data is the correct length, append the same amount of bits as the CRC, so with a generator, a divisor, that has 5 bits, this is a 4 bit CRC, so append 4 0 bits to the end of the data. The sender appends 4 0 bits to the end of the data: 11010110110000 Perform binary division against the resultant string as stated above with the CRC This results in a remainder of 1110 Append this CRC to the end of the data: 11010110111110

Receiver

The receiver can validate this message by performing the same calculation again using binary division against the polynomial generator used to generate the CRC, if the remainder is 0 then the data has not been corrupted. Evaluation

The result of this calculation and the simple ability to apply the generator on both the sender and receiver side allows for a simple efficient method for data validation. The benefits of this over a parity check is that we are looking at all the bits in the data, rather than a single bit of information, as is seen in parity checks, this is discussed by (Drummond, 1997)

Example Implementation using Python

"""
    A CRC example

    Author:
        Matthew Barber <mfmbarber@gmail.com>
"""
class CRC:
    @staticmethod
    def xor(a, b):
        '''
            Perform an xor operation on a and b and return the result
            XOR truth table:
            a, b, result
            0, 0, 0
            0, 1, 1
            1, 0, 1
            1, 1, 0

            Args:
                a (string)  A binary string
                b (string)  A binary string

            Return:
                string
        '''
        return "".join(
            ['0' if a[i] == b[i] else '1' for i in range(1, len(b))]
        )


    @staticmethod
    def modulo2division(divident, divisor):
        '''
            Given a divident, and a divisor carry out modulo 2 division using XOR

            Args:
                divident (string) String of bits to divide
                divisor (string)  String of bits to divide by

            Returns:
                string (the remainder)
        '''

        # The number of bits to in the divisor to XOR against
        selection = len(divisor)

        # The amount of bits in the divident (the data)
        dividentLength = len(divident)

        # A helper function, if the current slice has a leading 1 XOR against the divisor
        # If the current slice has a leading 0, XOR against 0
        xorSlice = lambda slice: CRC.xor(divisor if slice[0] == '1' else '0'*selection, slice)

        if selection > dividentLength:
            raise ValueError("Divisor bit count must be less than divident")

        # Take out first slice of selection size from the divident
        slice = divident[0: selection]
        # While the selection isn't at the end of the length of the data
        while selection < dividentLength:
            # XOR the current slice
            result = xorSlice(slice)
            print("Current selection: %s Divisor: %s XOR: %s"%(slice, divisor, result))
            slice = result + divident[selection]
            # move along the divident
            selection += 1
        slice = xorSlice(slice)
        return slice

    def encodeData(data, generator):
        '''
            Encode data with a CRC generator

            Args:
                data        (string)   The data (string of bits) to encode
                generator   (string)   The generator to calculate the CRC

            Return:
                tuple
        '''
        # Appends n-1 zeroes at end of data
        crc = CRC.modulo2division(data + '0'*(len(generator)-1), generator)
        # Append remainder in the original data
        return (data + crc, crc)

    def decodeData(data, generator):
        '''
            Decode the data recieved against the CRC generator

            Args:
                data        (string)    The data (string of bits to decode)
                generator   (string)    The generator to calculate the CRC

            Returns:
                tuple
        '''
        crc = CRC.modulo2division(data, generator)
        return (data, crc)


def testCRC():
    print("===\t DATA \t===")
    data = "1101011011"
    generator = "10011"
    print("Data to transmit: " + data)
    print("CRC Generator: " + generator)

    print("===\t SENDER \t===")
    encoded = CRC.encodeData(data, generator)
    print("Data: " + encoded[0])
    print("CRC: " + encoded[1])

    print("===\t DATA SENT \t===")

    print("===\t RECEIVER \t===")
    decoded = CRC.decodeData(encoded[0], generator)
    print("Data: " + decoded[0])
    print("Remainder: " + decoded[1])

    print("OK" if int(decoded[1]) == 0 else "CORRUPT")

testCRC()

Output
17:59:45 [crc]()$ python3 crc.py 
===      DATA   ===
Data to transmit: 1101011011
CRC Generator: 10011
===      SENDER         ===
Current selection: 11010 Divisor: 10011 XOR: 1001
Current selection: 10011 Divisor: 10011 XOR: 0000
Current selection: 00001 Divisor: 10011 XOR: 0001
Current selection: 00010 Divisor: 10011 XOR: 0010
Current selection: 00101 Divisor: 10011 XOR: 0101
Current selection: 01011 Divisor: 10011 XOR: 1011
Current selection: 10110 Divisor: 10011 XOR: 0101
Current selection: 01010 Divisor: 10011 XOR: 1010
Current selection: 10100 Divisor: 10011 XOR: 0111
Data: 11010110111110
CRC: 1110
===      DATA SENT      ===
===      RECEIVER       ===
Current selection: 11010 Divisor: 10011 XOR: 1001
Current selection: 10011 Divisor: 10011 XOR: 0000
Current selection: 00001 Divisor: 10011 XOR: 0001
Current selection: 00010 Divisor: 10011 XOR: 0010
Current selection: 00101 Divisor: 10011 XOR: 0101
Current selection: 01011 Divisor: 10011 XOR: 1011
Current selection: 10111 Divisor: 10011 XOR: 0100
Current selection: 01001 Divisor: 10011 XOR: 1001
Current selection: 10011 Divisor: 10011 XOR: 0000
Data: 11010110111110
Remainder: 0000
OK

References

Ritter, T. 1986. The Great CRC Mystery. Dr. Dobb’s Journal of Software Tools. February. 11(2): 26-34, 76-83.

Messender, B. (2013). Understanding the Cyclic Redundancy Check

Cardinal Peak. [online] Cardinal Peak. Available at: https://cardinalpeak.com/blog/understanding-the-cyclic-redundancy-check/ [Accessed 9 Nov. 2019].

Peterson, W. W.; Brown, D. T. (January 1961). “Cyclic Codes for Error Detection”. Proceedings of the IRE. 49 (1): 228–235. doi:10.1109/JRPROC.1961.28781

Drummond, J. (1997). Parity, Checksums and CRC Checks. [online] Faraday.physics.utoronto.ca. Available at: https://faraday.physics.utoronto.ca/GeneralInterest/Drummond/Micro/ln_comm1.pdf [Accessed 9 Nov. 2019].

Humphreys, D. (n.d.). Polynomial codes for error detection. [online] Computing.dcu.ie. Available at: https://www.computing.dcu.ie/~humphrys/Notes/Networks/data.polynomial.html [Accessed 9 Nov. 2019].