EXPERIMENT-3
ANAND JHA (2K21/EE/042)
Aim: Write a program to implement CRC (Cyclic Redundancy Check).
Theory:
Error: A condition when the receiver’s information does not match the sender’s information. During transmission,
digital signals suffer from noise that can introduce errors in the binary bits traveling from sender to receiver. That
means a 0 bit may change to 1 or a 1 bit may change to 0.
Error Detecting Codes (Implemented either at the Data link layer or Transport Layer of the OSI Model): Whenever a
message is transmitted, it may get scrambled by noise, or data may get corrupted. To avoid this, we use error-detecting
codes which are additional data added to a given digital message to help us detect if any error has occurred during the
transmission of the message. The basic approach used for error detection is the use of redundancy bits, where
additional bits are added to facilitate the detection of errors. Some popular techniques for error detection are:
1. Simple Parity check
2. Two-dimensional Parity checks
3. Checksum
4. Cyclic redundancy check
Cyclic redundancy check (CRC): CRC is based on binary division. In CRC, a sequence of redundant bits, called cyclic
redundancy check bits, are appended to the end of the data unit so that the resulting data unit becomes exactly
divisible by a second, predetermined binary number. At the destination, the incoming data unit is divided by the same
number. If at this step there is no remainder, the data unit is assumed to be correct and is therefore accepted.
A remainder indicates that the data unit has been damaged in transit and therefore must be rejected.
Algorithm:
1. A string of n is appended to the data unit. The length of the predetermined divisor is n+ 1.
2. The newly formed data unit i.e., original data + string of n as are divided by the divisor using binary division, and
the remainder is obtained. This remainder is called CRC.
3. Now, a string of n O’s appended to the data unit is replaced by the CRC remainder (which is also of n bit).
4. The data unit + CRC is then transmitted to the receiver.
5. The receiver on receiving it divides data unit + CRC by the same divisor & checks the remainder.
6. If the remainder of the division is zero, the receiver assumes that there is no error in the data and it accepts it.
7. If the remainder is non-zero then there is an error in the data and the receiver rejects it.
Program:
#include <bits/stdc++.h>
using namespace std;
string xorem(string input, string key)
{
int key_len = key.length();
int n = input.length();
for (int i = 0; i < n - key_len + 1; i++)
{
for (int j = 0; j < key_len; j++)
{
input[i + j] = input[i + j] == key[j] ? '0' : '1';
}
for (; i < n && input[i] != '1'; i++)
;
if (input[i] == '1')
i--;
}
return input.substr(n - key_len + 1);
}
int main()
{
string data, gen;
cout << "Enter data:";
cin >> data;
cout << "Enter Key:";
cin >> gen;
string temp = data;
for (int i = 0; i < gen.length() - 1; i++)
temp += '0';
string checksum;
checksum = xorem(temp, gen);
cout << "Encoded data:";
cout << data + checksum;
cout << "\nCheck Sum:";
cout << checksum;
cout << "\n Reciever Side -\n ";
cout<< "Enter data recieved:";
string msg;
cin >> msg;
if (msg.length() != data.length())
{
cout << "Error in communication";
return 0;
}
string remainder;
remainder = xorem(msg, gen);
for (auto x : remainder)
if (x != '0')
{
cout << "Error in communication";
return 0;
}
cout << "No Error!\n";
}
Output
Conclusion
Cyclic Redundancy Check was discussed and implemented, and the outputs were verified.
