23EACE302 DATA COMMUNICATION AND NETWORKS
Data Link Layer:
Error Detection
Error Detection
• When data are transmitted from one node to the
next, they can become corrupted due to noise,
interference and distortion
• However, we must be able to transfer data with
acceptable accuracy even under these errors
• Some applications can tolerate a small level of error,
e.g., random errors in audio or video transmissions
may be tolerable
• But, when we transfer text files, we expect 100%
accuracy
Error Detection
• Providing acceptable level of accuracy requires a
mechanism for detecting the errors and sometimes
correcting the errors, e.g.,
• Some multimedia applications try to correct the
corrupted frame
• However, most link-layer protocols simply discard the
frame upon detection of errors and let the upper-layer
protocols handle the retransmission of the frame
Error Detection
• The design of the error detection / correction mechanism
depends on the statistics of errors caused by the channel
• Single bit error: Only 1 bit is in error in the entire data unit
(e.g., a byte, character or packet)
• Burst error: Two or more bits in the data unit are in error
Error Detection
• Error Detection
• Requires only checking if an error has occurred; YES or NO?
• Error Correction
• Need to know the exact number of bits that are corrupted and,
more importantly, their locations in a long string of bits
• It is a very difficult task. Consider, for example, the task of
finding the locations of 10 errors in a packet of 1000 bits!
• Redundancy
• It is the central concept in detecting or correcting errors
• We need to send some extra bits with our data
• The redundant bits are added by the sender before
transmission and removed by the receiver
Error Detection
• Error Control Coding is the systematic way of adding
redundant bits to the actual data bits that we want to transmit
• The redundant bits depend on the pattern of data bits that we
want to transmit and are derived from the data bits as per a
specific rule in order to satisfy some properties
• E.g., odd parity or even parity is a simple property
• The receiver checks if the specific properties between the
data and redundant bits still hold even after passing through
the channel and thereby can determine if there is any error
and possibly correct it
Error Detection
• Types of Coding Schemes:
• Block Coding: Each block of data is encoded independent
of other blocks
• Convolutional Coding: Each block of data is encoded also
depending on ‘m’ previous blocks and we call it a memory
order of ‘m’
• Performance Metrics:
• The code rate or the ratio of data bits to coded bits
• Robustness of the coding scheme, e.g., how many different
types of errors it can detect / correct
Block Coding
• Divide the message into k-bit blocks called datawords
• Add r redundant bits to each block
• The resulting n-bit blocks (n = k + r) are called codewords
• Since n > k, the number of possible codewords (2n) is larger
than the number of possible datawords (2k)
• The block coding process is one-to-one
• The same dataword is always encoded as the same codeword
• Thus, we have 2n - 2k codewords that are unused
• We call those codewords invalid or illegal
Block Coding
• Always valid codewords are transmitted
• If the received codeword is invalid, then it indicates that the
data was corrupted during transmission
• The receiver must have the list of valid codewords at its
end – the sender can share this in the beginning
• When a valid codeword is received it is accepted and the
dataword is extracted from it
• When an invalid codeword is received, it is discarded
• For error detection to work the originally transmitted
valid codeword has to change to an invalid one
Block Coding
• Sometimes one valid codeword may change to another
valid codeword due to errors
• The error detection will fail if this happens and the error will
remain undetected in this case
• If two valid codewords are spaced far apart then small
levels of noise cannot turn one valid codeword into
another valid codeword and errors will be detected
• We need a way to measure the distance between
two codewords
Hamming Distance
• The Hamming Distance between two codewords of the
same size is the number of bit positions where they differ
• One can take the XOR of the two codewords and then
count the number of 1’s to compute their Hamming
distance
• In a set of codewords, the minimum Hamming distance
is the smallest Hamming distance for all possible pairs of
codewords
• If we want to detect up to s bit errors with guarantee then
the minimum Hamming distance must be s+1
Linear Block Codes
• A linear block code is a code in which the exclusive OR
(addition modulo-2) of two valid codewords creates
another valid codeword
• The minimum Hamming distance for a linear block
code is the number of 1s in the nonzero valid
codeword with the smallest number of 1s
• An example of a linear block code is a parity-check code
with even parity (see the table on the next slide)
• In this code we use only one redundant bit
• The minimum Hamming distance of this code is 2
• It can detect single bit errors (in fact an odd number of errors)
Cyclic Codes
• Cyclic codes are special linear block codes with one extra
property; In a cyclic code, if a codeword is cyclically shifted
(rotated), the result is another codeword
• One type of cyclic codes called the cyclic redundancy check
(CRC) is commonly used in LANs and WANs (see table on
the previous slide; observe both linear and cyclic properties)
• One advantage of a cyclic code is that the encoder and
decoder can be easily and cheaply implemented in hardware
Cyclic Redundancy Check (CRC)
• The encoder takes a dataword and augments it with n − k
number of 0s
• It then divides the augmented dataword by the divisor
using modulo-2 binary division
• The process of modulo-2 binary division is similar to the
familiar division process we use for decimal numbers
• But,
• Addition and subtraction in this case are the same; we use the
XOR operation to do both
• Multiplication is done by bitwise AND operation
• When there are no bits left to pull down, we have a result
Cyclic Redundancy Check (CRC)
• The remainder forms the check bits
• They are appended to the dataword to create the
codeword
• The codeword can change during transmission
• The decoder does the same division process as the
encoder
• The remainder of the division is called the syndrome
• If the syndrome is all 0s, there is no error with a high
probability; the dataword is separated from the received
codeword and accepted
• Otherwise, everything is discarded
Cyclic Redundancy Check (CRC)
• How should we choose the divisor?
• Depends on what error detection / correction properties
we would like the CRC to possess, e.g., certain choices
of divisors can guarantee the detection of
• all single bit errors
• all odd number of errors
• all burst errors of a certain length, etc.
Cyclic Redundancy Check (CRC)
References
[1] Behrouz Forouzan, “Data Communication and
Networking”, Tata McGraw Hill, 6th edition, 2022.
[2] James Kurose and Keith Ross, “Computer Networking:
A Top-down Approach” 8th edition, Addison Wesley 2021.
[3] Andrew S Tannenbaum, David J. Whetheral, “Computer
Networks”, Prentice Hall, 6th edition, 2021.
CRC Polynomials
• The choice of divisors is better understood by
expressing binary patterns as polynomials
• A pattern of 0s and 1s can be represented as a
polynomial with coefficients of 0 and 1
• The power of each term shows the position of the bit;
the coefficient shows the value of the bit
CRC Polynomials
• The degree of a polynomial is the highest power in the
polynomial
• Adding and subtracting polynomials are done by adding or
subtracting the coefficients of terms with the same power
• The coefficients are only 0 and 1, and addition is
modulo-2 which has two consequences
• First, addition and subtraction are the same
• Second, adding or subtracting is done by combining terms and
deleting pairs of identical terms
• Multiplying a term by another term is very simple
• We just add the powers
CRC Polynomials
• Multiplying a polynomial by another is done term by term
• Each term of the first polynomial is multiplied by all terms of
the second, and added
• The result is then simplified, and pairs of equal terms are
deleted
• Example: (x5 + x3 + x2 + x)(x2 + x + 1)
= x7 + x6 + x3 + x
• Appending a dataword with n-k 0s is equivalent to
shifting the dataword to the left n-k times
• Shifting a dataword to the left (right) k times is equivalent
to multiplying the corresponding polynomial by xk (x-k)
CRC Polynomials
• Define the following polynomials
d(x) = dataword g(x) = divisor or generator
q(x) = quotient r(x) = remainder
c(x) = codeword e(x) = error
s(x) = syndrome
• xn-k d(x) = g(x) q(x) + r(x) : Append n-k zeros and
divide by g(x) and get the augmented dataword
• c(x) = xn-k d(x) + r(x) = g(x) q(x) : Add the remainder
to the augmented dataword and get the codeword c(x)
CRC Polynomials
• c(x) + e(x) = g(x) q(x) + e(x) : Received codeword
• Syndrome polynomial s(x)
= Remainder when the received codeword c(x)+e(x)
is divided by g(x) = Remainder of e(x) / g(x)
• If g(x) divides e(x) then s(x) = 0 and the error goes
undetected
• We can choose g(x) such that it never divides
certain error polynomials e(x) and then the errors
corresponding to e(x) will always be detected
CRC Polynomials
• Example 1: Single Bit Errors
• To detect single bit errors g(x) must have at least
two terms
• Explanation: For single bit errors the error polynomial
is of the form e(x) = xj for some j. If g(x) has at least
two terms, then it will not divide e(x)
CRC Polynomials
• Example 2: An Odd Number of Bit Errors
• To detect an odd number of errors g(x) must have x+1
as one of its factors
• Explanation: Any polynomial multiplied by x+1 will have an
even number of terms. So, if g(x) contains x+1 as one of its
factors then g(x) will not divide polynomials with an odd
number of terms. For an odd number of bit errors, however,
the error polynomial e(x) will have an odd number of terms,
and it will not be divisible by g(x) if g(x) contains x+1 as
one of its factors
CRC Polynomials
• Example 3: An Error Burst of Length m
• To detect an error burst of length m, g(x) must be a
polynomial of degree m or higher and must have at
least two terms
• Explanation: For a burst error of length m, the error
polynomial is e(x) = xj (xm-1 +…+1) for some j. If g(x) has
at least two terms, then it will not divide xj. If g(x) has
degree m or higher, then it will not divide (xm-1 +…+1).
CRC Polynomials
• Example 4: Two Isolated Bit Errors of Any Length
• If g(x) has a primitive polynomial of degree N as a
factor, then it can detect all double errors as long as
the codeword length does not exceed 2N – 1
• Explanation: For two isolated bit errors the error
polynomial is e(x) = xj (xi-j +1) for some i and j. If g(x) has
at least two terms, then it will not divide xj. It turns out that
g(x) can be chosen to be a primitive polynomial of
degree N which has the special property that it will not
divide any polynomial of the form xL +1 if L £ 2N – 1.