Micro-Project Proposal Micro Project for information about

ERROR DETECTION AND CORRECTION

❖ Aims of the Micro-Project

Projects focused on error correction and detection can be incredibly impactful,
especially in fields like computing, communication, and engineering. Here are a
few common aims such projects might target:

1. Enhancing System Reliability: Design techniques to identify and correct

errors in systems, ensuring they remain functional even in challenging
conditions.
2. Improving Data Integrity: Protect data from corruption during transmission
or storage and develop methods to recover corrupted data.
3. Optimizing Algorithms: Build algorithms for efficient error detection and
correction that reduce processing time and resource consumption.
4. Developing Robust Protocols: Innovate communication protocols to prevent
errors in data exchanges across networks.
5. Testing Fault Tolerance: Explore ways to measure and improve a system's
capacity to handle faults without compromising performance.
6. Application-Specific Solutions: Tailor error correction methods for specialized
fields like healthcare, finance, or space exploration, where precision is critical.

P a g e |1
 ❖ Course Outcomes Addressed
Error correction and detection in computer networks and data communication
often address the following course outcomes:
1. Understanding Error Types: Students learn about single-bit errors, burst
errors, and their impact on data integrity.
2. Mastering Detection Techniques: Techniques like parity checks and cyclic
redundancy checks (CRC) are explored to identify errors during data
transmission.
3. Implementing Correction Methods: Methods such as Hamming codes
and forward error correction are taught to recover corrupted data.
4. Analyzing Protocols: Students study protocols that ensure reliable
communication, such as TCP/IP and OSI models.
5. Designing Efficient Systems: The course emphasizes designing systems
that minimize errors and optimize data transmission

P a g e |2
 ❖ Proposed Methodology
A proposed methodology for error detection and correction in computer
networks and data communication could follow these key steps:
1. Problem Identification
- Define the specific challenges in error detection and correction, such as
reducing latency, minimizing false positives, or improving data reliability.
2. Study of Existing Techniques
- Review current error detection and correction methods, like parity checks,
CRC, Hamming codes, and forward error correction.
- Identify limitations and areas for improvement.
3. System Design
- Develop a conceptual framework or algorithm for a new or improved error
handling approach.
- Determine the specific parameters, such as the type of errors to target,
computational efficiency, and scalability.
4. lmplementation
- Build prototypes or simulations to test the proposed method in a controlled
environment.
- Use programming languages like Python, C++, or MATLAB to develop
algorithms or tools.
5. Performance Testing
- Evaluate the proposed methodology using key metrics such as accuracy,
speed, computational cost, and robustness against various types of errors.
- Compare results with existing methods.

P a g e |3
 INDEX
Sr.No Chapter name Page No.

1. Synopsis 5

2. Abstract 6

3. Introduction 7

4. Error 8

5. Technic for Error Detection(repetition code, 10

Parity bit,CRC)

6. Technic for Error Correction(ARQ, Hamming 21

code)

7. Conclusion 23

8. referance 24

P a g e |4
 1.Synopsis
1.1Project Title
Error Correction and Detection
1.2. Project Option
None
1.3. Internal Guide
Prof. Thorat.S.K
1.4. Problem Statement
Error Correction and Detection

P a g e |5
 2.Abstract
Error detection and correction are critical components in
ensuring the reliability and accuracy of data transmission in communication
systems and networks. As data is transmitted over various channels, it is
susceptible to corruption due to noise, interference, or signal degradation,
leading to transmission errors. To mitigate these issues, error detection and
correction techniques are employed to ensure that data is accurately
received, even in the presence of errors.
This paper explores various error detection and correction
methods, including parity bits, cyclic redundancy check (CRC), Hamming
code, and Reed-Solomon code. Additionally, the paper examines the
trade-offs between error detection and correction mechanisms in terms
of computational complexity, bandwidth overhead, and system
performance. The implementation of these techniques plays a crucial
role in maintaining data integrity and minimizing retransmissions,
thereby optimizing network efficiency. With the growing demand for
high-speed communication and reliable networks, error detection and
correction continue to be fundamental in advancing modern data
communication systems.

P a g e |6
 3.INTRODUCTION
