Error Correction

• Error correction is the detection of errors and reconstruction of the

original ,error-free data.
• In this section we will study ARQ and ECC technique for error correction.

• Stop and wait ARQ

• Go back N ARQ
• Selective Repeat ARQ

Compiled by Kalyani Pawar

 Automatic Repeat request(ARQ)

• ARQ is an error control method for data transmission that

makes use of error-detection codes,acknowledgment and /or
negative acknowledgment messages, and timeouts to
achieve reliable data transmission.
• An acknowledgment is a message sent by the receiver to
indicate that it has correctly received a data frame.
• Usually, when the transmitter does not receive the
acknowledgment before the timeout occurs ,it retransmits
the frame until it is either correctly received orthe error
persists beyond a predetermined number of retransmssions.
• Three types of ARQ protocols are Stop and wait ARQ,Go
back N ARQ and Selective Repeat ARQ.
Compiled by Kalyani Pawar
 Stop-and-wait ARQ

Stop-and-Wait ARQ is a reliable data transmission protocol

used in networking and communication systems. It ensures
that each data frame is successfully received before
sending the next one.
Stop-and-Wait ARQ
Case 1: When data frame is damaged
Case 2 When Acknowlegment is lost
 Working Principle
[Link] Transmits a Frame → The sender sends one frame to
the receiver and waits for an acknowledgment (ACK).
[Link] Sends Acknowledgment (ACK) → If the frame is
received without errors, the receiver sends an ACK back to
the sender.
[Link] Receives ACK & Sends Next Frame → After
receiving the ACK, the sender transmits the next frame.
[Link] & Retransmission → If the sender does not receive
an ACK within a set timeout period, it resends the frame
assuming it was lost or corrupted.
[Link] Handling → If the receiver detects an error in the
received frame, it discards it and does not send an ACK. The
sender, upon timeout, retransmits the frame.

Page
7
 Example
• Imagine sending a message over a network:
• Sender transmits Frame 1 and waits for an ACK.
• If ACK is received, Frame 2 is sent.
• If no ACK is received (due to a lost/corrupted
frame), the sender retransmits Frame 1 after the
timeout.

Page
8
• Advantages of Stop-and-Wait ARQ
• Simple Implementation – Easy to understand and
implement.
Reliable Communication – Ensures every frame is received
correctly.
Efficient for Low-Speed Networks – Works well when
transmission speeds are low.
• Disadvantages of Stop-and-Wait ARQ
• Low Efficiency – Only one frame is sent at a time, leading
to idle waiting time.
Increased Delay – Transmission slows down, especially
over long distances.
Wasted Bandwidth – The sender remains idle while
waiting for ACK, underutilizing the network.
Page
9
Video on Stop & Wait ARQ
 Sliding window ARQ
• Sliding window ARQ it is an extended version of sliding window flow control to
include retransmission of data in case of loss an damaged frame two protocols
are most popular
1) Go back an ARQ and
2) Selective reject ARQ or selective Repeat ARQ.
Go-Back-N ARQ
• Go-Back-N ARQ is a sliding window protocol used in data
communication to ensure reliable transmission by
handling packet loss or corruption. It allows multiple
frames to be sent before needing an acknowledgment but
requires retransmission of all frames after an error is
detected.
• In this protocol if one frame is lost or damaged all frames
sent since the last frame acknowledged are retransmitted.
• A NAK means a positive acknowledgement of all frames
received prior to the damaged frame if the first
acknowledgement is an NAK 3 it means that data frames0,
1 and 2 and were all received in good shape only frame 3
must be resent.
 Go-Back-N ARQ
• As soon as the receiver discovers an error it stops accepting subsequent frames
until the damaged frame has been replaced correctly .In this scenario data frame
3 arrives damaged and so is discarded as are data frame 4 and data frame 5
whether or not the arrived intact retransmission therefore consists of frames 3 ,4
and 5.
• If one or more frames are lost in transit the next frame to arrive at the receiver
will be out of sequence. The receiver checks the identifying number on each
frame, discovers that one or more frames have been skipped or last, an returns a
NAK for the first missing frame.
• A NAK frame does not indicate whether the frame has been lost or damaged,
just that it needs to be resent.
• The sending device then retransmits the frame indicated by NAK, as well as
any frame that it had transmitted after the lost one.
Go-Back-N ARQ Case 1:If Ack is lost
 Summary
