Abstract. The weight of a coset of a code is the smallest Hamming weight of any vector in the coset. For a linear code of length \(n\), we call integral weight spectrum the overall numbers of weight \(w\) vectors, \(0\le w\le n\), in all the cosets of a fixed weight. For maximum distance separable (MDS) codes, we obtained new convenient formulas of integral weight spectra of cosets of weight 1 and 2. Also, we give the spectra for the weight 3 cosets of MDS codes with minimum distance \(5\) and covering radius \(3\).

Keywords: cosets weight distribution, MDS codes.

Mathematics Subject Classication (2010). 94B05, 51E21, 51E22

1 Introduction↩︎

Let \(\mathbb{F}_{q}\) be the Galois field with \(q\) elements, \(\mathbb{F}_{q}^*=\mathbb{F}_{q}\setminus\{0\}\). Let \(\mathbb{F}_{q}^{n}\) be the space of \(n\)-dimensional vectors over \({\mathbb{F}}_{q}\). We denote by \([n,k,d]_{q}R\) an \(\mathbb{F}_q\)-linear code of length \(n\), dimension \(k\), minimum distance \(d\), and covering radius \(R\). If \(d=n-k+1\), it is a maximum distance separable (MDS) code. For an introduction to coding theory see [1]–[4].

A coset of a code is a translation of the code. A coset \(\mathcal{V}\) of an \([n,k,d]_{q}R\) code \(\mathcal{C}\) can be represented as \[\begin{align} \label{eq195coset} \mathcal{V}=\{\mathbf{x}\in\mathbb{F}_q^n\,|\,\mathbf{x}=\mathbf{c}+\mathbf{v},\mathbf{c}\in \mathcal{C}\}\subset\mathbb{F}_q^n \end{align}\tag{1}\] where \(\mathbf{v}\in \mathcal{V}\) is a vector fixed for the given representation; see [1]–[5] and the references therein.

The weight distribution of code cosets is an important combinatorial property of a code. In particular, the distribution serves to estimate decoding results. There are many papers connected with distinct aspects of the weight distribution of cosets for codes over distinct fields and rings, see e.g. [1], [6]–[19], [20], [3], [2], [5] and the references therein.

For a linear code of length \(n\), we call integral weight spectrum the overall numbers of weight \(w\) vectors, \(0\le w\le n\), in all the cosets of a fixed weight.

In this work, for MDS codes, using and developing the results of [9], we obtain new convenient formulas of integral weight spectra of cosets of weight 1 and 2. The obtained formulas for weight 1 and 2 cosets, seem to be simple and expressive.

This paper is organized as follows. Section 2 contains preliminaries. In Section 3, we consider the integral weight spectrum of the weight 1 cosets of MDS codes with minimum distance \(d\ge3\). In Section 4, we obtain the integral weight spectrum of the weight 2 cosets of MDS codes with minimum distance \(d\ge5\). In Section 5, we give the spectra for the weight 3 cosets of MDS codes with minimum distance \(5\) and covering radius \(3\).

2 Preliminaries↩︎

2.1 Cosets of a linear code↩︎

We give a few known definitions and properties connected with cosets of linear codes, see e.g. [1]–[5] and the references therein.

We consider a coset \(\mathcal{V}\) of an \([n,k,d]_{q}R\) code \(\mathcal{C}\) in the form 1 . We have \(\#\mathcal{V}=\#\mathcal{C}=q^k\). One can take as \(\mathbf{v}\) any vector of \(\mathcal{V}\). So, there are \(\#\mathcal{V}=q^k\) formally distinct representations of the form 1 ; all they give the same coset \(\mathcal{V}\). If \(\mathbf{v}\in \mathcal{C}\), we have \(\mathcal{V}=\mathcal{C}\). The distinct cosets of \(\mathcal{C}\) partition \(\mathbb{F}_{q}^{n}\) into \(q^{n-k}\) sets of size \(q^k\).

We remind that the Hamming weight of the vector \(\mathbf{x}\in \mathbb{F}_q^n\) is the number of nonzero entries in \(\mathbf{x}\).

Notation 1. For an \([n,k,d]_{q}R\) code \(\mathcal{C}\) and its coset \(\mathcal{V}\) of the form 1 , the following notation is used: \[\begin{align} &t=\left\lfloor\frac{d-1}{2}\right\rfloor&&\text{the number of correctable errors};\displaybreak[3]\\ &A_w(\mathcal{C})&&\text{the number of weight w codewords of the code \mathcal{C};}\displaybreak[3]\\ &A_w(\mathcal{V})&&\text{the number of weight w vectors in the coset }\mathcal{V};\displaybreak[3]\\ &\text{the weight of a coset}&&\text{the smallest Hamming weight of any vector in the coset;}\displaybreak[3]\\ &\mathcal{V}^{(W)}&&\text{a coset of weight }W;~~A_w(\mathcal{V}^{(W)})=0\text{ if }w<W;\displaybreak[3]\\ &\text{a coset leader}&&\text{a vector in the coset of the smallest Hamming weight;}\displaybreak[3]\\ &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(W)})&&\text{the overall number of weight w vectors in all cosets of weight }W;\displaybreak[3]\\ &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le W})&&\text{the overall number of weight w vectors in all cosets of weight }\le W. \end{align}\]

