CPE 313 - DATA AND DIGITAL COMMUNICATION

FINAL PROJECT
Group 5|Error Detection

Gerona, Eyra Franzine

Muñoz, Jian Jayne
Pandinuela, Paul Bradley
Reyes, Mark Jaycee
Sarucam, Jan Ira

ERROR DETECTION
Error control mechanism may involve two possible ways:
- Error detection
 - Error correction

After completing this lesson, the student will be capable of

● Understand error transmission
● Know the types of error
● Understand error detection
● Know the various error detection techniques

Error Detection
- Data is transmitted in the network.
- The data can be corrupted during transmission
- Transmission Error
- For Reliable Communication, error must be detected and corrected
- Error detection and correction are implemented either at the data link layer or transport layer of
the OSI model.
Error Detection means it’s the job of the receiver to detect the error, if it is there, it will discard it
otherwise it will accept it. Error detection is very simple, just accept or reject.

Types of Error
1. Bit Error
2. Burst Error

Bit Error
In a bit error, only one bit is going to be changed so it is also known as single bit error. In a single bit
error, only 1 bit in the data unit has been changed.

Burst Error
In burst error, 2 or more bits in the data unit have changed.
How to detect the errors?
- Error detection means to decide whether the received data is correct or not without having a copy
of the original message.
● The receiver normally will not be having a copy of the original message because the
original message itself has been corrupted by transmission error.
● Now how to detect these errors? When we send only the original message, it’s very
difficult for the receiver to understand or to know whether there’s an error or not. So,
with the message some additional information has to be sent by the sender. So, this
additional information will help the receiver to understand or to find out whether there is
an error or not in the data that is being transmitted.
- To detect or correct errors, we need to send some extra bits with the data.
● The extra bits are called redundant bits.

Redundancy
 - In a redundancy check, the sender gives the data to the generating function or algorithm and this
algorithm generates a code which is called the redundant code or redundant bits, or redundancy
check. And this information is appended with the message that has to be sent.

- Redundancy check or the redundancy bits are added with the message. Added means just
appended. And the whole information is now sent to the receiver.

- The message going into the receiver has two parts in the message, one is the original message and
the other one is redundant bits. Message sent to the receiver will go through a checking function
if it is matched to the original data bits it will accept the message if it is not it will reject.

- Checking function is also an algorithm that calculates redundant bits, it compares the redundant
bits with the redundant bits that was sent by the receiver again if both are matching and the
receiver understands that there are no errors in data transmission. So, it accepts it otherwise the
receiver will reject it.

Error Correction (Briefly)

Error correction is a tedious job. The receiver has to correct the errors.
It can be handled in two ways:
1. Receiver can have the sender retransmit the entire data unit.
2. The receiver can use an error-correcting code, which automatically corrects certain errors.
Error Detection and Correction needs redundancy.

Error Detection Techniques or Methods

Four Types of redundancy checks are used in the data communications. They are:
1. Vertical Redundancy Check (VRC)
2. Longitudinal Redundancy Check (LRC)
3. Checksum
4. Cyclic Redundancy Check (CRC)

Errors in the received frames are detected by means of Parity Check and Cyclic Redundancy Check
(CRC). In both cases, a few extra bits are sent along with actual data to confirm that bits received at the
other end are the same as they were sent. If the counter-check at receiver’ end fails, the bits are
considered corrupted.

1. Vertical Redundancy Check (VRC)

- It is also called as parity check
Suppose, if this is the data that we would like to send to the receiver. In other words let this be the data
sender generates.
And this is obviously the data that is generated by the sender. Now this data is given to the even parity
generator. An even parity generator accepts this data and generates a parity bit. This even parity
generator checks for the number of ones that are there in the data.

Even Parity
The receiver simply counts the number of 1s in a frame. If the count of 1s is even and even parity is used,
the frame is considered to be not-corrupted and is accepted. If the count of 1s is odd and odd parity is
used, the frame is still not corrupted.
If a single bit flips in transit, the receiver can detect it by counting the number of 1s. But when more than
one bit is erro neous, then it is very hard for the receiver to detect the error.

