Cryptography Reference
In-Depth Information
Syndrome
s
is null if, and only if,
r
is a codeword. A non-null syndrome implies
the presence of errors. However, it should be noted that a null syndrome does
not necessarily mean absence of errors since
r
can belong to the set of codewords
even though it is different from
c
. For this to occur, it suces for word
e
to be a
codeword. Indeed, for a linear block code, the sum of two codewords is another
codeword.
Finally, let us note that for any linear block code, there are configurations
of non-detectable errors.
Detection capability
Let
c
j
be the transmitted codeword and
c
l
its nearest neighbour. We have the
following inequality:
d
min
Introducing the received word
r
,wecanwrite:
d
H
(
c
j
,
c
l
)
d
min
≤
d
H
(
c
j
,
c
l
)
≤
d
H
(
c
j
,
r
)+
d
H
(
c
l
,
r
)
and thus all the errors can be detected if the Hamming distance between
r
and
c
l
is higher than or equal to 1, that is, if
r
is not merged with
c
l
.
The detection capability of a
C
(
n, k
)
code with minimum distance
d
min
is
therefore equal to
d
min
−
1
.
Probability of non-detection of errors
Considering a block code
C
(
n, k
)
and a binary symmetric channel with error
probability
p
, the probability of non-detection of the errors
P
nd
is equal to:
n
A
j
p
j
(1
p
)
n−j
P
nd
=
−
(4.22)
j
=
d
min
where
A
j
is the number of codewords with weight
j
.
Examining the hypothesis of a completely degraded transmission, that is, of
an error probability of
p
=1
/
2
on the channel, and taking into account the fact
that for any block code we have:
n
A
j
=2
k
−
1
j
=
d
min
(the
1
in the above expression corresponds to the null codeword), probability
P
nd
is equal to:
−
2
k
−
1
= 2
−
(
n−k
)
P
nd
=
2
n