In cosets of weight \(> t\), a vector of the minimal weight is not necessarily unique. Cosets of weight \(\leq t\) have a unique leader.

The code \(\mathcal{C}\) is the coset of weight zero. The leader of \(\mathcal{C}\) is the zero vector of \(\mathbb{F}_q^{n}\).

Definition 1. Let \(\mathcal{C}\) be an \([n,k,d]_{q}R\) code and let \(\mathcal{V}^{(W)}\) be its coset of weight \(W\). Let \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(W)})\) be the overall number of weight \(w\) vectors in all cosets of weight \(W\). For a fixed \(W\), we call the set \(\{\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(W)})|w=0,1,\ldots,n\}\) integral weight spectrum of the code cosets of weight \(W\).

Distinct representations of the integral weight spectra \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(W)})\) and values of \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le W})\) are considered in the literature, see e.g. [1], [9], [10], [18], [2]. For instance, in [9], for an MDS code correcting \(t\)-fold errors, the value \(D_u\) gives \(\mathcal{A}_{u}^{\Sigma}(\mathcal{V}^{\le t})\).

2.2 Some useful relations↩︎

For \(w\ge d\), the weight distribution \(A_{w}(\mathcal{C})\) of an \([n,k,d=n-k+1]_q\) MDS code \(\mathcal{C}\) has the following form, see e.g. [3], [2]: \[\begin{align} \label{eq295wd95MDS} A_{w}(\mathcal{C})=\binom{n}{w}\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}(q^{w-d+1-j}-1). \end{align}\tag{2}\]

In \(\mathbb{F}_q^n\), the volume of a sphere of radius \(t\) is \[\begin{align} \label{eq295sphere} V_n(t)=\sum_{i=0}^t(q-1)^i\binom{n}{i}. \end{align}\tag{3}\]

The following combinatorial identities are well known, see e.g. [21]: \[\begin{align} &\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.\tag{4}\displaybreak[3]\\ &\binom{n}{m}\binom{m}{p}=\binom{n}{p}\binom{n-p}{m-p}=\binom{n}{m-p}\binom{n-m+p}{p}.\tag{5}\displaybreak[3]\\ &\sum_{k=0}^m(-1)^k\binom{n}{k}=(-1)^m\binom{n-1}{m}.\tag{6} \end{align}\]

In [9], for an \([n,k,d\ge 2t+1]_q\) MDS code correcting \(t\)-fold errors, the following relations for \(\mathcal{A}_u^{\Sigma}(\mathcal{V}^{\le t})\) denoted by \(D_u\) are given: \[\begin{align} \tag{7} & \mathcal{A}_u^{\Sigma}(\mathcal{V}^{\le t})=D_u=\binom{n}{u}\sum_{j=0}^{u-d+t}(-1)^jN_j,~d-t\le u\le n,\displaybreak[3] \\ &\text{where}\displaybreak[3]\notag \\ &N_j=\binom{u}{j}\left[q^{u-d+1-j}V_n(t)-\sum_{i=0}^t\binom{u-j}{i}(q-1)^i\right]~\text{ if }~0\le j\le u-d,\tag{8}\displaybreak[3] \\ &N_j=\binom{u}{j}\left[\,\sum_{w=d-u+j}^t\binom{n-u+j}{w}\sum_{i=0}^{w-d+u-j}(-1)^i\binom{w}{i}(q^{w-d+u-j-i+1}-1)\right.\tag{9}\displaybreak[3]\\ &\left.\times\sum_{s=w}^t\binom{u-j}{s-w}(q-1)^{s-w}\right]~\text{ if }~u-d+1\le j \le u-d+t.\notag \end{align}\]