In modern data communication and networking, the integrity of
transmitted data is essential for ensuring the reliability of systems that rely on
the accurate exchange of information. However, data transmission is inherently
prone to errors due to various factors such as noise, signal attenuation, and
interference. These errors can cause the loss of crucial information, leading to
significant issues in applications ranging from internet browsing to financial
transactions and real-time communications.
Error detection and correction mechanisms are designed to address these
challenges by enabling the identification and correction of errors in the
transmitted data. Error detection techniques, such as parity checks and cyclic
redundancy checks (CRC), help identify the presence of errors, while error
correction methods like Hamming codes and Reed-Solomon codes ensure that
corrupted data can be reconstructed or corrected without requiring a
retransmission. These techniques are pivotal in ensuring data integrity,
minimizing the need for retransmissions, and optimizing overall network
performance.
The importance of error correction and detection has grown significantly
with the proliferation of high-speed networks, cloud computing, and the
increasing reliance on data-driven applications. As networks become more
complex and data volumes continue to grow, efficient error detection and
correction techniques have become an essential part of communication
protocols, allowing for faster, more reliable, and more secure data exchange.
This paper provides an in-depth examination of the different error detection
and correction methods commonly used in data communication systems. It
also discusses their applications, strengths, limitations, and the role they play in
improving the overall performance of communication networks. Understanding
these techniques is crucial for designing systems capable of delivering high-
quality, error-free communication in today’s digital world.

P a g e |7
 ERROR DETECTION AND CORRECTION

Error:
In data communication and networking, an error refers to any discrepancy or
alteration that occurs in the transmitted data, causing the received data to
differ from the original, intended message. Errors can arise due to various
factors, including noise, interference, or signal degradation during
transmission. These errors can lead to data corruption or loss, affecting the
integrity and reliability of the communication.

Types of error:
1.Single bit error
2.Burst error
1.Single bit error: A single-bit error occurs when a single bit of data is
flipped during transmission, either from 0 to 1 or from 1 to 0. It’s the
simplest type of error and typically happens due to noise or
interference that disturbs only one bit in a data stream.
Example:

• Original Data: 10110011

• Received Data (with a single-bit error): 10110111
• In this example, the 4th bit is flipped from 0 to 1, causing the
error.

P a g e |8
2. Burst Error: A burst error occurs when a contiguous sequence of
bits in the data stream is altered during transmission. Unlike a
singlebit error, where only one bit is affected, a burst error affects
multiple consecutive bits at once. Burst errors are more common in
real-world communication channels due to factors like signal
interference, reflections, and transmission delays.
Example:

• Original Data: 00000000000

• Received Data (with a burst error affecting 4 bits):
00000010001
• Here, the seventh, eleventh bits have been altered in a burst.

Burst errors are a common occurrence in data transmission,

especially when there is significant interference or degradation of the
signal over time. These errors are more complex than single-bit
errors and require more sophisticated error detection and correction
techniques, such as CRC to ensure data integrity.

P a g e |9
Error Detection
Error detection is a fundamental concept in data communication, ensuring that
the data transmitted across a network or communication channel remains
intact and free of errors. It involves techniques and algorithms used to identify
errors that occur during the transmission or processing of data. Understanding
error detection in-depth involves exploring various methods, protocols, and
tools used to identify and handle errors in data transmission.
Why Error Detection is Needed
• Data Integrity: Errors can occur due to noise, signal degradation,
interference, or transmission issues. Without error detection, corrupted
data could be accepted as valid, leading to faulty information being
processed.
• Reliability: In network communications, error detection helps ensure
that the data received by the recipient is the same as the data sent by
the sender.
• Prevention of Data Loss: When errors are detected, corrective actions
can be taken to request retransmission of data, ensuring data is delivered
reliably.

Error detection is a critical aspect of data communication that helps maintain

data integrity and system reliability. There are various techniques, ranging from
simple methods like parity checks to complex methods like ReedSolomon
codes, each with strengths and weaknesses depending on the application. By
using the appropriate error detection technique, data communication systems
can ensure that errors are identified and addressed promptly, maintaining high-
quality and reliable communication.

