Error Detection & Correction
Error
receiver’s information does not match with the sender’s information.
• noise.
• a 0 bit may change to 1 or a 1 bit may change to 0.
Types of Errors
• Errors can be of three types, namely
1. single bit errors
2. multiple bit errors
3. burst errors.
Single bit error
• In the received frame, only one bit has been corrupted, i.e. either
changed from 0 to 1 or from 1 to 0.
Multiple bits error
• In the received frame, more than one bits are corrupted.
Burst error
• In the received frame, more than one consecutive bits are corrupted
Error Control
• Error control can be done in two ways
• Error detection −
• checking whether any error has occurred or not.
• not interested in the number of errors. A single-bit error is the
same for as a burst error
• Error correction −
• need to know the exact number of bits that are corrupted and
more importantly, their location in the message.
• The number of the errors and the size of the message are
important factors.
Error detection
• Basic approach is the use of redundancy bits,
• Every data unit is send twice
• Receiving device would then be able to do a bit by bit comparison
between the two versions of data
• Any mismatch would an error
• Original Data: 10110010
• Transmitted Data: 10110010 10110010
• The receiver compares the two copies:
Error detection-Redundancy check
• Disadvantage
• Transmission time and bandwidth becomes doubled.
• Therefore instead of repeating the entire data stream,a shorter group
of bits may be appended to end of each bit
• This technique is called redundancy because the extra bits are
redundant to the information and they are discarded
Error detection
• Three types of redundancy checks are common in data
communication
1. Parity check
2. Checksum
3. Cyclic redundancy check
Cyclic redundancy check-CRC
• It is based on binary division.
• CRC uses Generator Polynomial which is available on both sender and
receiver side.
• Generator Polynomials are used to generate the divisor.
• 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.
Properties Of CRC Generator
The algebraic polynomial chosen as a CRC generator should have at
least the following properties-
Rule-01:
It should not be divisible by x.
This condition guarantees that all the burst errors of length equal to
the length of polynomial are detected.
Rule-02:
It should be divisible by x+1.
This condition guarantees that all the burst errors affecting an odd
number of bits are detected.
STEPS IN CRC- At sender
Let n be the number of bits in divisor
1. A string of n-1 zeros is appended to the data unit
2. Newly extended data is divided by a divisor(generator polynomial)
using a process is known as binary division.
The remainder generated from this division is known as CRC
remainder.
3. Replace the appended 0s at the end of the original data with CRC
remainder .
4. This newly formed code word (Original data + CRC) is transmitted
to the receiver.
STEPS IN CRC- At Receiver
1. The receiver receives the data followed by the CRC remainder.
2. The receiver will treat this whole unit as a single unit, and it is
divided by the same divisor that was used to find the CRC
remainder.
3. On division If the remainder is zero,
• Receiver assumes that no error occurred in the data during the transmission.
• Receiver accepts the data.
4. If the remainder is non-zero,
• Receiver assumes that some error occurred in the data during the
transmission.
• Receiver rejects the data and asks the sender for retransmission.
Example -CRC
• Data word is 1001 and the divisor is x3+x+ 1
• The generator polynomial G(x) x3+x+ 1 (x3 + 0x2 + x + 1 )is encoded as
1011 .
• The generator polynomial consists of 4 bits.
• So, a string of 3 zeroes is appended to the bit stream to be
transmitted.
• The resulting bit stream is 1001000.
At sender
At receiver
Suppose in previous example the fourth bit from the left is
inverted during transmission. Show that this error is detected
at the receiver's end.
Example -CRC
• Suppose the original data is 11100 and divisor is x3 + 1
• The generator polynomial G(x) x3 + 1 (x3 + 0x2 + 0x1 + 1 )is encoded
as 1001.
• Clearly, the generator polynomial consists of 4 bits.
• So, a string of 3 zeroes is appended to the bit stream to be
transmitted.
• The resulting bit stream is 11100000.
•CRC remainder replaces the appended string of 0s at the end of the data
unit, and the final string would be 11100111 which is sent across the
network.
At Receiver
CRC checker generates the remainder of zero. Therefore, the data is accepted.
Questions
1. What is the remainder obtained by dividing x7 + x5 + 1 by the
generator polynomial x3 + 1?
2. A bit stream 10011101 is transmitted using the standard CRC
method. The generator polynomial is x3 + 1. Show the actual bit
string transmitted.
Suppose the third bit from the left is inverted during transmission.
Show that this error is detected at the receiver's end.
Questions
1. What is the remainder obtained by dividing x7 + x5 + 1 by the
generator polynomial x3 + 1?
The remainder is x 2 + x + 1.
Questions
.A bit stream 10011101 is transmitted using the standard CRC method described
in the text. The generator polynomial is x3 + 1. Show the actual bit string
transmitted. Suppose the third bit from the left is inverted during transmission.
Show that this error is detected at the receiver's end.
Ans :
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 [Link], the receiver detects the error and
can ask for a retransmission. If the 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.
Questions
A bit stream 10101010 is transmitted using the standard CRC method.
The generator polynomial is x3 +x2 +1. Show the actual bit string
transmitted. Suppose the second bit from the left is inverted during
transmission. Show that this error is detected at the receiver’s end.
Data link protocols almost always put the
CRC in a trailer rather than in a header. Why?
• The CRC is computed during transmission and appended to the
output stream as soon as the last bit goes out onto the wire. If the
CRC were in the header, it would be necessary to make a pass over
the frame to compute the CRC before transmitting. This would require
each byte to be handled twice— once for checksumming and once for
transmitting. Using the trailer cuts the work in half.
Parity Check
• adding an extra bit, called parity bit to the original data .
• helps to check if any error occurred
• The two types of parity checking are
1. Even Parity
2. Odd Parity
Parity Check
• The two types of parity checking are
• Even Parity − The total number of 1’s in the data unit is made even in
case of even parity.
• Odd Parity − The total number of 1’s in the data unit is made odd in
case of odd parity.
Steps at sender
1. Total number of 1’s in the data unit to be transmitted is counted.
2. The total number of 1’s in the data unit is made even in case of even
parity or
3. The total number of 1’s in the data unit is made odd in case of odd
[Link] is done by adding an extra bit called as parity bit.
4. The newly formed code word (Original data + parity bit) is transmitted to
the receiver.
Steps at Receiver
• At receiver side,
• Receiver receives the transmitted code word.
• The total number of 1’s in the received code word is counted.
• Then, following cases are possible-
• If total number of 1’s is even and even parity is used, then receiver assumes that no
error occurred.
• If total number of 1’s is odd and even parity is used, then receiver assumes that
error occurred.
• If total number of 1’s is even and odd parity is used, then receiver assumes that
error occurred.
• If total number of 1’s is odd and odd parity is used, then receiver assumes that no
error occurred.
Parity Check Example
• Consider the data unit to be transmitted is 1001001 and even parity is
used.
Parity Check Example
• Consider the data unit to be transmitted is 1001001 and even parity is
used.
• At Sender Side-
• Total number of 1’s in the data unit is counted.
• Total number of 1’s in the data unit = 3.
• Clearly, even parity is used and total number of 1’s is odd.
• So, parity bit = 1 is added to the data unit to make total number of 1’s even.
• Then, the code word 10010011 is transmitted to the receiver.
Parity Check Example
At Receiver Side-
•After receiving the code word, total number of 1’s in the code word is
counted.
•Consider receiver receives the correct code word = 10010011.
•Even parity is used and total number of 1’s is even.
•So, receiver assumes that no error occurred in the data during the
transmission.
Limitation
• This technique can not detect an even number of bit errors (two, four, six and so
on).
• If even number of bits flip during transmission, then receiver can not catch the
error.
• EXAMPLE
• Consider the data unit to be transmitted is 10010001 and even parity is used.
• Then, code word transmitted to the receiver = 100100011
• Consider during transmission, code word modifies as 101100111. (2 bits flip)
• On receiving the modified code word, receiver finds the number of 1’s is even and
even parity is used.
• So, receiver assumes that no error occurred in the data during transmission
though the data is corrupted.
Checksum
• Error detection method based on redundancy
• Step - At sender side
1. If m bit checksum is used, the data unit to be transmitted is divided
into segments of m bits.
2. All the m bit segments are added.(Add carry to sum if any)
3. The result of the sum is then complemented using 1’s complement
arithmetic.
The value so obtained is called as checksum.
4. The data along with the checksum value is transmitted to the
receiver.
Checksum- At receiver side
1. The received data unit is divided into segments of m bits.
2. All the m bit segments are added along with the checksum value.
3. The value so obtained is complemented and the result is checked.
Then, following two cases are possible-
If the result is zero,
Receiver assumes that no error occurred in the data during the transmission.
Receiver accepts the data.
If the result is non-zero,
Receiver assumes that error occurred in the data during the transmission.
Receiver discards the data and asks the sender for retransmission.
Question
• Suppose that a message 1010100100111001 is transmitted
using Checksum method (8-bit word). What is the value of the
checksum?
• Also verify that the data is received at the receiver with out any error.
Solution
• At sender
• Sum = 10101001 + 00111001 =11100010
• Compliment =00011101
• Checksum=00011101
• Data transmitted is 101010010011100100011101
At receiver
Find the sum of 10101001 + 00111001 + 00011101
Sum= 11111111
Compliment is 00000000 ,Since it is zero no error has occurred
during transmission
Question
• Suppose that a message 1001110010100011 is transmitted
using Internet Checksum (4-bit word). What is the value of the
checksum?
• Also verify that the data is received at the receiver with out any error.
Solution
• Suppose that a message 1001 1100 1010 0011 is transmitted using Internet
Checksum (4-bit word). What is the value of the checksum?
• At sender
• Sum = 1001 + 1100 + 1010 + 0011=0100
• Compliment =1011
• Checksum=1011
• Data transmitted is 1001 1100 1010 0011 1011
At receiver
Find the sum of 1001 + 1100 + 1010 + 0011 + 1011
Sum=1111
Compliment is 0000 ,Since it is zero no error has occured during
transmission
Question 2
• Consider the data unit to be transmitted is-
•10011001111000100010010010000100
• Consider 8 bit checksum is used.
Solution
• At sender side,
• The given data unit is divided into segments of 8 bits
• Now, all the segments are added and the result is obtained as-
• 10011001 + 11100010 + 00100100 + 10000100 = 1000100011
• Since the result consists of 10 bits, so extra 2 bits are wrapped around.
• 00100011 + 10 = 00100101 (8 bits)
• Now, 1’s complement is taken which is 11011010.
• Thus, checksum value = 11011010
• The data along with the checksum value is transmitted to the receiver.
• At receiver side,
• The received data unit is divided into segments of 8 bits.
• All the segments along with the checksum value are added.
• Sum of all segments + Checksum value = 00100101 + 11011010 = 11111111
• Complemented value = 00000000
• Since the result is 0, receiver assumes no error occurred in the data and therefore
accepts it.