Cyclic Generalized Separable (L, G) Codes

Abstract

A new class of cyclic generalized separable (L, G) codes is constructed.

1 Introduction

A classical Goppa code [1] is determined by two objects: a Goppa polynomial G(x) with coefficients from GF(q ^m) and location set L of codeword positions

$$\displaystyle{L =\{\alpha _{1},\alpha _{2},\ldots,\alpha _{n}\} \subseteq GF(q^{m}),G(\alpha _{ i})\neq 0,\;\forall \alpha _{i} \in L.}$$

Definition 1

A q-ary vector $\boldsymbol{a} = (a_{1}a_{2}\ldots a_{n})$ is a codeword of (L, G)-code if and only if the following equality is satisfied

$$\displaystyle{\sum \limits _{i=1}^{n}a_{ i} \frac{1} {x -\alpha _{i}} \equiv 0\mod G(x).}$$

Definition 2

Goppa code is called separable if the polynomial G(x) does not have multiple roots.

In [1] V.D. Goppa proved that the primitive BCH codes are the only subclass of Goppa codes that are cyclic with $G(x) = (x-\gamma )^{t},\gamma \in GF(q^{m}),L \subseteq GF(q^{m})\setminus \{\gamma \}.$ Accordingly, the only one class of separable Goppa codes with $G(x) = (x-\gamma ),\gamma \in GF(q^{m}),L \subseteq GF(q^{m})\setminus \{\gamma \}$ defined as cyclic.

In 1973 in [2] and later in [3–11] a subclasses of extended separable Goppa codes and subclasses of separable Goppa codes with Goppa polynomials of degree 2 and additional parity check were proposed. It was proved that these codes are cyclic. However, the existence among separable Goppa codes any subclass of cyclic codes remained an open problem ([12] Ch.12, Corollary 9, Research Problem 12.3).

In 2013 in [13] the subclass of cyclic separable Goppa codes with a special choice of location set L and and Goppa polynomial G(X) of degree 2 was suggested.

$$\displaystyle{ \begin{array}{l} L =\{\alpha _{1},\alpha _{2}\ldots,\alpha _{n-1},\alpha _{n}\} \subset \{ GF(q^{2m})\setminus GF(q^{m})\}\bigcup \{1\}, \\ \alpha _{n} = 1,\alpha _{i}^{q^{m} } =\alpha _{ i}^{-1} =\alpha _{n-i},n = q^{m} \pm 1, \\ G(x) = (x-\beta )(x -\beta ^{-1}),\;\beta \in GF(q^{2m}),\;\beta +\beta ^{-1} \in GF(q^{m}), \\ G(\alpha _{i})\neq 0,\alpha _{i}\neq \alpha _{j},\;\forall i,j \in \{ 1,\ldots,n\},\;i\neq j. \end{array} }$$

A generalized Goppa code [14] can be constructed by using the following generalization of location set L:

