Cryptography Reference
In-Depth Information
maybe easilydetected via a check that
cP
t
=
0 for
c
C
. For the example of
the binary[8
,
5
,
1]-code given on the previous page, we have
∈
10000100
00001010
11010001
.
P
=
We note that for the codeword (1
,
1
,
1
,
1
,
1
,
1
,
1
,
1) =
cG
, we have
cGP
t
=
0=
(0
,
0
,
0). Observe, as well, that the subspace of
F
n
that forms a zero dot prod-
uct
11.9
with all codewords from
C
in
F
n
has dimension
n
k
, and is called the
dual code of
C
. This space is typically denoted by
C
⊥
, so a parity-check matrix
for
C
maybe defined as a generator matrix for
C
⊥
. In other words, the dual
code of a linear [
n,k
]-code
C
with generating matrix
G
=[
I
k
|
−
M
k,n
−
k
], is given
by
c
=
0 for all
c
C
⊥
=
F
n
:
v
{
v
∈
·
∈
C
}
,
which is itself a linear [
n,n
−
k
]-code with generating matrix,
M
k,n
−
k
|
P
=[
−
I
n
−
k
]
.
In this way,
G
maybe viewed as a parity-check matrix for
C
⊥
.
Remark 11.1
There is some linear algebra at work in the above. If
M
∈
M
m
×
n
(
F
)
, then all vectors
v
such that
vM
=
0
is a subspace of
F
n
, called the
left null space
of
M
. This space is often called the
kernel
of
M
. Our linear codes
are constructed via a
k
-dimensional subspace of
F
n
, which is manufactured by
selecting
k
linearly independent vectors and taking their span. This is achieved
by choosing a
k
n
generating matrix
G
of rank
k
with entries in
F
. The set of
vectors of the form
vG
where
v
runs over all vectors in
F
k
provides the desired
subspace. It is a fact from linear algebra that the left null space space of a matrix
M
×
∈
M
m
×
n
(
F
)
of rank
r
, has dimension
n
−
r
. Since our generating matrix has
rank
k
, its null space
C
⊥
has rank
n
k
.
(
See the discussion in Appendix A of
matrix-related data, especially pages 494 and 495.
)
In any case, the mechanism
now exists for checking errors since if
cP
t
−
=
0
, then we know there is an error.
However, the converse need not be true. It may be the case that
cP
t
=
0
and
there is still an error but the chances are small that this is the case. It has much
higher probability that no errors have occurred than that enough errors occurred
to create a valid codeword from another. Hence, the parity check is taken as a
signal that no errors have arisen.
If a generating matrix
G
can be transformed into standard form
[
I
k
|
M
k,n
−
k
]
employing
only
row operations R1-R3, then the latter will generate exactly the
same
code as the former. However, if C1-C2 are used, then the latter will
generate a code that is
equivalent
to the former, but not necessarily the same.
Furthermore,
[
I
k
|
M
k,n
−
k
]
obtained from
G
is not unique, since permuting the
columns of
M
k,n
−
k
creates a generator matrix for an
equivalent
code.
11.9
Recall that a dot product is the pointwise multiplication of two vectors. For instance, if
c
=(
c
1
,c
2
,...,c
n
)
∈ C
and
x
=(
x
1
,x
2
,...,x
n
), then
cx
=(
c
1
· x
1
,c
2
· x
2
,...,c
n
· x
n
) is the
dot product, which may be given via the above matrix equations.
Search WWH ::
Custom Search