Cryptography Reference
In-Depth Information
F
q
[
x
] modulo (
x
n
which are the elements in
1). Hence, we will always be
considering polynomials of degree no more than
n
−
−
1, since anypolynomial of
degree
n
or larger maybe divided by
x
n
1, and we merelytake the remainder
since we are working modulo the latter. (Note that since
x
n
−
1(mod
x
n
1),
then we need onlyreplace the powers of
x
accordingly, so division in the usual
sense, by
x
n
≡
−
−
1 is not required.) With this setup, and the notation given in
(11.10), general cyclic codes are described as follows.
Polynomials and Cyclic Codes
: Suppose that
C
is a cyclic code of length
n
over
F
q
. To each codeword
c
=(
c
0
,c
1
,...,c
n
−
1
)
∈
C
associate the polyno-
mial,
+
c
n
−
1
x
n
−
1
.
f
c
(
x
)=
c
0
+
c
1
x
+
···
Notice that
xf
c
(
x
)=
c
n
−
1
+
c
0
x
+
c
1
x
2
+
+
c
n
−
2
x
n
−
1
···
corresponds to a single cyclic shift of the vector,
(
c
0
,c
1
,...,c
n
−
1
)
.
Consequently, multiplying
f
c
(
x
)by
x
m
corresponds to a cyclic shift through
m
positions to the right.
If we let
g
(
x
) be the unique monic polynomial of smallest degree from the
set of all such
f
c
, then let
C
denote
C
embedded in
R
n,q
,so
g
(
x
) is called the
generating polynomial
for
C
.
(Observe that if the polynomial from this set of smallest degree is not monic,
we can make it so bydividing through bythe coeLcient of the highest degree
term, which is possible since our coeLcients are from a field.)
If we therefore view the embedding
C
of
C
in
R
n,q
via the polynomial iden-
tification, we get the following characterizations.
The Generating polynomial and Criteria for Cyclic Codes in R
n
,
q
First, we observe that
C
in
R
n,q
as above means that it is cyclic code if and
onlyif it is closed under addition and closed under multiplication from elements
of
R
n,q
, namely, it is an ideal of
R
n,q
. This tells us that anycclic code can
be generated by a polynomial. Hence, the cyclic codes are exactly the ideals of
R
n,q
. In other words,
a linear code
C
is cyclic if and only if
C
is an ideal in
R
n,q
.
If
C
is a cyclic code in
R
n,q
, then there exists a generating polynomial
g
(
x
)
satisfying each of the following.
1.
C
=
,so
g
(
x
) is uniquelydetermined by
C
, which equals the set of
polynomials of the form
f
(
x
)
g
(
x
), where deg(
f
)
g
(
x
)
≤
n
−
deg(
g
)
−
1.
2.
g
(
x
)
(
x
n
−
1).
Search WWH ::
Custom Search