CS321: Computer Networks

Error Detection and Correction

Dr. Manas Khatua

Assistant Professor
Dept. of CSE
IIT Jodhpur
E-mail: manaskhatua@iitj.ac.in
Error Detection and Correction
• Objective: System must guarantee that the data received are identical to the data
transmitted

• Methods:
1. If a frame is corrupted between the two nodes, it needs to be corrected
2. Drop the frame and let the upper layer (e.g. Transport) protocol to handle it by
retransmission

• Reason of error: noise in the channel

• Types of Error

24-04-2018 Dr. Manas Khatua 2

Detection and Correction
• Central idea: use redundancy
– put some extra bit with our data
– Achieved by coding scheme
• Block coding
• Convolution coding

• Error Detection : looking to see if any error has occurred

• Error Correction: trying to recover the corruption

– Need to know exact number of bits that are corrupted
– Needs the position of those bits

24-04-2018 Dr. Manas Khatua 3

Block Coding

Add r
bits

• How the extra r bits are chosen or calculated?

• How can errors be detected?
– Finds the existence of invalid codeword
24-04-2018 Dr. Manas Khatua 4
Example
• Let us assume that k = 2 and n = 3. Table shows the list of
datawords and codewords.
• Later, we will see how to derive a codeword from a dataword.

Assume the sender encodes the dataword

Dataword Codeword 01 as 011 and sends it to the receiver.
00 000
Possible options at receiver (assume one
01 011
bit corruption):
10 101
11 110 011 => valid option
111 => invalid
001 => invalid
010 => invalid

24-04-2018 Dr. Manas Khatua 5

Hamming Distance
• The Hamming distance between two words (of the same size) is the
number of differences between the corresponding bits.

• Notation: Hamming distance between two words x and y as d(x, y).

• Calculation: apply the XOR operation on the two words and count
the number of 1’s in the result

• To guarantee the detection of up to s errors in all cases, the

minimum Hamming distance in a block code must be dmin = s + 1.

24-04-2018 Dr. Manas Khatua 6

Types of Block Codes
• Types:
– Linear Block Code
– Non-linear Block Code

• A linear block code is a code in which the exclusive OR (addition modulo-2)

of two valid codewords creates another valid codeword.
• Example:
– Reed-Solomon codes
– Hamming codes
– Parity Check Code.

• Minimum Hamming distance: number of 1s in the nonzero valid codeword

with the smallest number of 1s.
Dataword Codeword
00 000
01 011
10 101
11 110
24-04-2018 Dr. Manas Khatua 7
Parity Check Code
Dataword Codeword Dataword Codeword
0000 00000 1000 10001
0001 00011 1001 10010
0010 00101 1010 10100
0011 00110 1011 10111

24-04-2018 Dr. Manas Khatua 8

Cont…
• Modulo arithmetic:
• Generator:
r0 = a3 + a2 + a1 + a0 (modulo-2)
• Checker:
s0 = a3 + a2 + a1 + a0 + q0 (modulo-2)

• A parity-check code can detect an odd number of errors.

• what happens if an even number of bit errors occur?

– a more robust error-detection scheme is needed

24-04-2018 Dr. Manas Khatua 9

Insight into Error-Correction
• two-dimensional parity scheme

• The receiver can thus not only

detect but can identify the bit
that has corrupted.

• The ability of the receiver to both

detect and correct errors is
known as forward error
correction (FEC).

24-04-2018 Dr. Manas Khatua 10

Cyclic Redundancy Check (CRC)
• It is an error-detection technique used widely in today’s computer networks
(e.g., LAN, WAN)

• It is linear block code

• If a codeword is cyclically shifted (rotated), the result is another codeword.

– E.g., if 1011000 is a codeword and we cyclically left-shift, then 0110001 is also a
codeword.

24-04-2018 Dr. Manas Khatua 11

CRC with C(7,4)
• C(7,4) => 4 bits dataword, 7 bits codeword

24-04-2018 Dr. Manas Khatua 12

CRC Encoding

24-04-2018 Dr. Manas Khatua 13

CRC Decoding

24-04-2018 Dr. Manas Khatua 14

