On Linear Perfect b-Symbol Codes over Finite Fields

Abstract

Motivated by the application of high-density data storage technologies, Cassuto and Blaum introduced codes for symbol-pair read channels in 2011, and Yaakobi et al. generalized the coding framework to that for b-symbol read channels where $b\ge 2$ in 2016. In this paper, we establish a b-sphere-packing bound and present a recurrence relationship for the b-weight enumerator. We determine all parameters of linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for $e<2b$ and show that for $2b\le e<3b$, there exist at most finite such codes for a given $b, e,$ and q. We construct a family of linear perfect b-symbol b-error-correcting codes over ${\mathbb{F}}_q$ using constacyclic codes.

1. Introduction

Motivated by the application of high-density data storage technologies, Cassuto and Blaum [1] proposed a new coding framework for symbol-pair read channels in 2011. In this framework, the reading from the channel is performed as overlapping pairs of symbols due to physical limitations, and the design object is to protect against pair errors rather than symbol errors.

Construction and decoding for symbol-pair codes and bounds on their sizes were further studied in [2,3,4]. Chee et al. [5,6] established a Singleton-like bound on symbol-pair codes and constructed some MDS symbol-pair codes meeting this bound from Mendelsohn designs. More MDS symbol-pair codes were constructed by Kai et al. [7] based on constacyclic codes.

Yaakobi et al. [8] generalized symbol-pair codes to b-symbol codes where $b\ge 2$ and provided extensions of some concepts and results in 2016. Subsequently, many MDS b-symbol codes were constructed in [9,10,11,12,13,14] through constacyclic codes, repeated-root cyclic codes, and projective geometry. Yang et al. [15] established a Plotkin-like bound and constructed some b-symbol codes on irreducible cyclic codes and constacyclic codes meeting this bound.

The symbol-pair sphere-packing bound was first presented in [1]. Cassuto and Litsyn [2] showed that cyclic binary Hamming codes are perfect symbol-pair codes. In [9], a constacyclic ${[q^2+q+1,q^2+q-2,5]}_q$ Hamming symbol-pair code was constructed and shown to be both MDS and perfect.

In 2018, Song et al. [16] established the sphere-packing bound and Gilbert–Varshamov bound for b-symbol codes. Chen [17] studied the covering radii of linear codes in the b-symbol metric, and many cyclic and algebraic-geometric codes were proved non-perfect in the b-symbol metric.

In this paper, we continue the investigation of perfect b-symbol codes. We establish a b-sphere-packing bound for linear b-symbol codes and study the existence of linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for $e<3b$. We determine all parameters of linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for $e<2b$ and show that for $2b\le e<3b$, there exist at most finite such codes for a given $b, e,$ and q. In particular, we construct a family of linear perfect b-symbol b-error-correcting codes over ${\mathbb{F}}_q$ using constacyclic codes.

This paper is organized as follows. Section 2 gives some preliminaries concerning b-symbol codes. The sphere-packing bound on b-symbol codes and the enumeration of b-spheres are presented in Section 3. In Section 4, we study the existence of linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for $e<3b$. Section 5 is the conclusion.

2. Preliminaries

Basic concepts and propositions related to linear codes over finite fields, the Hamming distance, and the Hamming weight can be found in Chapter 1 of [18].

Let $\mathsf{\Sigma }$ be an alphabet consisting of q elements and $b\ge 2$ be an integer. For a vector $\mathbf{x}=(x_0,x_1,\dots ,x_{n-1})\in {\mathsf{\Sigma }}^n$, the b-symbol read vector of $\mathbf{x}$ is defined as

$${\pi }_b\left(\mathbf{x}\right)=((x_0,x_1,\dots ,x_{b-1}),(x_1,x_2,\dots ,x_b),\dots ,(x_{n-1},x_0,\dots ,x_{b-2}))\in {\left({\mathsf{\Sigma }}^b\right)}^n.$$

For b-symbol vectors

$$\overleftrightarrow{u^{\left(i\right)}}=((u_{11}^{\left(i\right)},u_{12}^{\left(i\right)},\dots ,u_{1b}^{\left(i\right)}),(u_{21}^{\left(i\right)},u_{22}^{\left(i\right)},\dots ,u_{2b}^{\left(i\right)}),\dots ,(u_{n1}^{\left(i\right)},u_{n2}^{\left(i\right)},\dots ,u_{nb}^{\left(i\right)}))\in {\left({\mathsf{\Sigma }}^b\right)}^n$$

where $i=1,2$, the b-distance between $\overleftrightarrow{u^{\left(1\right)}}$ and $\overleftrightarrow{u^{\left(2\right)}}$ is defined as

$$D_b(\overleftrightarrow{u^{\left(1\right)}},\overleftrightarrow{u^{\left(2\right)}})=\left|\{1\le i\le n:(u_{i1}^{\left(1\right)},u_{i2}^{\left(1\right)},\dots ,u_{ib}^{\left(1\right)})\ne (u_{i1}^{\left(2\right)},u_{i2}^{\left(2\right)},\dots ,u_{ib}^{\left(2\right)})\}\right|,$$

where $(u_{i1}^{\left(1\right)},u_{i2}^{\left(1\right)},\dots ,u_{ib}^{\left(1\right)})=(u_{i1}^{\left(2\right)},u_{i2}^{\left(2\right)},\dots ,u_{ib}^{\left(2\right)})$ if $u_{ij}^{\left(1\right)}=u_{ij}^{\left(2\right)}$ for all $1\le j\le b$.

For notational aesthetics, we have

$$D_b(\mathbf{x},\overleftrightarrow{u})\triangleq D_b({\pi }_b\left(\mathbf{x}\right),\overleftrightarrow{u}),D_b(\mathbf{x},\mathbf{y})\triangleq D_b({\pi }_b\left(\mathbf{x}\right),{\pi }_b\left(\mathbf{y}\right)),$$

where $\mathbf{x},\mathbf{y}\in {\mathsf{\Sigma }}^n$. As in the Hamming case, ${\mathsf{\Sigma }}^n$ with the b-distance is a metric space.

The b-weight of $\mathbf{x}\in {\mathsf{\Sigma }}^n$ is defined as

$$w{t}_b\left(\mathbf{x}\right)=D_b(\mathbf{x},\mathbf{0}).$$

Throughout this paper, we consider $\mathsf{\Sigma }$ to be the finite field ${\mathbb{F}}_q$, with q a prime power, and $\mathcal{C}\subseteq {\mathbb{F}}_q^n$ to be a linear code of length n and dimension k over ${\mathbb{F}}_q$.