3 The integral weight spectrum of the weight 1 cosets of MDS codes with minimum distance \(d\ge3\)↩︎

In Sections 3–5, we represent the values \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(W)})\) in distinct forms that can be convenient in distinct utilizations, e.g. for estimates of the decoder error probability, see [9], [10] and the references therein.

We use (with some transformations) the results of [9] where, for an MDS code correcting \(t\)-fold errors, the value \(D_u\) gives the overall number \(\mathcal{A}_{u}^{\Sigma}(\mathcal{V}^{\le t})\) of weight \(u\) vectors in all cosets of weight \(\le t\). We cite [9] by formulas 7 –9 , respectively.

In the rest of the paper we put that a sum \(\sum_{i=0}^A\ldots\) is equal to zero if \(A<0\).

Lemma 1. [9] Let \(d-1\le w\le n\). For an \([n,k,d=n-k+1]_q\) MDS code \(\mathcal{C}\) of minimum distance \(d\ge3\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{\le1})\) of weight \(w\) vectors in all cosets of weight \(\le1\) is as follows: \[\begin{align} \label{eq495AwSigma60611MDS} &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le1})=\binom{n}{w}\left[\sum_{j=0}^{w-d}(-1)^j\binom{w}{j} \left[q^{w-d+1-j}(1+n(q-1))-1-(w-j)(q-1)\right]\right.\displaybreak[3]\\ &\left.-(-1)^{w-d}\binom{w}{d-1}(n-d+1)(q-1)\right].\notag \end{align}\tag{10}\]

Proof. In the relations for \(D_u\) of [9] cited by 7 –9 , we put \(t=1\) and then use 3 . In 9 , we have \(j=u-d+1\) whence \(w=1\) in all terms. Finally, we change \(u\) by \(w\) to save the notations of this paper. ◻

Lemma 2. The following holds: \[\begin{align} \label{eq495combin95equal} \sum_{j=0}^{m}(-1)^j\binom{w}{j}\binom{w-j}{v}=(-1)^{m}\binom{w}{v}\binom{w-v-1}{m}. \end{align}\tag{11}\]

Proof. In 5 , we put \(n=w\), \(p=j\), \(m-p=v\), and obtain \[\begin{align} \sum_{j=0}^{m}(-1)^j\binom{w}{j}\binom{w-j}{v}=\binom{w}{v}\sum_{j=0}^{m}(-1)^j\binom{w-v}{j}. \end{align}\] Now we use 6 . ◻

Lemma 3. Let \(d-1\le w\le n\). The following holds: \[\begin{align} &\sum_{j=0}^{w+1-d}(-1)^j\binom{w}{j}q^{w+1-d-j}=\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\left(q^{w+1-d-j}-1\right)-(-1)^{w-d}\binom{w-1}{d-2}. \end{align}\]

Proof. We write the left sum of the assertion as \[\begin{align} \sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\left(q^{w+1-d-j}-1+1\right)-(-1)^{w-d}\binom{w}{d-1}. \end{align}\] By 6 , \[\begin{align} \sum_{j=0}^{w-d}(-1)^j\binom{w}{j} =(-1)^{w-d}\binom{w-1}{d-1}. \end{align}\] Finally, we apply 4 . ◻

For an \([n,k,d]_q\) code \(\mathcal{C}\), we denote \[\begin{align} \Omega_w^{(j)}(\mathcal{C})=(-1)^{w-d}\binom{n-j}{w-j}\binom{w-j-1}{d-j-2}.\label{eq495Omega} \end{align}\tag{12}\] Also, we denote \[\begin{align} \label{eq495Phi} &\Phi_w^{(j)}=(-1)^{w-5}\left[\binom{q+1}{w}\binom{w-1}{3}-\binom{q+1-j}{w-j}\binom{w-1-j}{3-j}\right]. \end{align}\tag{13}\]

Theorem 2. (integral weight spectrum 1)

Let \(d-1\le w\le n\). Let \(\mathcal{C}\) be an \([n,k,d=n-k+1]_q\) MDS code of minimum distance \(d\ge3\).