Cont…

24-04-2018 Dr. Manas Khatua 15

Polynomial Representation

• The power of each term shows the position of the bit

• The coefficient shows the value of the bit

• The degree of a polynomial is the highest power in the polynomial.

24-04-2018 Dr. Manas Khatua 16

Polynomial Operations
• Adding and Subtracting Polynomials
– Not same as it is performed in mathematics
– addition and subtraction are the same
– adding or subtracting is done by combining terms and deleting pairs of identical
terms
– E.g., x5+x4+x2 + x6+x4+x2 => x6+x5

• Multiplying or Dividing Terms

– just add the powers
– E.g., x4 * x3 => x7 x7/x3 => x4

• Multiplying Two Polynomials

– is done term by term
– E.g., (x5+x3+x2+x)(x2+x+1)
=> (x7+x6 +x5)+(x5+x4+x3)+(x4+x3+x2)+(x3+x2+x)
=> x7+x6+x3+x

• Dividing One Polynomial by Another

– Division of polynomials is conceptually the same as the binary division we
discussed for an encoder.

24-04-2018 Dr. Manas Khatua 17

Cont…

• Shifting Operation

24-04-2018 Dr. Manas Khatua 18

Cyclic Code Encoder Using Polynomials

• The divisor in a cyclic code is normally called the generator

polynomial or simply the generator.

24-04-2018 Dr. Manas Khatua 19

Standard Polynomials for CRC
• The divisor in a cyclic code is normally called the generator
polynomial or simply the generator.

24-04-2018 Dr. Manas Khatua 20

Divisor Polynomial Selection
• This depends on the expectation we have from the code.
• Let, Dataword: d(x), Codeword: c(x), Generator: g(x), Syndrome: s(x), Error: e(x)

• If s(x) ≠ 0 --> one or more bits is corrupted

• If s(x) == 0 --> either no bit is corrupted or the decoder failed to detect any errors

• Those errors that are divisible by g(x) are not caught.

• A good polynomial generator needs to have the following characteristics:

– It should have at least two terms.
– The coefficient of the term x0 should be 1.
– It should not divide xt + 1, for t between 2 and n - 1.
– It should have the factor x + 1.

24-04-2018 Dr. Manas Khatua 21

Checksum
• Error detection technique
• Used in Network and Transport Layer

24-04-2018 Dr. Manas Khatua 22

Example
• Want to send a message represented by five 4-bit units (7,11,12,0,6)
• We send (7,11,12,0,6,36)
• Receiver checks (7+11+12+0+6-36)=?

• Problem:
– Number of bits required to present the units and checksum is more ( in the
above example it is >4bits)

• Solution: using One’s complement

– 7,11,12,0,6 require 4 bits
– Change the 36 (=100100) as follows: (10+0100) = 6; One’s complement of 6 is 9
– Send (7,11,12,0,6,6) OR (7,11,12,0,6,9)

24-04-2018 Dr. Manas Khatua 23

Internet Checksum
• The implementation of the checksum in
the IPv4 packet follows the same
principles.
• Used a 16-bit checksum

• Initially, the value of the checksum field is

set to 0.
• Then the entire header is divided into 16-
bit sections and added together.
• The result (sum) is complemented and
inserted into the checksum field.

• The checksum in the IPv4 packet covers

only the header, not the data. Why?
– First, all higher-level protocols that
encapsulate data in the IPv4 datagram have a
checksum field that covers the whole packet.
– Second, the header of the IPv4 packet changes
with each visited router, but the data do not.

24-04-2018 Dr. Manas Khatua 24

Cont…
• Advantage:
– Fast checking
– Small number of bits required

• Disadvantage:
– Not robust
– e.g., if the values of several words are incremented but the sum
and the checksum do not change, the errors are not detected.
– Solution: weighted checksum proposed by Fletcher and Adler

24-04-2018 Dr. Manas Khatua 25

Error Correction
• Two ways:
– Forward Error Correction (FEC)
– Retransmission

Flow Control: production and consumption rates must be

balanced

24-04-2018 Dr. Manas Khatua 26

24-04-2018 Dr. Manas Khatua 27