Stopping Sets of Algebraic Geometry Codes over Hyperelliptic Curves of Genus Two

1. Introduction

Stopping sets and stopping set distribution of a linear code play an important role in analyzing the performance of the code under an iterative decoding algorithm over an erasure channel [1,2].

Let C be an $[n, k, d]$ linear code over $F_{q}$ with length n, dimension k, and minimum distance d, with H being an $r \times n$ parity check matrix of C, i.e., $c H^{T} = 0$ for all codewords $c \in C$ . Let S be a set of column indices of H. We say that S is a stopping set of C if the $r \times | S |$ matrix, formed from H deleting those columns with indices not in S, does not have a row of weight one. The stopping set distribution is the sequence ${T_{i} (H)}_{i = 1}^{n}$ , with $T_{i} (H)$ being the number of stopping sets of size i.

Recently, many researchers have studied the stopping sets and stopping set distribution [1,3,4,5,6,7], with a comprehensive review given in [8]. The importance of studying stopping sets is that the performance of any linear code under iterative decoding on the binary erasure channel (BEC) is completely determined by stopping sets [1]. Even though iterative decoding is best suited to codes defined by spare matrices (low-density parity-check (LDPC) codes), the algorithm itself can be applied to any linear code, including Hamming codes [3], Reed–Muller codes [9], the simplex and Hamming codes [10], and algebraic geometry codes.

The study of stopping sets of algebraic geometry codes was first introduced by Zhang, Fu, and Wan [11]. They studied algebraic geometry codes with a special parity check matrix

H^{*}

, whose rows are, precisely, the nonzero codewords of the dual code, and they used Riemann–Roch spaces to determine whether a set of column indices of

H^{*}

is a stopping set. They applied these results to the case of algebraic geometry codes from the rational function field corresponding to genus

g = 0

(i.e., generalized Reed–Solomon codes) and algebraic geometry codes from the elliptic function field corresponding to genus

g = 1

For Reed–Solomon codes (and MDS codes in general), the authors of [11] gave a complete classification for stopping sets based on their cardinalities.

Proposition 1

([11], Proposition 2). Let C be an

[n, k, n - k + 1]

MDS code (i.e., the minimum distance equal to

n - k + 1

) and

S \subseteq 1, 2, \dots, n

be a set of column indices of

H^{*}

. Then,

(a): If $| S | \geq n - k + 1$ , then S is a stopping set;
(b): If $0 < | S | \leq n - k$ , then S is not a stopping set.

For algebraic geometry codes (AG codes) from an elliptic curve, the authors of [11] gave a characterization of stopping sets based on the cardinality of the set, as well as the group structure of the set of rational points on an elliptic curve.

Anderson and Gretchen [12] generalized the results of [11] for general parity check matrix H and they considered the stopping sets of the Hermitian codes. In the absence of a group structure on the points of the curve, they relied on the explicit bases for Riemann–Roch spaces and information on the Weierstrass semigroup.

Recently, Tenório and Tizziotti [13] considered stopping sets of one-point and m-point algebraic geometry codes defined by a certain family of curves,

X_{f, g}

, with a plane model of the form

f (y) = g (x)

, where many notable algebraic curves arise from this family, including the Hermitian curve, norm-trace curve, curves defined by the Kummer extension, etc. As in [12], the authors of [13] used the knowledge of the Weierstrass semigroup of m-tuple of rational points on

X_{f, g}

determined in [14] to study the stopping sets of these algebraic geometry codes arising from this family of curves,

X_{f, g}

In this paper, we consider stopping sets of one-point algebraic geometry codes defined by a hyperelliptic curve of genus

g = 2

defined by the plane model

y^{2} = f (x)

, where the degree of

f (x)

is 5. Many papers were devoted to studying such curves; for example, in [15], information about the curve is given for

g = 2

and for the general hyperelliptic curve of genus g in [13]. In [16], the authors gave an explicit way for determining a basis of the Riemann–Roch space

L (P_{1} + P_{2} + \dots + P_{j} + (n - j) ω)

, for

P_{i}

’s are points on the curve distinct from the Weierstrass point at infinity

ω

