Error Detection and Correction Codes in Block Coding

 
1
T
o
 
g
u
a
r
a
n
t
e
e
 
t
h
e
 
d
e
t
e
c
t
i
o
n
 
o
f
 
u
p
 
t
o
 
s
e
r
r
o
r
s
 
i
n
 
a
l
l
 
c
a
s
e
s
,
 
t
h
e
 
m
i
n
i
m
u
m
H
a
m
m
i
n
g
 
d
i
s
t
a
n
c
e
 
i
n
 
a
 
b
l
o
c
k
c
o
d
e
 
m
u
s
t
 
b
e
 
d
m
i
n
 
=
 
s
 
+
 
1
.
T
o
 
g
u
a
r
a
n
t
e
e
 
c
o
r
r
e
c
t
i
o
n
 
o
f
 
u
p
 
t
o
 
t
 
e
r
r
o
r
s
i
n
 
a
l
l
 
c
a
s
e
s
,
 
t
h
e
 
m
i
n
i
m
u
m
 
H
a
m
m
i
n
g
d
i
s
t
a
n
c
e
 
i
n
 
a
 
b
l
o
c
k
 
c
o
d
e
m
u
s
t
 
b
e
 
d
m
i
n
 
=
 
2
t
 
+
 
1
.
 
A code scheme has a Hamming distance d
min
 = 4. What is
the error detection and correction capability of this
scheme?
 
Solution
This code guarantees the detection of up to 
three
 errors
(s = 3), but it can correct up to 
one
 error. In other words,
if this code is used for error correction, part of its capability
is wasted. Error correction codes need to have an odd
minimum distance (3, 5, 7, . . . ).
 
Example
A
 
s
i
m
p
l
e
 
p
a
r
i
t
y
-
c
h
e
c
k
 
c
o
d
e
 
i
s
 
a
s
i
n
g
l
e
-
b
i
t
 
e
r
r
o
r
-
d
e
t
e
c
t
i
n
g
c
o
d
e
 
i
n
 
w
h
i
c
h
n
 
=
 
k
 
+
 
1
 
w
i
t
h
 
d
m
i
n
 
=
 
2
.
 
Table 1
:
  
Simple parity-check code C(5, 4)
 
Figure 1
:
  
Encoder and decoder for simple parity-check code
 
Let us look at some transmission scenarios. Assume the
sender sends the dataword 1011. The codeword created
from this dataword is 10111, which is sent to the receiver.
We examine five cases:
 
1.
  No error occurs; the received codeword is 10111. The
      
syndrome is 0
. The dataword 1011 is created.
2.
  One single-bit error changes a
1 
. The received
     codeword is 10
0
11. The syndrome is 1. No dataword
     is created.
3.
 One single-bit error changes r
0 
. The received codeword
     is 1011
0
. The syndrome is 1. No dataword is created.
 
Example 
1
 
4
. An error changes 
r
0
 and a second error changes 
a
3
 
.
    The received codeword is 
0
011
0
. The syndrome is 0.
    The dataword 0011 is created at the receiver. Note that
    here the dataword is  wrongly created due to the
    syndrome value.
5
. Three bits—a
3
, a
2
, and a
1
—are changed by errors.
    The received codeword is 01011. The syndrome is 1.
    The dataword is not created. 
This shows that the simple
    parity check, guaranteed to detect one single error, can
    also find any odd number of errors
.
 
Example 1  (continued)
A
 
s
i
m
p
l
e
 
p
a
r
i
t
y
-
c
h
e
c
k
 
c
o
d
e
 
c
a
n
 
d
e
t
e
c
t
a
n
 
o
d
d
 
n
u
m
b
e
r
 
o
f
 
e
r
r
o
r
s
.
 
Table 
2
 
Hamming code C(7, 4)
 
r
0
 
= 
a
2 
+ 
a
1
 + 
a
0               
modulo 2
r
l
 = 
a
3
 + 
a
2
 + 
a
1               
modulo 2
r
2 
= 
a
1
 + 
a
0
 + 
a
3               
modulo 2
 
S
0
 = 
b
2
 + 
b
1
 + 
b
0
 + 
q
0     
modulo 2
S
1
 = 
b
3
 + 
b
2
 + 
b
1
 + 
q
l      
modulo 2
S
2
 = 
b
l
 + 
b
0
 + 
b
3
 + 
q
2      
modulo 2
 
Figure 
2
  
The structure of the encoder and decoder for a Hamming code
 
Table 
3
  
Logical decision made by the correction logic analyzer
 
Let us trace the path of three datawords from the sender to
the destination:
1.
 The dataword 0100 becomes the codeword 0100011.
     The codeword 0100011 is received. 
The syndrome is
     000
, the final dataword is 0100.
2.
 The dataword 0111 becomes the codeword 0111001.
 if the received codeword is 0
0
11001 the syndrome is 011.
After  flipping 
b
2
 (changing the 0 to 1), the final dataword
is 0111.
3.
 The dataword 1101 becomes the codeword 1101000. The