Proposition 1.

For all $\mathbf{x},\mathbf{y}\in {\mathbb{F}}_q^n$, $D_b(\mathbf{x},\mathbf{y})=w{t}_b(\mathbf{x}-\mathbf{y})$.

Proposition 2

([12]). For all $\mathbf{x}\in {\mathbb{F}}_q^n$ such that $0<w{t}_H\left(\mathbf{x}\right)\le n-(b-1)$,

$$w{t}_H\left(\mathbf{x}\right)+b-1\le w{t}_b\left(\mathbf{x}\right)\le b·w{t}_H\left(\mathbf{x}\right).$$

The minimum b-distance of a code $\mathcal{C}$ is defined as

$$d_b=min\{D_b(\mathbf{x},\mathbf{y}):\mathbf{x},\mathbf{y}\in \mathcal{C},\mathbf{x}\ne \mathbf{y}\}.$$

Since $\mathcal{C}$ is linear, we have

Proposition 3.

$d_b=min\{w{t}_b\left(\mathbf{x}\right):\mathbf{x}\in \mathcal{C},\mathbf{x}\ne \mathbf{0}\}$.

Referring to these propositions, we have

Corollary 1.

For a linear code $\mathcal{C}$ over ${\mathbb{F}}_q$ with $d_H\left(\mathcal{C}\right)>0$,

$$min\{d_H\left(\mathcal{C}\right)+b-1,n\}\le d_b\left(\mathcal{C}\right)\le b·d_H\left(\mathcal{C}\right).$$

Let $\mathbf{x}\in {\mathbb{F}}_q^n$. In the b-symbol sense, a b-symbol vector $\overleftrightarrow{u}\in {\left({\mathbb{F}}_q^b\right)}^n$ is the result of an e-error from $\mathbf{x}$ if $D_b(\mathbf{x},\overleftrightarrow{u})\le e$. A code $\mathcal{C}$ is an e-error-correcting code if no $\overleftrightarrow{u}$ is the result of an e-error from both $\mathbf{x}$ and $\mathbf{y}$ for some $\mathbf{x}\ne \mathbf{y}\in \mathcal{C}$.

Proposition 4.

A code $\mathcal{C}$ is an e-error-correcting code if and only if $d_b\ge 2e+1$.

Proof. 

This follows from the fact that ${\mathbb{F}}_q^n$ with the b-distance is a metric space. □

3. Sphere-Packing Bound and b-Spheres

Let $\mathbf{x}\in {\mathbb{F}}_q^n$. We define the b-sphere $S_r^{n,b,q}\left(\mathbf{x}\right)$ of radius r as the set of all $\mathbf{y}\in {\mathbb{F}}_q^n$ such that $D_b(\mathbf{x},\mathbf{y})=r$ and the b-ball $B_r^{n,b,q}\left(\mathbf{x}\right)$ of radius r as the set of all $\mathbf{y}\in {\mathbb{F}}_q^n$ such that $D_b(\mathbf{x},\mathbf{y})\le r$.

Since $\mathbf{x}$ is in ${\mathbb{F}}_q^n$, $|S_r^{n,b,q}\left(\mathbf{x}\right)|$ and $|B_r^{n,b,q}\left(\mathbf{x}\right)|$ do not rely on the selection of $\mathbf{x}$. Hence, we denote $|S_r^{n,b,q}\left(\mathbf{x}\right)|=f_r^{b,q}\left(n\right)$ and $|B_r^{n,b,q}\left(\mathbf{x}\right)|=g_r^{b,q}\left(n\right)$.

For a linear b-symbol e-error-correcting code $\mathcal{C}$ of length n and dimension k over ${\mathbb{F}}_q$, since there are $q^k$ disjoint b-balls of radius e, we can establish a b-sphere-packing bound if we can enumerate $g_r^{b,q}\left(n\right)$.

Definition 1.

For a word $\mathbf{x}\in {\mathbb{F}}_q^n$, suppose that $w{t}_H\left(\mathbf{x}\right)=l$. The remaining $n-l$ indices $\{i:x_i=0\}$ can be uniquely partitioned into a union of its subsets such that each subset consists of consecutive numbers $j,j+1,\dots ,j+h-1$ modulo n for some $j,h$, and $x_{j-1},x_{j+h}\ne 0$. Suppose that there are $c_i$ of these subsets in the partition with an exact cardinality of i for $i=1,2,\dots ,b-2$, and c of them have a cardinality of no less than $b-1$. Then, we say that $\mathbf{x}$ is an $(l;c_1,\dots ,c_{b-2},c)$-word, in the b-symbol sense.

Now, we calculate the b-weight of an $(l;c_1,\dots ,c_{b-2},c)$-word.

Proposition 5.

Suppose that $\mathbf{x}$ is an $(l;c_1,\dots ,c_{b-2},c)$-word; then, we have

$$w{t}_b\left(\mathbf{x}\right)=l+\sum _{i=1}^{b-2}i{c}_i+(b-1)c.$$

Proof. 

By the definition of the b-weight,

$$w{t}_b\left(\mathbf{x}\right)=n-\left|\{0\le i\le n-1:x_i=x_{i+1}=\dots =x_{i+b-1}=0\}\right|,$$

where the indices may wrap around modulo n. The indices of b consecutive zeros must belong to one of the c subsets which have a cardinality of no less than $b-1$ in the partition of zeros of $\mathbf{x}$. On the other hand, each $A_j$ of these c subsets contributes $|A_j|-(b-1)$ of indices i such that $x_i=x_{i+1}=\dots =x_{i+b-1}=0$. Hence, we have

$$\begin{array}{cc}\hfill w{t}_b\left(\mathbf{x}\right)=& n-\left|\right\{0\le i\le n-1:x_i=x_{i+1}=\dots =x_{i+b-1}=0\left\}\right|\hfill \\ \hfill =& n-\sum _{j=1}^c\left[\right|A_j|-(b-1)]\hfill \\ \hfill =& n-\sum _{j=1}^c\left|A_j\right|+(b-1)c\hfill \\ \hfill =& l+\sum _{i=1}^{b-2}i{c}_i+(b-1)c.\hfill \end{array}$$

□

For example, the word $\mathbf{x}=(0,1,2,0,0,1,0,2,0,0,0,1,2,0)\in {\mathbb{F}}_3^{14}$ is a $(6;1,3)$-word in the three-symbol sense, and $w{t}_3\left(\mathbf{x}\right)=6+1·1+2·3=13$. The following theorem shows how many $(l;c_1,\dots ,c_{b-2},c)$-words there are.

