ERROR DETECTION

When data is transmitted from one device to another device, the system
does not guarantee whether the data received by the device is identical
to the data transmitted by another device. An Error is a situation when
the message received at the receiver end is not identical to the message
transmitted.

Types Of Errors

Single-Bit Error:

The only one bit of a given data unit is changed from 1 to 0 or from 0 to
1.

In the above figure, the message which is sent is corrupted as single-bit,

i.e., 0 bit is changed to 1.

Single-Bit Error does not appear more likely in Serial Data Transmission.
For example, Sender sends the data at 10 Mbps, this means that every
bit lasts only for 0.1 micro sec and for a single-bit error to occurred, a
noise must have duration of 0.1 micro sec. Generally the duration of
noise longer than the duration of each bit.
Single-Bit Error mainly occurs in Parallel Data Transmission. For example,
if eight wires are used to send the eight bits of a byte, if one of the wire
is noisy, then single-bit is corrupted per byte.

Burst Error:

The two or more bits are changed from 0 to 1 or from 1 to 0 is known as

Burst Error.

The Burst Error is determined from the first corrupted bit to the last
corrupted bit.

The duration of noise in Burst Error is more than the duration of noise in
Single-Bit.

Burst Errors are most likely to occur in Serial Data Transmission.

The number of affected bits depends on the duration of the noise and
data rate.

Redundancy: The central concept in detecting or correcting errors is

redundancy. To be able to detect or correct errors, we need to send
some extra bits with our data. These redundant bits are added by the
sender and removed by the receiver. Their presence allows the receiver
to detect or correct corrupted bits.
Coding: Redundancy is achieved through coding schemes. The sender
adds redundant bits through a process that creates a relationship
between the redundant bits and the actual data bits. The receiver checks
the relationships between the two sets of bits to detect or correct the
errors. Figure shows the general idea of coding.

The most popular Error Detecting Techniques are:

1. Single Parity Check / VRC

o Single Parity checking is the simple mechanism and inexpensive to

detect the errors.
o 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 1s becomes even. Therefore, the total number of transmitted
bits would be 9 bits.
o If the number of 1s bits is odd, then parity bit 1 is appended and if
the number of 1s bits is even, then parity bit 0 is appended at the
end of the data unit.
 o At the receiving end, the parity bit is calculated from the received
data bits and compared with the received parity bit.
o This technique generates the total number of 1s even, so it is
known as even-parity checking.

Example –
If the source wants to transmit data unit 1100111 using even parity
to the destination. The source will have to pass through Even Parity
Generator.

Advantages :
 VRC can detect all single bit error.
 It can also detect burst errors but only in those cases where
number of bits changed is odd, i.e. 1, 3, 5, 7, …….etc.
Disadvantages :
 The major disadvantage of using this method for error detection
is that it is not able to detect burst error if the number of bits
changed is even, i.e. 2, 4, 6, 8, …….etc.
 It can only detect single-bit errors which are very rare.

2. Two-Dimensional Parity Check/ Longitude Redundancy Check

(LRC)

In this method, data which the user want to send is organised into
tables of rows and columns. A block of bit is divided into table or matrix
of rows and columns. In order to detect an error, a redundant bit is
added to the whole block and this block is transmitted to receiver. The
receiver uses this redundant row to detect error. After checking the
data for errors, receiver accepts the data and discards the redundant
row of bits.
Example :
If a block of 32 bits is to be transmitted, it is divided into matrix of four
rows and eight columns which as shown in the following figure :

Advantage:
LRC is used to detect burst errors.

Disadvantage:
The main problem with LRC is that, it is not able to detect error if two
bits in a data unit are damaged and two bits in exactly the same
position in other data unit are also damaged. Example: If data 110011
010101 is changed to 010010110100.

Figure : Two bits at same bit position damaged in 2 data units

In this example 1st and 6th bit in one data unit is changed . Also the 1st
and 6th bit in second unit is changed.
3. Checksum

A Checksum is an error detection technique based on the concept of

redundancy.

It is divided into two parts:

Checksum Generator

A Checksum is generated at the sending side. 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.

The Sender follows the given steps:

1. The block unit is divided into k sections, and each of n bits.

2. All the k sections are added together by using one's complement to g
et the sum.
3. The sum is complemented and it becomes the checksum field.
4. The original data and checksum field are sent across the network.

Checksum Checker

A Checksum is verified 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.

The Receiver follows the given steps:

1. The block unit is divided into k sections and each of n bits.
2. All the k sections are added together by using one's complement algo
rithm to get the sum.
3. The sum is complemented.
4. If the result of the sum is zero, then the data is accepted otherwise th
e data is discarded.
Example

Suppose that the sender wants to send 4 frames each of 8 bits, where
the frames are 11001100, 10101010, 11110000 and 11000011.

Advantage :
The checksum detects all the errors involving an odd number of bits as
well as the error involving an even number of bits.
Disadvantage :
The main problem is that the error goes undetected if one or more bits
of a subunit is damaged and the corresponding bit or bits of a subunit
are damaged and the corresponding bit or bits of opposite value in
second subunit are also damaged. This is because the sum of those
columns remains unchanged. Example –
If the data transmitted along with checksum is 10101001 00111001
00011101. But the data received at destination is 00101001 10111001
00011101.
Receiver Site :
00101001 1st bit of subunit 1 is damaged
10111001 1st bit of subunit 2 is damaged
00011101 checksum
11111111 sum
00000000 Ok 1's complement
Although data is corrupted, the error is undetected.

4.Cyclic Redundancy Check (CRC)

CRC is a redundancy error technique used to determine the error.

Following are the steps used in CRC for error detection:

o In CRC technique, 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.
o 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.
o Thirdly, the CRC remainder replaces the appended 0s at the end of
the original data. This newly generated unit is sent to the receiver.
o 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.

Let's understand this concept through an example:

Suppose the original data is 11100 and divisor is 1001.

CRC Generator
o 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.
o Now, the string becomes 11100000, and the resultant string is
divided by the divisor 1001.
o The remainder generated from the binary division is known as CRC
remainder. The generated value of the CRC remainder is 111.
o 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 Checker
o The functionality of the CRC checker is similar to the CRC
generator.
o When the string 11100111 is received at the receiving end, then
CRC checker performs the modulo-2 division.
o A string is divided by the same divisor, i.e., 1001.
o In this case, CRC checker generates the remainder of zero.
Therefore, the data is accepted.
ERROR CORRECTION

When bits are transmitted over the computer network, they are subject
to get corrupted due to interference and network problems. The
corrupted bits leads to spurious data being received by the receiver and
are called errors.
Error-correcting codes (ECC) are a sequence of numbers generated by
specific algorithms for detecting and removing errors in data that has
been transmitted over noisy channels. Error correcting codes ascertain
the exact number of bits that has been corrupted and the location of the
corrupted bits, within the limitations in algorithm.

Error Correction can be handled in two ways:

o Backward error correction If the receiver detects an error in the

incoming frame, it requests the sender to retransmit the frame. It is
a relatively simple technique. But it can be efficiently used only
where retransmitting is not expensive as in fiber optics and the
time for retransmission is low relative to the requirements of the
application.
o Forward error correction: If the receiver detects some error in the
incoming frame, it executes error-correcting code that generates
the actual frame. This saves bandwidth required for retransmission.
It is inevitable in real-time systems. However, if there are too many
errors, the frames need to be retransmitted.

The four main error correction codes are

 Hamming Codes
 Binary Convolution Code
 Reed – Solomon Code not in syllabus
 Low-Density Parity-Check Code
Hamming Code
Hamming code is a block code that is capable of detecting up to two
simultaneous bit errors and correcting single-bit errors. It was
developed by R.W. Hamming for error correction.
In this coding method, the source encodes the message by inserting
redundant bits within the message. These redundant bits are extra bits
that are generated and inserted at specific positions in the message
itself to enable error detection and correction. When the destination
receives this message, it performs recalculations to detect errors and
find the bit position that has error.

NB: 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

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.

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.

Let's understand the concept of Hamming code through an

example:

Suppose the original data is 1010 which is to be sent.

SENDER SIDE----------------------------------------------------------------

1. Determining the number of the 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;

2. Determining the position of the redundant bits

The number of redundant bits is 3. The three bits are represented

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

The position of r1 = 1
The position of r2 = 2
The position of r4 = 4

Representation of Data on the addition of parity bits:

3. Determining the Parity bits

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.

Determining 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.

Determining 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.

Data transferred is given below:

-------------------------------------------------------------------------------
Suppose the 4th bit is changed from 0 to 1 at the receiving end, then
parity bits are recalculated.

RECIEVER’s SIDE------------------------------------------------------------
R1 bit

The bit positions of the r1 bit are 1,3,5,7

We observe from the above 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 above 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.

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.

o 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.

-------------------------------------------------------------------------------