Scribd
Upload
281 views

CRC (Cyclic Redundancy Check)

CRC is a method to detect errors in data transmission by attaching a fixed number of CRC bits to the end of the data. It uses a generator polynomial known to both the sender and receiver. The sender divides the data by the polynomial and attaches the remainder as CRC bits. The receiver divides the received data and checks if the remainder is 0, indicating no errors. Integer division forms the basis, where the remainder verifies the integrity of the transmission. Examples show how CRC encoding is done on the sender side and error detection on the receiver side by checking the remainder.

Uploaded by

Kumar Shashank
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
281 views

CRC (Cyclic Redundancy Check)

CRC is a method to detect errors in data transmission by attaching a fixed number of CRC bits to the end of the data. It uses a generator polynomial known to both the sender and receiver. The sender divides the data by the polynomial and attaches the remainder as CRC bits. The receiver divides the received data and checks if the remainder is 0, indicating no errors. Integer division forms the basis, where the remainder verifies the integrity of the transmission. Examples show how CRC encoding is done on the sender side and error detection on the receiver side by checking the remainder.

Uploaded by

Kumar Shashank
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

CRC (Cyclic Redundancy Check)

Saturday, March 13, 2021


10:38 PM

CRC is a method of detecting accidental errors in communication channnel.


To detect errors , we attach a fixed no of digits to lower end of data LSB . (these bits are called CRC bits)

Integer division forms the basis for the use of CRCs.


• When 723 is divided by 5 (divisor), the remainder is 3. If the dividend (723) and the remainder (3)are
transmitted from a source to a target, the integrity of the transmission can be verified at the target by re-
computing the remainder and verifying that the remainder matches the transmitted remainder.
• Alternatively, the target could divide the difference between the transmitted dividend and remainder and
expect to see a zero remainder if there were no errors.

CRC uses Generator Polynomial which is available on both sender and receiver side. An example generator
polynomial is of the form like x3 + x + 1. This generator polynomial represents key 1011. Another example is x2 + 1
that represents key 101.

n : Number of bits in data to be sent


from sender side.
k : Number of bits in the key obtained
from generator polynomial.

Sender Side (Generation of Encoded Data from Data and Generator Polynomial (or Key)):
1. The binary data is first augmented by adding k-1 zeros in the end of the data
2. Use modulo-2 binary division to divide binary data by the key and store remainder of division.
3. Append the remainder at the end of the data to form the encoded data and send the same

Receiver Side (Check if there are errors introduced in transmission)


1. Perform modulo-2 division again and if the remainder is 0, then there are no errors.

The process of modulo-2 binary division is the same as the familiar division process we use for decimal
numbers. Just that instead of subtraction, we use XOR here.
• In each step, a copy of the divisor (or data) is XORed with the k bits of the dividend (or key).
• The result of the XOR operation (remainder) is (n-1) bits, which is used for the next step after 1 extra bit
is pulled down to make it n bits long.
• When there are no bits left to pull down, we have a result. The (n-1)-bit remainder which is appended at
the sender side.

Example 1 (No error in transmission):


Data word to be sent - 100100
Key - 1101 [ Or generator polynomial x3 + x2 + 1]
Sender Side:
n= 6 bits

crc Page 1
n= 6 bits
k= 4 bits
zeros to be appended = k-1= 3 zeros

Therefore, the remainder is 001 and hence the encoded


data sent is 100100001.
Receiver Side:
Code word received at the receiver side 100100001

Therefore, the remainder is all


zeros. Hence, the
data received has no error.

Example 2: (Error in transmission)


Data word to be sent - 100100
Key - 1101
Sender Side:

crc Page 2
Therefore, the remainder is 001 and hence the
code word sent is 100100001.
Receiver Side
Let there be an error in transmission media
Code word received at the receiver side - 100000001

Example 3:

crc Page 3
Example 3:

crc Page 4

You might also like