Theorem 1.

The number of $(l;c_1,\dots ,c_{b-2},c)$-words $(l>0)$ in ${\mathbb{F}}_q^n$ is

$$\frac{n}{l}\left(\genfrac{}{}{0pt}{}{n-l-{\displaystyle \sum _{i=1}^{b-2}}i{c}_i-(b-1)c+c-1}{c-1}\right)\left(\genfrac{}{}{0pt}{}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+c}{c_1,c_2,\dots ,c_{b-2},c}\right)\left(\genfrac{}{}{0pt}{}{l}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+c}\right){(q-1)}^l.$$

Proof. 

We prove the theorem by the following five steps:

(1)

We sort all these $(l;c_1,\dots ,c_{b-2},c)$-words into several classes such that $\mathbf{x}$ and $\mathbf{y}$ are in the same class if and only if for some j, $x_i=y_{i+j}$ for all $i=0,1,\dots ,n-1$. For each of these classes, whether or not the cardinality is n, the exact $l/n$ of the words in the class satisfy $x_0\ne 0$. Hence, the exact $l/n$ of all $(l;c_1,\dots ,c_{b-2},c)$-words satisfies $x_0\ne 0$. For example, the two words $(1,0,1,0)$ and $(0,1,0,1)$ form a class, and $2/4$ of them, i.e., $(1,0,1,0)$, satisfy $x_0\ne 0$.

(2)

By Proposition 5, the c subsets $A_1,A_2,\dots ,A_c$, which have a cardinality of no less than $b-1$ in the partition of zeros of an $(l;c_1,\dots ,c_{b-2},c)$-word $\mathbf{x}$, contribute all $n-w{t}_b\left(\mathbf{x}\right)=n-l-{\sum }_{i=1}^{b-2}i{c}_i-(b-1)c$ indices i such that $x_i=x_{i+1}=\dots =x_{i+b-1}=0$. Consider the number of non-negative integer solutions $(X_1,X_2,\dots ,X_c)=\left(\right|A_1|-(b-1),|A_2|-(b-1),\dots ,|A_c|-(b-1))$ of the equation

$$X_1+X_2+\dots +X_c=n-l-\sum _{i=1}^{b-2}i{c}_i-(b-1)c,$$

or, equivalently, the number of positive integer solutions $(X_1^{\prime },X_2^{\prime },\dots ,X_c^{\prime })=(X_1+1,X_2+1,\dots ,X_c+1)$ of the equation

$$X_1^{\prime }+X_2^{\prime }+\dots +X_c^{\prime }=n-l-\sum _{i=1}^{b-2}i{c}_i-(b-1)c+c.$$

The latter is obviously $\left(\genfrac{}{}{0pt}{}{n-l-{\sum }_{i=1}^{b-2}i{c}_i-(b-1)c+c-1}{c-1}\right)$.

(3)

We then consider the order of the ${\sum }_{i=1}^{b-2}{c}_i+c$ subsets in the partition. Since we suppose that $x_0\ne 0$, no subset wraps around modulo n, and the number is simply $\left(\genfrac{}{}{0pt}{}{{\sum }_{i=1}^{b-2}{c}_i+c}{c_1,c_2,\dots ,c_{b-2},c}\right)$.

(4)

Now that the cardinalities and the order of these subsets have been determined, we just need to choose ${\sum }_{i=1}^{b-2}{c}_i+c$ from these l non-zeros and insert corresponding zeros after each of them. The number of possible choices is $\left(\genfrac{}{}{0pt}{}{l}{{\sum }_{i=1}^{b-2}{c}_i+c}\right)$.

(5)

Each of the l non-zeros has $(q-1)$ possible values.

Now, by the rule of product, the number of $(l;c_1,\dots ,c_{b-2},c)$-words is

$$\frac{n}{l}\left(\genfrac{}{}{0pt}{}{n-l-{\displaystyle \sum _{i=1}^{b-2}}i{c}_i-(b-1)c+c-1}{c-1}\right)\left(\genfrac{}{}{0pt}{}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+c}{c_1,c_2,\dots ,c_{b-2},c}\right)\left(\genfrac{}{}{0pt}{}{l}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+c}\right){(q-1)}^l.$$

□

Corollary 2.

The number of $(l;c)$-words $(l>0)$ in ${\mathbb{F}}_2^n$ is

$$\frac{n}{l}\left(\genfrac{}{}{0pt}{}{n-l-1}{c-1}\right)\left(\genfrac{}{}{0pt}{}{l}{c}\right).$$

Proof. 

Take $b=2$ and $q=2$ in Theorem 1. □

This corollary coincides with Theorem 8 in [1]. By these results, we can determine the size of b-spheres and b-balls.

Proposition 6.

The cardinality $f_r^{b,q}\left(n\right)$ of a b-sphere $S_r^{n,b,q}\left(\mathbf{x}\right)$$(r>0)$ is

$$\sum _{l+{\sum }_{i=1}^{b-2}i{c}_i+(b-1)c=r}\frac{n}{l}\left(\genfrac{}{}{0pt}{}{n-r+c-1}{c-1}\right)\left(\genfrac{}{}{0pt}{}{\sum _{i=1}^{b-2}{c}_i+c}{c_1,c_2,\dots ,c_{b-2},c}\right)\left(\genfrac{}{}{0pt}{}{l}{\sum _{i=1}^{b-2}{c}_i+c}\right){(q-1)}^l.$$

The cardinality $g_r^{b,q}\left(n\right)$ of a b-ball $B_r^{n,b,q}\left(\mathbf{x}\right)$ is $1+{\sum }_{i=1}^r{f}_i^{b,q}\left(n\right)$.

Finally, we establish the following bound.

Theorem 2

(b-Sphere-Packing Bound). For a linear b-symbol e-error-correcting code $\mathcal{C}$ of length n and dimension k over ${\mathbb{F}}_q^n$, we have

$$g_e^{b,q}\left(n\right)\le q^{n-k},$$

where $g_e^{b,q}\left(n\right)=1+{\sum }_{r=1}^e{f}_r^{b,q}\left(n\right)$ and $f_r^{b,q}\left(n\right)=$

$$\sum _{l+{\sum }_{i=1}^{b-2}i{c}_i+(b-1)c=r}\frac{n}{l}\left(\genfrac{}{}{0pt}{}{n-r+c-1}{c-1}\right)\left(\genfrac{}{}{0pt}{}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+c}{c_1,c_2,\dots ,c_{b-2},c}\right)\left(\genfrac{}{}{0pt}{}{l}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+c}\right){(q-1)}^l.$$