(i) For the code \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})\) of weight \(w\) vectors in all weight \(1\) cosets is as follows: \[\begin{align} \tag{14} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})=\binom{n}{w}(q-1)\left[n\sum_{j=0}^{w+1-d}(-1)^j\binom{w}{j}q^{w+1-d-j}+(-1)^{w-d}w\binom{w-2}{d-3}\right]\displaybreak[3]\\ &=n(q-1)\left[\binom{n}{w}\sum_{j=0}^{w+1-d}(-1)^j\binom{w}{j}q^{w+1-d-j}+\Omega_w^{(1)}(\mathcal{C})\right]\tag{15}\displaybreak[3]\\ &=n(q-1)\left[\binom{n}{w}\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\left(q^{w+1-d-j}-1\right)-\Omega_w^{(0)}(\mathcal{C})+\Omega_w^{(1)}(\mathcal{C})\right]\tag{16}\displaybreak[3]\\ &=n(q-1)\left[A_w(\mathcal{C})-\Omega_w^{(0)}(\mathcal{C})+\Omega_w^{(1)}(\mathcal{C})\right]\tag{17}\displaybreak[3]\\ &=n(q-1)\left[A_w(\mathcal{C})-(-1)^{w-d}\left(\binom{n}{w}\binom{w-1}{d-2}-\binom{n-1}{w-1}\binom{w-2}{d-3}\right)\right].\tag{18} \end{align}\]

(ii) Let the code \(\mathcal{C}\) be a \([q+1,k,d=q+2-k]_q\) MDS code of length \(n=q+1\) and minimum distance \(d\ge3\). For \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})\) of weight \(w\) vectors in all weight \(1\) cosets is as follows \[\begin{align} \label{eq495Aw1sum95q431} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})=\binom{q+1}{w}(q-1)\left[q^{w+2-d}-\sum_{i=0}^{w-d}(-1)^{i}\left(\binom{w}{i+1}-\binom{w}{i}\right)q^{w+1-d-i}\right.\\ &\left.-(-1)^{w-d}\left(\binom{w}{d-1}-w\binom{w-2}{d-3}\right)\right],~d-1\le w\le q+1.\notag \end{align}\tag{19}\]

(iii) Let the code \(\mathcal{C}\) be a \([q+1,q-3,5]_q\) MDS code of length \(n=q+1\) and minimum distance \(d=5\). For \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})\) of weight \(w\) vectors in all weight \(1\) cosets is as follows \[\begin{align} \label{eq495Aw1sum95q431955} \mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})=(q^2-1)\left[A_w(\mathcal{C})-\Phi_w^{(1)}\right],~4\le w\le q+1. \end{align}\tag{20}\]

Proof. (i) By the definition of \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le 1})\), see Notation 1, for the code \(\mathcal{C}\) of Lemma 1, we have \[\begin{align} \label{eq4956061381} \mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})=\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{\le1})-A_w(\mathcal{C}). \end{align}\tag{21}\] We subtract 2 from 10 that gives \[\begin{align} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})=\binom{n}{w}(q-1)\left[-(-1)^{w-d}\binom{w}{d-1}(n-d+1)\right.\displaybreak[3]\\ &\left.+\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\left(q^{w-d+1-j}n-w+j\right)\right]\displaybreak[3]\\ &=\binom{n}{w}(q-1)\left[n\sum_{j=0}^{w-d+1}(-1)^j\binom{w}{j}q^{w-d+1-j}-\sum_{j=0}^{w-d+1}(-1)^j\binom{w}{j}(w-j)\right]. \end{align}\] Here some simple transformations are missed out. Now, for the 2-nd sum \(\sum_{j=0}^{w-d+1}\ldots\), we use Lemma 2 and obtain 14 .

To form 15 from 14 , we change \(w\binom{n}{w}\) by \(n\binom{n-1}{w-1}\), see 5 . To obtain 16 from 15 , we apply Lemma 3. For 17 , we use 2 . Finally, 18 is 17 in detail.

(ii) We substitute \(n=q+1\) to 14 that implies 19 after simple transformations.

(iii) We substitute \(n=q+1\) and \(d=5\) to 18 that gives 20 . ◻

For \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le1})\), we give a formula alternative to 10 .

