ERROR DETECTION AND CORRECTIONS

REVIEW

In the previous topics we studied the functions of the Datalink layer which include:

1. Medium Access Control- ​This functionality helps to regulate/mediate the access to the shared
channel by the connected nodes. There are various protocols to perform this function e.g. CSMA,
ALOHA, channel Partitioning protocols
2. Framing: ​This functionality helps to determine the beginning and end of frames. There various
scheme to perform framing
3. Flow Control: ​The functionality helps two devices working at different speeds to communicate with
each other. It involves a set of rules to restrict the amount of frames sent by the source to avoid
overwhelming a slow receiver. There are two approaches to flow control:
a. Controlling the rate of transmission of data
b. Stop and Wait - where the source waits stops and waits for an acknowledgement after
sending data to the receiver. The sender can only send more data after the acknowledgement
has arrived.
4. Error Detection and Correction. The functionality helps the receiver to detect and correct errors

Introduction to Error Detection and Correction

Every channel has an upper limit on the rate at which information can be transmitted reliably through the
channel. The channel can be optical fiber, Radio (Wireless), Twisted Pair cable or any other. The limitation
on the capacity of a channel to transmit information is what is known as CHANNEL CAPACITY. This
capacity is determined according to the Shannon Equation studied in the previous chapter, the Physical Layer.
Due to the Noise present in the channel and other phenomena of channel impairment, errors occur in
transmitted bits on the receiver side. These errors are detected and corrected with aid of error detection and
correction codes. The channel happens at the transmitter side before actual transmission inorder to aid in
resolution of errors. The process involves addition of redundant bits known as ​parity bits.

There are three types of errors which can occur. These include:

● Single bit error, means that only 1 bit in the data has changed.

1
 ● Bursty errors, means that 2 or more bits in the data have changed

When an error occurs, the receiver can decide to:

● Correct the error, this is known as Forward Error Correction (FEC)

FEC refers​ to the ability of the receiver to both detect and correct errors in the received bit stream. FEC
techniques are valuable because they can decrease the number of sender retransmissions required and hence
improve the performance of the network.

Error correction and detection happens mainly in the ​Transport and Data Link layers​ of the OSI and
TCP/IP network models..

The basic techniques for error detection and correction to be discussed in this chapter are:

● Parity checks
● Checksum
● Cyclic Redundancy Check
● Hamming Codes

It is out of scope of this chapter to discuss advanced error detection and correction codes used in today's
digital communication systems. Such codes include advanced block codes (eg. Reed solomon codes, and
others) and convolutional codes.

Parity Checks

The simplest form of parity check is ​a single bit parity check, ​also known a​s simple parity check.​ This is a
channel encoding technique in which a single redundant bit (known as parity) is added to the data bits to

2
generate a codeword for transmission. This technique can be implemented using two possible configurations:
Odd and Even Parity configurations. ​With ​odd parity scheme,​ the parity bit value is chosen such that
there is an odd number of 1’s in the codeword (original data bits plus parity). On the other hand, with ​even
parity scheme​, the parity bit value is chosen such that there is an even number of 1’s in the code word.

On the receiving side, the receiver just need to count the total number of 1’s to ensure that the number is
even (incase of even parity scheme) or odd in case of odd parity. If odd number of 1’s is found within even
parity scheme, the receiver knows that there is ​at least one bit error​ in the received bit stream (codeword).
Also in the case of odd parity scheme,in case the receiver finds an even number of 1’s, it knows that there is
at least one bit error in the received codeword.

From this discussion, it is clear that the receiver may not discover some bit errors. For example, in the case of
even parity scheme, if two bits are in error, the sum of 1’s will be an even number and therefore the error will
be undetected. The diagram below shows an example of one bit even parity scheme

Incase of bursty errors, a single parity scheme does not work. Furthermore, the single parity scheme can not
detect the exact bit in error.

The ​two dimensional parity check helps​ to improve the performance of parity scheme in that, it can both
detect when an error has occurred and where it has occurred and correct it. With 2D parity check, the block
of bits is organised into rows and columns, that is, i rows and j columns. A parity value is computed for each
row and for each column. Therefore, total number of parity bits is given as ​i+j+1 a​ s shown in the figure
below.

Example: suppose the transmitter wants to transmit the information message shown below

3
 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1

This message can be represented in the following 2D matrix form

If the received bit stream is given as

1 0 1 0 1 1 0 1 1 0 0 1 1 1 0 0 0 1 0 1

The error can be located as follows

The corrupted bit is in position (2,2) and can now be corrected. 2D can ​detect a combination of 2 errors in a
packet but cannot correct.

Checksum

