Cryptography Reference
In-Depth Information
Fig. 11.1
Definition of
robustness
11.3 Definition and Basic Properties of Robust Codes
We present most of the definitions in terms of binary codes. These results can be
easily generalized for codes over nonbinary fields.
2
n
Definition 11.1
(
R-Robust Code
) A code
C
⊆
GF
(
)
is
R
-robust if the size of the
C
intersection of the code
C
and any of its translations
={˜
x
|˜
x
=
x
+
e
,
x
∈
C
,
e
∈
2
n
GF
(
),
e
=
0
}
is upper bounded by
R
:
R
=
max
)
|{
x
|
x
∈
C
,
x
+
e
∈
C
}|
.
2
n
0
=
e
∈
GF
(
where
+
is the component-wise addition modulo 2.
A graphic depiction of the definition of a robust code is shown in Fig.
11.1
.
Let
C
C
e
be the set of all codewords of
C
shifted by an element
2
n
⊆
(
)
GF
, and
2
n
2
n
e
∈
GF
(
)
. The code C is
R
-robust if for any nonzero
e
∈
GF
(
)
, the size of the
intersection of C and
C
e
is upper bounded by
R
.
The above-defined robust codes have beneficial properties when the worst case
error masking probability of the codes is considered. Let
M
be the number
of codewords in a code
C
. By the definition of an
R
-robust code there are at most
R
codewords which can mask any fixed error
e
. The error masking probability
Q
=|
C
|
(
e
)
can be thus defined as
)
=
|{
x
|
x
∈
C
,
x
+
e
∈
C
}|
Q
(
e
.
(11.1)
M
Robust codes have no undetectable errors. For an
R
-robust code, the worst case
probability of masking an error is at most
R
M
for any error when the codewords
of the robust code are assumed equiprobable. Clearly, robust codes which have a
minimum
R
for a given
M
will also have the lowest probability of error masking
and hence predictable behavior in the presence of unpredictable error distributions,
since the worst case probability of masking any error is bounded. In the following
sections we investigate the construction and optimality of the codes followed by
some examples of applications.
/