• Working of Go-Back-N ARQ
[Link] Side:
1. The sender can transmit N frames (defined by the window size) before waiting
for an acknowledgment (ACK).
2. Frames are assigned sequence numbers.
3. The sender moves forward only after receiving an ACK for the oldest
unacknowledged frame.
[Link] Side:
1. If a frame is correctly received, the receiver sends an acknowledgment (ACK)
for the highest in-order received frame.
2. If a frame is lost or received with an error, the receiver discards it and does not
acknowledge it.
3. The receiver only accepts frames in sequence (it does not buffer out-of-order
frames).
[Link] Handling (Retransmission):
1. If the sender does not receive an acknowledgment within a timeout period, it
goes back and retransmits all frames starting from the last unacknowledged
frame.
Page
16
Go-Back-N ARQ Case 2:If Frame is damaged or lost
• Advantages of Go-Back-N ARQ
• Efficient when errors are rare.
Better than Stop-and-Wait ARQ in terms of utilization.
Simple implementation as receiver does not need buffering.
• Disadvantages of Go-Back-N ARQ
• Wastes bandwidth due to unnecessary retransmissions.
Increased delay in case of errors.
Not suitable for networks with frequent errors.

Page
18
Definition
• SelectiveReject (also known as Selective Repeat ARQ) is a sliding
window protocol used in data communication for reliable
transmission. Unlike Go-Back-N ARQ, which retransmits all frames
after an error, Selective Reject ARQ only retransmits the specific
erroneous or lost frame.

Page
19
• Working of Selective Reject ARQ
[Link] Side:
1. Sends multiple frames using a sliding window protocol.
2. Waits for acknowledgments (ACKs) for each frame.
3. If a frame is not acknowledged (NAK), only that frame is retransmitted.

[Link] Side:
1. Receives and buffers out-of-order frames.
2. If a frame is received correctly, it sends an ACK for that frame.
3. If a frame is missing or incorrect, it sends a Negative Acknowledgment
(NAK) for that frame.
4. Once the missing frame arrives, it reorders the buffered frames before
passing them to the higher layers.
[Link] Handling (Retransmission):
1. The sender retransmits only the erroneous or lost frames based on NAKs,
avoiding unnecessary retransmissions.
Page
20
Selective Reject ARQ or Selective Repeat ARQ
• Advantages of Selective Reject ARQ
• Efficient bandwidth usage as only erroneous frames are retransmitted.
Better performance in high-error-rate environments.
Buffers out-of-order frames, reducing retransmission delays.

• Disadvantages of Selective Reject ARQ

• More complex implementation due to the need for frame buffering and
reordering.
Increased memory usage at the receiver side to store out-of-order
frames.
Higher processing overhead compared to Go-Back-N ARQ.

Page
22
Compare (6marks)

Page
23
 Hamming Code: Error Detection and Correction

• Hamming Code is a forward error correction (FEC) technique used in

computer networks and digital communication to detect and correct
single-bit errors. It was invented by Richard Hamming in 1950.

Why Hamming Code?

• Errors can occur during data transmission due to noise or interference.
Hamming Code allows the receiver to detect and correct a single-bit
error without retransmission, improving data reliability.

Page
24
 Hamming Code
Hamming code is an error-detection and error-correction method that ensures data
integrity during transmission. It adds redundant bits (known as parity bits) to a
data string, enabling the receiver to detect and correct single-bit errors.

Steps to Implement Hamming Code:

[Link] Data Bits: Start with the data bits that need to be transmitted.
[Link] Parity Bits: Insert parity bits at specific positions (powers of 2: 1, 2, 4, 8,
etc.).
[Link] Parity Values: Each parity bit covers a set of data bits to ensure the
total number of 1s in the covered set is even (even parity) or odd (odd parity).
[Link] Data: Send the encoded data (original data + parity bits) to the receiver.
[Link] Detection at Receiver: Check the parity bits to detect errors.
[Link] the Error (if any): Use the positions indicated by the parity checks to
identify and correct the erroneous bit.
 Example: 4-bit Data with Hamming (7,4) Code

Step 1: Assume Data Bits

Let’s take a 4-bit data: 1011
Page
27
Step 3: Compute Parity Bits

Each parity bit covers certain positions using even parity (or odd
parity):

P1 covers positions 1, 3, 5, 7

P2 covers positions 2, 3, 6, 7

P3 covers positions 4, 5, 6, 7

Page
28
Page
29
 Hamming Code
• Advantages of Hamming Code
• Can detect and correct single-bit errors.
Reduces the need for retransmission.
Efficient and widely used in RAM, satellite communication, and
networking.

• Limitations of Hamming Code

• Cannot correct multiple-bit errors.
Requires additional parity bits, increasing data size.

Hamming Code is a fundamental error correction method in networking,

ensuring reliable data transfer in noisy environments. It is widely used in
memory systems, data transmission, and digital communication.

Page
30
Thank You

Kalyani Pawar
Department of Information Technology(NBA Accredited)
Vidyalankar Polytechnic
Vidyalankar College Marg, Wadala(E), Mumbai 400 037
E-mail: [Link]@[Link]
31
Any Questions

32