Cryptography Reference
In-Depth Information
This code has 16 codewords but only 8 configurations for the syndrome as indi-
cated in Table 4.4.
Syndrome
s
Error word
e
000 0000000
001 0000001
010 0000100
011 0001000
100 0000100
101 0010000
110 0100000
111 1000000
Table 4.4: Syndromes and corresponding error words for a
C
(7
,
4)
code.
Let us assume that the codeword transmitted is
c
= [0101101]
and that the
received word
r
= [0111101]
has an error in position 3. The syndrome is then
equal to
s
= [101]
and, according to the table,
e
= [0010000]
. The decoded
codeword is
c
=
r
+
e
= [0101101]
and the error is corrected.
If the number of configurations of the syndrome is still too high to apply
this decoding procedure, we use decoding algorithms specific to certain classes
of codes but that, unfortunately, do not always exploit the whole correction
capability of the code. These algorithms will be presented below.
Correction power
Let
c
j
be the codeword transmitted and
c
l
its nearest neighbour. We have
the following inequality:
•
d
min
Introducing the received word
r
and assuming that the minimum distance
d
min
is equal to
2
t
+1
(integer
t
), we can write:
d
H
(
c
j
,
c
l
)
2
t
+1
≤
d
H
(
c
j
,
c
l
)
≤
d
H
(
c
j
,
r
)+
d
H
(
c
l
,
r
)
We see that if the number of errors is lower than or equal to
t
,
c
j
is the most
likely codeword since it is nearer to
r
than to
c
l
and thus the
t
errors can be
corrected. If the minimum distance is now
(2
t
+2)
, using the same reasoning,
we arrive at the same error correction capability. In conclusion, the correction
capability of a linear block code with minimum distance
d
min
with hard decoding
is equal to:
t
=
d
min
−
1
(4.23)
2
where
x
is the whole part of
x
rounded down (for example
2
.
5
=2)
.