Corollary 1. Let \(V_n(1)\) be as in 3 . Let \(\mathcal{C}\) be an \([n,k,d=n-k+1]_q\) MDS code of minimum distance \(d\ge3\). Then for \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{\le1})\) of weight \(w\) vectors in all cosets of weight \(\le1\) is as follows: \[\begin{align} \label{eq495AwSigma60611MDS95new} &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le1})=A_w(\mathcal{C})\cdot V_n(1)-(-1)^{w-d}n(q-1)\sum_{j=0}^1(-1)^j\binom{n-j}{w-j}\binom{w-j-1}{d-j-2}. \end{align}\tag{22}\]

Proof. We use 21 and 18 . ◻

4 The integral weight spectrum of the weight 2 cosets of MDS codes with minimum distance \(d\ge5\)↩︎

As well as in Lemma 1, we use the results of [9] with some transformations.

Lemma 4. [9] Let \(d-2\le w\le n\). Let \(V_n(t)\) be as in 3 . For an \([n,k,d=n-k+1]_q\) MDS code \(\mathcal{C}\) of minimum distance \(d\ge5\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{\le2})\) of weight \(w\) vectors in all cosets of weight \(\le2\) is as follows: \[\begin{align} \label{eq595AwSigma60612MDS} &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le2})=\binom{n}{w}\left[\sum_{j=0}^{w-d}(-1)^j\binom{w}{j} \left[q^{w-d+1-j}\cdot V_n(2)-V_{w-j}(2)\right]\right.\\ &\left.-(-1)^{w-d}\frac{(n-d+1)(q-1)}{2}\left(\binom{w}{d-1}[2+(q-1)(n+d-2)] -\binom{w}{d-2}(n-d+2)\right)\right].\notag \end{align}\tag{23}\]

Proof. In the relations for \(D_u\) of [9] cited by 7 –9 , we put \(t=2\) that gives, in 9 , \(j=u-d+1\) and \(j=u-d+2\), whence \(w=1,2\) and \(w=2\), respectively. Then we do simple transformations. Finally, we change \(u\) by \(w\) to save the notations of this paper. ◻

For an \([n,k,d]_q\) code \(\mathcal{C}\), we denote \[\begin{align} &\Delta_w(\mathcal{C})=(-1)^{w-d}\binom{n}{w}\binom{w}{d-2}\binom{n-d+2}{2}(q-1);\displaybreak[3]\label{eq595Delta}\\ &\Delta_w^\star(\mathcal{C})=\frac{\Delta_w(\mathcal{C})}{\binom{n}{2}(q-1)^2}.\notag \end{align}\tag{24}\]

Lemma 5. The following holds: \[\begin{align} \label{eq595DeltaStar} \Delta_w^\star(\mathcal{C})=(-1)^{w-d}\binom{n-d+2}{n-w}\binom{n-2}{d-2}\frac{1}{q-1}. \end{align}\tag{25}\]

Proof. By 5 , we have \[\begin{align} &\binom{n}{w}\binom{w}{d-2}=\binom{n}{d-2}\binom{n-d+2}{w-d-2}=\binom{n}{d-2}\binom{n-d+2}{n-w},\displaybreak[3]\\ &\binom{n}{d-2}\binom{n-d+2}{2}=\binom{n}{d}\binom{d}{d-2}=\binom{n}{d}\binom{d}{2}=\binom{n}{2}\binom{n-2}{d-2}. \end{align}\] ◻

Theorem 3. (integral weight spectrum 2)

Let \(d-2\le w\le n\). Let \(\mathcal{C}\) be an \([n,k,d=n-k+1]_q\) MDS code of minimum distance \(d\ge5\). Let \(\Omega_w^{(j)}(\mathcal{C})\) and \(\Phi_w^{(j)}\) be as in 12 and 13 .

