4.4 Cyclic Codes
51
β = α
i for some primitive element α ∈ F q m , then the minimal polynomial of β = α
i
is denoted by M
(i)
(x).
Irreducible polynomials are generated in the following way.
Theorem 4.4.1 x
q
m − x = product of all monic, irreducible polynomials over F q ,
whose degree divides m.
The following result is well known.
Theorem 4.4.2 x
n
− 1 =
j
M
( j)
(x), where M
( j)
(x) denotes the minimal polynomial of α
j
∈ F q m and j runs through the coset representatives mod n.
In order to proceed further, the reader can recall some known concepts of algebra
such as ideals in commutative rings and quotient rings. These concepts can be found
in the Appendix of this book.
Let F q [x] denote the ring of polynomials in F q and consider the quotient ring
R n = F q [x]/(x
n
− 1). From this context we define the concept of cyclic code.
Definition 4.4.2 A cyclic code C of length n over F q is a nonzero ideal in R n .
It is well-known that there exists only one polynomial g(x) with minimal degree
in C; g(x) is a generator polynomial of C. Moreover, g(x) is a factor of x
n
− 1.
The dimension of a cyclic code C is equal to n − deg(g(x)), where deg(g(x)) is the
degree of the polynomial g(x).
The dual code C
⊥ of a cyclic code C is also cyclic and has generator polynomial
given by
g(x)
⊥
= x
deg h(x) h(x
−1
),
(4.1)
where h(x) = (x
n
− 1)/g(x).
Definition 4.4.3 Two codes C and C
∗ are called equivalent if they differ only in the
arrangement of symbols. More precisely, if C is the row space of a matrix G, then
C
∗ is a code equivalent to C if and only if C
∗ is the row space of a matrix G
∗ that is
obtained from G by rearranging columns.
Based on Definition 4.4.3 and from Eq. (4.1), it follows that the code with generator
polynomial h(x) is equivalent to the (Euclidean) dual code C
⊥ .
Let us recall the well-known BCH bound theorem.
Theorem 4.4.3 (The BCH bound) Let q be a prime power and α a primitive nth
root of unity. Let C be a cyclic code with generator polynomial g(x) such that, for
some integers b ≥ 0 and δ ≥ 1, and for α ∈ F q , we have
g(α
b
) = g(α
b+1
) = . . . = g(α
b+δ−2
) = 0,
51
β = α
i for some primitive element α ∈ F q m , then the minimal polynomial of β = α
i
is denoted by M
(i)
(x).
Irreducible polynomials are generated in the following way.
Theorem 4.4.1 x
q
m − x = product of all monic, irreducible polynomials over F q ,
whose degree divides m.
The following result is well known.
Theorem 4.4.2 x
n
− 1 =
j
M
( j)
(x), where M
( j)
(x) denotes the minimal polynomial of α
j
∈ F q m and j runs through the coset representatives mod n.
In order to proceed further, the reader can recall some known concepts of algebra
such as ideals in commutative rings and quotient rings. These concepts can be found
in the Appendix of this book.
Let F q [x] denote the ring of polynomials in F q and consider the quotient ring
R n = F q [x]/(x
n
− 1). From this context we define the concept of cyclic code.
Definition 4.4.2 A cyclic code C of length n over F q is a nonzero ideal in R n .
It is well-known that there exists only one polynomial g(x) with minimal degree
in C; g(x) is a generator polynomial of C. Moreover, g(x) is a factor of x
n
− 1.
The dimension of a cyclic code C is equal to n − deg(g(x)), where deg(g(x)) is the
degree of the polynomial g(x).
The dual code C
⊥ of a cyclic code C is also cyclic and has generator polynomial
given by
g(x)
⊥
= x
deg h(x) h(x
−1
),
(4.1)
where h(x) = (x
n
− 1)/g(x).
Definition 4.4.3 Two codes C and C
∗ are called equivalent if they differ only in the
arrangement of symbols. More precisely, if C is the row space of a matrix G, then
C
∗ is a code equivalent to C if and only if C
∗ is the row space of a matrix G
∗ that is
obtained from G by rearranging columns.
Based on Definition 4.4.3 and from Eq. (4.1), it follows that the code with generator
polynomial h(x) is equivalent to the (Euclidean) dual code C
⊥ .
Let us recall the well-known BCH bound theorem.
Theorem 4.4.3 (The BCH bound) Let q be a prime power and α a primitive nth
root of unity. Let C be a cyclic code with generator polynomial g(x) such that, for
some integers b ≥ 0 and δ ≥ 1, and for α ∈ F q , we have
g(α
b
) = g(α
b+1
) = . . . = g(α
b+δ−2
) = 0,