Data Link Layer

Error Detection and Correction

Types of Errors
► Single-Bit Error
► In a single-bit error, only 1 bit in the data unit has changed.

► Burst Error
► A burst error means that 2 or more bits in the data unit have
changed.
Error Detection Techniques

► Single parity check / Vertical Redundancy Check (VRC)

► Two-dimensional parity check / Longitudinal Redundancy Check (LRC)
► Cyclic Redundancy Check (CRC)
► Checksum
Single Parity Check (VRC)
► Single Parity checking is the simple mechanism and inexpensive to
detect the errors.
► In this technique, a redundant bit is also known as a parity bit which
is appended at the end of the data unit so that the number of 1 bits
becomes even. Therefore, the total number of transmitted bits would
be 9 bits.
► If the number of 1 bits is odd, then parity bit 1 is appended and if the
number of 1 bits is even, then parity bit 0 is appended at the end of
the data unit.
► At the receiving end, the parity bit is calculated from the received
data bits and compared with the received parity bit.
► This technique generates the total number of 1 even, so it is known as
even-parity checking.
Single Parity Check (VRC)
Limitations of Single Parity Check (VRC)
► It can only detect single-bit errors which are very rare.
► If two bits are interchanged, then it cannot detect the errors.
Two-dimensional parity check (LRC)

► Organizes the data in the form of a table.

► Parity check bits are computed for each row, which is equivalent to
the single-parity check.
► In this, a block of bits is divided into rows, and the redundant row of
bits is added to the whole block.
► At the receiving end, the parity bits are compared with the parity bits
computed from the received data.
Two-dimensional parity check (LRC)
Limitations of Two-dimensional parity
check (LRC)
► If two bits in one data unit are corrupted and two bits exactly the
same position in another data unit are also corrupted, then 2D Parity
checker will not be able to detect the error.
► This technique cannot be used to detect the 4-bit errors or more in
some cases.
Two-dimensional parity check (LRC) -
Example
Two-dimensional parity check (LRC) -
Example
Two-dimensional parity check (LRC) -
Example
Cyclic Redundancy Check (CRC)
► First a string of n 0s is appended to the data unit, and this n number is
less than the number of bits in a predetermined number, known as
division which is n+1 bits.
► Secondly, the newly extended data is divided by a divisor using a
process is known as binary division. The remainder generated from
this division is known as CRC remainder.
► Thirdly, the CRC remainder replaces the appended 0s at the end of
the original data. This newly generated unit is sent to the receiver.
► The receiver receives the data followed by the CRC remainder. 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.
► If the resultant of this division is zero which means that it has no
error, and the data is accepted.
► If the resultant of this division is not zero which means that the data
consists of an error. Therefore, the data is discarded.
Cyclic Redundancy Check (CRC)
CRC Generator
Suppose the original data is 11100 and divisor is 1001.
► A CRC generator uses a modulo-2 division. Firstly, three zeroes are
appended at the end of the data as the length of the divisor is 4 and
we know that the length of the string 0s to be appended is always one
less than the length of the divisor.
► Now, the string becomes 11100000, and the resultant string is divided
by the divisor 1001.
► The remainder generated from the binary division is known as CRC
remainder. The generated value of the CRC remainder is 111.
► 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.
CRC Generator / Encoder
CRC Dcoder
CRC decoder for two cases
CRC Checker
► The functionality of the CRC checker is similar to the CRC generator.
► When the string 11100111 is received at the receiving end, then CRC
checker performs the modulo-2 division.
► A string is divided by the same divisor, i.e., 1001.
► In this case, CRC checker generates the remainder of zero. Therefore,
the data is accepted.
CRC Checker
Checksum Method
► A Checksum is an error detection technique based on the concept of
redundancy.
► Checksum Generator:
► At the sending side the checksum generator subdivides the data into equal
segments of n bits each, and all these segments are added together by using
one's complement arithmetic.
► The sum is complemented and appended to the original data, known as
checksum field.
► The extended data is transmitted across the network.
► Checksum Checker
► This is used to verify at the receiving side.
► The receiver subdivides the incoming data into equal segments of n bits each,
and all these segments are added together, and then this sum is complemented.
► If the complement of the sum is zero, then the data is accepted otherwise data
is rejected.
Sender and Receiver in Checksum Model
Sender and Receiver in Checksum Model
► The Sender follows the given steps:
► The block unit is divided into k sections, and each of n bits.
► All the k sections are added together by using one's complement to get the
sum.
► The sum is complemented and it becomes the checksum field.
► The original data and checksum field are sent across the network.
► The Receiver follows the given steps:
► The block unit is divided into k sections and each of n bits.
► All the k sections are added together by using one's complement algorithm
to get the sum.
► The sum is complemented.
► If the result of the sum is zero, then the data is accepted otherwise the
data is discarded.
Checksum Example
Datawords and Codewords
► Message is divided into blocks, each of k bits, called datawords.
► r redundant bits to each block to make the length n = k + r.
► The resulting n-bit blocks are called codewords.
► With k bits, we can create a combination of 2k datawords; with n bits,
we can create a combination of 2n codewords.
► Since n > k, the number of possible codewords is larger than the
number of possible datawords.
► The same dataword is always encoded as the same codeword.
► This means that we have 2n - 2k codewords that are not used.
► We call these codewords invalid or illegal.
► Example: Let’s consider a coding scheme, where k =4 and n =5. There
are 2k =16 datawords and 2n =32 codewords. Only 16 out of 32
codewords are used for message transfer and 16 are unused.
Example for Error Detection
► Let us assume that k =2 and n =3. The following table shows the list of
datawords and codewords.