(i) For the code \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})\) of weight \(w\) vectors in all weight \(2\) cosets is as follows: \[\begin{align} \tag{26} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=\binom{n}{w}(q-1)^2\left[\binom{n}{2}\sum_{j=0}^{w+1-d}(-1)^j\binom{w}{j}q^{w+1-d-j}+(-1)^{w-d}\binom{w}{2}\binom{w-3}{d-4}\right]\displaybreak[3]\\ &\phantom{\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=}+\Delta_w(\mathcal{C}).\displaybreak[3]\notag\\ &=\binom{n}{2}(q-1)^2\left[\binom{n}{w}\sum_{j=0}^{w+1-d}(-1)^j\binom{w}{j}q^{w+1-d-j}+\Omega_w^{(2)}(\mathcal{C})\right]+\Delta_w(\mathcal{C}).\tag{27}\displaybreak[3]\\ &=\binom{n}{2}(q-1)^2\left[\binom{n}{w}\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\left(q^{w+1-d-j}-1\right)-\Omega_w^{(0)}(\mathcal{C})+\Omega_w^{(2)}(\mathcal{C})\right] +\Delta_w(\mathcal{C})\tag{28}\displaybreak[3]\\ &=\binom{n}{2}(q-1)^2\left[A_w(\mathcal{C})-\Omega_w^{(0)}(\mathcal{C})+\Omega_w^{(2)}(\mathcal{C})\right] +\binom{n}{2}(q-1)^2\Delta_w^\star(\mathcal{C})\tag{29}\displaybreak[3]\\ &=\binom{n}{2}(q-1)^2\left[A_w(\mathcal{C})-(-1)^{w-d}\left(\binom{n}{w}\binom{w-1}{d-2}-\binom{n-2}{w-2}\binom{w-3}{d-4}\right)\right]\tag{30}\\ &+(-1)^{w-d}\binom{n}{2}(q-1)\binom{n-d+2}{n-w}\binom{n-2}{d-2}.\notag \end{align}\]

(ii) Let the code \(\mathcal{C}\) be a \([q+1,q-3,5]_q\) MDS code of length \(n=q+1\) and minimum distance \(d=5\). For \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})\) of weight \(w\) vectors in all weight \(1\) cosets is as follows \[\begin{align} \label{eq595AwSigma295q431955} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=\binom{q+1}{2}(q-1)^2\left[A_w(\mathcal{C})-\Phi_w^{(2)}+(-1)^{w-5}\,\frac{1}{3}\binom{q-2}{w-3}\binom{q-2}{2}\right],\displaybreak[3]\\ &\phantom{\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=}3\le w\le q+1. \notag \end{align}\tag{31}\]

Proof. (i) By the definition of \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le 2})\), see Notation 1, for the code \(\mathcal{C}\) of Lemma 4, we have \[\begin{align} \label{eq595extract} \mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{\le2})-\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{\le1}). \end{align}\tag{32}\] We subtract 10 from 23 that gives \[\begin{align} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=\binom{n}{w}\left[\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\left(q^{w+1-d-j}\binom{n}{2}(q-1)^2-\binom{w-j}{2}(q-1)^2\right)\right.\displaybreak[3]\\ &\left.+(-1)^{w+1-d}\binom{w}{d-1}\frac{1}{2}(n-d+1)(q-1)^2(n+d-2)\right]+\Delta_w(\mathcal{C})\displaybreak[3]\\ &=\binom{n}{w}(q-1)^2\left[\binom{n}{2}\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}q^{w+1-d-j}-\sum_{j=0}^{w-d}(-1)^j\binom{w}{j}\binom{w-j}{2}\right.\displaybreak[3]\\ &\left.-(-1)^{w-d}\binom{w}{d-1}\left(\frac{1}{2}(n-d+1)(n+d-2)+\binom{n}{2}-\binom{n}{2}\right)\right]+\Delta_w(\mathcal{C}). \end{align}\] Applying Lemma 2 to the 2-nd sum \(\sum_{j=0}^{w-d}\ldots\), after simple transformations we obtain \[\begin{align} &\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})=\binom{n}{w}(q-1)^2\left[\binom{n}{2}\sum_{j=0}^{w+1-d}(-1)^j\binom{w}{j}q^{w+1-d-j}-(-1)^{w-d}\binom{w}{2}\binom{w-3}{w-d}\right.\displaybreak[3]\\ &\left.+(-1)^{w-d}\binom{w}{d-1}\binom{d-1}{2}\right]+\Delta_w(\mathcal{C}). \end{align}\] Due to 5 and 4 , we have \[\binom{w}{d-1}\binom{d-1}{2}=\binom{w}{2}\binom{w-2}{d-3}=\binom{w}{2}\left[\binom{w-3}{d-4}+\binom{w-3}{d-3}\right].\] Also, \(\binom{w-3}{w-d}=\binom{w-3}{d-3}\). Now we can obtain 26 . Moreover, by 5 , we have \[\binom{n}{w}\binom{w}{2}=\binom{n}{2}\binom{n-2}{w-2}\] that gives 27 .