P a g e | 10
Technic for Error detection
 Repetition Code
A Repetition Code is a simple error detection and correction technique used in
communication systems to protect data against errors during transmission. The
basic idea of a repetition code is to send the same bit (or group of bits)
multiple times to ensure that the receiver can correctly identify the original
value, even if some bits are corrupted during transmission.

How Repetition Code Works

In a repetition code, each bit in the original message is repeated multiple times
(typically three or more times) before being transmitted over the
communication channel. The receiver, upon receiving the repeated bits, can
use a majority vote to determine the correct value of the bit.
For example, if the sender sends a bit 1, the repetition code would transmit it
multiple times as 111. The receiver would then perform a majority vote on the
received bits to decide whether the transmitted bit was 1 or 0.
Example
Let’s assume that the original message is a single bit 1, and we use a 3-bit
repetition code (i.e., each bit is repeated 3 times):
• Original message: 1
• Sent message (with 3-bit repetition): 111 At the receiver’s side:
• If the received message is 111, the receiver correctly detects 1 by using
the majority vote (since 2 out of 3 bits are 1).
• If the received message is 101, the receiver still detects 1 by majority
vote (since 2 out of 3 bits are 1).
• If the received message is 000, the receiver detects 0 by majority vote
(since 2 out of 3 bits are 0).
• If the received message is 010, the receiver would detect 0 by majority
vote (since 2 out of 3 bits are 0).

P a g e | 11
Key Properties of Repetition Code
1. Error Detection and Correction: The repetition code can correct errors
when there are fewer errors than half the number of repetitions. For
instance, in a 3-bit repetition code, if 2 bits are received correctly, the
third bit can be corrected using the majority rule. If more than half the
bits are corrupted, the receiver might not be able to recover the original
message accurately.

2. Simplicity: Repetition codes are easy to implement, making them useful

in scenarios where simplicity and low overhead are needed.

3. Error Handling: The primary advantage of the repetition code is that it

can correct single-bit errors. If one bit in the transmission is flipped due
to noise or interference, the receiver can still recover the original bit
using the majority voting method.
Example of Repetition Code in Action Scenario: Sending the bit 1 • Original
Data: 1 • Transmission (with repetition): 111
Now, let’s simulate different cases where errors occur during transmission:

1. No Error (received as 111):

o Received Data: 111 o Majority Voting: 2 out of 3 bits are 1, so
the receiver detects 1.
o Result: Correct detection, no error.

2. One-bit error (received as 101):

o Received Data: 101
o Majority Voting: 2 out of 3 bits are 1, so the receiver detects 1.
o Result: Correct detection, single-bit error is corrected.

3. Two-bit error (received as 011):

o Received Data: 011 o Majority Voting: 1 out of 3 bits are 1, so
the receiver detects 0.

P a g e | 12
 o Result: Incorrect detection, more than one bit was corrupted, so
the receiver cannot correct the error.

4. Three-bit error (received as 000):

o Received Data: 000
o Majority Voting: 3 out of 3 bits are 0, so the receiver detects 0.
o Result: Incorrect detection, three bits were corrupted, and the
error cannot be corrected.
Advantages of Repetition Code

1. Error Correction: Repetition codes are simple and effective for error
correction, especially in low-error environments.

2. Simplicity and Ease of Implementation: It is easy to implement,

requiring only repetition of bits and a majority vote at the receiver side.

3. Noise Tolerance: Repetition codes work well in situations with occasional

bit flips due to noise or interference.
Disadvantages of Repetition Code

1. Inefficiency: Repetition codes increase the number of transmitted bits,

leading to overhead. For example, a 3-bit repetition code requires 3
times more bandwidth for every bit of data.

2. Limited Error Correction: While repetition codes can correct single-bit

errors, they cannot correct multiple errors that affect more than half of
the bits being transmitted. In such cases, the majority vote may lead to
an incorrect decision.

3. Resource Consumption: Repeating bits increases transmission time and

resource consumption, which can be inefficient in high-bandwidth
applications.

P a g e | 13
  Parity Bit:
A parity bit is a simple error detection mechanism used in data communication
to ensure that data has been transmitted correctly. It involves adding an extra
bit (called the parity bit) to a data unit, such as a byte, which helps in detecting
errors that may have occurred during transmission.
The basic idea of a parity bit is to make the total number of 1's in the data
(including the parity bit) either even or odd, depending on the type of parity
used.

Types of Parity
1. Even Parity:
o In even parity, the parity bit is set so that the total number of 1's in
the data (including the parity bit) is even.
o Example: For the data 1101011 (which has 5 ones), the parity bit
would be set to 1 so that the total number of 1's becomes 6
(even). 2. Odd Parity:
o In odd parity, the parity bit is set so that the total number of 1's in
the data (including the parity bit) is odd.
o Example: For the data 1101011 (which has 5 ones), the parity bit
would be set to 0 so that the total number of 1's remains 5 (odd).

How the Parity Bit Works

Let’s walk through an example for each type of parity:
Example 1: Even Parity
• Original data: 1101011 o The number of 1s in this data is 5
(which is odd).
o To make it even, we need to add a 1 as the parity bit.

• Transmitted data (with even parity): 11010111 o Now the total

number of 1s is 6 (which is even).
At the receiver's side, the system checks if the number of 1s (including
the parity bit) is even

• If the number is even, the receiver assumes no error occurred.

P a g e | 14
 • If the number is odd, an error is detected (i.e., one or more bits
have been flipped).
Example 2:
Odd Parity
• Original data: 1101011 o The number of 1s in this data is 5 (which is
already odd).
o Since we are using odd parity, we do not need to add a parity bit.
• Transmitted data (with odd parity): 1101011 o The total number of
1s remains 5 (which is odd).
At the receiver's side, the system checks if the number of 1s (including
the parity bit) is odd:
• If the number is odd, the receiver assumes no error occurred.
• If the number is even, an error is detected.

Error Detection with Parity Bit

The parity bit is primarily used for detecting single-bit errors. Here’s how it
works:

1. No Error: If the transmitted data has the correct number of 1’s (even or
odd, based on the type of parity used), the receiver assumes the data is
correct.
2. Single-Bit Error: If a bit is flipped during transmission (due to noise or
interference), the parity will no longer match the expected even or odd
count. In this case, the receiver can detect that an error has occurred.
3. Burst Error (Multiple Bit Errors): Parity can not detect burst errors (errors
affecting multiple bits), because it only checks the overall count of 1's,
not the specific positions of the errors.
Example: Error Detection

Let’s say we use even parity for error detection:

• Original Data: 101101 (there are 4 ones, which is even).
• Parity Bit: Since we are using even parity, we add a 0 to make the total
count of 1's even

P a g e | 15
 At the receiver's side, if the received data is:
