Cyclic Codes over Galois Rings

Abstract

Let R be a Galois ring of characteristic $p^a$, where p is a prime and a is a natural number. In this paper cyclic codes of arbitrary length n over R have been studied. The generators for such codes in terms of minimal degree polynomials of certain subsets of codes have been obtained. We prove that a cyclic code of arbitrary length n over R is generated by at most $min\{a, t+1\}$ elements, where $t=max\{deg(g(x))\},$ g(x) a generator. In particular, it follows that a cyclic code of arbitrary length n over finite fields is generated by a single element. Moreover, the explicit set of generators so obtained turns out to be a minimal strong Gröbner basis.

J. Kaur — Work submitted in partial fulfillment of requirements for the degree of Doctor of Philosophy.

1 Introduction

Cyclic codes over finite rings are being studied extensively these days and the literature is abundant with results on cyclic codes over finite rings where the characteristic of the ring under consideration and the length of the code are coprime. For reference see ([4, 5, 9, 14, 15]). The methodology used in most of these papers is to focus on irreducible factors of $x^n-1$ and to obtain in turn, the ideals of the ring $R[x]/\langle x^n-1 \rangle$ by Hensel’s lifting. However, this technique cannot be applied to codes of general length n as the ring ceases to be a unique factorization domain in case the length of the code and the characteristic s of the ring are not coprime. A few expositions are available for the study of cyclic codes over finite rings in case $(n,s)\ne 1$. For reference see ([6, 7, 10, 11, 16, 17, 19]). Dougherty et al. in [7] have given a structure theorem for codes over Galois rings and employed Chinese remainder theorem and lifting of irreducible polynomials. Sălăgean in [16] has given an existential proof for the existence of a minimal strong Gröbner basis for cyclic codes of arbitrary length over a finite chain ring. Norton et al. in [13, 14] formalized the notion of generating set in standard form for cyclic codes over principal ideal ring and obtained necessary and sufficient conditions for the generating set to be a minimal strong Gröbner basis as defined in [2]. The result for repeated root cyclic codes over chain ring was extended by Sălăgean in [16]. Abualrub et al. in [1] have given a simpler approach by introducing minimal degree polynomials to find the generators of cyclic codes of length $2^k$ over $\mathbb {Z}_4.$

In this paper we take further the approach of Abualrub and find the generators of cyclic codes of general length over Galois rings in an explicit constructive manner. Also, the set of generators obtained turns out to be a minimal strong Gröbner basis. The results of Garg and Dutt [8] follow from our results.

2 Preliminaries

A cyclic code over a ring R is a linear code which is closed under cyclic shifts. It is well known that the cyclic codes of length n over a ring R are in correspondence with the ideals of $R[x]/\bigl \langle x^n-1 \rangle$ and thus cyclic codes over R, written as vectors, can be recognized as polynomials of degree less than n,  that is, $c=(c_0,c_1,\ldots ,c_{n-1})$ is identified with the polynomial $c_0+c_1x+\ldots +c_{n-1}x^{n-1}$.

A finite ring with identity is called a Galois ring if its zero divisors including zero form a principal ideal $\bigl \langle p \bigr \rangle$ for some prime p [18]. For any $m \ge 1,$ the Galois extension ring of $Z_{p^a}$ can be constructed as $GR(p^a,m)=Z_{p^a}[x]/\bigl \langle f(x) \bigr \rangle ,$ where p is a prime, a is a natural number and $f(x) \in Z_{p^a}[x]$ is a monic basic irreducible polynomial of degree m. The ring $GR(p^a,m)$ is called a Galois ring and has $p^{am}$ elements. For $a=1,$ we obtain the finite field $GF(p^m)$ with $p^m$ elements ([12, 18]).

Let I be an ideal in R[x] and A(x) be an element of I. Let lm(A(x)) denote the leading monomial of A(x). A set $G=\{B_i(x), 1\le i \le \nu \}$ of non zero elements of I is called a Gröbner basis of I if for each $A(x) \in I$ there exists an $i \in \{1,2,\ldots , \nu \}$ such that lm(A(x)) is divisible by $lm(B_i(x)).$ An arbitrary subset G of R[x] is called a Gröbner basis if it is a Gröbner basis of $\langle G \rangle$ [3].