Parity Check
One extra bit is sent along with the original bits to make a number of 1s either even in case of even parity,
or odd in case of odd parity.

The sender while creating a frame counts the number of 1s in it. For example, if parity is used and
number of 1s is even then one bit with value 0 is added. This way the number of 1s remains even. If the
number of 1s is odd, to make it even a bit with value 1 is added.

Performance of VRC
It can detect single bit errors and it can detect burst only if the number of errors is odd.

2. Longitudinal Redundancy Check

- In the longitudinal redundancy method, a BLOCK of bits is arranged in a table format (in rows
and columns) and we will calculate the parity bit for each column separately. The set of these
parity bits are also sent along with our original data bits. Longitudinal redundancy check is a bit
by bit parity computation, as we calculate the parity of each column individually. This method
 can easily detect burst errors and single bit errors and it fails to detect the 2 bit errors occurring in
the same vertical slice.

3. Check Sum
- Checksums are similar to parity bits except, the number of bits in the sums is larger than parity
and the result is always constrained to be zero. That means if the checksum is zero, an error is
detected. A checksum of a message is an arithmetic sum of code words of a certain length. The
sum is stated by means of 1’s complement and stored or transferred as a code extension of the
actual code word. At the receiver a new checksum is calculated by receiving the bit sequence
from the transmitter.

The checksum method includes parity bits, check digits and longitudinal redundancy check
(LRC). For example, if we have to transfer and detect errors for a long data sequence (also called as Data
string) then we divide that into shorter words and we can store the data with a word of same width. For
each incoming bit we will add them to the already stored data. At every instance, the newly added word is
called “Checksum”.

At the receiver side, the received bits checksum is the same as that of the transmitter's, there is no
error found.

We can also find the checksum by adding all data bits. For example, if we have 4 bytes of data as
25h, 62h, 3fh, 52h.

Then, adding all bytes we get 118H

Dropping the carry Nibble, we get 18H

Find the 2’s complement of the nibble, i.e. E8H

This is the checksum of the transmitted 4 bits of data.

 At the receiver side, to check whether the data is received without error or not, just add the
checksum to the actual data bits (we will get 200H). By dropping the carry nibble, we get 00H. This
means the checksum is constrained to zero. So, there is no error in the data.

In general, there are 5 types of checksum methods like

● Integer addition checksum

● One’s complement checksum
● Fletcher Checksum
● Adler Checksum
● ATN Checksum (AN/466)

Example:

As of now we discussed the error detection codes. But to receive the exact and perfect data
sequence without any errors, is not done enough only by detecting the errors occurred in the data. But
also, we need to correct the data by eliminating the presence of errors, if any. To do this we use some
other codes.

4. Cyclic Redundancy Check (CRC)

 - CRC is a different approach to detect if the received frame contains valid data. This technique
involves binary division of the data bits being sent. The divisor is generated using polynomials.
The sender performs a division operation on the bits being sent and calculates the remainder.
Before sending the actual bits, the sender adds the remainder at the end of the actual bits. Actual
data bits plus the remainder is called a codeword. The sender transmits data bits as codewords

At the other end, the receiver performs division operation on codewords using the same CRC
divisor. If the remainder contains all zeros the data bits are accepted, otherwise it is considered as
there some data corruption occurred in transit.

References:
Neso Academy. https://www.youtube.com/watch?v=1A_NcXxdoCc
Electronics Hub. https://www.electronicshub.org/error-correction-and-detection-codes/?
fbclid=IwAR1Qn1UHnO8wk-kkA8lkl2qh5UkpxnAc_uxPvMVkW7X3dtuz7LqBfkDNBUk
Tutorials point. https://www.tutorialspoint.com/data_communication_computer_network/
error_detection_and_correction.htm