Proof. 

The $q^k$b-balls, each with a cardinality $g_e^{b,q}\left(n\right)$, are disjoint and contained in ${\mathbb{F}}_q^n$; hence, $q^k{g}_e^{b,q}\left(n\right)\le q^n$. □

The e-error-correcting code meeting this bound is called a perfect code, as in the Hamming case.

We set $W_n^{b,q}\left(x\right)=1+{\sum }_{r=1}^n{f}_r^{b,q}\left(n\right)x^r$ to be the b-weight enumerator of all words in ${\mathbb{F}}_q^n$; then, for a linear perfect b-symbol code $\mathcal{C}$, the following equation holds:

$$\sum _{\mathbf{x}\in \mathcal{C}}\sum _{\mathbf{y}\in B_e^{b,q}\left(\mathbf{x}\right)}{x}^{w{t}_b\left(\mathbf{y}\right)}=W_n^{b,q}\left(x\right).$$

Before studying the existence of perfect codes, we present another way to calculate $f_r^{b,q}\left(n\right)$. Note that for a given b and q, $f_r^{b,q}\left(n\right)$ is a polynomial of n, by the expression in Theorem 2.

Proposition 7.

For $n>b$, we have

$$f_r^{b,q}\left(n\right)=f_r^{b,q}(n-1)+(q-1)\sum _{i=1}^b{f}_{r-i}^{b,q}(n-i)-(q-1)\sum _{i=1}^{b-1}{f}_{r-i}^{b,q}(n-1-i).$$

Proof. 

For $r\le b$, the equation holds trivially. Now, we consider $r>b$.

For each $\mathbf{x}\in {\mathbb{F}}_q^m$ and $w{t}_b\left(\mathbf{x}\right)=r-i(i=0,1,\dots ,b)$, we have $w{t}_H\left(\mathbf{x}\right)\ge 1$. Suppose that

$$\begin{array}{cc}\hfill & x_0=x_1=\dots =x_{i-1}=0,x_i\ne 0,\hfill \\ \hfill & x_{m-1}=x_{m-2}=\dots =x_{m-j}=0,x_{m-j-1}\ne 0\hfill \end{array}$$

for some non-negative integers $i,j$. Then, we define $\alpha \left(\mathbf{x}\right)=i$ and $\beta \left(\mathbf{x}\right)=j$.

For each $\mathbf{x}\in {\mathbb{F}}_q^m$ and $w{t}_b\left(\mathbf{x}\right)=r$, we have $w{t}_H\left(\mathbf{x}\right)\ge 2$. Suppose that

$$\begin{array}{cc}\hfill & x_{m-1}=x_{m-2}=\dots =x_{m-j}=0,x_{m-j-1}\ne 0,\hfill \\ \hfill & x_{m-j-2}=x_{m-j-3}=\dots =x_{m-j-k-1}=0,x_{m-j-k-2}\ne 0\hfill \end{array}$$

for some non-negative integers $j,k$. Then, we define $\gamma \left(\mathbf{x}\right)=k$.

For example, if $\mathbf{x}=(0,1,0,0,1,0,0,1)$, then $\alpha \left(\mathbf{x}\right)=1$, $\beta \left(\mathbf{x}\right)=0$ and $\gamma \left(\mathbf{x}\right)=2$.

We divide the set $S_r^{n,b,q}\left(\mathbf{0}\right)$ into four parts:

$$\begin{array}{cc}\hfill A& =\{\mathbf{x}\in S_r^{n,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)\ge b\}\hfill \\ \hfill B& =\{\mathbf{x}\in S_r^{n,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)<b,\gamma \left(\mathbf{x}\right)<\alpha \left(\mathbf{x}\right)\}\hfill \\ \hfill C& =\{\mathbf{x}\in S_r^{n,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)<b,\gamma \left(\mathbf{x}\right)\ge \alpha \left(\mathbf{x}\right)\}\hfill \\ \hfill D& =\{\mathbf{x}\in S_r^{n,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)=0\}\hfill \end{array}$$

We divide the set $S_r^{n-1,b,q}\left(\mathbf{0}\right)$ into four parts:

$$\begin{array}{cc}\hfill A^{\prime }& =\{\mathbf{x}\in S_r^{n-1,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)\ge b-1\}\hfill \\ \hfill B^{\prime }& =\{\mathbf{x}\in S_r^{n-1,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)<b-1,\gamma \left(\mathbf{x}\right)<\alpha \left(\mathbf{x}\right)\}\hfill \\ \hfill C^{\prime }& =\{\mathbf{x}\in S_r^{n-1,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)<b-1,\gamma \left(\mathbf{x}\right)\ge \alpha \left(\mathbf{x}\right)\}\hfill \\ \hfill D^{\prime }& =\{\mathbf{x}\in S_r^{n-1,b,q}\left(\mathbf{0}\right):\beta \left(\mathbf{x}\right)=0,\alpha \left(\mathbf{x}\right)<b-1\}\hfill \end{array}$$

For $1\le i\le b-1$, we divide the set $S_{r-i}^{n-i,b,q}\left(\mathbf{0}\right)$ into four parts:

$$\begin{array}{cc}\hfill E_i& =\{\mathbf{x}\in S_{r-i}^{n-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge i,\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)\ge b\}\hfill \\ \hfill B_i& =\{\mathbf{x}\in S_{r-i}^{n-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge i,\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)<b\}\hfill \\ \hfill C_i& =\{\mathbf{x}\in S_{r-i}^{n-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\le i-2\}\hfill \\ \hfill D_i& =\{\mathbf{x}\in S_{r-i}^{n-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge i,\beta \left(\mathbf{x}\right)=0or\alpha \left(\mathbf{x}\right)=i-1\}\hfill \end{array}$$

For $i=b$, we divide the set $S_{r-b}^{n-b,b,q}\left(\mathbf{0}\right)$ into two parts:

$$\begin{array}{cc}\hfill C_b& =\{\mathbf{x}\in S_{r-b}^{n-b,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\le b-2\}\hfill \\ \hfill D_b& =\{\mathbf{x}\in S_{r-b}^{n-b,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge b-1\}\hfill \end{array}$$

For $1\le i\le b-1$, we divide the set $S_{r-i}^{n-1-i,b,q}\left(\mathbf{0}\right)$ into four parts:

$$\begin{array}{cc}\hfill E_i^{\prime }& =\{\mathbf{x}\in S_{r-i}^{n-1-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge i,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)\ge b-1\}\hfill \\ \hfill B_i^{\prime }& =\{\mathbf{x}\in S_{r-i}^{n-1-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge i,\beta \left(\mathbf{x}\right)\ge 1,\alpha \left(\mathbf{x}\right)+\beta \left(\mathbf{x}\right)<b-1\}\hfill \\ \hfill C_i^{\prime }& =\{\mathbf{x}\in S_{r-i}^{n-1-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\le i-2\}\hfill \\ \hfill D_i^{\prime }& =\{\mathbf{x}\in S_{r-i}^{n-1-i,b,q}\left(\mathbf{0}\right):\alpha \left(\mathbf{x}\right)\ge i,\beta \left(\mathbf{x}\right)=0,\alpha \left(\mathbf{x}\right)<b-1or\alpha \left(\mathbf{x}\right)=i-1\}\hfill \end{array}$$

We construct several maps:

$$\begin{array}{cc}\hfill \varphi :& (x_0,x_1,\dots ,x_{n-1})\mapsto (x_0,x_1,\dots ,x_{n-2})\hfill \\ \hfill \psi :& (x_0,x_1,\dots ,x_{n-1})\mapsto (x_0,x_1,\dots ,x_{n-2-\beta \left(\mathbf{x}\right)-\gamma \left(\mathbf{x}\right)},x_{n-\beta \left(\mathbf{x}\right)},x_{n-\beta \left(\mathbf{x}\right)+1},\dots ,x_{n-1})\hfill \\ \hfill \sigma :& (x_0,x_1,\dots ,x_{n-1})\mapsto (x_0,x_1,\dots ,x_{n-2-\alpha \left(\mathbf{x}\right)-\beta \left(\mathbf{x}\right)})\hfill \\ \hfill \tau :& (x_0,x_1,\dots ,x_{n-1})\mapsto (x_0,x_1,\dots ,x_{n-2-min\left\{\alpha \right(\mathbf{x}),\gamma (\mathbf{x}),b-1\}})\hfill \end{array}$$

For example, if we set $b=3$, then

$$\begin{array}{cc}\hfill & \varphi (0,0,1,2,0,1,0)=(0,0,1,2,0,1),\hfill \\ \hfill & \psi (0,1,0,1,2,1,0)=(0,1,0,1,2,0),\hfill \\ \hfill & \sigma (0,1,0,2,0,1,0)=(0,1,0,2),\hfill \\ \hfill & \tau (0,1,0,2,0,0,1)=(0,1,0,2,0).\hfill \end{array}$$

It is not hard to prove that

$$\begin{array}{cc}\hfill & \varphi :A\to A^{\prime },\hfill \\ \hfill & \varphi :E_i\to E_i^{\prime },i=1,2,\dots ,b-1\hfill \end{array}$$

are all well-defined one-to-one maps, and

$$\begin{array}{cc}\hfill & \psi :B\to \bigcup _{i=1}^{b-1}{B}_i,\psi :B^{\prime }\to \bigcup _{i=1}^{b-1}{B}_i^{\prime },\hfill \\ \hfill & \sigma :C\to \bigcup _{i=1}^b{C}_i,\sigma :C^{\prime }\to \bigcup _{i=1}^{b-1}{C}_i^{\prime },\hfill \\ \hfill & \tau :D\to \bigcup _{i=1}^b{D}_i,\tau :D^{\prime }\to \bigcup _{i=1}^{b-1}{D}_i^{\prime }\hfill \end{array}$$

are all well-defined $(q-1)$-to-1 maps. Thus, we have

$$\begin{array}{cc}\hfill & \left|A\right|=|A^{\prime }|,\hfill \\ \hfill & |E_i|=|E_i^{\prime }|,i=1,2,\dots ,b-1,\hfill \\ \hfill & \left|B\right|=(q-1)\sum _{i=1}^{b-1}|B_i|,\left|B^{\prime }\right|=(q-1)\sum _{i=1}^{b-1}|B_i^{\prime }|,\hfill \\ \hfill & \left|C\right|=(q-1)\sum _{i=1}^b|C_i|,\left|C^{\prime }\right|=(q-1)\sum _{i=1}^{b-1}|C_i^{\prime }|,\hfill \\ \hfill & \left|D\right|=(q-1)\sum _{i=1}^b|D_i|,\left|D^{\prime }\right|=(q-1)\sum _{i=1}^{b-1}|D_i^{\prime }|.\hfill \end{array}$$

Note that

$$\begin{array}{cc}\hfill & f_r^{b,q}\left(n\right)=\left|A\right|+\left|B\right|+\left|C\right|+\left|D\right|,\hfill \\ \hfill & f_r^{b,q}(n-1)=|A^{\prime }|+|B^{\prime }|+|C^{\prime }|+|D^{\prime }|,\hfill \\ \hfill & f_{r-i}^{b,q}(n-i)=|E_i|+|B_i|+|C_i|+|D_i|,i=1,2,\dots ,b-1,\hfill \\ \hfill & f_{r-b}^{b,q}(n-b)=|C_b|+|D_b|,\hfill \\ \hfill & f_{r-i}^{b,q}(n-1-i)=|E_i^{\prime }|+|B_i^{\prime }|+|C_i^{\prime }|+|D_i^{\prime }|,i=1,2,\dots ,b-1.\hfill \end{array}$$

Putting all these together, we have

$$f_r^{b,q}\left(n\right)=f_r^{b,q}(n-1)+(q-1)\sum _{i=1}^b{f}_{r-i}^{b,q}(n-i)-(q-1)\sum _{i=1}^{b-1}{f}_{r-i}^{b,q}(n-1-i).$$

□

The relationship between $f_r^{b,q}\left(n\right)$ gives a relationship between $W_n^{b,q}\left(x\right)$.

Theorem 3.

Suppose $b\ge 2$. For $n>b$, we have

$$W_n^{b,q}\left(x\right)=q{W}_{n-1}^{b,q}\left(x\right)+(q-1)\sum _{i=1}^b{x}^{i-1}(x-1)W_{n-i}^{b,q}\left(x\right).$$

Proof. 

Comparing the coefficients of $x^r$, the equation holds by Proposition 7. □

For example, we take $b=3$ and $q=3$. By this theorem, we have $W_5^{3,3}\left(x\right)=212x^5+20x^4+10x^3+1$; hence, $f_1^{3,3}\left(5\right)=f_2^{3,3}\left(5\right)=0$, $f_3^{3,3}\left(5\right)=10$, $f_4^{3,3}\left(5\right)=20$, and $f_5^{3,3}\left(5\right)=212$. The results coincide with Proposition 6.

4. Linear Perfect b-Symbol Codes for $e<3b$

For linear perfect b-symbol codes, $g_e^{b,q}\left(n\right)=q^{n-k}$. So far, we know that $g_e^{b,q}\left(n\right)$ is the sum of 1 and some $f_r^{b,q}\left(n\right)$, where each $f_r^{b,q}\left(n\right)$ is a polynomial of n. Now, we analyze the expression of $f_r^{b,q}\left(n\right)$ more carefully. When $e=n$, we have $g_e^{b,q}\left(n\right)=q^n$ and $k=0$, and the corresponding code is the trivial code. Hence, we suppose that $e<n$ from now on.

For each word in $B_e^{b,q}\left(\mathbf{0}\right)\backslash \left\{\mathbf{0}\right\}$, we have $l\ge c\ge 1$. Therefore, by Proposition 5, $e\ge l+(b-1)c\ge bc$, or $c\le \lfloor \frac{e}{b}\rfloor$. Note that each polynomial $f_r^{b,q}\left(n\right)$ of n has a degree of no more than c, and the sum $g_e^{b,q}\left(n\right)$ must be a polynomial of n with a degree of no more than $\lfloor \frac{e}{b}\rfloor$. On the other hand, there does exist a word with $c=0$ and $l=e-(b-1)c$; hence, $g_e^{b,q}\left(n\right)$ is a polynomial of n with degree $\lfloor \frac{e}{b}\rfloor$.

4.1. Linear Perfect b-Symbol Codes for $1\le e\le b-1$

In this case, $\lfloor \frac{e}{b}\rfloor =0$, and there is no possible c for a word in $B_e^{b,q}\left(\mathbf{0}\right)\backslash \left\{\mathbf{0}\right\}$; hence, $g_e^{b,q}\left(n\right)=1$ and $k=n$. The code $\mathcal{C}={\mathbb{F}}_q^n$ has a minimum b-distance b and is a perfect e-error-correcting code if and only if $e\le \lfloor \frac{b-1}{2}\rfloor$.

Theorem 4.

For $1\le e\le b-1$, linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ exist if and only if $1\le e\le \lfloor \frac{b-1}{2}\rfloor$. The parameters of these perfect codes are ${[n,n,b]}_q$.

4.2. Linear Perfect b-Symbol Codes for $e=b$

In this case, $\lfloor \frac{e}{b}\rfloor =1$. Hence, all words in $B_e^{b,q}\left(\mathbf{0}\right)\backslash \left\{\mathbf{0}\right\}$ satisfy $l=c=1$ and $c_i=0$ for $i=1,2,\dots ,b-2$, since $l+{\sum }_{i=1}^{b-2}i{c}_i+(b-1)c\le e$.

By Proposition 6, $g_e^{b,q}\left(n\right)=1+(q-1)n$. Let $1+(q-1)n=q^{n-k}$; thus, we have $n=\frac{q^r-1}{q-1}$ and $k=\frac{q^r-1}{q-1}-r$. Before we construct the corresponding perfect codes, we need the following lemma.

Lemma 1

([7], the BCH Bound for Constacyclic Codes). Let $\mathcal{C}$ be an ω-constacyclic code of length n over ${\mathbb{F}}_q$ with generating polynomial $g\left(x\right)$, where ω is a primitive t-th root of unity. Let δ be a primitive $nt$-th root of unity in an extension field of ${\mathbb{F}}_q$ such that ${\delta }^n=\omega$. If $g\left(x\right)$ has the elements $\{{\delta }^{1+ti}:i_0\le i\le i_0+d-1\}$ as its roots for some integer $i_0$, then $d_H\ge d+1$.

The basic idea of the following construction is from [12].

Theorem 5.

There exists a linear perfect ${[\frac{q^r-1}{q-1},\frac{q^r-1}{q-1}-r,2b+1]}_q$b-symbol b-error-correcting code over ${\mathbb{F}}_q$ for any $r\ge b+1$.

Proof. 

Let $n=\frac{q^r-1}{q-1}$; then, $n>1+(r-1)q\ge 1+bq\ge 1+2b$. Let $\omega$ be a primitive element of ${\mathbb{F}}_q$ and $\delta$ be a primitive element of ${\mathbb{F}}_q^r$ such that ${\delta }^n=\omega$. Note that $g\left(x\right)=(x-\delta )(x-{\delta }^q)\dots (x-{\delta }^{q^{r-1}})\in {\mathbb{F}}_q\left[x\right]$ divides $x^n-\omega$. Let $\mathcal{C}$ be the $\omega$-constacyclic code $\langle g\left(x\right)\rangle \subseteq {\mathbb{F}}_q\left[x\right]/(x^n-\omega )$. Then, $\mathcal{C}$ is a linear ${[\frac{q^r-1}{q-1},\frac{q^r-1}{q-1}-r,d_H]}_q$ code. By Lemma 1, $d_H\ge 3$.

Let $c\left(x\right)={\sum }_{i=0}^{n-1}{c}_i{x}^i$ be any non-zero codeword. If there exists a j such that

$$c_j=c_{j+1}=\dots =c_{j+b-2}=0,c_{j+b-1}\ne 0,$$

where the indices are the reduced modulo n, then we consider the codeword $c^{\prime }\left(x\right)=x^{n-j-b+1}$$c\left(x\right)={\sum }_{i=0}^{n-1}{c}_i^{\prime }{x}^i$. By the selection of j, we have

$$c_{n-1}^{\prime }=c_{n-2}^{\prime }=\dots =c_{n-b+1}^{\prime }=0,c_0^{\prime }\ne 0.$$

Suppose that

$$c_{n-1}^{\prime }=c_{n-2}^{\prime }=\dots =c_{t+1}^{\prime }=0,c_t^{\prime }\ne 0$$

for some $t\le n-b$. Since $g\left(x\right)\mid c^{\prime }\left(x\right)$, we have $t\ge r$. Consider the set

$$I=\{i:(c_i^{\prime },c_{i+1}^{\prime },\dots ,c_{i+b-1}^{\prime })\ne (0,0,\dots ,0)\},$$

where the indices are the reduced modulo n. The set I has at least $2b$ elements $t-b+1\le i\le t$ and $n-b+1\le i\le n$, since $t-b+1\ge r-b+1>0$; $n-b+1>n-b\ge t$; and $c_0^{\prime }\ne 0$, $c_t^{\prime }\ne 0$. If $\left|I\right|=2b$, then $(c_i^{\prime },c_{i+1}^{\prime },\dots ,c_{i+b-1}^{\prime })=(0,0,\dots ,0)$ for $1\le i\le t-b$, which means that $c_1^{\prime }=c_2^{\prime }=\dots =c_{t-1}^{\prime }=0$ and contradicts $d_H\ge 3$. Hence, $w{t}_b\left(c\left(x\right)\right)=w{t}_b\left(c^{\prime }\left(x\right)\right)=\left|I\right|\ge 2b+1$.

If there does not exist such a j, then $w{t}_b\left(c\left(x\right)\right)=n>2b+1$.

Hence, we always have $w{t}_b\left(c\left(x\right)\right)\ge 2b+1$ and $d_b\ge 2b+1$. On the other hand, the b-error-correcting code $\mathcal{C}$ meets the b-sphere-packing bound. Thus, $\mathcal{C}$ is a perfect code, and for the word $(1,1,0,0,\dots ,0)$, which has a b-weight $b+1$, there must be a codeword separated from it by a b-distance of no more than b. This codeword has a b-weight of no more than $2b+1$, and hence $d_b=2b+1$. □

Lemma 2

([12], b-Singleton Bound). Let $q\ge 2$ and $b\le d_b\le n$. If $\mathcal{C}$ is an ${(n,M,d_b)}_q$ b-symbol code, then we have $M\le q^{n-d_b+b}$.

Theorem 6.

For $e=b$, linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ exist. The parameters of all these perfect codes are ${[\frac{q^r-1}{q-1},\frac{q^r-1}{q-1}-r,2b+1]}_q$, where $r\ge b+1$.

Proof. 

By the discussion at the beginning of this subsection and Theorem 5, the only detail we need to prove is that $r\ge b+1$ must hold, which is exactly what the b-Singleton bound tells us. □

4.3. Linear Perfect b-Symbol Codes for $b+1\le e\le 2b-1$

In this case, $\lfloor \frac{e}{b}\rfloor =1$. Hence, all words in $B_e^{b,q}\left(\mathbf{0}\right)\backslash B_b^{b,q}\left(\mathbf{0}\right)$ satisfy $c=1$ and $l\ge 2$.

Theorem 7.

For $b+1\le e\le 2b-1$, $g_e^{b,q}\left(n\right)=1+q^{e-b}(q-1)n$.

Proof. 

By Proposition 6,

$$\begin{array}{cc}\hfill & g_e^{b,q}\left(n\right)-1-(q-1)n\hfill \\ \hfill =& \sum _{r=b+1}^e\sum _{l+{\sum }_{i=1}^{b-2}i{c}_i=r-b+1}\frac{n}{l}\left(\genfrac{}{}{0pt}{}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+1}{c_1,c_2,\dots ,c_{b-2},1}\right)\left(\genfrac{}{}{0pt}{}{l}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+1}\right){(q-1)}^l\hfill \\ \hfill =& \sum _{r=b+1}^e\sum _{l=2}^{r-b+1}\sum _{{\sum }_{i=1}^{b-2}i{c}_i=r-b+1-l}\left(\genfrac{}{}{0pt}{}{l-1}{c_1,c_2,\dots ,c_{b-2},l-1-{\displaystyle \sum _{i=1}^{b-2}}{c}_i}\right){(q-1)}^{l}n\hfill \end{array}$$

For a fixed r and l, the number of ways to insert $c_1$ 1-consecutive zeros, $c_2$ 2-consecutive zeros, …, $c_{b-2}$$(b-2)$-consecutive zeroes into l non-zeros is $\left(\genfrac{}{}{0pt}{}{l-1}{c_1,c_2,\dots ,c_{b-2},l-1-{\sum }_{i=1}^{b-2}{c}_i}\right)$. Note that $r-b+1-l\le 2b-1-b+1-2=b-2$, and the number of ways to insert $r-b+1-l$ zeros into l non-zeros is exactly

$$\sum _{{\sum }_{i=1}^{b-2}i{c}_i=r-b+1-l}\left(\genfrac{}{}{0pt}{}{l-1}{c_1,c_2,\dots ,c_{b-2},l-1-{\displaystyle \sum _{i=1}^{b-2}}{c}_i}\right).$$

On the other hand, this number is $\left(\genfrac{}{}{0pt}{}{r-b+1-l+l-2}{r-b+1-l}\right)=\left(\genfrac{}{}{0pt}{}{r-b-1}{l-2}\right)$. Thus, we have

$$\begin{array}{cc}\hfill g_e^{b,q}\left(n\right)=& 1+(q-1)n+\sum _{r=b+1}^e\sum _{l=2}^{r-b+1}\left(\genfrac{}{}{0pt}{}{r-b-1}{l-2}\right){(q-1)}^{l}n\hfill \\ \hfill =& 1+(q-1)n+\sum _{r=b+1}^e{q}^{r-b-1}{(q-1)}^{2}n\hfill \\ \hfill =& 1+q^{e-b}(q-1)n.\hfill \end{array}$$

□

Theorem 8.

For $b+1\le e\le 2b-1$, linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ do not exist.

Proof. 

By Theorem 7, $g_e^{b,q}\left(n\right)\equiv 1(modq)$ and hence cannot meet the b-sphere-packing bound. □

4.4. Linear Perfect b-Symbol Codes for $2b\le e\le 3b-1$

We present a general result first. The following lemma is a classical result, and the proof can be found in, for example, [19].

Lemma 3.

Let $f\left(x\right)$ be a polynomial with integer coefficients and at least two zeroes. When integer $x\to +\infty$, we have $P\to +\infty$, where P is the greatest prime factor of $f\left(x\right)$.

Theorem 9.

For $e\ge 2b$, there exist infinite linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for a given $b,e,$ and q only if $g_e^{b,q}\left(n\right)={(Kn+1)}^{\lfloor \frac{e}{b}\rfloor }$ for some integer K.

Proof. 

$g_e^{b,q}\left(n\right)$ is a polynomial with rational coefficients, and $deg\left(g_e^{b,q}\left(n\right)\right)=\lfloor \frac{e}{b}\rfloor \ge 2$. Consider the equation $g_e^{b,q}\left(n\right)=q^{n-k}$; we can rewrite it as $F\left(n\right)=C{q}^{n-k}$ such that $F\left(n\right)$ is a polynomial with integer coefficients and C is an integer. Since the greatest prime factor of $C{q}^{n-k}$ is a constant, the equation has infinite solutions only if $F\left(n\right)=C_0{(a_{0}n+b_0)}^{\lfloor \frac{e}{b}\rfloor }$, by Lemma 3.

Taking $n=0$, we have $C=C_0{b}_0^{\lfloor \frac{e}{b}\rfloor }$, since $g_e^{b,q}\left(0\right)=1$. Thus, $g_e^{b,q}\left(n\right)={(\frac{a_0}{b_0}n+1)}^{\lfloor \frac{e}{b}\rfloor }$. Taking $n=1$, we know that $\frac{a_0}{b_0}$ is an integer K, since $g_e^{b,q}\left(1\right)$ is an integer. The statement of the theorem follows. □

From now on, we focus on the case $2b\le e\le 3b-1$. In this case, $\lfloor \frac{e}{b}\rfloor =2$, and $g_e^{b,q}\left(n\right)$ is a quadratic function of n.

Theorem 10.

For $2b\le e\le 3b-1$, the coefficient of $n^2$ in $g_e^{b,q}\left(n\right)$ is

$$\frac{1}{2}[(e-2b)q^{e-2b-1}{(q-1)}^3+q^{e-2b}{(q-1)}^2].$$

Proof. 

In order to calculate the coefficient of $n^2$, we only need to consider those words satisfying $c=2$. By Proposition 6, this coefficient is

$$\begin{array}{cc}\hfill & \sum _{r=2b}^e\sum _{l+{\sum }_{i=1}^{b-2}i{c}_i=r-2b+2}\frac{1}{l}\left(\genfrac{}{}{0pt}{}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+2}{c_1,c_2,\dots ,c_{b-2},2}\right)\left(\genfrac{}{}{0pt}{}{l}{{\displaystyle \sum _{i=1}^{b-2}}{c}_i+2}\right){(q-1)}^l\hfill \\ \hfill =& \frac{1}{2}{(q-1)}^2+\hfill \\ \hfill & \frac{1}{2}\sum _{r=2b+1}^e\sum _{l=3}^{r-2b+2}\sum _{{\sum }_{i=1}^{b-2}i{c}_i=r-2b+2-l}(l-1)\left(\genfrac{}{}{0pt}{}{l-2}{c_1,c_2,\dots ,c_{b-2},l-2-{\displaystyle \sum _{i=1}^{b-2}}{c}_i}\right){(q-1)}^l\hfill \end{array}$$

Note that $r-2b+2-l\le 3b-1-2b+2-3=b-2$, and we have

$$\sum _{{\sum }_{i=1}^{b-2}i{c}_i=r-2b+2-l}\left(\genfrac{}{}{0pt}{}{l-2}{c_1,c_2,\dots ,c_{b-2},l-2-{\displaystyle \sum _{i=1}^{b-2}}{c}_i}\right)=\left(\genfrac{}{}{0pt}{}{r-2b-1}{l-3}\right)$$

by the same method we used to prove Theorem 7.

Thus, the coefficient is

$$\begin{array}{cc}\hfill & \frac{1}{2}{(q-1)}^2+\frac{1}{2}\sum _{r=2b+1}^e\sum _{l=3}^{r-2b+2}(l-1)\left(\genfrac{}{}{0pt}{}{r-2b-1}{l-3}\right){(q-1)}^l\hfill \\ \hfill =& \frac{1}{2}{(q-1)}^2+\frac{1}{2}\sum _{r=2b+1}^e\sum _{l=3}^{r-2b+2}(l-3)\left(\genfrac{}{}{0pt}{}{r-2b-1}{l-3}\right){(q-1)}^l+\hfill \\ \hfill & \sum _{r=2b+1}^e\sum _{l=3}^{r-2b+2}\left(\genfrac{}{}{0pt}{}{r-2b-1}{l-3}\right){(q-1)}^l\hfill \\ \hfill =& \frac{1}{2}{(q-1)}^2+\frac{1}{2}\sum _{r=2b+1}^e\sum _{l=4}^{r-2b+2}(r-2b-1)\left(\genfrac{}{}{0pt}{}{r-2b-2}{l-4}\right){(q-1)}^l+\hfill \\ \hfill & \sum _{r=2b+1}^e{q}^{r-2b-1}{(q-1)}^3\hfill \\ \hfill =& \frac{1}{2}{(q-1)}^2+\sum _{r=2b+1}^e[\frac{1}{2}(r-2b-1)q^{r-2b-2}{(q-1)}^4+q^{r-2b-1}{(q-1)}^3]\hfill \\ \hfill =& \frac{1}{2}[(e-2b)q^{e-2b-1}{(q-1)}^3+q^{e-2b}{(q-1)}^2]\hfill \end{array}$$

□

Theorem 11.

For $2b\le e\le 3b-1$, there exist at most finite linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for a given $b,e,$ and q.

Proof. 

By Theorems 9 and 10, we only need to consider the case $g_e^{b,q}\left(n\right)={(Kn+1)}^2$, and hence

$$\frac{1}{2}[(e-2b)q^{e-2b-1}{(q-1)}^3+q^{e-2b}{(q-1)}^2]=K^2.$$

for some integer K.

If $e=2b$, then $\frac{1}{2}{(q-1)}^2=K^2$, which is impossible.

If $e=2b+1$, then $\frac{1}{2}{(q-1)}^2(2q-1)=K^2$. Hence, $4q-2$ is a perfect square, which is also impossible.

If $e\ge 2b+2$, then $p\mid \frac{1}{2}[(e-2b)q^{e-2b-1}{(q-1)}^3+q^{e-2b}{(q-1)}^2]$, where q is a power of prime p. Hence, $p\mid K$, and $g_e^{b,q}\left(n\right)={(Kn+1)}^2\equiv 1(modp)$, which contradicts $g_e^{b,q}\left(n\right)=q^{n-k}$. □

5. Conclusions

In this paper, we established a b-sphere-packing bound and presented a recurrence relationship for the b-weight enumerator. We determined all parameters of linear perfect b-symbol e-error-correcting codes over ${\mathbb{F}}_q$ for $e<2b$ and showed that for $2b\le e<3b$, there exist at most finite such codes for a given $b, e,$ and q. A family of linear perfect b-symbol b-error-correcting codes over ${\mathbb{F}}_q$ was constructed using constacyclic codes.

So far, we have not found any perfect b-symbol e-error-correcting codes for $b<e<n$. New conditions for perfect b-symbol codes besides the b-sphere-packing bound may need to be established for a further study.

Most of our results stay true for a more general alphabet $\mathsf{\Sigma }$, such as ${\mathbb{Z}}_q$ with an arbitrary q. However, the construction using constacyclic codes does need $\mathsf{\Sigma }$ to be a finite field. Whether perfect b-symbol b-error-correcting codes exist for a q that is not a prime power is also unknown.