► Assume the sender encodes the dataword 01 as 011 and sends it to the
receiver. Consider the following cases:
► The receiver receives 011. It is a valid codeword. The receiver extracts
the dataword 01 from it.
► The codeword is corrupted during transmission, and 111 is received. This
is not a valid codeword and is discarded.
► The codeword is corrupted during transmission, and 000 is received. This
is a valid codeword. The receiver incorrectly extracts the dataword 00.
Two corrupted bits have made the error undetectable.
Example for Error Correction
► In the earlier example increase the redundant bits to 3 hence n = 5. The
following table shows the list of datawords and codewords.

► Assume the dataword is 01. The sender creates the codeword 01011.
► The codeword is corrupted during transmission, and 01001 is received.
the receiver finds that the received codeword is not valid.
► The receiver, assuming that there is only 1 bit corrupted, uses the
following strategy to guess the correct dataword.
► Comparing the received codeword with the first, third and fourth codewords,
the receiver decides that those are not the sent codeword because there are
two different bits.
► The receiver replaces 01001 with 01011 and finds the dataword 01.
Hamming Distance
► The Hamming distance between two words is the number
of differences between corresponding bits.
► The Hamming distance d(000, 011) is 2

► The Hamming distance d(10101, 11110) is 3

► The minimum Hamming distance is the smallest Hamming

distance between all possible pairs in a set of words.
Hamming Distance

► Therefore dmin = 2
► This code guarantees detection of only a single error.
► For example, if the third codeword (101) is sent and one error occurs,
the received codeword does not match any valid codeword.
► If two errors occur, however, the received codeword may match a
valid codeword and the errors are not detected.
Hamming Distance

► Therefore dmin = 3
► This code can detect up to two errors.
► When any of the valid codewords is sent, two errors create a codeword
which is not in the table of valid codewords. The receiver cannot be fooled.
► However, some combinations of three errors change a valid codeword to
another valid codeword. The receiver accepts the received codeword and
the errors are undetected.
Hamming Distance
► To guarantee the detection of up to s errors the minimum
Hamming distance be dmin = s + 1.
► To guarantee correction of up to t errors the minimum
Hamming distance be dmin = 2t + 1.
► A code scheme has a Hamming distance dmin = 4. What is
the error detection and correction capability of this
scheme?
► Detection of up to three errors (s = 3)
► Correction up to one error.
► Error correction codes need to have an odd minimum distance (3,
5, 7,. ).
Error Correction

► Error Correction codes are used to detect and correct the errors when
data is transmitted from the sender to the receiver.
► Error Correction can be handled in two ways:
► Backward error correction: Once the error is discovered, the receiver
requests the sender to retransmit the entire data unit.
► Forward error correction: In this case, the receiver uses the
error-correcting code which automatically corrects the errors.
► A single additional bit can detect the error, but cannot correct it.
Error Correcting Codes

► Hamming codes
► Binary convolutional codes
► Reed-Solomon codes.
► Low-Density Parity Check codes.
Hamming Codes
► For correcting the errors, one has to know the exact position of the error.
For example, If we want to calculate a single-bit error, the error
correction code will determine which one of seven bits is in error. To
achieve this, we have to add some additional redundant bits.
► Suppose r is the number of redundant bits and d is the total number of
the data bits. The number of redundant bits r can be calculated by using
the formula: 2r>=d+r+1 (For single bit error correction)
► The value of r is calculated by using the above formula.
► For example, if the value of d is 4, then the possible smallest value
that satisfies the above relation would be 3.
► To determine the position of the bit which is in error, a technique
developed by R.W Hamming is Hamming code which can be applied to
any length of the data unit and uses the relationship between data units
and redundant units.
Designing Hamming Code for Single Bit
Error Correction
► Imagine that we want to design a code with m message bits and r check
bits that will allow all single errors to be corrected.
► Each of the 2m legal messages has n illegal codewords at a distance of 1
from it.
► These are formed by systematically inverting each of the n bits in the n-bit
codeword formed from it.
► Thus, each of the 2m legal messages requires n + 1 bit patterns dedicated
to it.
► Since the total number of bit patterns is 2n, we must have (n + 1)2m ≤ 2n
► Using n = m + r, this requirement becomes (m + r + 1) ≤ 2r
Techniques used in Hamming Code

