Error correction, ARQ, FEC

1. 4.2.3
Error Correction

2. 4.2.3 Error Correction
•Once Detected, an error must be corrected.
•Two basic approaches to error correction are
available, which are:
–Automatic-repeat-request (ARQ):
–Forward error correction (FEC):

3. 4.2.3 Error Correction
•Automatic-repeat request (ARQ):
–ARQ procedures require the transmitter to resend
the portions of the exchange in which error have
been detected.
•Forward error correction (FEC):
–FEC techniques employ special codes that allow
the receiver to detect and correct a limited
number of errors without referring to the
transmitter.

4. ARQ Techniques
•Generally, ARQ procedures include the
following actions by the receiver or the
sender:

5. ARQ Techniques
•Receiver:
–Discard those frames in which errors are detected.
–For frames in which no error was detected, the
receiver returns a positive acknowledgment to the
sender.
–For the frame in which errors have been detected, the
receiver returns negative acknowledgement to the
sender.

6. ARQ Techniques
•Sender:
–Retransmit the frames in which the receiver has
identified errors.
–After a pre-established time, the sender
retransmits a frame that has not been
acknowledged.

7. ARQ Techniques
•Three Common ARQ Techniques are:
–Stop-and-Wait
–Go-back-n
–Selective-repeat

8. ARQ Techniques
•Stop-and-Wait
–The sender sends a frame and waits for
acknowledgment from the receiver.
–This technique is slow
–Suited for half-duplex connection.

9. ARQ Techniques
•Stop-and-Wait

10. ARQ Techniques
•Go-back-n:
–The sender sends frames in a sequence and
receives acknowledgements from the receiver.
–On detecting an error, the receiver discards the
corrupted frame, and ignores any further frames.
–The receiver notifies the sender of the number of
frame it expects to receive.

11. ARQ Techniques
•Go-back-n:
–On receipt of information, the sender begins re-
sending the data sequence starting from that
frame.
–This technique is faster than stop-and-wait
technique.

12. ARQ Techniques
•Selective-repeat:
–Used on duplex connections.
–The sender only repeats those frames for which
negative acknowledgment are received from the
receiver, or no acknowledgment is received.
–The appearance of a repeated frame out of
sequence may provide the receiver with
additional complications.

13. Forward Error Correction
–Possible for the receiver to detect and correct
errors without reference to the sender.
–This convenience is bought at the expense of
adding more bits.

14. Forward Error Correction
•For example
–If we only have two massages to send.
–we represent one (A) by the bits 10101010,
–And the other (B) by the bits 01010101.
–If the receiver knows that the message is A or B
and no other, and it is provided with the ability to
determine the logical distance between each
incoming massage and the two known messages,
this strategy will allow the receiver to correct for
up to three bits in error. The prove is as follows.

15. Forward Error Correction
•Proof:
–Suppose A is in error by 1 bit, so that
A’ = 00101010
–The logical distance between the received pattern
and A is 1
–And logical distance between the received pattern
and B is 7;
–Thus A’ is likely to be A.

16. Forward Error Correction
–Suppose A is in error by 2 bit, so that
A’ = 01101010
–The logical distance between the received pattern
and A is 2
–And logical distance between the received pattern
and B is 6;
–Thus A’ is likely to be A.

17. Forward Error Correction
–Suppose A is in error by 3 bit, so that
A’ = 01001010
–The logical distance between the received pattern
and A is 3
–And logical distance between the received pattern
and B is 5;
–Thus A’ is likely to be A.

18. Forward Error Correction
–Suppose A is in error by 4 bit, so that
A’ = 01011010
–The logical distance between the received pattern
and A is 4
–And logical distance between the received pattern
and B is 4;
–Thus A’ is likely to be A or B.

19. Forward Error Correction
•Continuing the sequence to higher levels of
error makes A’ more likely to be B than A.
•For this particular case, the limit of correction
is 3-bits in error.

20. Forward Error Correction
•Codes used to provide FEC (Forward Error
Correction) are more sophisticated than our
example. They can be divided into two types.
–Linear Block Codes
–Convolutional Codes