codeword 
00
01000 is received (two errors). The syndrome
is 101. After flipping 
b
0
 
, we get 0000, the wrong dataword.
This shows that our code cannot correct two errors.
 
Example 2
A
l
l
 
H
a
m
m
i
n
g
 
c
o
d
e
s
 
d
i
s
c
u
s
s
e
d
 
i
n
 
t
h
i
s
l
e
c
t
u
r
e
 
h
a
v
e
 
d
m
i
n
 
=
 
3
.
T
h
e
 
r
e
l
a
t
i
o
n
s
h
i
p
 
b
e
t
w
e
e
n
 
m
 
a
n
d
 
n
 
i
n
t
h
e
s
e
 
c
o
d
e
s
 
i
s
 
n
 
=
 
2
^
m
 
 
1
.
 
T
h
e
 
n
u
m
b
e
r
 
o
f
 
c
h
e
c
k
 
b
i
t
s
 
r
 
=
 
m
.
 
We need a dataword of at least 7 bits. Calculate values of
k  and  n  that satisfy this requirement.
 
Solution
We need to make k = n − m greater than or equal to 7, or
2^m − 1 − m ≥ 7.
1
. If we set m = 3, the result is n = 2^3 − 1 and k = 7 − 3,
    or 4, which is not acceptable.
2
. If we set m = 4, then n = 2^4 − 1 = 15 and k = 15 − 4 =
    11, which satisfies the condition. So the code is
 
Example 3
C(15, 11)
 
Figure 3  
Burst error correction using Hamming code
Slide Note
Embed
Share

Explanation of minimum Hamming distance for error detection and correction in block codes, examples of code schemes, transmission scenarios with simple parity-check code, and insights on Hamming codes. The content covers the essential principles and capabilities of error detection and correction mechanisms in coding theory.


Uploaded on Jul 19, 2024 | 2 Views


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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = s + 1. To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1. 1

  2. Example A code scheme has a Hamming distance dmin = 4. What is the error detection and correction capability of this scheme? Solution This code guarantees the detection of up to three errors (s = 3), but it can correct up to one error. In other words, if this code is used for error correction, part of its capability is wasted. Error correction codes need to have an odd minimum distance (3, 5, 7, . . . ).

  3. Note A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2.

  4. Table 1:Simple parity-check code C(5, 4)

  5. Figure 1:Encoder and decoder for simple parity-check code

  6. Example 1 Let us look at some transmission scenarios. Assume the sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver. We examine five cases: 1. No error occurs; the received codeword is 10111. The syndrome is 0. The dataword 1011 is created. 2. One single-bit error changes a1 . The received codeword is 10011. The syndrome is 1. No dataword is created. 3. One single-bit error changes r0 . The received codeword is 10110. The syndrome is 1. No dataword is created.

  7. Example 1 (continued) 4. An error changes r0 and a second error changes a3 . The received codeword is 00110. The syndrome is 0. The dataword 0011 is created at the receiver. Note that here the dataword is wrongly created due to the syndrome value. 5. Three bits a3, a2, and a1 are changed by errors. The received codeword is 01011. The syndrome is 1. The dataword is not created. This shows that the simple parity check, guaranteed to detect one single error, can also find any odd number of errors.

  8. Note A simple parity-check code can detect an odd number of errors.

  9. Table 2Hamming code C(7, 4)

  10. r0= a2 + a1 + a0 modulo 2 rl = a3 + a2 + a1 modulo 2 r2 = a1 + a0 + a3 modulo 2 S0 = b2 + b1 + b0 + q0 modulo 2 S1 = b3 + b2 + b1 + ql modulo 2 S2 = bl + b0 + b3 + q2 modulo 2

  11. Figure 2The structure of the encoder and decoder for a Hamming code

  12. Table 3Logical decision made by the correction logic analyzer

  13. Example 2 Let us trace the path of three datawords from the sender to the destination: 1. The dataword 0100 becomes the codeword 0100011. The codeword 0100011 is received. The syndrome is 000, the final dataword is 0100. 2. The dataword 0111 becomes the codeword 0111001. if the received codeword is 0011001 the syndrome is 011. After flipping b2 (changing the 0 to 1), the final dataword is 0111. 3. The dataword 1101 becomes the codeword 1101000. The codeword 0001000 is received (two errors). The syndrome is 101. After flipping b0 , we get 0000, the wrong dataword. This shows that our code cannot correct two errors.

  14. Note All Hamming codes discussed in this lecture have dmin = 3. The relationship between m and n in these codes is n = 2^m 1. The number of check bits r = m.

  15. Example 3 We need a dataword of at least 7 bits. Calculate values of k and n that satisfy this requirement. Solution We need to make k = n m greater than or equal to 7, or 2^m 1 m 7. 1. If we set m = 3, the result is n = 2^3 1 and k = 7 3, or 4, which is not acceptable. 2. If we set m = 4, then n = 2^4 1 = 15 and k = 15 4 = 11, which satisfies the condition. So the code is C(15, 11)

  16. Figure 3 Burst error correction using Hamming code

Related


More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#