Error Correction and Forward Error Correction
E
r
r
o
r
C
o
r
r
e
c
t
i
o
n
E
r
r
o
r
C
o
r
r
e
c
t
i
o
n
b
y
R
e
t
r
a
n
s
m
i
s
s
i
o
n
When an error is discovered, the receiver can have the sender retransmit the
entire data unit (related to flow and error control protocols).
F
o
r
w
a
r
d
E
r
r
o
r
C
o
r
r
e
c
t
i
o
n
(
F
E
C
)
- In this method, a receiver can use an error-correcting code, which
automatically corrects certain errors.
- Error correcting codes are more sophisticated than error detection codes
and require more redundancy bits.
- The simplest case is single-bit errors. It can be detected by the addition of
a redundant (parity) bit. This additional bit can detect single-bit error
because it must distinguish between only two conditions: error or no error. A
bit has two states (0 and 1) and these are sufficient for this level of
detection.
- For single-bit error correction, two states are enough to detect an error but
not to correct it. To correct the error, the receiver simply reverses the value
of the altered bit and to do so, it must know which bit is in error – the secret
of error correction.
- To correct a single-bit error in an ASCII character, the error correction code
must determine which of the 7 bits has changed, so we have eight states :
no error, error in position 1, error in position 2 , …., error in position 7
- For ASCII code, it needs a three-bit redundancy code (000-111)
- But what if an error occurs in the redundancy bits themselves? Additional
bits are necessary to cover all possible error locations. (7 + 3 = 10).
- To calculate the number of redundancy bits (R) required to correct a given
number of data bit (M)
-If the total number of bits in a transmittable unit is m+r, then r must be
able to indicate at least m+r+1 different states
2
r
m + r + 1
ex) For value of m is 7(ASCII) , the smallest r value that can satisfy this
equation is 4
2
4
7 + 4 + 1
R
e
l
a
t
i
o
n
s
h
i
p
b
e
t
w
e
e
n
d
a
t
a
a
n
d
r
e
d
u
n
d
a
n
c
y
b
i
t
s
H
a
m
m
i
n
g
C
o
d
e
:
- Developed by R.W.Hamming
- The key to the Hamming Code is the use of extra parity bits to allow the identification of a
single error. Create the code word as follows:
1)
Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.)
2) All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17,
etc.)
3) Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit
determines the sequence of bits that it alternately checks and skips.
Position 1
: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...)
Position 2
: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...)
Position 4
: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...)
Position 8
: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...)
Position 16
: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...)
Position 32
: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...)
etc.
4) Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if
the total number of ones in the positions it checks is even.
- Positions of redundancy bits in Hamming code for 7 bits ASCII (powers of 2)
- In the Hamming code, each r bit is the parity bit for one combination of
data bits.
r
1
= bits 1, 3, 5, 7, 9, 11
r
2
= bits 2, 3, 6, 7, 10, 11
r
4
= bits 4, 5, 6, 7
r
8
= bits 8, 9, 10, 11
E
x
a
m
p
l
e
:
Each data bit may be included in more than one calculation
R
e
d
u
n
d
a
n
c
y
b
i
t
s
c
a
l
c
u
l
a
t
i
o
n
E
x
a
m
p
l
e
o
f
R
e
d
u
n
d
a
n
c
y
b
i
t
s
c
a
l
c
u
l
a
t
i
o
n
(
r
v
a
l
u
e
s
)
E
r
r
o
r
d
e
t
e
c
t
i
o
n
a
n
d
c
o
r
r
e
c
t
i
o
n
Assume that by transmission, the number 7 bit has been changed from 1 to 0
The receiver takes the transmission and recalculate the recalculates 4 new parity
bits, using the same sets of bits used by the sender plus the relevant parity r bit
for each set. Then it assembles the new parity values into a binary number in
order of r position (r
8
,r
4
,r
2
,r
1
).
B
u
r
s
t
e
r
r
o
r
c
o
r
r
e
c
t
i
o
n
A
l
t
h
o
u
g
h
t
h
e
h
a
m
m
i
n
g
c
o
d
e
c
a
n
n
o
t
c
o
r
r
e
c
t
a
b
u
r
s
t
e
r
r
o
r
d
i
r
e
c
t
l
y
,
i
t
i
s
p
o
s
s
i
b
l
e
t
o
r
e
a
r
r
a
n
g
e
t
h
e
d
a
t
a
a
n
d
t
h
e
n
a
p
p
l
y
t
h
e
c
o
d
e
.
I
n
s
t
e
a
d
o
f
s
e
n
d
i
n
g
a
l
l
t
h
e
b
i
t
s
i
n
a
d
a
t
a
u
n
i
t
t
o
g
e
t
h
e
r
,
w
e
c
a
n
o
r
g
a
n
i
z
e
N
u
n
i
t
s
i
n
a
c
o
l
u
m
n
a
n
d
t
h
e
n
s
e
n
d
t
h
e
f
i
r
s
t
b
i
t
o
f
e
a
c
h
,
f
o
l
l
o
w
e
d
b
y
t
h
e
s
e
c
o
n
d
b
i
t
o
f
e
a
c
h
,
a
n
d
s
o
o
n
.
I
n
t
h
i
s
w
a
y
,
i
f
a
b
u
r
s
t
e
r
r
o
r
o
f
M
b
i
t
s
o
c
c
u
r
s
(
M
<
N
)
,
t
h
e
n
t
h
e
e
r
r
o
r
d
o
e
s
n
o
t
c
o
r
r
u
p
t
M
b
i
t
s
o
f
o
n
e
s
i
n
g
l
e
u
n
i
t
;
I
t
c
o
r
r
u
p
t
s
o
n
l
y
1
b
i
t
o
f
a
u
n
i
t
.
W
i
t
h
t
h
e
H
a
m
m
i
n
g
s
c
h
e
m
e
,
w
e
c
a
n
t
h
e
n
c
o
r
r
e
c
t
t
h
e
c
o
r
r
u
p
t
e
d
b
i
t
i
n
e
a
c
h
u
n
i
t
.
We need to send six data units where each unit is a character with Hamming
redundant bits. We organize the bits in columns and rows. We send the first column,
then the second column, and so on. Five consecutive bits are corrupted during the
actual transmission. When these bits arrive at the destination and are reorganized
into data units, each corrupted bit belongs to one unit and is automatically corrected.
The trick here is to let the burst error corrupt only 1 bit of each unit.
B
u
r
s
t
e
r
r
o
r
c
o
r
r
e
c
t
i
o
n
e
x
a
m
p
l
e
When errors are discovered, a receiver can request retransmission to rectify the data unit. Forward Error Correction (FEC) uses error-correcting codes to automatically fix certain errors. Error correction codes are more sophisticated than error detection codes, requiring redundancy bits. Learn about single-bit error detection and correction, ASCII code error correction, and the calculation of redundancy bits. Discover the concept of Hamming Code and how it allows for the identification of a single error by using extra parity bits.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Error Correction Error Correction Retransmission Forward Error Correction Error Correction by Retransmission When an error is discovered, the receiver can have the sender retransmit the entire data unit (related to flow and error control protocols).
Forward Error Correction (FEC) - In this method, a receiver can use an error-correcting code, which automatically corrects certain errors. - Error correcting codes are more sophisticated than error detection codes and require more redundancy bits. - The simplest case is single-bit errors. It can be detected by the addition of a redundant (parity) bit. This additional bit can detect single-bit error because it must distinguish between only two conditions: error or no error. A bit has two states (0 and 1) and these are sufficient for this level of detection. - For single-bit error correction, two states are enough to detect an error but not to correct it. To correct the error, the receiver simply reverses the value of the altered bit and to do so, it must know which bit is in error the secret of error correction. - To correct a single-bit error in an ASCII character, the error correction code must determine which of the 7 bits has changed, so we have eight states : no error, error in position 1, error in position 2 , ., error in position 7
- For ASCII code, it needs a three-bit redundancy code (000-111) - But what if an error occurs in the redundancy bits themselves? Additional bits are necessary to cover all possible error locations. (7 + 3 = 10). - To calculate the number of redundancy bits (R) required to correct a given number of data bit (M)
-If the total number of bits in a transmittable unit is m+r, then r must be able to indicate at least m+r+1 different states 2 ex) For value of m is 7(ASCII) , the smallest r value that can satisfy this equation is 4 24 7 + 4 + 1 r m + r + 1 Total bits m + r Number of data bits m 1 2 Number of redundancy bits r 2 3 3 5 3 3 6 4 3 7 5 4 9 6 4 10 7 4 11 Relationship between data and redundancy bits
Hamming Code : - Developed by R.W.Hamming - The key to the Hamming Code is the use of extra parity bits to allow the identification of a single error. Create the code word as follows: 1) Mark all bit positions that are powers of two as parity bits. (positions 1, 2, 4, 8, 16, 32, 64, etc.) 2) All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, etc.) 3) Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips. Position 1: check 1 bit, skip 1 bit, check 1 bit, skip 1 bit, etc. (1,3,5,7,9,11,13,15,...) Position 2: check 2 bits, skip 2 bits, check 2 bits, skip 2 bits, etc. (2,3,6,7,10,11,14,15,...) Position 4: check 4 bits, skip 4 bits, check 4 bits, skip 4 bits, etc. (4,5,6,7,12,13,14,15,20,21,22,23,...) Position 8: check 8 bits, skip 8 bits, check 8 bits, skip 8 bits, etc. (8-15,24-31,40-47,...) Position 16: check 16 bits, skip 16 bits, check 16 bits, skip 16 bits, etc. (16-31,48-63,80-95,...) Position 32: check 32 bits, skip 32 bits, check 32 bits, skip 32 bits, etc. (32-63,96-127,160-191,...) etc. 4) Set a parity bit to 1 if the total number of ones in the positions it checks is odd. Set a parity bit to 0 if the total number of ones in the positions it checks is even.
Example: - Positions of redundancy bits in Hamming code for 7 bits ASCII (powers of 2) - In the Hamming code, each r bit is the parity bit for one combination of data bits. r1 = bits 1, 3, 5, 7, 9, 11 r2 = bits 2, 3, 6, 7, 10, 11 r4 = bits 4, 5, 6, 7 r8 = bits 8, 9, 10, 11
Redundancy bits calculation Each data bit may be included in more than one calculation
Error detection and correction Assume that by transmission, the number 7 bit has been changed from 1 to 0 The receiver takes the transmission and recalculate the recalculates 4 new parity bits, using the same sets of bits used by the sender plus the relevant parity r bit for each set. Then it assembles the new parity values into a binary number in order of r position (r8,r4,r2,r1).
Burst error correction Although the hamming code cannot correct a burst error directly, it is possible to rearrange the data and then apply the code. Instead of sending all the bits in a data unit together, we can organize N units in a column and then send the first bit of each, followed by the second bit of each, and so on. In this way, if a burst error of M bits occurs (M< N), then the error does not corrupt M bits of one single unit; It corrupts only 1 bit of a unit. With the Hamming scheme, we can then correct the corrupted bit in each unit. Burst error correction example We need to send six data units where each unit is a character with Hamming redundant bits. We organize the bits in columns and rows. We send the first column, then the second column, and so on. Five consecutive bits are corrupted during the actual transmission. When these bits arrive at the destination and are reorganized into data units, each corrupted bit belongs to one unit and is automatically corrected. The trick here is to let the burst error corrupt only 1 bit of each unit.