It is typically used in transport layers of OSI, and TCP/IP network models. In this topic we will refer to the
Internet Checksum method. In this technique the d-bits of data is divided into K segments each of m-bits
(where m is typically 8, 16, and 32). At the sender side the segments are added using one’s complement

4
arithmetic to get the sum. The sum is then complemented to get the checksum. The checksum is then sent
along with the data.

At the receiver side, all received segments(including the checksum) are added together usings 1’s complement
arithmetic and the sum complimented. If the result is zero the data is accepted, otherwise it is rejected.

The checksum technique is implemented at the transport layer because it is easy to compute in software.
However, there are common types of errors that can not be detected with this technique. Therefore, the
checksum technique provides relatively weak protection against errors compared to link layer techniques.

Example:

Block codes

Hamming code belongs to a more complex channel code family known as ​block codes​. Block codes are
characterised by use of multiple parity bits. The use of multiple parity bits enhances the code performance in
that, it is able to detect and potentially correct more errors. In a block code, each block of ​n​ bits contains ​k
data bits​, ​the rest​ n-k bits ​are known as parity bits.​ ​ The block code is denoted as (n,k) code. Each parity bit
is computed from a different subset of data bits.

5
A code is defined by the set of all possible n-bit code words.

Coding Rate

The ​rate of code (coding rate) ​in a block code​,​ is the ratio of information bits (data bits) to total bits. It is
expressed as k/n. The coding rate measures the efficiency of the code. With increase in parity bits the code
rate decreases but the error correction ability increases.

Exercises

1. What is the code rate of a code with 4 codewords, each of which is 4 bits word.
2. The data rate over the channel is 50 Mbps; a rate ½ code is used. What is the throughput

Hamming Distance of a Bock code

Hamming Distance, is the number of bits that differ between 2 code words. To find the hamming distance
between two codewords you perform exclusive OR operation and count number of 1’s.

Example, for the codewords 01110 and 11011, the value of D is 3.

The Performance of a given code is usually determined by the minimum number Hamming distance(D​min​).

Example: find the minimum hamming distance of a code with codewords 0111,1011,1101 and 1110

Important note:​ A block code with a minimum hamming distance of ​d​ can detect a maximum ​d-1 errors
and correct​ (d-1)/2 errors.

Hamming code

Hamming code is an example of block codes.

6
This technique can be applied to data units of any length. Hamming code can detect errors, locate
the position of errors and correct them. The technique can detect up to two simultaneous bit errors
but can only correct single bit errors. The algorithm works by encoding the original message with a
series of redundant bits, known as parity bits in this context. The parity bits are placed in positions
of power of 2, that is, positions. The rest of the positions are occupied by data bits. This kind of
positioning makes it possible for the technique to be able to detect and correct errors.

Example a 7-bit hamming structure is given as

D7 D6 D5 P4 D3 P2 P1

In the structure Di represents data bit in i position , ​and Pi represent parity bit in position i , e.g.,
D7 is data bit in position 7.

The number of parity bits to be added to the original message (frame) is determined according to the
equality

Where m is number of bits in the original message, p is the number of parity bits to be added to the
message.

Each parity bit is computed from a different subset of data bits. This makes the code more
powerful in the sense that it can detect and potentially correct more errors. In hamming code
structure, the value of for each parity bit depends on the following factors:

● Bit position of parity in the Hamming structure.

7
 ● The hamming code technique configuration, that is, whether is configured as even or odd
parity

Example:

Suppose the sender intends to transmit the message 1101, in the 7-bit Hamming structure the bits
will be arranged as shown below

1 1 0 P4 1 P2 P1

The problem will now be to find the values of P1, P2, and P4.

These values are determined as follows:

1. P1, from the hamming code structure you start with bit P1, skip the next bit, select the next bit,
​

etc. The algorithm selects 1 bit, skips the next, repeatedly until the end of structure. From the

diagram above the algorithm will select P1 D3 D5 D7, replacing the data bits P1 101, therefore for

even parity the value of P1 is 0

2. P
​ 2, from the hamming code structure you start with bit P2, select 2 bits, skip the next 2 bits, etc.

The algorithm selects 2 bits, skips the next 2 bits, repeatedly until the end of structure. From the

diagram above the algorithm will select P2 D3 D6 D7, replacing the data bits P2 111, therefore for

even parity the value of P2 is 1

3. P4, from the hamming code structure you start with bit P4, select first 4 bits, skip the next 4
​

bits, etc. The algorithm selects 4 bits, skips the next 4 bits, repeatedly until the end of structure.

8
From the diagram above the algorithm will select P4 D5 D6 D7, replacing the data bits P4 011,

therefore for even parity the value of P4 is 0

Example