The choice for algebraic geometry code with $g = 2$ is due to the fact that the properties of the underlying hyperelliptic curve are well known, for example, the ramified places, the canonical divisors, and the evaluation of functions at the rational divisors and their extensions.

We use the results in [11,12] to completely classify the stopping sets of the one-point algebraic geometric codes

C = C_{Ω} (D, m P_{\infty})

defined by a hyperelliptic curve of genus 2 with

m \leq 4

. For

m = 3

, we prove in detail that all sets

S \subseteq 1, 2, \dots, n

of a size greater than 3 are stopping sets and we give an example of sets of size

2, 3

that are not. For such codes, the same proof can also be extended to the case in which

m = 4

. For

m \geq 5

, we show that it needs to be studied case by case, as we prove that there exists a hyperelliptic curve of genus 2 with five rational places other than the point at infinity, which gives an algebraic geometry code that is not as strongly defined as

\deg (G) \geq n

This paper is organized as follows. Section 2 gives some background information on stopping sets and algebraic geometry codes. The main results on stopping sets from algebraic geometry codes defined by hyperelliptic curves of genus 2 are presented in Section 3. In Section 4, examples of such codes and stopping sets are presented and the conclusions are presented in Section 5.

2. Stopping Sets of Algebraic Geometry Codes

Information about the stopping sets from algebraic geometry codes can be revealed from the structure of the underlying code; as in [11], the dimension of Riemann–Roch spaces can be used to determine whether a set is a stopping set. In this section, we review the results in [11,12] regarding the stopping sets from algebraic geometry codes.

Let C be an $[n, k, d]$ -linear code over $F_{q}$ with a parity check matrix H (i.e., $c H^{T} = 0$ , for all $c \in C$ ) and let $[n] : = 1, 2, \dots, n$ . Given an $r \times n$ matrix H and $S \subseteq [n]$ , the column restriction of H to S, denoted by ${H |}_{S}$ , is the $r \times | S |$ matrix formed from H by deleting those columns of H indexed by the elements of $[n] ∖ S$ .

Definition 1.

A stopping set S of the code C with a parity check matrix H is a subset of $[n]$ , such that the column restriction of H to S does not contain a row of Hamming weight one.

Remark 1.

The stopping set depends on both the code and the choice of the parity check matrix H of the code. The notation in [12] was adopted and we use

C = Γ (H)

to denote a code C with the parity check matrix H.

Given a code C, let

H^{*}

be a matrix formed by all the nonzero codewords of the dual code

C^{⊥}

as rows. The stopping sets of algebraic geometry codes

Γ (H^{*})

were studied by Zhang, Fu, and Wan [11]. Anderson and Gretchen [12] extended some of the results in [11] to

Γ (H)

, where H is an arbitrary parity check matrix of C. It turns out, as in the proposition below, that determining the stopping sets of

C = Γ (H^{*})

allows us to find the stopping sets of

C = Γ (H)

, where H is an arbitrary parity check matrix C.

Proposition 2

([12], Propostion 2.1). If S is a stopping set of

Γ (H^{*})

, then S is a stopping set of

Γ (H)

for any parity check matrix H of C.

For algebraic geometry codes, we focus on the residue codes

C_{Ω} (D, G)

. We review next some definitions and notations of algebraic geometry codes based on the exposition in [15].

Let $F ∣ F_{q}$ be a global function field of genus g. Let $P_{F}$ be the set of places of F. Given a divisor $A = \sum_{p \in P_{F}} a_{P} \cdot P$ of F, set $v_{P} (A) : = a_{P}$ and the degree of A is given by $\sum_{p \in P_{F}} a_{P} \cdot \deg (P)$ . If $f \in F$ is a nonzero function, we write $v_{P} (f) : = v_{P} ((f))$ , where $(f)$ denotes the principal divisor of the function f.

