Error Detection in Computer Networks



Error is a condition when the receiver’s information does not match the sender’s. Digital
signals suffer from noise during transmission that can introduce errors in the binary bits
traveling from sender to receiver. That means a 0 bit may change to 1 or a 1 bit may change
to 0.
Data (Implemented either at the Data link layer or Transport Layer of the OSI Model) may
get scrambled by noise or get corrupted whenever a message is transmitted. To prevent such
errors, error-detection codes are added as extra data to digital messages. This helps in
detecting any errors that may have occurred during message transmission.
Types of Errors
Single-Bit Error
A single-bit error refers to a type of data transmission error that occurs when one bit (i.e., a
single binary digit) of a transmitted data unit is altered during transmission, resulting in an
incorrect or corrupted data unit.

Single-Bit Error

Multiple-Bit Error
A multiple-bit error is an error type that arises when more than one bit in a data
transmission is affected. Although multiple-bit errors are relatively rare when compared to
single-bit errors, they can still occur, particularly in high-noise or high-interference digital
environments.
 Multiple-Bit Error

Burst Error
When several consecutive bits are flipped mistakenly in digital transmission, it creates a
burst error. This error causes a sequence of consecutive incorrect values.

Burst Error

Error Detection Methods

To detect errors, a common technique is to introduce redundancy bits that provide
additional information. Various techniques for error detection include:
 Simple Parity Check
 Two-Dimensional Parity Check
 Checksum
 Cyclic Redundancy Check (CRC)
Simple Parity Check
Simple-bit parity is a simple error detection method that involves adding an extra bit to a
data transmission. It works as:
 1 is added to the block if it contains an odd number of 1’s, and
 0 is added if it contains an even number of 1’s
This scheme makes the total number of 1’s even, that is why it is called even
parity checking.
Advantages of Simple Parity Check
 Simple parity check can detect all single bit error.
 Simple parity check can detect an odd number of errors.
 Implementation: Simple Parity Check is easy to implement in both hardware and
software.
 Minimal Extra Data: Only one additional bit (the parity bit) is added per data unit
(e.g., per byte).
 Fast Error Detection: The process of calculating and checking the parity bit is quick,
which allows for rapid error detection without significant delay in data processing or
communication.
 Single-Bit Error Detection: It can effectively detect single-bit errors within a data
unit, providing a basic level of error detection for relatively low-error environments.
Disadvantages of Simple Parity Check
 Single Parity check is not able to detect even no. of bit error.
 For example, the Data to be transmitted is 101010. Codeword transmitted to the
receiver is 1010101 (we have used even parity).
Let’s assume that during transmission, two of the bits of code word flipped to
1111101.
On receiving the code word, the receiver finds the no. of ones to be even and hence no
error, which is a wrong assumption.
Two-Dimensional Parity Check
Two-dimensional Parity check bits are calculated for each row, which is equivalent to a
simple parity check bit. Parity check bits are also calculated for all columns, then both are
sent along with the data. At the receiving end, these are compared with the parity bits
calculated on the received data.
Advantages of Two-Dimensional Parity Check
 Two-Dimensional Parity Check can detect and correct all single bit error.
 Two-Dimensional Parity Check can detect two or three bit error that occur any where
in the matrix.
Disadvantages of Two-Dimensional Parity Check
 Two-Dimensional Parity Check can not correct two or three bit error. It can only
detect two or three bit error.
 If we have a error in the parity bit then this scheme will not work.
Checksum
Checksum error detection is a method used to identify errors in transmitted data. The
process involves dividing the data into equally sized segments and using a 1’s
complement to calculate the sum of these segments. The calculated sum is then sent along
with the data to the receiver. At the receiver’s end, the same process is repeated and if all
zeroes are obtained in the sum, it means that the data is correct.
Checksum – Operation at Sender’s Side
 Firstly, the data is divided into k segments each of m bits.
 On the sender’s end, the segments are added using 1’s complement arithmetic to get
the sum. The sum is complemented to get the checksum.
 The checksum segment is sent along with the data segments.
Checksum – Operation at Receiver’s Side
 At the receiver’s end, all received segments are added using 1’s complement
arithmetic to get the sum. The sum is complemented.
 If the result is zero, the received data is accepted; otherwise discarded.
Cyclic Redundancy Check (CRC)
 Unlike the checksum scheme, which is based on addition, CRC is based on binary
division.
 In CRC, a sequence of redundant bits, called cyclic redundancy check bits, are
appended to the end of the data unit so that the resulting data unit becomes exactly
divisible by a second, predetermined binary number.
 At the destination, the incoming data unit is divided by the same number. If at this
step there is no remainder, the data unit is assumed to be correct and is therefore
accepted.
 A remainder indicates that the data unit has been damaged in transit and therefore
must be rejected.
 C
RC Working
We have given dataword of length n and divisor of length k.
Step 1: Append (k-1) zero’s to the original message
Step 2: Perform modulo 2 division
Step 3: Remainder of division = CRC
Step 4: Code word = Data with append k-1 zero’s + CRC
Note:
 CRC must be k-1 bits
 Length of Code word = n+k-1 bits
Example: Let’s data to be send is 1010000 and divisor in the form of polynomial is x3+1.
CRC method discussed below.
Error Detection Methods
Following are the error detection methods or techniques of error detection in networking.
1. VRC Method 2. LRC method 3. CRC method 4. Checksum method
Parity check or vertical redundancy check (VRC) method
In this error detection technique, a redundant bit called parity bit is appended to every data
unit so that total number of 1's in the unit (including parity bit) becomes even. The system
now transmits entire extended unit across the network link. At the receiver, all eight received
bits are checked through even parity checking function. If it counts even 1's data unit passes.
If it counts odd number of 1's, it means error has been introduced in the data somewhere.
Hence receiver rejects the whole data unit. Similar way odd parity VRC can also be
implemented. In this method, total number of 1's in should be odd before transmission.
Longitudinal Redundancy Check (LRC) method

In this error detection method, a block of bits are organized in a table (of rows and columns).
For example, instead of sending block of 32 bits, first it is organized into four rows and eight
columns. Then parity bits for each column is calculated and new row of eight parity bits is
formed. These eight parity bits are appended to original data before transmission.
CRC Error Detection and Correction Example
Following figure-2 depicts CRC addition at transmitter end. CRC is calculated based on
received block and compared with CRC appended by transmitter. When calculated CRC and
original CRC is equal, frame is considered to be error free. When calculated CRC and
original CRC is not equal, frame is said to be erroneous.

As shown in the figure, k bits are passed to the encoder block to generate parity bits. This
parity bits are added to input data bits and are transmitted as n bits. Hence n-k are parity bits.
This happens at the transmitter.
As shown in the figure at the receiver, parity bits along with data bits of total length n bits are
passed to the encoder. From the data part crc is again computed and will be compared with
the received CRC bits and based on this data is corrupted or not is decided. This process is
called error detection and correction.
Checksum method
There are two modules in this error detection method viz. checksum generator and checksum
checker. In the transmitter, checksum generator subdivides data unit into equal segments of n
bits (usually 16). These segments are added together using one's complement arithmatic in
such a way that total is also n bits long. The total (i.e. sum) is then complemented and
appended to the end of the original data unit as redundancy bits, called checksum field. The
extended data unit is transmitted across the network. So it sum of data segment is equal to T,
checksum will be -T.

The receiver subdivides the data unit as above and adds all segments together and
complements the result. If the extended data unit is intact, the total value found by adding all
data segments and checksum field should be zero. If the result is not zero, the packet contains
error and receiver rejects the packet.