3 Generators of Cyclic Codes over a Galois Ring Ras Ideals of $R[x]/\bigl \langle X^n-1\bigr \rangle$

Let $R = GR(p^a,m)$ be a Galois ring and $R_n=R[x]/\bigl \langle x^n-1\bigr \rangle$. The aim of this paper is to find the generators of cyclic codes over Galois rings as ideals of $R_n$. These generators are found in terms of minimal degree polynomials of certain subsets of the given code.

Let C be an ideal in $R_n$ and $g_e(x)$ be a minimal degree polynomial in C with minimum power of p in the leading coefficient. Let the leading coefficient of $g_e(x)$ be $p^{i_e}u_e$ where $u_e$ is a unit and $0\le {i_e}\le a-1$. If $i_e=0$ then $g_e(x)$ is a monic polynomial otherwise for $0 \le j \le e-1$, successively define $g_j(x)$ to be minimal degree polynomial with minimum power of p in the leading coefficient among all polynomials in C having the power of p in the leading coefficient less than $i_{j+1}$, where $i_{j}$ is the power of p in the leading coefficient of $g_{j}(x)$ and $i_0$ is the minimum power of p in the leading coefficients among all polynomials in C. Then $0\le i_0< i_1<\ldots <i_j<i_{j+1}<\ldots <i_e$. For $i_0=0,$ $g_0(x)$ is a monic polynomial. Let $t_j$ be the degree of the polynomial $g_j(x).$ Clearly $t_{j}>t_{j+1}$.

Remark 1

It is easy to see that for any polynomial c(x) in C with power of p in the leading coefficient l,  there exists a j with $0\le j\le e$ such that $t_j\le deg(c(x))< t_{j-1}.$ Then $l\ge i_j$ and the polynomial

$$r(x)=c(x)-p^{l-i_j}g_j(x)ux^{deg(c(x))-t_j}$$

is in C for some unit u. Moreover, $r(x)=0$ or $deg(r(x))<deg(c(x)).$ The polynomial r(x) can be expressed as $r(x)=c(x)-q(x)g_j(x)$ for some $q(x)\in R_n.$

The following theorem gives the generators of a cyclic code over the ring R.

Theorem 1

Let C be an ideal in $R_n$ and $g_j(x)$ be polynomials as defined above. Then $C= \bigl \langle g_0(x),g_1(x),\ldots , g_e(x)\bigr \rangle$.

Proof

Let c(x) be a polynomial in C. By Remark 1, there exists a j and a polynomial $q_1(x)\in R_n$ such that the polynomial

$$\begin{aligned} r_1(x)=c(x)-q_1(x)g_j(x) \end{aligned}$$

is in C. Moreover, $r_1(x)=0$ or $deg\bigl (r_1(x)\bigr )< deg\bigl (c(x)\bigr )$. If $r_1(x)=0$ then $c(x) \in \bigl \langle g_j(x)\bigr \rangle \subset \bigl \langle g_0(x),g_1(x),\ldots , g_e(x)\bigr \rangle$. If $deg\bigl (r_1(x)\bigr )< deg\bigl (c(x)\bigr )< t_{j-1}$ then by Remark 1 there exists a k and a polynomial $q_2(x)\in R_n$ such that the polynomial

$$\begin{aligned} r_2(x)=r_1(x)-q_2(x)g_k(x) \end{aligned}$$

is in C. Moreover, $r_2(x)=0$ or $deg\bigl (r_2(x)\bigr )< deg\bigl (r_1(x)\bigr )<deg\bigl (c(x)\bigr )$. Clearly $k\ge j.$ If $r_2(x)=0$ then c(x) belongs to $\bigl \langle g_j(x), g_k(x)\bigr \rangle \subset \bigl \langle g_0(x),g_1(x),\ldots , g_e(x)\bigr \rangle .$ If $deg\bigl (r_2(x)\bigr )< deg\bigl (r_1(x)\bigr ),$ it is evident that after repeating the argument a finite number of times we shall have the remainder equal to zero as the degrees of the remainders form a decreasing sequence of natural numbers which is bounded below by $t_e$. Therefore back substituting for the remainders it is clear that any polynomial c(x) in C belongs to $\bigl \langle g_j(x),\ldots , g_e(x)\bigr \rangle$ where j is the smallest value such that $deg\bigl (c(x)\bigr ) \ge t_j$ for $0\le j\le e.$ Consequently we get $C= \bigl \langle g_0(x),g_1(x),\ldots , g_e(x)\bigr \rangle .$    $\square$

