Cryptography Reference
In-Depth Information
q
m
+
1
q
m
q
m
−
1
−
1
−
1
−
1
parameters
(
v
=
,
M
=
1
,
R
=
)
, where
q
is a prime power and
q
−
1
q
−
q
−
1
m
>
1 is an integer. These are known as Singer difference sets.
PG
is shown in Fig.
11.2
. The set of any collinear points forms a perfect
robust code defined over
GF
(
2
,
2
)
(
7
)
with
n
=
1,
M
=
3 and
R
=
1. The differences of
(
)
the three codewords cover all nonzero elements of
GF
7
exactly once.
It has been shown that all difference sets over binary fields, and thus binary robust
codes which are the most important and practical for hardware design, exist only for
even dimensions and have the following parameters:
n
2
2
s
−
1
2
s
−
1
=
2
s
,
M
=
±
,
R
=
2
2
s
−
2
2
s
−
1
±
[42]. These codes can be constructed using the method presented in
[215].
Systematic codes, which are often more practical for many applications due to
their separation of data and check bits, cannot be perfect.
Theorem 11.1
[214] For any systematic R-robust code with length n and k infor-
mation bits, there are at least
2
n
−
k
2
n
elements in G F
(
)
which cannot be expressed
as differences of two codewords.
=
(
x
1
,
=
(
x
1
))
=
(
e
1
,
e
2
)
Proof
For any systematic codeword
x
x
2
f
an error
e
(
x
1
+
e
1
)
=
x
2
+
=
(
=
,
=
)
is masked iff
f
e
2
.Anerror
e
e
1
0
e
2
0
is never
masked since
f
0. An error that is never masked cannot be
expressed as a difference of two codewords. Hence elements from
GF
(
x
1
)
=
x
2
+
e
2
iff
e
2
=
2
n
(
)
of the
2
r
form
x
(
0
,
x
2
∈
GF
(
))
, where
r
=
n
−
k
, cannot be expressed as a difference of
two codewords.
Corollary 11.1
There are no perfect systematic robust codes.
When perfect robust codes are not available, the best possible codes which max-
imize
M
for a given
n
and
R
are referred to as optimum robust codes.
Definition 11.4
(
Optimum Robust Code
) Robust codes which have the maximum
possible number of codewords
M
for a given length
n
and robustness
R
with respect
to (
11.2
) are called optimum. For optimum codes, adding any additional codewords
would violate bound (
11.2
) and
M
2
2
n
M
2
−
M
≤
R
(
−
1
)<
+
M
.
(11.3)
Example 11.2
Consider the binary code
C
={
000
,
001
,
010
,
100
}
. It is easy to
2
3
verify that for any nonzero element
e
∈
GF
(
)
, there are at most two pairs of
c
1
,
c
2
satisfying
e
is the XOR operation. Hence the code is 2-robust.
The code is not perfect since equality does not hold for (
11.2
). The code, however
is an optimum robust code with
n
=
c
1
+
c
2
, where
+
2. No other code can exist
with the same
n
and
R
that has more codewords since five codewords would violate
condition (
11.2
).
=
3,
M
=
4,
R
=
Several constructions of optimum systematic robust codes will be presented in
the next section.