For two divisors A and $A^{'}$ , we write $A^{'} \leq A$ if $v_{P} (A^{'}) \leq v_{P} (A)$ for all places $P \in P_{F}$ . We call a divisor A an effective divisor (positive divisor) if $v_{P} (A) \geq 0$ for all places $P \in P_{F}$ . The support of a divisor A is supp $(A) : = v_{P} (A) \neq 0$ .

The Riemann–Roch space of a divisor A is

$L (A) : = (f) + A \geq 0 .$

The dimension of

L (A)

is denoted by

ℓ (A)

and satisfies the Riemann–Roch Theorem,

$ℓ (A) = \deg (A) - g + 1 + ℓ (K - A),$

where K is a canonical divisor of degree $2 g - 2$ . If $\deg (A) \geq 2 g - 1$ , then we have

$ℓ (A) = \deg (A) - g + 1 .$

An algebraic geometry code (AG code), denoted by

C_{L} (D, G)

, is constructed using two divisors, G and

D = P_{1} + P_{2} + \dots + P_{n}

on F with disjoint support and

P_{i}^{'} s

are distinct rational places as follows:

$C_{L} (D, G) : = e v (f),$

where

$e v (f) : = (f (P_{1}), f (P_{2}), \dots, f (P_{n})) \in F_{q}^{n} .$

Let

C_{Ω} (D, G) = C_{L} {(D, G)}^{⊥}

be the dual of the algebraic geometry code. A parity check matrix for

C_{Ω} (D, G)

is a generator matrix for

C_{L} (D, G)

and is of the form

$(\begin{matrix} f_{1} (P_{1}) & \dots & f_{1} (P_{n}) \\ f_{2} (P_{1}) & \dots & f_{2} (P_{n}) \\ \dots & \dots & \dots \\ f_{k} (P_{1}) & \dots & f_{k} (P_{n}) \end{matrix})$

where the set $f_{1}, f_{2}, \dots, f_{k}$ spans $L (G)$ as an $F_{q}$ –vector space.

The following lemma ([12], Lemma 2.2) plays an important role in determining the stopping sets of algebraic geometry codes.

Lemma 1.

Let $C = C_{Ω} (D, G)$ be an algebraic geometry code of length n and let $S \subseteq [n]$ with parity check matrix H.

1.: If
$L (G - \sum_{j \in S} P_{j}) = L (G - \sum_{j \in S ∖ i} P_{j}) for all i \in S,$
then S is a stopping set of $Γ (H)$ .
2.: If S is a stopping set of $Γ (H)$ , then $e v (f)$ is not a row of H for any
$f \in L (G - \sum_{j \in S ∖ i} P_{j}) ∖ L (G - \sum_{j \in S} P_{j}) and i \in S .$

Proof.

Let $C = C_{Ω} (D, G)$ be a code of length n and $S \subseteq [n]$ with H being a parity check matrix of C.

Assume
$L (G - \sum_{j \in S} P_{j}) = L (G - \sum_{j \in S ∖ i} P_{j}) for all i \in S$
and suppose $S = S$ is not a stopping set. Then, ${H |}_{S}$ contains a row of weight one. Thus, there exists a function $f \in L (G)$ such that
$wt (f (P_{i_{1}}), f (P_{i_{2}}), \dots, f (P_{i_{| S |}})) = 1,$
so there exists $i \in S$ such that $f (P_{i}) \neq 0$ and $f (P_{j}) = 0$ for all $j \in S ∖ i$ . This means that $v_{P_{i}} (f) = 0$ and $v_{P_{j}} (f) > 0$ for all $j \in S ∖ i$ . So, we have
$(f) + G - \sum_{j \in S ∖ i} P_{j} \geq 0 but (f) + G - \sum_{j \in S} P_{j} ≱ 0,$
which is equivalent to
$0 \neq f \in L (G - \sum_{j \in S ∖ i} P_{j}) ∖ L (G - \sum_{j \in S} P_{j})$
for some $i \in S$ and that is a contradiction.
Assume that $S =$ is a stopping set and $e v (f)$ is a row of H, where
$0 \neq f \in L (G - \sum_{j \in S ∖ i} P_{j}) ∖ L (G - \sum_{j \in S} P_{j})$
for some $i \in S$ , so we have both
$v_{p_{j}} (f) > 0 and v_{P_{i}} (f) = 0 \to f (P_{j}) = 0 and f (P_{i}) \neq 0;$
thus, $wt (e v (f)) = 1$ , which cannot be a row in H as S is a stopping set.

□

We note here for the parity check matrix

H^{*}

, Lemma 1 will be reformulated as

$S is a stopping set of Γ (H^{*}) if and only if L (G - \sum_{j \in S} P_{j}) = L (G - \sum_{j \in S ∖ i} P_{j}) .$

(1)

The lemma above helps with determining whether a set is a stopping set based on the cardinality of a set as in the following proposition.

Proposition 3

([12], Propotion 2.3). Let

C = C_{Ω} (D, G)

be an algebraic geometry code of length n and let

S \subseteq [n]

with parity check matrix H.

1.: If $| S | \geq \deg (G) + 2$ , then S is a stopping set of $Γ (H)$ ;
2.: If $| S | \leq \deg (G) - 2 g + 1$ , then S is not a stopping set of $Γ (H)$ for any parity check matrix H of C that has a row given by $e v (f)$ , where
$f \in L (G - \sum_{j \in S ∖ i} P_{j}) ∖ L (G - \sum_{j \in S} P_{j}) for some i \in S .$

Proof.

Assume $| S | \geq \deg (G) + 2$ ; hence,
$\deg (G - \sum_{j \in S} P_{j}) = \deg (G) - | S | < 0 \to L (G - \sum_{j \in S} P_{j}) = 0$
and
$\deg (G - \sum_{j \in S ∖ i} P_{j}) = \deg (G) - (| S | - 1) \leq - 1 < 0 \to L (G - \sum_{j \in S ∖ i} P_{j}) = 0,$
so we have
$L (G - \sum_{j \in S ∖ i} P_{j}) = L (G - \sum_{j \in S} P_{j});$
hence, S is a stopping set by Lemma 1.
Assume $| S | \leq \deg (G) - 2 g + 1$ ; we have
$\deg (G - \sum_{j \in S ∖ i} P_{j}) > \deg (G - \sum_{j \in S} P_{j}) = \deg (G) - | S | \geq 2 g - 1 .$
So, by the Riemann–Roch theorem,
$\begin{matrix} ℓ (G - \sum_{j \in S} P_{j}) & = \deg (G - \sum_{j \in S} P_{j}) - g + 1 \\ = \deg (G) - | S | - g + 1 \\ \neq \deg (G) - | S | + 1 - g + 1 \\ = ℓ (G - \sum_{j \in S ∖ i} P_{j}), \end{matrix}$
so we have $L (G - \sum_{j \in S ∖ i} P_{j}) \neq L (G - \sum_{j \in S} P_{j})$ and the result follows from Lemma 1.

□

Remark 2.

In the special case of a parity check matrix $H^{*}$ , Proposition 3 will be given the following characterization:

1.: If $0 \leq | S | \leq \deg (G) - 2 g + 1$ , then S is not a stopping set;
2.: If $\deg (G) + 2 \leq | S | \leq n$ , then S is a stopping set.

Many research papers classified the sets S with cardinality between the two bounds, i.e.,

\deg (G) - 2 g \leq | S | \leq \deg (G) + 1

; for example, a complete classification was performed in [11] for Reed–Solomon codes (

g = 0

) and algebraic geometry codes constructed from elliptic curves (

g = 1

). A classification based on the gap numbers and Weierstrass semigroup was carried out in [12] for one-point Hermitian codes.

The following lemma, due to [11], gives another description of the stopping sets of algebraic geometry codes

C = Γ (H^{*})

using a canonical divisor of the function field. Combining this result with Proposition 2 and Lemma 1 produces useful results on stopping sets for algebraic geometry codes

C = Γ (H)

, for any parity check matrix H. In this paper, we use this lemma to study stopping sets for one-point algebraic geometry codes defined by a hyperelliptic curve of genus 2.

Lemma 2

([12], Lemma 2.4). Assume

S \subseteq [n]

and let

C = Γ (H)

be an algebraic geometry code with

C = C_{Ω} (D, G)

. Assume for all

i \in S

that there exists an effective divisor M with

P_{i} \notin Supp (M)

and a canonical divisor K such that

$M \sim K - G + \sum_{j \in S} P_{j};$

then, S is a stopping set.

3. Stopping Sets of Algebraic Geometry Codes from Hyperelliptic Curve of Genus Two

In this section, we study the stopping sets of algebraic geometry codes defined by hyperelliptic curves of genus 2. Let

F ∣ F_{q}

be a hyperelliptic curve defined over

F_{q}

by the plane model,

where $f (x)$ is a square-free polynomial of degree $5 = 2 g + 1$ with $[F : F_{q} (x)] = 2$ . In [15], the following information about this function field is presented:

The divisor $W : = {(x)}_{\infty}$ is a canonical divisor with $\deg (W) = 2$ and $1, x \subseteq L (W)$ ; hence, $ℓ (W) \geq 2$ ;
Let $P \in P_{F_{q}}$ with $P^{'} \in P_{F}$ being an extension of P; then, the ramification index $e (P^{'} ∣ P)$ is given by
$e (P^{'} ∣ P) = \frac{2}{\gcd (2, v_{P} (f))};$
The places $P \in P_{F_{q}}$ , which ramify in $F ∣ F_{q} (x)$ , are all the zeros of $f (x)$ and the pole of x; hence, if $f (x)$ decomposes into linear factors over $F_{q}$ , then exactly $6 = 2 g + 2$ places of $F_{q} (x)$ are ramified in $F ∣ F_{q} (x)$ (so the rest of the places of $F_{q} (x)$ will split);
Let $f (x) = p_{1} (x) \dots p_{s} (x) \in F_{q} [x]$ be the decomposition of $f (x)$ into distinct irreducible monic polynomials and let $P_{i}$ be the zero place of $p_{i} (x)$ and $P_{\infty}$ be the pole of x in $F_{q} (x)$ . Consider the extensions $P_{i}^{'}, P_{\infty}^{'}$ of $P_{i}, P_{\infty}$ ; then, we have
$\begin{matrix} v_{P_{i}} (f (x)) = 1 v_{P_{\infty}} (f (x)) = - 5 v_{P_{i}^{'}} (y) = 1 v_{P_{\infty}^{'}} (y) = - 5 . \end{matrix}$

Next, we apply the construction in [13] for the one-point algebraic geometry codes constructed from the hyperelliptic curve of genus 2. Let

C_{Ω} (D, m P_{\infty}^{'})

be the one-point algebraic geometry code. Since we are interested in strongly algebraic geometry codes, we have

2 < m < n

, so we consider first the case with

m = 3

Proposition 4.

The sets $S \subseteq [n]$ of a size greater than 3 of $C_{Ω} (D, 3 P_{\infty}^{'})$ are stopping sets for any parity-check matrix H.

Proof.

For $| S | \geq 5 = \deg (3 P_{\infty}^{'}) + 2$ , by Proposition 3, S is a stopping set.

Let $| S | = 4$ and $G = 3 P_{\infty}^{'}$ . The idea of the proof is to construct a function h that satisfies the hypothesis of Lemma 2 with zeros P of h in S. We proceed as follows:

(a): If P is a zero for $f (x)$ , then $h = y h^{'}$ ;
(b): If P is not a zero for $f (x)$ , we take $h^{'} = (x - α) h^{″}$ , where the place $(x - α)$ lies below P in $F_{q} (x)$ .

In this construction, we create a function h that has zeros in S and maybe more. In that case, we take $- M$ to be a divisor consisting of the sum of the remaining places minus the poles at infinity and, since $| S | = 4$ , M will be an effective divisor and satisfies the hypothesis of Lemma 2.

Now, we illustrate the idea above in the cases (a) and (b). We assume first that S does not contain any zero places of

f (x)

. Let

(x - α)

be the place that lies below

P_{α}^{'} \in S

, which split in F, so we have

$div (x - α) = P_{α}^{'} + P_{α}^{″} - 2 P_{\infty}^{'}$

and assume that $P_{α}^{″}$ is not in S with the same assumption for the rest of the places in S (assuming all places in S lie above a split place and the other split $P^{″}$ is not in S), we obtain that for $h = (x - α_{1}) (x - α_{2}) (x - α_{3}) (x - α_{4})$ the principal divisor of h is

$\begin{matrix} div (h) & = P_{α_{1}}^{'} + P_{α_{1}}^{″} - 2 P_{\infty}^{'} + P_{α_{2}}^{'} + P_{α_{2}}^{″} - 2 P_{\infty}^{'} + P_{α_{3}}^{'} + P_{α_{3}}^{″} - 2 P_{\infty}^{'} + P_{α_{4}}^{'} + P_{α_{4}}^{″} - 2 P_{\infty}^{'} \\ = \sum_{j \in S} P_{j} - 3 P_{\infty}^{'} + 2 P_{\infty}^{'} + \underset{- M}{\underset{︸}{(P_{α_{1}}^{″} + P_{α_{2}}^{″} + P_{α_{3}}^{″} + P_{α_{4}}^{″} - 7 P_{\infty}^{'})}} \\ = \sum_{j \in S} P_{j} - G + K - M . \end{matrix}$

If one $P^{″}$ was in S, we adjust M accordingly; hence, by Lemma 2, we conclude that S is a stopping set.

Now, the second case is when

P_{α}^{'}

is a zero of

f (x)

lying above

(x - α)

, i.e.,

$div (x - α) = 2 P_{α}^{'} - 2 P_{\infty}^{'};$

in that case, we take $f = y \cdot h$ , where h is a product of $(x - β)$ , where $β$ is not a zero of $f (x)$ . In that case,

$\begin{matrix} div (f) & = div (y) + div (h) \\ = \underset{︸}{zeros of f (x)} - 5 P_{\infty}^{'} + \underset{︸}{places of P_{α}^{'}} - t P_{\infty}^{'} \\ = \sum_{j \in S} P_{j} - P_{\infty}^{'} + \underset{- M}{\underset{︸}{(remaining places - t^{'} P_{\infty}^{'})}} \\ = \sum_{j \in S} P_{j} - G + K - M, \end{matrix}$

which, again using 2, shows that S is a stopping set. □

Remark 3.

The idea of the proof of Proposition 4 can be used to prove the same results for the case $G = 4 P_{\infty}^{'}$ . However, for $\deg (G) > 5$ , we need to consider the underlying function fields; as we will see in Example 4, some hyperellitic curves have only five rational points other than the infinite place.

In Example 3 in Section 4, we give an example of a set S of size 3, which is not a stopping set. However, we can classify the stopping sets of size 3 as in the following lemma:

Lemma 3.

if S corresponds to three places in F that lie over three distinct places in $F_{q} (x)$ , then S is a stopping set.

Proof.

Let S be a set corresponding to the places

P_{1}^{'}, P_{2}^{'}, P_{3}^{'}

, where each

P_{i}^{'}

lies over

P_{i}

and those

P_{i}

are distinct. Now, we have

$L (3 P_{\infty}^{'} - (P_{1}^{'} + P_{2}^{'} + P_{3}^{'})) = 0,$

and if $L (3 P_{\infty}^{'} - (P_{2}^{'} + P_{3}^{'})) \neq 0$ , then there exists a nonzero function h with $v_{P_{2}^{'}} (h), v_{P_{3}^{'}} (h) \geq 1$ , which means that both places are in support of h and, if these lie above different places in $F_{q}$ , then the principal divisor of h will contain $P_{2}^{'} + P_{2}^{″} + P_{3}^{'} + P_{3}^{″} - 4 P_{\infty}$ and that means that the pole order (i.e., $v_{P_{\infty}^{'}} (h)$ ) will exceed 3, which cannot be the case; thus, $L (3 P_{\infty}^{'} - (P_{2}^{'} + P_{3}^{'})) = 0$ and, by Lemma 1, S is a stopping set. □

Source link

Abdulla Eid www.mdpi.com

Greenberg News

Stopping Sets of Algebraic Geometry Codes over Hyperelliptic Curves of Genus Two

1. Introduction

2. Stopping Sets of Algebraic Geometry Codes

3. Stopping Sets of Algebraic Geometry Codes from Hyperelliptic Curve of Genus Two

Greenberg

1. Introduction

2. Stopping Sets of Algebraic Geometry Codes

3. Stopping Sets of Algebraic Geometry Codes from Hyperelliptic Curve of Genus Two

Related Posts

Trump’s second term is already derailing food talks at COP29

Environmental Factor – October 2023: NIEHS publishes Climate Change and Human Health Glossary

Rhode Island offering $10M, hoping to install more than 100 electric vehicle chargers

Greenberg