The following corollaries are an immediate consequence of Theorem 1.

Corollary 1

A cyclic code C of arbitrary length n over a Galois ring of characteristic $p^a$ is generated by at most k elements, with $k=min\{a, t+1\},$ where $t=max\{deg(g(x))\},$ g(x) a generator.

Corollary 2

A cyclic code C of arbitrary length n over an integer residue ring of characteristic $p^a$ is generated by at most k elements, with $k=min\{a, t+1\},$ where $t=max\{deg(g(x))\},$ g(x) a generator.

Proof

For $m=1$, the Galois ring $GR(p^a,m)$ is an integer residue ring of characteristic $p^a$.    $\square$

As finite fields are special case of Galois rings with $a=1$. We have the following corollary.

Corollary 3

A cyclic code C of arbitrary length n over finite fields is generated by a single element.

Theorem 2

Let $g_e(x)$ be the polynomial as defined above. Then $g_e(x)=$ $p^{i_e}h_e(x)$, where $h_e(x)$ is a monic polynomial in $R^e[x]/\bigl \langle x^n-1\bigr \rangle$, $R^e$ is a Galois ring of characteristic $p^{a-{i_e}}$.

Proof

Let $g_e(x)= p^{i_e}u_{e}x^{t_e}+b_{t_e-1}x^{t_e-1}+\ldots +b_0$. Suppose $b_j\not \equiv 0\ (\text {mod}\ {p^{i_e}})$ for some j, where $0\le j \le {t_e-1}$. Now $p^{a-{i_e}}g_e(x)\in C$ and is a polynomial of degree less than $t_e$, a contradiction. Hence $b_j \equiv 0\ (\mathrm{{mod}}\ p^{i_e})$ for every j. Thus $g_e(x)= p^{i_e}h_e(x)$ where $h_e(x)\in R^e[x]/\bigl \langle x^n-1\bigr \rangle$, $R^e$ is a Galois ring of characteristic $p^{a-{i_e}}$. Clearly $h_e(x)$ is a monic polynomial.    $\square$

Theorem 3

Let the polynomials $g_j(x)$ be the polynomials as defined above. Then for $0 \le j \le e-1$

• 1. $p^{i_{j+1}-i_j}g_j(x)\in \bigl \langle g_{j+1}(x),g_{j+2}(x),\ldots ,g_e(x)\bigr \rangle$.

• 2. $g_j(x) = p^{i_j}h_j(x)$ where $h_j(x)$ is a monic polynomial in $R^j[x]/\bigl \langle x^n-1\bigr \rangle$, $R^j$ is a Galois Ring of characteristic $p^{a-{i_j}}$.

• 3. $h_{j+1}(x)|h_j(x)$ (mod $p^{i_{j+2}-i_{j+1}}$).

Proof

Let $c(x)=p^{i_{j+1}-i_j}g_j(x)-g_{j+1}(x)x^{t_j-t_{j+1}}.$ Then c(x) is in C and deg(c(x)) $< t_j.$ Now proceeding as in Theorem 1, it is easy to see that

$$c(x)=p^{i_{j+1}-i_j}g_j(x)-g_{j+1}(x)x^{t_j-t_{j+1}}\in \langle g_{k}(x), g_{k+1}(x), \ldots , g_e(x) \rangle $$

for some $k>j.$ This further implies that

$$\begin{aligned} p^{i_{j+1}-i_j}g_j(x)\in \langle g_{j+1}(x), g_{j+2}(x), \ldots , g_e(x) \rangle \end{aligned}$$

(1)

This completes the proof for part 1 of the theorem.

Next, we need to show that

$$\begin{aligned} g_j(x) = p^{i_j}h_j(x) \end{aligned}$$

(2)

for $0 \le j \le e-1$. From Theorem 2, $g_e(x)= p^{i_e}h_e(x)$, where $h_e(x)$ is a monic polynomial in $R^e[x]/\bigl \langle x^n-1\bigr \rangle$, $R^e$ is a Galois ring of characteristic $p^{a-{i_e}}$. Suppose $g_{e-1}(x), g_{e-2}(x), \ldots , g_j(x)$ satisfy (2). Then we will show that $g_{j-1}(x)$ satisfies (2). From (1) we have