To obtain 28 from 27 , we apply Lemma 3. For 29 , we use 2 . Finally, 30 is 29 in detail.

(ii) We substitute \(n=q+1\) and \(d=5\) to 30 that gives 31 . ◻

5 The integral weight spectrum of the weight 3 cosets of MDS codes with minimum distance \(d=5\) and covering radius \(R=3\)↩︎

Theorem 4. (integral weight spectrum 3)

Let \(d-2\le w\le n\). Let \(\mathcal{C}\) be an \([n,n-4,5]_q3\) MDS code of minimum distance \(d=5\) and covering radius \(R=3\). Let \(V_n(t)\), \(\Phi_w^{(j)}\), \(\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le2})\), and \(\Delta_w(\mathcal{C})\) be as in 3 , 13 , 23 , and 24 , respectively. Let \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(1)})\) and \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(2)})\) be as in Theorems 2 and 3, respectively.

(i) For the code \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{3})\) of weight \(w\) vectors in all cosets of weight \(3\) is as follows: \[\begin{align} \tag{33} &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(3)})=\binom{n}{w}(q-1)^w-\mathcal{A}_w^{\Sigma}(\mathcal{V}^{\le2})\displaybreak[3]\\ &=\binom{n}{w}(q-1)^w-\left[A_w(\mathcal{C})+\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(1)})+\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(2)})\right]\displaybreak[3]\tag{34}\\ &=\binom{n}{w}(q-1)^w-\left[\binom{n}{w}\sum_{j=0}^{w-5}(-1)^j\binom{w}{j} \left[q^{w-4-j}\cdot V_n(2)-V_{w-j}(2)\right]\right.\tag{35}\\ &\left.-(-1)^{w-5}\frac{(n-4)(q-1)}{2}\left(\binom{w}{4}[2+(q-1)(n+3)] -\binom{w}{3}(n-3)\right)\right].\notag \end{align}\]

(ii) Let the code \(\mathcal{C}\) be a \([q+1,q-3,5]_q3\) MDS code of length \(n=q+1\), minimum distance \(d=5\), and covering radius \(R=3\). For \(\mathcal{C}\), the overall number \(\mathcal{A}_{w}^{\Sigma}(\mathcal{V}^{(3)})\) of weight \(w\) vectors in all weight \(3\) cosets is as follows \[\begin{align} \tag{36} &\mathcal{A}_w^{\Sigma}(\mathcal{V}^{(3)})=\binom{q+1}{w}(q-1)^w-\left[\binom{q+1}{w}\sum_{j=0}^{w-5}(-1)^j\binom{w}{j} \left[q^{w-4-j}\cdot V_{q+1}(2)-V_{w-j}(2)\right]\right.\\ &\left.-(-1)^{w-5}\frac{(q-3)(q-1)}{2}\left(\binom{w}{4}(q^2+3q-2) -\binom{w}{3}(q-2)\right)\right]\notag\\ &=\binom{q+1}{w}(q-1)^w-\left[V_{q+1}(2)A_w(\mathcal{C})-(q^2-1)\Phi_w^{(1)}-\binom{q+1}{2}(q-1)^2\Phi_w^{(2)}-\Delta_w(\mathcal{C})\right].\tag{37} \end{align}\]

Proof. (i) Due to covering radius \(3\), in \(\mathcal{C}\) there are not cosets of weight \(>3\); therefore for \(\mathcal{C}\) we have 33 where \(\binom{n}{w}(q-1)^w\) is the total number of weight \(w\) vectors in \(\mathbb{F}_q^{n}\).

The relation 34 follows from 33 , 21 , and 32 .

To form 35 , we substitute 23 to 33 with \(d=5\).

(ii) We substitute \(n=q+1\) to 35 and obtain 36 .

To obtain 37 from 34 , we use 20 , 31 , 24 , and 25 with \(n=q+1\), \(d=5\). ◻

References↩︎

[1]

R.E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, Reading, 1984.

[2]

F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, third ed., North- Holland, Amsterdam, The Netherlands, 1981.

[3]

W.C. Huffman, V.S. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, 2003.

[4]

R.M. Roth, Introduction to Coding Theory, Cambridge, Cambridge Univ. Press, 2007.

[5]

