CRC- Cyclic Redundancy Code

CYCLIC REDUNDANCY CHECK(CRC)

A Cyclic Redundancy Check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to raw data. CRCs are designed to provide a quick check to ensure the integrity of data being transmitted or stored. 

Data Representation:

• The data to be sent can be  represented as a polynomial , where each bit in the data is a coefficient in the polynomial or in form of bits.
• For example, the data 1101 is represented as 1x3+1x2+0x1+11x^3 + 1x^2 + 0x^1 + 11x3+1x2+0x1+1.

Generator Polynomial:

• A predefined polynomial called the generator polynomial is agreed upon by both the sender and receiver.
• This polynomial is also represented in binary form, and its degree determines the size of the CRC .

Division Process:

• The data polynomial is divided by the generator polynomial using binary division.
• The remainder of this division is the CRC checksum.

Appending CRC:

• The calculated CRC checksum is appended to the end of the data before transmission.

Verification at Receiver's End:

• Upon receiving the data with the appended CRC, the receiver performs the same division process.
• If the remainder is zero, it indicates that the data has likely been received correctly.
• If the remainder is non-zero, it indicates that an error has occurred during transmission.

Example:

Data Word: 100100

Generator Polynomial: 1101

Append (n-1) number of zeros to original message before division , where n is the number of bits of generator polynomial.

QUESTION:

1. A bit stream 1101011011 is transmitted using the standard CRC method. The generator polynomial is x⁴+x+1. What is the actual bit string transmitted?

 

2. A bit stream 10011101 is transmitted using the standard CRC method. The generator polynomial is x³+1.

 

What is the actual bit string transmitted?

Suppose the third bit from the left is inverted during transmission. How will receiver detect this error?