$$p^{i_{j}-i_{j-1}}g_{j-1}(x)\in \langle g_{j}(x), g_{j+1}(x), \ldots , g_e(x) \rangle .$$

This gives

$$\begin{aligned} \begin{aligned} p^{i_{j}-i_{j-1}}g_{j-1}(x)&= g_{j}(x)F_{j}(x)+\ldots + g_e(x)F_e(x)\\&= p^{i_{j}}h_{j}(x)F_{j}(x)+\ldots +p^{i_e}h_e(x)F_e(x)\\&= p^{i_{j}}K(x). \end{aligned} \end{aligned}$$

Suppose there exists a coefficient $g_{l,{j-1}}$ of the polynomial $g_{j-1}(x)$ such that $g_{l,{j-1}} \not \equiv 0\ (\mathrm{{mod}}\ {p^{i_{j-1}}}).$ Multiplying both sides by $p^{a-i_j}$ we get, $p^{a-i_{j-1}}g_{j-1}(x)=0,$ a contradiction. Thus $g_{j-1}(x)=p^{i_{j-1}}h_{j-1}(x),$ where $h_{j-1}(x)$ is a monic polynomial. Therefore by principle of mathematical induction (2) holds for all j.

Next, for $1\le k\le a-1,$ consider the maps

$$\psi _k: GR(p^a,m) \longrightarrow GR(p^k,m)$$

defined by

$$\psi _k(\alpha ) = \alpha ~(\text {mod}\ p^k).$$

$\psi _k$ is a ring homomorphism for all k which can be extended to

$$\phi _k:GR(p^a,m)[x]/\bigl \langle x^n-1\bigr \rangle \longrightarrow GR(p^k,m)[x]/\bigl \langle x^n-1\bigr \rangle $$

by defining

$$\phi _k(c_0+ c_1x +\ldots + c_{n-1}x^{n-1})=\psi _k(c_0) + \psi _k(c_1)x +\ldots + \psi _k(c_{n-1})x^{n-1}.$$

From (1) and (2) we have

$$p^{i_{j+1}}h_j(x)\in \bigl \langle p^{i_{j+1}}h_{j+1}(x),p^{i_{j+2}}h_{j+2}(x),\ldots ,p^{i_e}h_e(x)\bigr \rangle ,$$

which implies

$$\begin{aligned} p^{i_{j+1}}h_j(x)=p^{i_{j+1}}h_{j+1}(x)F_{j+1}(x) + p^{i_{j+2}}h_{j+2}(x)F_{j+2}(x)+\ldots +p^{i_e}h_e(x)F_e(x), \end{aligned}$$

where $F_k(x) \in R_n$ for $j+1\le k\le e$. Therefore

$$\begin{aligned} \begin{aligned} p^{i_{j+1}} \bigl (h_j(x) - h_{j+1}(x)F_{j+1}(x)\bigr )&= p^{i_{j+2}}h_{j+2}(x)F_{j+2}(x)+\ldots +p^{i_e}h_e(x)F_e(x)\\&= p^{i_{j+2}}F(x), \end{aligned} \end{aligned}$$

where $F(x) = h_{j+2}(x)F_{j+2}(x)+\ldots +p^{{i_e}-{i_{j+2}}}h_e(x)F_e(x)$. Now

$$\begin{aligned} p^{i_{j+1}} \bigl (h_j(x) - h_{j+1}(x)F_{j+1}(x)- p^{i_{j+2}-i_{j+1}}F(x)\bigr )= 0. \end{aligned}$$

It follows that the power of p in each coefficient of the polynomial

$$h_j(x) - h_{j+1}(x)F_{j+1}(x) - p^{i_{j+2}-i_{j+1}}F(x)$$

is greater than or equal to $a-i_{j+1}.$ As $\bigl \langle p^{a-i_{j+1}}\bigr \rangle \subset \bigl \langle p^{i_{j+2}-{i_{j+1}}}\bigr \rangle ,$ the coefficients of the polynomial $h_j(x) - h_{j+1}(x)F_{j+1}(x)- p^{i_{j+2}-{i_{j+1}}}F(x)$ vanish mod $p^{i_{j+2}-{i_{j+1}}}$. Thus