V.S. Pless, W.C. Huffman, R.A. Brualdi, An Introductiom to Algebraic Codes, In: V.S. Pless, W.C. Huffman, R.A. Brualdi, (eds.) Handbook of Coding Theory, Chapter I, pp. 3–139, Elsevier, Amsterdam, The Netherlands, 1998.

[6]

E.F. Assmus, Jr., H.F. Mattson, Jr., The weight-distribution of a coset of a linear code, IEEE Trans. Inform. Theory 24(4), 497 (1978) https://doi.org/10.1109/tit.1978.1055903.

[7]

A. Bonnecaze, I.M. Duursma, Translates of linear codes over \(\mathbf{Z}_4\), IEEE Trans. Inform. Theory 43(4), 1218–1230 (1997) https://doi.org/10.1109/18.605585.

[8]

P. Charpin, T. Helleseth, V. Zinoviev, The coset distribution of triple-error-correcting binary primitive BCH codes. IEEE Trans. Inform. Theory, 52(4), 1727–1732 (2006) https://doi.org/10.1109/TIT.2006.871605.

[9]

K.-M. Cheung, More on the decoder error probability for Reed-Solomon codes. IEEE Trans. Inform. Theory 35(4), 895-–900 (1989) https://doi.org/10.1109/18.32169.

[10]

K.-M. Cheung, On the decoder error probability of block codes. IEEE Trans. Commun. 40(5), 857–-859 (1992) https://doi.org/10.1109/26.141450.

[11]

P. Delsarte, Four fundamental parameters of a code and their combinatorial significance. Inform. Control 23, 407–438 (1973) https://doi.org/10.1016/s0019-9958(73)80007-5.

[12]

P. Delsarte, V.I. Levenshtein, Association schemes and coding theory. IEEE Trans. Inform. Theory 44(6), 2477–2504 (1998) https://doi.org/10.1109/18.720545.

[13]

T. Helleseth, The weight distribution of the coset leaders of some classes of codes with related parity-check matrices, Discrete Math. 28, 161–171 (1979) https://doi.org/10.1016/0012-365X(79)90093-1.

[14]

R. Jurrius, R. Pellikaan, The coset leader and list weight enumerator. In: G. Kyureghyan, G.L. Mullen, A. Pott, Eds., Contemporary Math. vol. 632, Topics in Finite Fields (2015) 229–251. Corrected version (2019) https://www.win.tue.nl/ ruudp/paper/71.pdf.

[15]

K. Kaipa, Deep Holes and MDS Extensions of Reed–Solomon Codes, IEEE Trans. Inform. Theory 63 (8) (2017) 4940 – 4948. https://doi.org/10.1109/TIT.2017.2706677.

[16]

T. Kasami, S. Lin, On the Probability of Undetected Error for the Maximum Distance Separable Codes, IEEE Trans. Commun. 32(9), 998–1006 (1984) https://doi.org/10.1109/TCOM.1984.1096175.

[17]

J.R. Schatz, On the Weight Distributions of Cosets of a Linear Code. American Math. Month. 87(7), 548-551 (1980) https://doi.org/10.1080/00029890.1980.11995087.

[18]

F.J. MacWilliams, A theorem on the distribution of weights in a systematic code, Bell Syst. Tech. J. 42(1), 79-94 (1963) https://doi.org/10.1002/j.1538-7305.1963.tb04003.x.

[19]

J. Zhang, D. Wan, K. Kaipa, Deep Holes of Projective Reed-Solomon Codes. IEEE Trans. Inform. Theory 66(4), 2392–2401 (2020) https://doi.org/10.1109/TIT.2019.2940962.

[20]

P. Delsarte, An Algebraic Approach to the Association Schemes of Coding Theory. Philips Res. Repts. Suppl. 10, 1973.

[21]

J. Riordan, Combinatorial Identities, Willey, New York, 1968.

The research of A.A. Davydov was done at IITP RAS and supported by the Russian Government (Contract No 14.W03.31.0019).↩︎
The research of S. Marcugini and F. Pambianco was supported in part by the Italian National Group for Algebraic and Geometric Structures and their Applications (GNSAGA - INDAM) (No U-UFMBAZ-2017-000532, 28.11.2017) and by University of Perugia (Project: Curve, codici e configurazioni di punti, Base Research Fund 2018, No 46459, 15.06.2018).↩︎

On integral weight spectra of the MDS codes cosets of weight 1, 2, and 3