$$\displaystyle{ L = \left \{\frac{f'_{1}(x)} {f_{1}(x)}, \frac{f'_{2}(x)} {f_{2}(x)},\ldots, \frac{f'_{n}(x)} {f_{n}(x)}\right \}, }$$

(1)

where f′ _i (x) is a formal derivative of f _i (x) in GF(q) and

$$\displaystyle{\begin{array}{l} f_{i}(x) = x^{\ell} + a_{i,\ell-1}x^{\ell-1} +\ldots +a_{i,1}x + a_{i,0},a_{i,j} \in GF(q^{\mu }), \\ \gcd (f_{i}(x),f_{j}(x)) = 1,\;\gcd (f_{i}(x),G(x)) = 1,\;\forall i,j,\;i\neq j. \end{array} }$$

Definition 3

q-ary vector $\boldsymbol{a} = (a_{1}a_{2}\ldots a_{n})$ is a codeword of generalized (L, G)-code if and only if the following equality is satisfied

$$\displaystyle{ \sum \limits _{i=1}^{n}a_{ i}\frac{f'_{i}(x)} {f_{i}(x)} \equiv 0\mod G(x). }$$

(2)

Generalized Goppa codes have allowed to expand a class of cyclic Goppa codes with $G(x) = (x-\gamma )^{t}.$ Many cyclic (n, k, d) codes can be described as generalized Goppa codes [15] with

$$\displaystyle{\begin{array}{l} f_{i}(x) = f(\alpha ^{i}x),\;f(x) = x^{\ell} + a_{\ell-1}x^{\ell-1} +\ldots +a_{1}x + a_{0},\;\alpha,a_{j} \in GF(q^{\mu }), \\ a_{0}\neq 0,\alpha ^{n} = 1,\;n\vert (q^{\mu } - 1),\;\gcd (f_{i}(x),f_{j}(x)) = 1,\;\forall i,j,\;i\neq j\end{array} }$$

and

$$\displaystyle{G(x) = x^{t}.}$$

For such codes the design bound for minimum distance $d_{G} \geq \frac{t+1} {\ell}$ and the corresponding decoding algorithm were determined [16, 17]. However, a subclass of cyclic generalized separable Goppa codes is still remained limited by polynomial $G(x) = (x-\gamma ),\gamma \in GF(q^{\mu })$.

2 Two Subclasses of Binary Cyclic Generalized Separable Goppa Codes

In this paper we will consider a binary case with two variants of separable Goppa polynomial

$$\displaystyle{ G(x) = x^{n} - 1\text{ and }\hat{G}(x) = x(x^{n} - 1). }$$

(3)

We will need the following definitions.

Definition 4

For any integers n,  n | (2^m − 1) and l,  0 ≤ l < n a cyclotomic coset m _l is given by

$$\displaystyle{m_{l} =\{ l2^{j}\mod n,\forall j = 0,1,\ldots,\lambda _{ l} - 1\},}$$

where λ _l is the smallest integer greater than 0 such that $l2^{\lambda _{l}} \equiv l\mod n.$

Definition 5

The minimal polynomial M _l (x) of element α ^l ∈ GF(2^m) is given by

$$\displaystyle{M_{l}(x) =\prod \limits _{j\in m_{l}}(x -\alpha ^{j}),\;\deg M_{ l}(x) =\lambda _{l}.}$$

Definition 6

The generator polynomial of a cyclic (n, k, d) code C is given by

$$\displaystyle{g(x)\,=\,\prod \limits _{j\in D}(x -\alpha ^{j}),\;D\,=\,\bigcup \limits _{ j=1}^{\nu }m_{ l_{j}}\text{ and }g(x)\,=\,\prod \limits _{j=1}^{\nu }M_{ l_{j}}(x),\;\deg g(x)\,=\,\prod \limits _{j=1}\lambda _{l_{j}}\,=\,n - k,}$$

where D is the set containing the indices of the zeros of the generator polynomial g(x). The size of set D is equal to n − k.

For some D let’s consider a binary linear (η, κ, τ) code C _L with the length η, dimension κ, minimum distance τ and parity-check matrix H _L

$$\displaystyle{ H_{L} = \left [\begin{array}{ccc} \frac{\beta _{1}^{j_{1}}} {G(\beta _{1})} & \ldots & \frac{\beta _{\eta }^{j_{1}}} {G(\beta _{\eta })} \\ \frac{\beta _{1}^{j_{2}}} {G(\beta _{1})} & \ldots & \frac{\beta _{\eta }^{j_{2}}} {G(\beta _{\eta })}\\ \vdots & \ddots & \vdots \\ \frac{\beta _{1}^{j_{k}}} {G(\beta _{1})} & \ldots & \frac{\beta _{\eta }^{j_{k}}} {G(\beta _{\eta })} \end{array} \right ],\begin{array}{l} \beta _{i} \in GF(2^{\mu })\setminus \{0,1\},\;GF(2^{\mu }) \cap GF(2^{m}) =\{ 0,1\}, \\ N =\{ j_{1},j_{2},\ldots,j_{k}\},N \cup D =\{ 0,1,\ldots,n - 1\}. \end{array} }$$

(4)

Let $\mathbf{b} = (\begin{array}{lllllll} b_{1} & b_{2} & \ldots & b_{\tau }&b_{\tau +1} & \ldots & b_{\eta }) \end{array} \text{ with }b_{i} = 1,\forall i = 1,\ldots \tau \text{ and }b_{i} = 0,\forall i =\tau +1,\ldots,\eta$ be a codeword of this code. Then for this vector b and parity-check matrix H _L we obtain

$$\displaystyle{ \mathbf{b} \cdot H^{T} = 0\text{ and }\sum \limits _{ i=1}^{\eta }b_{ i} \frac{\beta _{i}^{j_{l}}} {G(\beta _{i})} =\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{j_{l}}} {G(\beta _{i})} = 0,\forall l = 1,\ldots,k. }$$

(5)

As in [17] we will call C _L as non-zero-locator code for cyclic code C with the set D if for any m _i  ⊂ D exists $j: j \in m_{i},\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{j}} {G(\beta _{i})}\neq 0$. We associate with codeword b of this non-zero-locator code C _L the following locator polynomial

$$\displaystyle{ \begin{array}{l} f(x) = (x -\beta _{1})(x -\beta _{2})\cdots (x -\beta _{\tau }),\;\beta _{j} \in GF(2^{\mu }),\;j = 1,\ldots,\tau, \\ f_{i}(x) = (x -\alpha ^{i}\beta _{1})(x -\alpha ^{i}\beta _{2})\cdots (x -\alpha ^{i}\beta _{\tau }),\;\alpha \in GF(2^{m}),\;\alpha ^{n} = 1, \\ \gcd (f_{i}(x),f_{j}(x)) = 1,\;\forall i\neq j,\;\;i,j = 1,\ldots,n. \end{array} }$$

(6)

Theorem 7

Generalized (L,G) code with Goppa polynomial G(x) (3) and locator set L (1) defined by non-zero-locator code C _L (4),(5) and by associated locator polynomial f(x) (6) is a cyclic code C with the set D of indices of zeroes of generator polynomial.

Proof

Parity-check matrix H _G for this code is:

$$\displaystyle{ \begin{array}{l} H_{G} = \left [\begin{array}{ccc} \alpha _{1}^{\ell_{1}}\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{\ell_{1}}} {G(\beta _{i})}&\ldots &\alpha _{n}^{\ell_{1}}\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{\ell_{1}}} {G(\beta _{i})} \\ \alpha _{1}^{\ell_{2}}\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{\ell_{2}}} {G(\beta _{i})}&\ldots &\alpha _{n}^{\ell_{2}}\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{\ell_{2}}} {G(\beta _{i})}\\ \vdots &\ddots & \vdots \\ \alpha _{1}^{\ell_{\delta }}\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{\ell_{\delta }}} {G(\beta _{i})} &\ldots & \alpha _{n}^{\ell_{\delta }}\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{\ell_{\delta }}} {G(\beta _{i})} \end{array} \right ] = \left [\begin{array}{ccc} \alpha _{1}^{\ell_{1}}&\ldots &\alpha _{n}^{\ell_{1}} \\ \alpha _{1}^{\ell_{2}}&\ldots &\alpha _{n}^{\ell_{2}} \\ \vdots &\ddots& \vdots\\ \alpha _{ 1}^{\ell_{\delta }} &\ldots & \alpha _{ n}^{\ell_{\delta }} \end{array} \right ], \\ \text{where }\{\ell_{1},\ell_{2},\ldots,\ell_{\delta }\} \subseteq D. \end{array} }$$