► Parity bits: The bit which is appended to the original data of binary
bits so that the total number of 1s is even or odd.
► Even parity: To check for even parity, if the total number of 1s is
even, then the value of the parity bit is 0. If the total number of 1s
occurrences is odd, then the value of the parity bit is 1.
► Odd Parity: To check for odd parity, if the total number of 1s is even,
then the value of parity bit is 1. If the total number of 1s is odd, then
the value of parity bit is 0.
Algorithm of Hamming Code
► An information of 'd' bits are added to the redundant bits 'r' to form
d+r.
► The location of each of the (d+r) digits is assigned a decimal value.
► The 'r' bits are placed in the positions 1,2,.....2r-1.
► At the receiving end, the parity bits are recalculated. The decimal
value of the parity bits determines the position of an error.
Hamming Code - Example
Suppose the original data is 1010 which is to be sent.
Step 1: Determining number of redundant bits
Total number of data bits 'd' = 4
Number of redundant bits r : 2r >= d+r+1
2r>= 4+r+1
Therefore, the value of r is 3 that satisfies the above relation.
Total number of bits = d+r = 4+3 = 7;

Step 2: Determining the position of the redundant bits

The number of redundant bits is 3. The position of the redundant bits is calculated
with corresponds to the raised power of 2. Therefore, their corresponding
positions are 20, 21, 22. The three bits are represented by r1, r2, r4.

The position of r1 = 1
The position of r2 = 2
The position of r4 = 4
Hamming Code - Example

► Representation of Data on the addition of parity bits:

The position of r1 = 1
The position of r2 = 2
The position of r4 = 4
Hamming Code - Example
Determining the r1 bit: The r1 bit is calculated by performing a parity check on
the bit positions whose binary representation includes 1 in the first position.

We observe from the above figure that the bit positions that includes 1 in the
first position are 1, 3, 5, 7. Now, we perform the even-parity check at these bit
positions. The total number of 1 at these bit positions corresponding to r1 is
even, therefore, the value of the r1 bit is 0.
Hamming Code - Example
Determining the r2 bit: The r2 bit is calculated by performing a parity check on
the bit positions whose binary representation includes 1 in the second position.

We observe from the above figure that the bit positions that includes 1 in the
second position are 2, 3, 6, 7. Now, we perform the even-parity check at these
bit positions. The total number of 1 at these bit positions corresponding to r2
is odd, therefore, the value of the r2 bit is 1.
Hamming Code - Example
Determining the r4 bit: The r4 bit is calculated by performing a parity check on
the bit positions whose binary representation includes 1 in the third position.

We observe from the above figure that the bit positions that includes 1 in the
third position are 4, 5, 6, 7. Now, we perform the even-parity check at these bit
positions. The total number of 1 at these bit positions corresponding to r4
is even, therefore, the value of the r4 bit is 0.
Hamming Code - Example
► Data transferred is given below:

► If the data received at the other end is as follows:

► The 4th bit is changed from 0 to 1 at the receiving end

Hamming Code - Example
Parity recalculated at receiving end
► r1 bit: The bit positions of r1 bit are 1,3,5,7
We observe from the figure that the binary
representation of r1 is 1100. Now, we perform the
even-parity check, the total number of 1s appearing
in the r1 bit is an even number. Therefore, the value
of r1 is 0.

► r2 bit: The bit positions of r2 bit are 2,3,6,7.

We observe from the figure that the binary
representation of r2 is 1001. Now, we perform the
even-parity check, the total number of 1s appearing
in the r2 bit is an even number. Therefore, the value
of r2 is 0.
Hamming Code - Example
► r4 bit: The bit positions of r4 bit are 4,5,6,7.
We observe from the above figure that the binary
representation of r4 is 1011. Now, we perform the
even-parity check, the total number of 1s appearing
in the r4 bit is an odd number. Therefore, the value
of r4 is 1.

The binary representation of redundant bits,

i.e., r4r2r1 is 100,
and its corresponding decimal value is 4.
Therefore, the error occurs in a 4th bit position.
The bit value must be changed from 1 to 0 to correct the error.
Convolution Code

► In a convolutional code, an encoder processes a sequence of input bits