If the 7-bit hamming code word received by the receiver is 1011011. Assuming even parity
configuration state whether the code word is correct or wrong and locate the bit having error

P1 D3 D5 D7

1 0 1 1

P1=1, because there contradiction (we are getting odd sum )

P2 D3 D6 D7

1 0 0 1

P2=0, because there is no contradiction with the parity configuration (No of Is is even)

P4 D5 D6 D7

9
 1 1 0 1

P4=1, there is contradiction

P4P2P1=(101)​2​=(5)​10 , the
​ 5th bit is in error, set D5 to zero

Cyclic Redundancy Check (CRC)

It is a type of block code. Redundant bits are added to the data bits to generate codewords for transmission.
This technique is the one widely used in computer networks today. CRC codes are also known as ​polynomial
codes​. This is because, it is possible to view the bit string as polynomial whose coefficients are the 0 and 1
values of the bit string. For example, code 01101 can be represented as

0x​4​+1x​3​+1x​2​+0x​1​+1x​0

The redundant bits is a remainder derived from polynomial division of the message polynomial by a
generator, denoted as ​G ​in this chapter. The redundant bits are added at the end of the message bits to
generate a systematic block code shown in figure2 below. The technique has a considerable bursty error
detection capability.

OPERATION OF CRC

Consider d-bit piece of data, D, to be transmitted to the receiving node. The sender and receiver must first
agree of the Generator (G) which consist of r+1 bit pattern. The left most bit (most significant bit) of G must
be 1. For a given Data D, the sender will choose ​r additional bits, R, and append to D such that d+r bits are
exactly divisible by G using modulo 2 arithmetics.

To check error, the receiver divides d+r bits received by G, and if the remainder is nonzero, the receiver
knows that an error has occurred otherwise the data is accepted as being correct.

10
CRC calculations are done with modulo arithmetics without carries or borrows for addition and subtraction.
Addition and subtractions are equivalent to bitwise Exclusive OR (XOR) of the operands. With XOR
operation the result is 1 if the bits are different otherwise zero. For example

1011 XOR 0101=1110

Example 2: ​Suppose the data bits to be transmitted, D, is 101110, and the generator, G, is 1001, the
transmitted bit stream is computed as shown below

Therefore, the transmitted bit stream is given as 101110011, which is a 9-bit stream.

At the receiving node, the received bit stream, is divided by G to check for errors. If the division results to a
remainder of zero it deemed that no error has occurred, otherwise for non zero remainder an error has
occurred.

Example 2

If the generator polynomial, G(x) is given as G(x)=x​3​+x+1, and the data to be protected against
errors is 1001. Determine the CRC and the transmitted codeword.

11
HUB, BRIDGE AND SWITCH

HUB: It is a layer 1 (physical layer) device. A hub is a simple device that takes an input (i.e., a frame's bits)
and retransmits it to all connected devices. When data comes into a hub interface, the hub simply broadcasts
the bit on all the connected hosts. This is because it has no knowledge of addresses. The other hosts, other
than the intended receiver dicards the received data. The device ​works in half duplex mode, meaning that it
can not send and receive data at the same time(device can either be sending or receiving but not both).
FInally the device has security risks because it broadcasts data to all connected devices. Nowadays, they have
been replaced by switches.

Bridge: They were introduced to deal with limitations of hubs. They are used to interconnect different LAN
segments. In contrast to hubs, which are physical-level devices, bridges operate on Ethernet frames and thus
are layer-2 devices. They filter and forward packets between different LAN segments in an organization. The
bridge examines the destination address of the frame and forwards it to the appropriate LAN segment. .
Filtering is the ability to determine whether a frame should be forwarded to an interface or should just be
dropped. When the frame should be forwarded, ​forwarding is the ability to determine which of the interfaces
the frame should be directed to. Bridge filtering and forwarding are done with a ​bridge table relying on
MAC addresses (Link layer addresses).

The major difference between ​routers and bridges is that bridges rely on MAC address (layer 2 address) to
filter and forward traffic to hosts, while routers rely on IP addresses (layer 3 address) to filter and forward
traffic to hosts. In the figure below, the numbers 1,2,3,4,5 represent the layers TCP/IP network model.

12
Bridges have been replaced by switches.

SWITCH

Switch is a layer 2 device just like a bridge. It relies on a Link Layer (MAC)address to filter and forward
traffic. The device has a MAC address table to aid in filtering and forwarding of data. The device self learns
the MAC addresses of all connected hosts. It forwards frames only to the intended destination connected to
it. Unlike a hub works in full duplex mode, meaning that it can send and receive data at the same time.
Compared to a hub the device has increased security and saves huge amount of bandwidth. The figure below
depicts an image of a switch

13