(7)

 □ 

Note 8

By Definition 6 dimension of this code is $k = n -\| D\|$, where $\|D\|$ is a size of the set D.

For the case $\hat{G}(x) = x(x^{n} - 1)$ we will obtain a similar theorem.

Theorem 9

Generalized $(L,\hat{G})$ code with Goppa polynomial $\hat{G}(x)$ (3) and locator set L (1) defined by non-zero-code C _L (4),(5) is a cyclic code $\hat{C}$ with the set $\hat{D} \subseteq D \cup m_{-1}$ of indices of zeroes of generator polynomial.

Proof

Parity-check matrix $H_{\hat{G}}$ for this code is:

$$\displaystyle{ H_{\hat{G}} = \left [\begin{array}{ccc} \alpha _{1}^{-1}\sum \limits _{i=1}^{\tau } \frac{1} {G(\beta _{i})} & \ldots & \alpha _{n}^{-1}\sum \limits _{ i=1}^{\tau } \frac{1} {G(\beta _{i})} \\ \alpha _{1}^{\ell_{1}}\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{\ell_{1}}} {G(\beta _{i})} & \ldots & \alpha _{n}^{\ell_{1}}\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{\ell_{1}}} {G(\beta _{i})} \\ \alpha _{1}^{\ell_{2}}\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{\ell_{2}}} {G(\beta _{i})} & \ldots & \alpha _{n}^{\ell_{2}}\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{\ell_{2}}} {G(\beta _{i})}\\ \vdots & \ddots & \vdots \\ \alpha _{1}^{\ell_{\delta }}\sum \limits _{i=1}^{\tau } \frac{\beta _{i}^{\ell_{\delta }}} {G(\beta _{i})} & \ldots & \alpha _{n}^{\ell_{\delta }}\sum \limits _{ i=1}^{\tau } \frac{\beta _{i}^{\ell_{\delta }}} {G(\beta _{i})} \end{array} \right ] = \left \{\begin{array}{l} H_{G},\text{ if } - 1 \in D\text{ or }0 \in N, \\ \left [\begin{array}{c} \alpha _{1}^{-1}\ldots \alpha _{ n}^{-1} \\ H_{G} \end{array} \right ],\text{ if } - 1\notin D\text{ and }0\notin N. \end{array}\right. }$$

