Cryptography Reference
In-Depth Information
Remark 11.1 The nonlinearity of the encoding function f for systematic codes cor-
responds to the worst case error masking probability of the codes [213, 214]. We
have
P f
=
max
Q
(
e
) =
max
Q
(
e
).
e
= (
e 1 ,
e 2 ),
e 1 =
0
e
GF
(
2 k + r
)
2 k
2 r
where e 1
GF
(
),
e 2
GF
(
)
.
The following two constructions are examples of optimum robust codes based on
perfect nonlinear functions.
Construction 11.1 (Quadratic Systematic Code [213]) Let
x
= (
x 1 ,
x 2 ,...,
x 2 s ,
x 2 s + 1 ),
2 r
2 ( 2 s + 1 ) r
(
),
(
)
x i
GF
s
1 . A vector x
GF
belongs to the code iff
x 1
x 2 +
x 3
x 4 +···+
x 2 s 1
x 2 s =
x 2 s + 1 ,
(11.5)
and i = 1 x 2 i 1
2 r
where
is the multiplication in G F
(
)
x 2 i is a perfect nonlin-
2 2 sr
2 r
ear function from G F
(
)
to G F
(
)
. The resulting code is a robust code with
2 ( 2 s 1 ) r ,n
2 2 sr . The code is optimum with respect to
R
=
= (
2 s
+
1
)
r and M
=
Definition 11.4.
Applications of binary quadratic systematic codes for designing of memories with
self-detection, for data transmission in noisy channels and for data verification can
be found in [213].
Example 11.3 (Robust Parity) s Methods based on linear parity check codes are
often used for online error detection in combinational circuits [247]. The linear 1-
dim parity codes can detect all errors of odd multiplicities but offer no protection for
errors of even multiplicities.
As an alternative to the 1-dim parity codes, the quadratic systematic robust codes
defined in Construction 11.1 can be used. When r
1, the function defined in ( 11.5 )
is known as the bent function. The resulting systematic robust code has the same
redundancy as the linear parity code. Unlike the linear parity code, the robust code
will mask an error with a probability of at most
=
1
2 regardless of the error multiplicity,
providing predictable error detection regardless of the error distribution.
2 k
2 k
Perfect nonlinear functions from GF
(
)
to GF
(
)
do not exist [80]. Functions
2 k + 1 and are called almost
perfect nonlinear (APN) functions [276]. When the f are APN functions, the robust
codes constructed as in Theorem 11.2 have R
with optimum nonlinearity in this case have P f
=
=
2. These codes are not optimum.
2 r
Construction 11.2 (Robust Duplication Code) Let x
= (
x 1 ,
x 2 )
,x 1 ,
x 2
GF
(
)
2 2 r
(k
=
r ). The robust duplication code C contains all vectors x
GF
(
)
which
Search WWH ::




Custom Search