Cryptography Reference
In-Depth Information
There are also lower bounds, the following of which was discovered in the
middle of the twentieth century(see [104] and [284]).
The Gilbert-Varshamov Bound
: Given
n,d
∈
N
with
n
≥
d
, there
exists a
q
-ary(
n,M,d
)-code satisfying,
q
n
M
≥
1)
j
.
d
−
1
j
=0
j
(
q
−
Linear Codes
An [
n,k
]-
linear code
over a field
F
is a
k
-dimensional subspace
C
of
F
n
.If
the minimum distance
d
=
d
(
C
) is given then we call it an [
n,k,d
]-linear code.
Note that a a
q
-ary[
n,k,d
]-code is also a
q
-ary(
n,q
k
,d
)-code, but not every
(
n,q
k
,d
)-code is an [
n,k,d
]-code.
11.7
If
M
k
×
n
is a
k
n
matrix whose rows form a basis for the [
n,k
]-code, then
M
k
×
n
is called a
generator matrix
for
C
. It is preciselythis mechanism of being
able to describe the entire code via a basis of the codewords that make linear
codes such a palatable means of error correction/detection.
An example of a binary[8
,
5
,
1]-code is given bythe generating matrix,
×
10000101
01000001
00100000
00010001
00001010
G
=
.
The value of
d
= 1 maybe achieved via the notion of
weight
. The weight of a
codeword
c
is the number of nonzero entries in
c
. The weight of an entire code
C
is the minimum of the weights of the nonzero codewords in
C
. Thus, the
weight of a given codeword
c
C
is
d
(
0
,c
) where
0 is the zero vector.
A major advantage to linear codes is the ease with which we can encode.
Suppose that
G
is the generating matrix for an [
n,k
]-code
C
over a finite field
F
q
. Then a simple encoding rule for
c
∈
∈
C
is the following:
c
→
cG,
the multiplication of the 1
n
matrix
G
. For instance, if
we take the matrix
G
displayed above and the vector
c
=(1
,
1
,
1
,
1
,
1)
×
k
vector
c
bythe
k
×
∈
C
, then
cG
=(1
,
1
,
1
,
1
,
1
,
1
,
1
,
1)
.
Note that a linear
q
-arycode cannot be defined unless
q
is a prime power.
This maybe considered to a drawback to linear codes. Yet, even this seeming
11.7
The reader may review the notion of vector spaces and dimension in Appendix A, espe-
cially Definition A.39 on page 490. It is important for this discussion to recall that a subspace
C
of dimension
k
in
q
, satisfies the property that every vector of
C
can be uniquely expressed
as a linear combination of the basis vectors
{v
1
,v
2
,...,v
k
}
for
C
, and that
C
contains exactly
q
k
vectors. This explains why every
q
-ary [
n, k, d
]-code is also a
q
-ary (
n, q
k
,d
)-code.
F
Search WWH ::
Custom Search