and generates a sequence of output bits.
► There is no natural message size or encoding boundary as in a block
code.
► The output depends on the current and previous input bits, that the
encoder has in memory.
► The number of previous bits on which the output depends is called the
constraint length of the code.
► Convolutional codes are specified in terms of their rate and
constraint length.
Convolution Code - Example
► This code is known as the NASA convolutional code of r = 1/2 and k = 7

► In this each input bit on the left-hand side produces two output bits on the
right-hand side that are XOR sums of the input and internal state.
► Since it deals with bits and performs linear operations, this is a binary, linear
convolutional code.
► Since 1 input bit produces 2 output bits, the code rate is 1/2.
► It is not systematic since none of the output bits is simply the input bit.
Convolution Code - Example

► The internal state is kept in six memory registers.

► Each time another bit is input the values in the registers are shifted to
the right.
► If 111 is input and the initial state is all zeros, the internal state,
written left to right, will become 100000, 110000, and 111000 after
the first, second, and third bits have been input.
► The output bits will be 11, followed by 10, and then 01.
► It takes seven shifts to flush an input completely so that it does not
affect the output.
► The constraint length of this code is thus k = 7.
Convolution Code
► A convolutional code is decoded by finding the sequence of input bits
that is most likely to have produced the observed sequence of output
bits.
► Widely used algorithm developed by Viterbi (Forney, 1973).
► Convolutional codes have been popular in practice because it is easy
to factor the uncertainty of a bit being a 0 or a 1 into the decoding.
► Extensions of the Viterbi algorithm can work with these uncertainties
to provide stronger error correction.
► This approach of working with the uncertainty of a bit is called
soft-decision decoding.
► Conversely, deciding whether each bit is a 0 or a 1 before subsequent
error correction is called hard-decision decoding.
Reed-Solomon code
► Reed-Solomon codes operate on m bit symbols and are based on the fact that
every n degree polynomial is uniquely determined by n + 1 points.
► For example
► A line having the form ax + b is determined by two points.
► Extra points on the same line are redundant, which is helpful for error correction.
► Imagine that we have two data points that represent a line and we send those two
data points plus two check points chosen to lie on the same line.
► If one of the points is received in error, we can still recover the data points by
fitting a line to the received points.
► Three of the points will lie on the line, and one point, the one in error, will not.
► By finding the line we have corrected the error.
► These codes are widely used in practice because of their strong
error-correction properties, particularly for burst errors.
► Reed-Solomon codes are often used in combination with other codes such as a
convolutional code.
LDPC (Low-Density Parity Check) code

► In an LDPC code, each output bit is formed from only a fraction of the
input bits.
► This leads to a matrix representation of the code that has a low
density of 1s, hence the name for the code.
► The received codewords are decoded with an approximation algorithm
that iteratively improves on a best fit of the received data to a legal
codeword.
► This corrects errors.
► LDPC codes are practical for large block sizes and have excellent
error-correction abilities that outperform many other codes
Encoding in LDPC

► A low - density parity check (LDPC) code is specified by a parity-check

matrix containing mostly 0s and a low density of 1s.

► The rows of the matrix represent the equations and the columns
represent the bits in the codeword, i.e. code symbols.
► A LDPC code is represented by (n, j, k) , where j is the block length, is
the number of 1s in each column and k is the number of 1s in each
row, holding the following properties −
► j is the small fixed number of 1’s in each column, where j > 3

► k is the small fixed number of 1’s in each row, where k > j.

Example 1 − Parity Check Matrix of
Hamming Code
► The following parity check matrix Hamming code having n = 7, with 4
information bits followed by 3 even parity bits. The check digits are
diagonally 1. The parity equations are given alongside:
Example 2 − Low - Density Parity Check
Matrix
► This examples illustrates an (12, 3, 4) LDPC matrix, i.e. n = 12, j = 3 and k =
4. This implies that each equation operates on 4 code symbols and each code
symbol appears in 3 equations. Unlike parity check matrix of the Hamming
code, this code does not have any diagonal 1s in parity bits.
Decoding of LDPC Codes
► In the first technique,
► the decoder does all the parity checks as per the parity equations.
► If any bit is contained in more than a fixed number of unsatisfied parity equations,
the value of that bit is reversed.
► Once the new values are obtained, parity equations are recomputed using the new
values.
► The procedure is repeated until all the parity equations are satisfied.
► This decoding procedure is simple, but is applicable only when the parity-check
sets are small.
► The second method
► performs probabilistic algorithms on LDPC graphs.
► The graph is a sparse bipartite graph that contains two sets of nodes, one set
representing the parity equations and the other set representing the code symbols.
► A line connects node in first set to the second if a code symbol is present in the
equation.
► Decoding is done by passing messages along the lines of the graph.
► Messages are passed from message nodes to check nodes, and from check nodes
back to message nodes and their parity values are calculated.