$$\begin{aligned} \phi _{i_{j+2}-{i_{j+1}}}\bigl (h_j(x) - h_{j+1}(x)F_{j+1}(x)- p^{i_{j+2}-i_{j+1}}F(x)\bigr )= 0. \end{aligned}$$

As $\phi _{i_{j+2}-{i_{j+1}}}$ is a homomorphism, we have

$$\begin{aligned} \phi _{i_{j+2}-{i_{j+1}}}\bigl (h_j(x)\bigr ) = \phi _{i_{j+2}-{i_{j+1}}}\bigl (h_{j+1}(x)F_{j+1}(x)\bigr )+ \phi _{i_{j+2}-{i_{j+1}}}\bigl (p^{i_{j+2}-i_{j+1}}F(x)\bigr ) \end{aligned}$$

or

$$\begin{aligned} \phi _{i_{j+2}-{i_{j+1}}}\bigl (h_j(x)\bigr ) =\phi _{i_{j+2}-{i_{j+1}}}\bigl (h_{j+1}(x)F_{j+1}(x)\bigr ) \end{aligned}$$

which gives $h_{j+1}(x)|h_j(x)$ (mod $p^{i_{j+2}-{i_{j+1}}}$).    $\square$

Theorem 4

The set $\{g_0(x),g_1(x),\ldots , g_e(x)\}$ is a minimal strong Gröbner basis of C.

Proof

The result follows as an immediate consequence of Theorem 3 above and Theorem 3.2 of [14].    $\square$

Some examples of minimal strong Gröbner basis are given below.

Example 1

Let $G=\{g_0(x), g_1(x), g_2(x)\}$ where $g_j(x)=2^jh_j(x)$ for $0 \le j \le 2$ with $h_0(x)= x^3+x^2+x+1,$ $h_1(x)=x^2+1$ and $h_2(x)=x+1.$ Let C be the cyclic code of length 8 over $\mathbb {Z}_8$ generated by G. It is easy to see that $x+1|x^2+1$ over $\mathbb {Z}_2$ and $x^2+1|x^3+x^2+x+1$ over $\mathbb {Z}_4.$ Also, $4(x^2+1)\in \langle 4(x+1) \rangle$ and $2(x^3+x^2+x+1)\in \langle 2(x^2+1), 4(x+1)\rangle .$ Therefore by Theorem 3 above, G is a minimal strong Gröbner basis.

Example 2

Let $G_1=\{g_0(x), g_1(x)\}$ where $g_j(x)=2^jh_j(x)$ for $0 \le j \le 1$ with $h_0(x)= x^5+x^4+x^3+x^2+x+1$ and $h_1(x)=x^4+x^2+1.$ Let $C_1$ be the cyclic code of length 6 over $\mathbb {Z}_4$ generated by $G_1.$ Then $G_1$ is a minimal strong Gröbner basis.

Example 3

Let $G_2=\{g_0(x), g_1(x)\}$ where $g_j(x)=2^jh_j(x)$ for $0 \le j \le 1$ with $h_0(x)= x^3-1,$ $h_1(x)=x+1.$ Then $G_2$ is a minimal strong Gröbner basis for the cyclic code $C_2$ of length 6 over $\mathbb {Z}_4.$

Example 4

Let $G_3=\{g_0(x), g_1(x)\}$ where $g_j(x)=2^jh_j(x)$ for $0 \le j \le 1$ with $h_0(x)= x^3+x^2+x+1$ and $h_1(x)=x^2+1.$ Let $C_3$ be the cyclic code of length 4 over $\mathbb {Z}_4$ generated by $G_3.$ Then $G_3$ is a minimal strong Gröbner basis.

Example 5

Let $G_4=\{g_0(x), g_1(x)\}$ where $g_j(x)=2^jh_j(x)$ for $0 \le j \le 1$ with $h_0(x)= x^2+1$ and $h_1(x)=x+1.$ Then $G_4$ is a minimal strong Gröbner basis for the cyclic code $C_4$ of length 4 over $\mathbb {Z}_4.$

4 Conclusion

A cyclic code of arbitrary length n over a Galois ring of characteristic $p^a$ is generated by at most $min\{a, t+1\}$ elements, where $t=max\{deg(g(x))\},$ g(x) a generator. Moreover, the set of generators so obtained is a minimal strong Gröbner basis of the code.