(8)

 □ 

Theorem 10

From (2) , (3) and (6) we obtain the following estimation for minimal distance of binary cyclic generalized separable Goppa code:

$$\displaystyle{d_{G} \geq \frac{2n + 1} {\tau } \text{ for }G(x) = x^{n} - 1}$$

and

$$\displaystyle{d_{\hat{G}} \geq \frac{2n + 3} {\tau } \text{ for }\hat{G}(x) = x(x^{n} - 1).}$$

3 Trace Non-zero-Locator Code

As example of non-zero-locator code let’s consider a binary linear code with length η, parity-check matrix

$$\displaystyle{ H_{L} = \left [\begin{array}{cccc} \frac{\beta ^{j_{1}}} {G(\beta )} & \frac{\beta ^{2j_{1}}} {G(\beta ^{2})} & \ldots & \frac{\beta ^{\eta j_{1}}} {G(\beta ^{\eta })} \\ \frac{\beta ^{j_{2}}} {G(\beta )} & \frac{\beta ^{2j_{2}}} {G(\beta ^{2})} & \ldots & \frac{\beta ^{\eta j_{2}}} {G(\beta ^{\eta })}\\ \vdots & \ddots & \vdots \\ \frac{\beta ^{j_{k}}} {G(\beta )} & \frac{\beta ^{2j_{k}}} {G(\beta ^{2})} & \ldots & \frac{\beta ^{\eta j_{k}}} {G(\beta ^{\eta })} \end{array} \right ],\;\;\begin{array}{l} \beta -\text{ primitive element in }GF(2^{\mu }), \\ tr(\beta ^{j_{i}}) = 0,\forall i = 1,\ldots,k, \\ N =\{ j_{1},j_{2},\ldots,j_{k}\}, \\ N \cup D =\{ 0,1,\ldots,n - 1\}. \end{array} }$$

(9)

and codeword

$$\displaystyle{\mathbf{b} = (b_{1}b_{2}\ldots b_{\eta }),wt(\boldsymbol{b}) =\mu \text{ and }b_{1} = b_{2} = b_{2^{2}} =\ldots = b_{2^{\mu -1}} = 1.}$$

Now we can rewrite matrix H _G  (7) in the following form

$$\displaystyle{ \begin{array}{l} H_{G} = \left [\begin{array}{ccc} \alpha _{1}^{\ell_{1}}tr\left ( \frac{\beta ^{\ell_{1}}} {G(\beta )}\right )&\ldots &\alpha _{n}^{\ell_{1}}tr\left ( \frac{\beta ^{\ell_{1}}} {G(\beta )}\right ) \\ \alpha _{1}^{\ell_{2}}tr\left ( \frac{\beta ^{\ell_{2}}} {G(\beta )}\right )&\ldots &\alpha _{n}^{\ell_{2}}tr\left ( \frac{\beta ^{\ell_{2}}} {G(\beta )}\right )\\ \vdots &\ddots & \vdots \\ \alpha _{1}^{\ell_{\delta }}tr\left ( \frac{\beta ^{\ell_{\delta }}} {G(\beta )}\right ) &\ldots & \alpha _{n}^{\ell_{\delta }}tr\left ( \frac{\beta ^{\ell_{\delta }}}{ G(\beta )}\right ) \end{array} \right ] = \left [\begin{array}{ccc} \alpha _{1}^{\ell_{1}}&\ldots &\alpha _{n}^{\ell_{1}} \\ \alpha _{1}^{\ell_{2}}&\ldots &\alpha _{n}^{\ell_{2}} \\ \vdots &\ddots& \vdots\\ \alpha _{ 1}^{\ell_{\delta }} &\ldots & \alpha _{ n}^{\ell_{\delta }} \end{array} \right ], \\ \text{where }\;\;tr\left ( \frac{\beta ^{\ell_{i}}} {G(\beta )}\right )\neq 0,i = 1,\ldots,\delta,\;\;\{\ell_{1},\ell_{2},\ldots,\ell_{\delta }\} \subseteq D. \end{array} }$$

(10)

For such trace non-zero-locator code we have locator polynomial f(x) from (6):

$$\displaystyle{f(x) = (x-\beta )(x -\beta ^{2})\cdots (x -\beta ^{2^{\mu -1} }) =\varOmega _{1}(x),\;\varOmega _{1}(x) \in \mathbb{F}_{2}[x],\;\deg \varOmega _{1}(x) =\mu,}$$

