Cryptography Reference
In-Depth Information
binaryGolaycode
G
23
; and (3) the ternary(11
,
6) Golaycode, described
above. The problem of actuallyfinding all perfect codes having parameters
of the Hamming and Golaycodes remains diLcult and unsolved. What
has
been proved is that if there is a perfect code, then the parameters of
these codes must be the same as one of the Golay, Hamming or repetition
codes, which is a result is due to van Lint [154] and Tietavainen [278].
Now we turn to a natural and highlyimportant tpe of code of which the
preceding are examples.
Cyclic Codes
We will be working over some fixed finite field
F
q
.An(
n,k
)-code
C
is called
cyclic
if, whenever
c
=(
c
1
,c
2
,...,c
n
)
∈
C,
so is the cyclic shift,
c
=(
c
n
,c
1
,c
2
,...,c
n
−
1
)
,
For instance, the two Golaycodes
G
j
for
j
=23
,
24 are both cyclic codes.
Moreover, there are always four cyclic (
n,k
)-codes for any
n>
2 over
F
q
, given
as follows.
Example 11.12
Given
n
, there are always four cyclic codes of length
n
.
They are:
(1)
the singleton zero vector of length
n
,
0
, having dimension
0
;
(2)
the collection of constant codewords of length
n
,
c
=(
c
0
,c
0
,...,c
0
)
, having
dimension
1
;
(3)
any collection of codewords,
c
=(
c
1
,c
2
,...,c
n
)
, that satisfy
the property,
∈
N
···
c
1
+
c
2
+
+
c
n
=0
,
having dimension
n
−
1
; and
(4)
the entirety of
F
q
, having dimension
n
. There
are also the two Golay codes
G
j
for
j
=23
,
24
, as well as the Hamming code
Ham(3
,
2)
, all studied above.
We will now reindex our reference to the codewords in the cyclic codes so
that we look at
c
=(
c
0
,c
1
,...,c
n
−
1
)
,
since we wish to associate this vector with the polynomial,
+
c
n
−
1
x
n
−
1
.
c
0
+
c
1
+
···
In general, we have the following situation, for which the reader needs famil-
iaritywith the notion of polynomial rings and related phenomena in Appendix
A, especiallypages 484-491.
For a fixed
n
∈
N
,welookat
F
q
[
x
]
/
(
x
n
R
n,q
=
−
1)
,
(11.10)
Search WWH ::
Custom Search