B.1 (10 Marks)
A bit stream 1110010011 is transmitted using the standard CRC method. The generator polynomial is x3+x+1. This process involves (i) Creation of the bit stream to be transmitted (ii) Calculation of CRC at receiver and (iii) Identification of error, if any. Show how the above steps are carried out using the bit stream and the generator polynomial.
B1.1 Show the actual bit string transmitted.
B1.2 Suppose that the fourth bit from the left is inverted during transmission. Show that this error is detected at the receiver’s end.
B1.3 Give an example of a bit error in the bit string transmitted that will not be detected by the receiver.
4.1 Overview:Cyclic Redundancy Check (CRC) is a method of error detection used for reliable communication over internetwork. Consider the polynomial x3+x+1 as divisor and at the sender and the receiver, to verify that the data is not corrupted. Next, change the data bits at the receiver and compute CRC to demonstrate corruption of data .The report should comprise the following:
4.2 Solution to the question:B3.1 Introduction
Cyclic Redundancy Check (CRC) is used for error detection in Local Area Networks (LANs) and Wide Area Networks (WANs) which provides a category of codes.
The Cyclic Redundancy code is used to detect the errors during the data transmission
Here The input data with remainder of CRC is transmitted which is also called as sender side.
The transmitted data is received by the receiver side and also regenerates the CRC remainder.
To calculate this long division of binary number method is used with XOR operation in CRC.
The XOR operations rules are
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
• The encoder takes the data word and augments it with n – k number of 0s.
• It then divides the augmented data word by the divisor.
To detect inconsistency of data the checksum algorithm is used, e.g. During the transmission of data the error occurs. One of the most common method to calculate checksum is by using CRC where the data is attached to help the receiver to detect such errors.
Computer Networks | Error Detection
What Is error?
After the transmission of data , data received by receiver doesn’t match with the sender’s information as there is a lost of bits during transmission error occurs. When the binary bits are travelling from sender to receiver during the transmission there is a occurance of noise which affects the digital signals where the errors are introduced.
Few cases where bit may change from 0 to 1 , 1 to 0.
4. Cyclic redundancy check (CRC)
CRC is one of the method for error detection by binary division
In CRC, a sequence of redundant bits, called cyclic redundancy check bits which is the divisor, where the appending occurs at the end of the data which is number of bits in dividend -1 (n-1) bits of data are appended . Hence the result data unit is exactly divisible by a second, predetermined binary number
Here the division is done by using XOR operation. If the remainder is not 0 then their is no error and data is accpeted . The remainder is later added to the divisor by replacing redundancy bits. This is the procedure in transmitter. A remainder is the main part which determines the data has error or free of error. If ths error occurs ( where remainder is 0 ) the data is rejected.
The frame is 10011101. The generator is 1001. The message after appending three zeros is 10011101000. The remainder on dividing 10011101000 by 1001 is 100. So, the actual bit string transmitted is 10011101100. The received bit stream with an error in the third bit from the left is 10111101100. Dividing this by 1001 produces a remainder of 100, which is different from 0. Thus, the receiver detects the error and can ask for transmitted bit stream is converted to any multiple of 1001, the error will not be detected. A trivial example is if all ones in the bit stream are inverted to zeros.
a) Show the actual bits transmitted:
The given frame is: 1 0 0 1 1 1 0 1 Generator: 1 0 0 1
Message after 3 zeros bits are appended: 1 0 0 1 1 1 0 1 0 0 0
At transmitter: At receiver:
The transmitted bit is: 1 0 0 1 1 1 0 1 1 0 0
Since the remainder is (0 0 0), it is proved that the data bit stream is successfully transmitted.
b) Suppose that the third bit from the left is inverted during transmission. Show that this error is detected at the receiver’s end.
From the above part the transmitted bit stream is: 1 0 0 1 1 1 0 1 1 0 0
Since the third bit from the left is inverted then the bit stream becomes: 1 0 1 1 1 1 0 1 1 0 0
Since from the above calculation, we have (0 1 0) as the remainder in the receiver side. This indicates that there is some error in the transmission.
c) Give an example of bit error in the bit string transmitted that will not be detected by the receiver.
The transmitted bit stream is: 1 0 0 1 1 1 0 1 1 0 0
Here I am changing two bit of the data so that the error is not detected as shown below.
So at the receiver, the calculation is:
Since the remainder is (0 0 0) in the receiver side even after changing the bits. Hence proved that the error is not detected.
2.3 Discussions /Suggestions/Views/RecommendationsWhen given the frames and generator. Firstly count the length of the generator and append (length – 1) zeros to the frames. Now the new frame has data added with the appended zeros. Then divide the bit string corresponding to generator into the bit string corresponding to new frame using modulo 2 division. At last subtract the remainder from the bit string corresponding to new frame using modulo 2 subtraction. This new result is the frame that has to be transmitted.
Performance CRC is a very effective error detection technique. If the divisor is chosen according to the previously mentioned rules, its performance can be summarized as follows:
• CRC can detect all single-bit errors
• CRC can detect all double-bit errors (three 1’s)
• CRC can detect any odd number of errors (X+1)
• CRC can detect all burst errors of less than the degree of the polynomial.
• CRC detects most of the larger burst errors with a high probability.
• For example CRC-12 detects 99.97% of errors with a length 12 or more.
By analyzing the above techniques, I understood, The different types of Errors. That is, the errors can be divided into two types: Single-bit error and Burst error.
• Single-bit Error: the term single-bit error means that only one bit of given data unit (such as a byte, character, or data unit) is changed from 1 to 0 or from 0 to 1.
• Burst Error: The term burst error means that two or more bits in the data unit have changed from 0 to 1 or vice-versa. Note that burst error doesn’t necessary means that error occurs in consecutive bits.
Use of parity check for error detection: In the Parity Check error detection scheme, a parity bit is added to the end of a block of data. The value of the bit is selected so that the character has an even number of 1s (even parity) or an odd number of 1s (odd parity). For odd parity check, the receiver examines the received character and if the total number of 1s is odd, then it assumes that no error has occurred. If any one bit (or any odd number of bits) is erroneously inverted during transmission, then the receiver will detect an error.
The different types of errors detected by parity check: If one bit (or odd number of bits) gets inverted during transmission, then parity check will detect an error. In other words, only odd numbers of errors are detected by parity check. But, if two (or even number) of bits get inverted, and then the error remains undetected.
2.4 ConclusionsCRC method is used for detecting errors only which is done in data link layer. When the CRC method is applied, both the sender and receiver has to agree upon the generator polynomial in advance. Both the high and low bits of the generator must be 1. The frame must be longer than the generator. Here the calculation may see complicated but it is easy to verify that the correct data has been transmitted to the receiver. The frames must be longer than the generator. The data link layer helps the CRC to detect the errors.