Ω ₁(x) is a minimal polynomial of element β ∈ GF(2^μ).

From Theorem 10 we obtain the following estimation for minimal distance of binary cyclic generalized separable Goppa code with trace non-zero-locator code:

$$\displaystyle{d_{G} \geq \frac{2n + 1} {\mu } \text{ for }G(x) = x^{n} - 1}$$

and

$$\displaystyle{d_{\hat{G}} \geq \frac{2n + 3} {\mu } \text{ for }\hat{G}(x) = x(x^{n} - 1).}$$

4 Examples

• 1.
  $$\displaystyle{\begin{array}{l} n = 21,\hat{G}(x) = x(x^{21} - 1),\alpha \in GF(2^{6}),\alpha ^{21} = 1,\beta \in GF(2^{7}), \\ f(x) = x^{7} + x^{6} + x^{4} + x + 1,f_{i}(x) =\alpha ^{7i}x^{7} +\alpha ^{6i}x^{6} +\alpha ^{4i}x^{4} +\alpha ^{i}x + 1, \\ L =\{ \frac{x^{6}+1} {x^{7}+x^{6}+x^{4}+x+1}, \frac{\alpha ^{7}x^{6}+\alpha } {\alpha ^{7}x^{7}+\alpha ^{6}x^{6}+\alpha ^{4}x^{4}+\alpha x+1},\ldots, \frac{\alpha ^{14}x^{6}+\alpha ^{20}} {\alpha ^{14}x^{7}+\alpha ^{15}x^{6}+\alpha ^{17}x^{4}+\alpha ^{20}x+1}\}, \\ tr\left ( \frac{\beta ^{i}} {\hat{G}(\beta )}\right ) = 1,\;i = 0,3,4,6,7,12,14,21, \\ tr\left ( \frac{\beta ^{i}} {\hat{G}(\beta )}\right ) = 0,\;i = 1,2,5,8,9,10,11,13,15,16,17,18,19,20.\end{array} }$$

  Therefore from Theorem 9 we have (21, 6, 7) cyclic code with generator polynomial g(x) = m ₁(x)m ₃ m ₅(x). From Theorem 10 we obtain the following estimation for minimum distance for this generalized separable $(L,\hat{G})$ code:

  $$\displaystyle{d_{G} \geq \frac{2n + 3} {\mu } = \frac{45} {7}> 6\text{ and we have }d_{G} = d = 7.}$$
• 2.
  $$\displaystyle{\begin{array}{l} n = 21,\hat{G}(x) = x^{21} - 1,\alpha \in GF(2^{6}),\alpha ^{21} = 1,\beta \in GF(2^{7}), \\ f(x) = x^{7} + x^{6} + x^{4} + x^{2} + 1,f_{i}(x) =\alpha ^{7i}x^{7} +\alpha ^{6i}x^{6} +\alpha ^{4i}x^{4} +\alpha ^{2i}x^{2} + 1, \\ L =\{ \frac{x^{6}} {x^{7}+x^{6}+x^{4}+x^{2}+1}, \frac{\alpha ^{7}x^{6}} {\alpha ^{7}x^{7}+\alpha ^{6}x^{6}+\alpha ^{4}x^{4}+\alpha ^{2}x^{2}+1},\ldots, \frac{\alpha ^{14}x^{6}+\alpha ^{20}} {\alpha ^{14}x^{7}+\alpha ^{15}x^{6}+\alpha ^{17}x^{4}+\alpha ^{19}x^{2}+1}\}, \\ tr\left ( \frac{\beta ^{i}} {\hat{G}(\beta )}\right ) = 1,\;i = 2,3,5,6,11,13,20, \\ tr\left ( \frac{\beta ^{i}} {\hat{G}(\beta )}\right ) = 0,\;i = 0,1,4,7,8,9,10,12,14,15,16,17,18,19.\end{array} }$$

  From Eq. (10) and Theorem 7 we have (21, 6, 7) cyclic code with generator polynomial g(x) = m ₁(x)m ₃(x)m ₅(x). From Theorem 10 we obtain the following estimation for minimum distance for this generalized separable (L, G) code:

  $$\displaystyle{d_{\hat{G}} \geq \frac{2n + 1} {\mu } = \frac{43} {7}> 6\text{ and we have }d_{\hat{G}} = d = 7.}$$

5 Conclusion

The new subclasses of cyclic generalized separable Goppa codes with Goppa polynomials x ⁿ − 1 and x(x ⁿ − 1) are proposed. The parameters and examples of the codes from these subclasses are shown.