Cryptography Reference
In-Depth Information
4
c
j
x
j
=
x
4
+
α
3
x
3
+
x
2
+
αx
+
α
3
.
j
=0
Since the only other root s of
x
7
−
1=0
are
1
,α
5
,α
6
, then the parity check
polynomial for this code is
α
5
)(
x
α
6
)=
x
3
+
α
3
x
2
+
α
2
x
+
α
4
.
p
(
x
)=(
x
−
1)(
x
−
−
The corresponding generating and parity-check matrices are given by
α
3
α
1
α
3
100
,
0
α
3
α
1
α
3
G
=
10
00
α
3
α
1
α
3
1
and
α
4
α
2
α
3
1000
0
α
4
α
2
α
3
100
P
=
.
00
α
4
α
2
α
3
10
000
α
4
α
2
α
3
1
The dimension of
C
=
g
(
x
)
is
n
−
2
t
=3
. Since
C
is the embedding of
C
⊆
F
q
q
via
c
into
cG
, then we may illustrate the relationship as follows
(
see page
446
)
.
C
has basis,
F
→
{
(100)
,
(010)
,
(001)
}
,
in
F
q
and these correspond to
1
,α,α
2
{
}
via the association,
c
0
+
c
1
α
+
c
2
α
2
.
(
c
0
,c
1
,c
2
)
↔
Notice that, for instance,
(100)
G
=(
α
3
,α,
1
,α
3
,
1
,
0
,
0)
,
(010)
G
=(0
,α
3
,α,
1
,α
3
,α,
0)
,
(001)
G
=(0
,
0
,α
3
,α,
1
,α
3
,
1)
,
which are rows 1-3 of G, respectively, and all codewords of
C
are linear combi-
nations of these three rows. for instance,
(111)
G
=(
α
3
,
1
,
0
,
0
,α
3
,α,
1)
is the sum of all three rows. Indeed, there are
q
n
−
2
t
=8
3
= 512
codewords in
C
, which are all linear combinations modulo
8
of the three rows of
G
.
In Example 11.15, the number of
n
-tuples is 512 out of a total possible
2
21
=2
,
097
,
152, or 1
/
4096 of them. This illustrates the fact that if
q
=2
m
,
then in the
n
-tuple space 2
nm
n
-tuples there 2
km
are codewords in the Reed-
Solomon code, where
k
=
n
−
2
t
. This is a small proportion of the possible
Search WWH ::
Custom Search