1. Correct data: 1011010 (still even number of 1's), the receiver assumes
there is no error.
2. Single-bit error: 1011110 (now the number of 1's is 5, which is odd), the
receiver detects the error.

Advantages of Parity Bit

1. Simplicity: Parity is easy to compute and implement, making it a
costeffective and straightforward method for detecting errors.
2. Low Overhead: Only one additional bit (the parity bit) is needed for error
detection.
3. Efficient for Low Error Rates: Parity is suitable for detecting errors in
lowerror-rate systems, where single-bit errors are more likely than burst
errors.

Limitations of Parity Bit

1. Limited Error Detection: Parity only detects single-bit errors. It cannot
detect multiple-bit errors or burst errors.
2. No Error Correction: Parity can only detect errors but cannot correct
them. More advanced methods (such as Hamming code or CRC) are
required for error correction.

3. Vulnerability to Burst Errors: Since it only checks the parity of the entire
block of data, burst errors (where multiple consecutive bits are flipped)
can go undetected.

P a g e | 16
  CRC(Cyclic redundancy chain)
A Cyclic Redundancy Check (CRC) is a powerful error-detection technique used
in computer networks and storage devices to detect accidental changes to raw
data. It is widely used due to its ability to detect burst errors effectively. CRC is
especially useful for ensuring data integrity in high-performance systems, such
as Ethernet, CDs/DVDs, and file systems.
How CRC Works
CRC uses polynomial division to detect errors. The concept involves treating
the data as a large polynomial and performing polynomial division using a fixed
divisor (also called the generator polynomial or CRC polynomial). The result of
this division is a remainder, which is appended to the original data as the CRC
checksum.

1. Data Representation: The data to be sent is represented as a binary

string.
2. Divisor (CRC Polynomial): A predefined binary polynomial (divisor) is
used to divide the data.
3. Division Process: The data is divided by the divisor using binary long
division (XOR operations), which does not carry over any values like
traditional division.
4. Remainder: The remainder (which is usually smaller than the divisor) is
the CRC checksum.
5. Appending the CRC: The remainder is appended to the original data as
the CRC value (the checksum).
6. Transmission: The data, along with the CRC, is transmitted.
7. Verification: Upon receiving the data, the receiver divides the received
data (which includes the CRC) by the same divisor. If the remainder is
zero, the data is considered error-free. If the remainder is non-zero, an
error is detected.

P a g e | 17
 Key Concepts of CRC
• Generator Polynomial: The divisor used in the CRC process is a fixed
binary number known as the generator polynomial. The polynomial
defines the error-detection capability of the CRC.
• Data Polynomial: The binary string representing the data is treated as a
polynomial in the CRC process.
• Remainder (CRC checksum): The result of the polynomial division
process. This is appended to the data and transmitted.
• Receiver Check: The receiver performs the same polynomial division. If
the remainder is zero, no error is detected. If the remainder is non-zero,
an error is detected.

Example of CRC Calculation

Let’s walk through a basic example using CRC-8 (a common 8-bit CRC) with the
following polynomial divisor:
• Divisor: 100000111 (this is often written as x^8 + x^2 + x + 1 in
polynomial form).
Step 1: Prepare the Data
Let’s say we want to send the data 1101011011 (which is 10 bits long).
• Data (in binary): 1101011011
• Add zeros:
The length of the CRC divisor (in this case 8 bits) dictates that we add 8 zeros
to the end of the data to account for the CRC.
Thus, we add 8 zeros to the data:
Copy
1101011011 → 110101101100000000

P a g e | 18
Step 2: Polynomial Division (Binary Division)
Now, we perform binary long division using the divisor 100000111 on the data
110101101100000000. This division involves XORing the data with the divisor
at each step, and the result is the remainder (CRC checksum).
After performing the division process, you get a remainder of:
CRC (remainder) = 10111000
Step 3: Append CRC to the Data
The remainder is the CRC checksum. You append this checksum to the original
data, and the final transmitted data is:
Transmitted data = 1101011011 + 10111000
= 110101101110111000
Step 4: Receiver's Check
When the receiver receives the data 110101101110111000, it performs the
same division with the same divisor (100000111). If the division result is zero,
no error occurred; otherwise, the receiver detects an error.
Properties of CRC

1. Error Detection: CRC is capable of detecting common transmission errors

such as:
o Single-bit errors: Errors where only one bit is corrupted.

o Burst errors: Errors where multiple consecutive bits are

corrupted.
2. Error Detection Power: The larger the divisor polynomial (i.e., the CRC
size), the more powerful the CRC is in detecting errors.,
3. Efficiency: CRC is very efficient and fast, as it uses XOR operations (which
are computationally inexpensive) instead of more complex arithmetic.
4. Polynomial Choice: The choice of the generator polynomial significantly
impacts the error detection capabilities of the CRC. A well-chosen
polynomial can detect a wide variety of common error patterns in data
transmission.

P a g e | 19
Case 1: No Error
Sent data: 101100110111
CRC checksum: 1001010001101010
Received data: 1011001101111001010001101010
Check: The receiver performs the same division process and finds that the
remainder is 0, indicating no error.
Case 2: Error Detected
Sent data: 101100110111
CRC checksum: 1001010001101010
Received data (corrupted): 1011001100111001010001101010
Check: The receiver performs the division and finds a non-zero remainder,
indicating that an error occurred during transmission.

Advantages of CRC
1. High Error Detection Power: CRC can detect a wide range of errors,
including burst errors, which makes it highly reliable.
2. Efficiency: It is computationally efficient, requiring only XOR operations
to detect errors.
3. Flexibility: The size of the CRC (8, 16, 32, etc.) can be adjusted depending
on the requirements for error detection.
4. Widely Used: CRC is widely implemented in communication protocols
(like Ethernet and Bluetooth) and file formats (like ZIP and PNG).

Limitations of CRC
1. Cannot Correct Errors: CRC can only detect errors, but it cannot correct
them. If errors are detected, the system must request a retransmission.
2. Requires Fixed Divisor: The error detection capability is largely
determined by the choice of the generator polynomial. A poor choice of
polynomial can limit the effectiveness of CRC.

P a g e | 20
 ERROR CORRECTION
Automatic Repeat request (ARQ)
ARQ (Automatic Repeat request) is an error control protocol for reliable
data communication in computer networks. It ensures that data is transmitted
accurately from the sender to the receiver by detecting errors and requesting
retransmission of corrupted or lost data packets. ARQ is widely used in
communication systems to guarantee the reliability of data transmission,
particularly in noisy environments.

Key Concepts of ARQ

ARQ is based on the principle of error detection and retransmission. When the
receiver detects an error in a packet or fails to receive it, it sends a negative
acknowledgment (NAK) or simply requests a retransmission. If the data is
received correctly, the receiver sends an acknowledgment (ACK).

The main elements of ARQ are:

1. Acknowledgments (ACK): When a packet is correctly received, the
receiver sends an ACK to the sender, indicating that the transmission was
successful.
2. Negative Acknowledgments (NAK): When a packet is corrupted or
missing, the receiver sends a NAK or a request for retransmission.
3. Timeout Mechanism: If the sender does not receive an acknowledgment
within a specified timeout period, it retransmits the data packet.

Advantages:
• Simple to implement and understand.
• Guarantees reliable communication, even in noisy channels.

P a g e | 21
Hamming Code
The Hamming code is an error-correcting code that can detect and correct
single-bit errors in data transmission. It was developed by Richard Hamming in
1950 and is one of the most widely used methods for error correction in digital
communication systems. The Hamming code is an example of a block code and
works by adding redundant bits (called parity bits) to the data, allowing the
receiver to detect and correct errors.
Key Concepts of Hamming Code
• Parity Bits: These extra bits are inserted into the data at specific positions
to check the parity (even or odd) of the data. The parity bits help in both
error detection and correction.
• Error Detection and Correction: The Hamming code can detect and
correct single-bit errors and detect two-bit errors.
• Redundant Bits: The number of parity bits (redundant bits) required
depends on the number of data bits. The general rule is that for k data
bits, the number of parity bits r should satisfy the inequality:
2r≥k+r+12^r \ k + r + 12r≥k+r+1where r is the number of parity bits and k
is the number of data bits.

Advantages of Hamming Code

• Error Correction: The Hamming code can detect and correct single-bit
errors and detect two-bit errors.
• Simple to Implement: The Hamming code is relatively simple to
implement in hardware or software.
• Efficient Use of Parity Bits: The code uses a minimal number of parity
bits to correct errors, making it more efficient compared to other codes
like Reed-Solomon in terms of overhead.

P a g e | 22
  Conclusion

Error detection and correction are essential components of reliable data

communication and storage systems. These techniques ensure that transmitted
or stored data remains accurate and intact, even in the presence of noise,
interference, or other transmission errors. By using various error control
methods, systems can detect errors and, in some cases, correct them without
requiring retransmission or manual intervention.
In conclusion, error detection and correction are foundational techniques in
modern communication and data storage systems. They help ensure data
integrity, enhance system reliability, and optimize performance, especially in
environments with high error rates. While error detection ensures errors are
identified, error correction goes further to recover the data, making both
techniques indispensable in the world of digital communications.

P a g e | 23
  References
Forouzan, B. A. (2007). Data Communications and Networking (4th ed.):

• McGraw-Hill Website (for textbook)

IEEE 802.11 Wireless LAN Standards:
• IEEE 802.11 Standard
Hamming, R. W. (1950). Error Detecting and Error Correcting Codes:
• IEEE Xplore: Error Detecting and Error Correcting Codes

P a g e | 24