The equivalent condition for GRL codes to be MDS, AMDS or self-dual
Zhonghao Liang, Qunying Liao* · 2025
Read The equivalent condition for GRL codes to be MDS, AMDS or self-dual by Zhonghao Liang, Qunying Liao* (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-03874.txt.
Introduction
The authors study a family of error-correcting codes in a mathematics paper from 2025. The codes are generalized Roth-Lempel codes, a class not equivalent to the better-known Reed-Solomon codes. Such codes matter for communication, storage, and quantum settings when they hit special quality marks: maximum distance, near-maximum distance, or self-duality, where a code equals its own dual.
The paper gives an exact condition, in both directions, for these codes or their duals to reach each of those marks in the non-Reed-Solomon case. Worked examples show the condition in action. Results of this kind help designers pick code parameters with known guarantees.
Catalog record
| CREATOR | Zhonghao Liang, Qunying Liao* |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-03874
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The equivalent condition for GRL codes to be MDS, AMDS or self-dual Thanks: This paper is supported by National Natural Science Foundation of China (Grant No. 12471494) and Natural Science Foundation of Sichuan Province (2024NSFSC2051). The corresponding author is professor Qunying Liao. Zhonghao Liang, Qunying Liao* Abstract It’s well-known that MDS, AMDS or self-dual codes have good algebraic properties, and are applied in communication systems, data storage, quantum codes, and so on. In this paper, we focus on a class of generalized Roth-Lempel linear codes, and give an equivalent condition for them or their dual to be non-RS MDS, AMDS or non-RS self-dual and some corresponding examples. I Introduction Let \mathbb{F}_{q} be the finite field of q elements, where q is a prime power and \mathbb{F}_{q}^{*}=\mathbb{F}_{q}\backslash\left\{0\right\} . An [n,k,d] linear code \mathcal{C} over \mathbb{F}_{q} is a k -dimensional subspace of \mathbb{F}_{q}^{n} with minimum (Hamming) distance d . If d=n-k+1 , i.e., the Singleton bound is satisfied, then \mathcal{C} is maximum distance separable (in short, MDS). If d=n-k , then \mathcal{C} is almost MDS (in short, AMDS). If a linear code is not equivalent to any RS code, then it is called to be non-Reed- Solomon (non-RS) type. Since MDS or AMDS codes have important applications in communications, data storage, combinatorial theory and secret sharing, and so on [ 1 , 2 , 3 , 4 , 5 , 6 ] , the study for MDS codes or AMDS codes, including their weight distributions, constructions, equivalence, self-orthogonal, and (almost) self-dual property, has attracted a lot of attentions [ 7 , 8 , 9 , 10 , 11 , 12 ] . It’s well-known that the dual code of an [n,k]_{q} linear code \mathcal{C} is given by \mathcal{C}^{\perp}=\left\{\left(x_{1},\ldots,x_{n}\right)=\boldsymbol{x}\in\mathbb{F}_{q}^{n}\mid\langle\boldsymbol{x},\boldsymbol{y}\rangle=\sum\limits_{i=1}^{n}x_{i}y_{i}=0,\forall\boldsymbol{y}=\left(y_{1},\ldots,y_{n}\right)\in\mathcal{C}\right\}. Especially, a linear code \mathcal{C} is self-dual if \mathcal{C}=\mathcal{C}^{\perp} . Self-dual linear codes have various connections with combinatorics and lattice theory [ 3 , 13 ] . In practice, self-dual linear codes have also important applications in cryptography [ 14 , 15 ] . The Reed-Solomon code, as a good class of MDS linear codes, is defined as \mathrm{RS}_{k}(\boldsymbol{\alpha}):=\left\{\left(f\left(\alpha_{1}\right),\ldots,f\left(\alpha_{n}\right)\right)|f(x)\in\mathbb{F}_{q}^{k}[x]\right\}, where \mathbb{F}_{q}[x] is the polynomial ring over \mathbb{F}_{q} , \mathbb{F}_{q}^{k}[x]=\left\{f(x)=\sum_{i=0}^{k-1}f_{i}x^{i}\mid f_{i}\in\mathbb{F}_{q},0\leq i\leq k-1\right\}, and \boldsymbol{\alpha}=\left(\alpha_{1},\ldots,\alpha_{n}\right)\in\mathbb{F}_{q}^{n} with \alpha_{i}\neq\alpha_{j}(i\neq j) . It’s easy to prove that \boldsymbol{G}_{1}=\left(\begin{matrix}1&1&\cdots&1&1\\ \alpha_{1}&\alpha_{2}&\cdots&\alpha_{n-1}&\alpha_{n}\\ \vdots&\vdots&\quad&\vdots&\vdots\\ \alpha_{1}^{k-2}&\alpha_{2}^{k-2}&\cdots&\alpha_{n-1}^{k-2}&\alpha_{n}^{k-2}\\ \alpha_{1}^{k-1}&\alpha_{2}^{k-1}&\cdots&\alpha_{n-1}^{k-1}&\alpha_{n}^{k-1}\\ \end{matrix}\right)_{k\times n} (1) is a generator matrix of \mathrm{RS}_{k}(\boldsymbol{\alpha}) and \mathrm{RS}_{k}(\boldsymbol{\alpha}) have parameters \left[n,k,n-k+1\right] . Since MDS codes based on \mathrm{RS} codes are equivalent to RS codes, and so it’s interesting to construct non-RS MDS codes [ 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 ] . In 1989, Roth and Lempel [ 20 ] constructed a class of non-RS type MDS codes by adding two columns to the matrix \boldsymbol{G}_{1} given by (\ref{RS}) , the corresponding linear code over \mathbb{F}_{q} has the generator matrix \boldsymbol{G}_{2}=\left(\begin{matrix}\boldsymbol{G}_{1}&\begin{matrix}\boldsymbol{0}\\ \boldsymbol{A}_{1}\end{matrix}\end{matrix}\right)_{k\times(n+2)}, (2) where 4\leq k+1\leq n\leq q and \boldsymbol{A}_{1}=\left(\begin{matrix}0&1\\ 1&\delta\end{matrix}\right) with \delta\in\mathbb{F}_{q} . Recently, Wu et al. [ 21 ] added three columns to \boldsymbol{G}_{1} , the corresponding linear code over \mathbb{F}_{q} has the generator matrix \boldsymbol{G}_{3}=\left(\begin{matrix}\boldsymbol{G}_{1}&\begin{matrix}\boldsymbol{0}\\ \boldsymbol{A}_{2}\end{matrix}\end{matrix}\right)_{k\times(n+3)}, (3) where 4\leq k+1\leq n\leq q and \boldsymbol{A}_{2}=\left(\begin{matrix}0&0&1\\ 0&1&\tau\\ 1&\delta&\pi\end{matrix}\right) with \delta,\tau,\pi\in\mathbb{F}_{q} . We continue this work, i.e., replaces \boldsymbol{A}_{2} by \boldsymbol{A}_{3\times 3}=(a_{ij})\in\mathrm{GL}_{3}\left(\mathbb{F}_{q}\right) and generalize the corresponding results. This paper is organized as follows. In Section 2, we give the definition of the GRL code and some necessary lemmas. In Section 3, we give an equivalent condition for the code \mathrm{RL}_{k}(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}) given by Remark 2 to be non-RS MDS or its dual to be AMDS, respectively. In Section 4, we determine a parity-check matrix of \mathrm{GRL}_{k}(\boldsymbol{\alpha},\boldsymbol{v},\boldsymbol{A}_{3\times 3}) given by Definition 1 , and then also give an equivalent condition for that it is non-RS self-dual. In Section 5, we conclude the whole paper. II Preliminaries In this section, we give the definition of the GRL code and some necessary lemmas. Definition 1 . Let \mathbb{F}_{q} be the finite field of q elements, where q is a prime power. Let l+1\leq k+1\leq n\leq q , \boldsymbol{\alpha}=\left(\alpha_{1},\ldots,\alpha_{n}\right)\in\mathbb{F}_{q}^{n} with \alpha_{i}\neq\alpha_{j}(i\neq j) and \boldsymbol{v}= \left(v_{1},\ldots,v_{n}\right)\in\left(\mathbb{F}_{q}^{*}\right)^{n} . The generalized Roth-Lempel (in short, GRL) code \mathrm{GRL}_{k}(\boldsymbol{\alpha},\boldsymbol{v},\boldsymbol{A}_{l\times l}) is defined as \mathrm{GRL}_{k}(\boldsymbol{\alpha},\boldsymbol{v},\boldsymbol{A}_{l\times l}):=\left\{\left(v_{1}f\left(\alpha_{1}\right),\ldots,v_{n}f\left(\alpha_{n}\right),\boldsymbol{\beta}\right)|f(x)\in\mathbb{F}_{q}^{k}[x]\right\}, where \boldsymbol{A}_{l\times l}=(a_{ij})_{l\times l}\in\mathrm{GL}_{l}\left(\mathbb{F}_{q}\right) and \boldsymbol{\beta}=\left(f_{k-l},\ldots,f_{k-1}\right)\boldsymbol{A}_{l\times l}=\left(a_{11}f_{k-l}+a_{21}f_{k-(l-1)}+\cdots+a_{l1}f_{k-1},\ldots,a_{1l}f_{k-l}+a_{2l}f_{k-(l-1)}+\cdots+a_{ll}f_{k-1}\right). Remark 2 . (1) By taking \boldsymbol{v}=\left(1,\ldots,1\right) and \boldsymbol{A}_{l\times l}=\boldsymbol{A}_{1} in Definition 1 , then \mathrm{GRL}_{k}(\boldsymbol{\alpha},\boldsymbol{v},\boldsymbol{A}_{l\times l}) is a classical Roth-Lemmpel (in short RL) code and denote by \mathrm{RL}_{k}(\boldsymbol{\alpha},\delta) . (2) By taking \boldsymbol{v}=\left(1,\ldots,1\right) and \boldsymbol{A}_{l\times l}=\boldsymbol{A}_{3\times 3} in Definition 1 , the corresponding code has the generator matrix \boldsymbol{G}_{4}=\left(\begin{matrix}1&1&\cdots&1&1&0&0&0\\ \alpha_{1}&\alpha_{2}&\cdots&\alpha_{n-1}&\alpha_{n}&0&0&0\\ \vdots&\vdots&&\vdots&\vdots&\vdots&\vdots&\vdots\\ \alpha_{1}^{k-4}&\alpha_{2}^{k-4}&\cdots&\alpha_{n-1}^{k-4}&\alpha_{n}^{k-4}&0&0&0\\ \alpha_{1}^{k-3}&\alpha_{2}^{k-3}&\cdots&\alpha_{n-1}^{k-3}&\alpha_{n}^{k-3}&a_{11}&a_{12}&a_{13}\\ \alpha_{1}^{k-2}&\alpha_{2}^{k-2}&\cdots&\alpha_{n-1}^{k-2}&\alpha_{n}^{k-2}&a_{21}&a_{22}&a_{23}\\ \alpha_{1}^{k-1}&\alpha_{2}^{k-1}&\cdots&\alpha_{n-1}^{k-1}&\alpha_{n}^{k-1}&a_{31}&a_{32}&a_{33}\\ \end{matrix}\right)_{k\times(n+3)} (4) and denote by \mathrm{RL}_{k}(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}) . By taking m=n-3 , (k_{1},\ldots,k_{m-1},k_{m})=(1,\ldots,n-4,n-1) and (x_{1},\ldots,x_{m+1})=(\alpha_{1},\ldots,\alpha_{n-2}) in Lemma 2 [ 21 ] , we have the following Lemma 3 . ( [ 21 ] , Lemma 2) For any positive integer k>3 , we have \det\left(\begin{array}[]{cccc}1&1&\ldots&1\\ \alpha_{1}&\alpha_{2}&\ldots&\alpha_{n-2}\\ \vdots&\vdots&\ddots&\vdots\\ \alpha_{1}^{n-4}&\alpha_{2}^{n-4}&\ldots&\alpha_{n-2}^{n-4}\\ \alpha_{1}^{n-1}&\alpha_{2}^{n-1}&\ldots&\alpha_{n-2}^{n-1}\end{array}\right)=\left(\sum_{i=1}^{n-2}\alpha_{i}^{2}+\sum_{1\leq i<j\leq n-2}\alpha_{i}\alpha_{j}\right)\prod_{1\leq i<j\leq n-2}\left(\alpha_{j}-\alpha_{i}\right). Lemma 4 . ( [ 22 ] , Lemma 2.9) Let u_{i}=\prod\limits_{j=1,j\neq i}^{n}\left(\alpha_{i}-\alpha_{j}\right)^{-1} for 1\leq i\leq n . Then for any subset \left\{\alpha_{1},\ldots,\alpha_{n}\right\}\subseteq\mathbb{F}_{q} with n\geq 3 , we have \sum\limits_{i=1}^{n}u_{i}\alpha_{i}^{j}=\left\{\begin{array}[]{ll}0,&\text{if}\ 0\leq j\leq n-2;\\ 1,&\text{ if }j=n-1;\\ \sum\limits_{i=1}^{n}\alpha_{i},&\text{ if }j=n;\\ \sum\limits_{i=1}^{n}\alpha_{i}^{2}-\sum\limits_{1\leq i<j\leq n}\alpha_{i}\alpha_{j},&\text{ if }j=n+1.\end{array}\right. By taking \boldsymbol{\alpha}=\left(\alpha_{1},\ldots,\alpha_{n+3}\right)\in\mathbb{F}_{q}^{n+3} and \boldsymbol{v}=(1,\ldots,1)\in\mathbb{F}_{q}^{n+3} in Theorem 1 [ 26 ] , we can get the following Lemma 5 . ( [ 26 ] , Theorem 1) Let \boldsymbol{\alpha}=\left(\alpha_{1},\ldots\alpha_{n+3}\right)\in\mathbb{F}_{q}^{n+3} with \alpha_{i}\neq\alpha_{j}(i\neq j) . Suppose that \boldsymbol{B} is a k\times(n+3-k) matrix and \boldsymbol{G}=\left(\boldsymbol{E}_{k}|\boldsymbol{B}\right) is a k\times(n+3) matrix over \mathbb{F}_{q} , where \boldsymbol{E}_{k} is the k\times k identity matrix. Then \boldsymbol{G} generates the \mathrm{RS} code \operatorname{RS}_{k}(\boldsymbol{\alpha}) if and only if for 1\leq i\leq k and 1\leq j\leq n+3-k , the (i,j) -th entry of \boldsymbol{B} is given by \frac{\eta_{k+j}\eta_{i}^{-1}}{\alpha_{k+j}-\alpha_{i}}, where \eta_{i}=\prod\limits_{s=1,s\neq i}^{k}\left(\alpha_{i}-\alpha_{s}\right) and \eta_{k+j}=\prod\limits_{s=1}^{k}\left(\alpha_{k+j}-\alpha_{s}\right). Lemma 6 . ( [ 27 ] , Proposition 2.1) An [n,k] linear code over \mathbb{F}_{q} is \mathrm{MDS} if and only if any k columns of its generator matrix are \mathbb{F}_{q} -linearly independent. III The property of \mathrm{RL}_{k}\left(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}\right) and its dual In this section, we prove that \mathrm{RL}_{k}(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}) is non-RS when k>3 , and give an equivalent condition for \mathrm{RL}_{k}\left(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}\right) to be MDS or for \mathrm{RL}_{k}^{\perp}\left(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}\right) to be AMDS, respectively. Since their proofs are a little long, for the convenience, we divide them into the following three subsections. III-A The non-RS property of \mathrm{RL}_{k}\left(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}\right) In this subsection, we prove that \mathrm{RL}_{k}(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3})(k>3) is non-RS as the following Theorem 7 . If k>3 , then \mathrm{RL}_{k}(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}) is non-RS. Proof . Let f_{i}(x)=\sum_{j=1}^{k}f_{ij}x^{j-1}=\prod_{j=1,j\neq i}^{k}\left(x-\alpha_{j}\right)(1\leq i\leq k), \boldsymbol{C}=\left(\begin{array}[]{cccc}f_{11}&f_{12}&\cdots&f_{1k}\\ f_{21}&f_{22}&\cdots&f_{2k}\\ \vdots&\vdots&&\vdots\\ f_{k1}&f_{k2}&\cdots&f_{kk}\end{array}\right), (5) \eta_{i}=\prod_{s=1,s\neq i}^{k}\left(\alpha_{i}-\alpha_{s}\right)(1\leq i\leq k), \eta_{k+j}=\prod_{s=1}^{k}\left(\alpha_{k+j}-\alpha_{s}\right)(1\leq j\leq n-k), and e_{i}=a_{3i}-\left(a_{2i}+a_{1i}\alpha_{1}\right)\sum\limits_{i=1}^{k}\alpha_{i}+a_{1i}\sum\limits_{1\leq i<j\leq k}\alpha_{i}\alpha_{j}(1\leq i\leq 3). Now for \boldsymbol{C} and \boldsymbol{G}_{4} given by (\ref{C}) and (\ref{RL}) , respectively, we have \displaystyle\overline{\boldsymbol{G}_{4}}=\boldsymbol{CG_{4}}= \displaystyle\left(\begin{matrix}\begin{matrix}f_{1}\left(\alpha_{1}\right)&0&\cdots&0\\ 0&f_{2}\left(\alpha_{2}\right)&\cdots&0\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&f_{k}\left(\alpha_{k}\right)\end{matrix}&\boldsymbol{D}\end{matrix}\right) \displaystyle= \displaystyle\left(\begin{matrix}\begin{matrix}\eta_{1}&0&\cdots&0\\ 0&\eta_{2}&\cdots&0\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&\eta_{k}\end{matrix}&\boldsymbol{D}\end{matrix}\right) \displaystyle= \displaystyle\left(\begin{matrix}\eta_{1}&0&\cdots&0\\ 0&\eta_{2}&\cdots&0\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&\eta_{k}\end{matrix}\right)\left(\begin{matrix}\begin{matrix}1&0&\cdots&0\\ 0&1&\cdots&0\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&1\end{matrix}&\boldsymbol{F}\end{matrix}\right) \displaystyle= \displaystyle\boldsymbol{V}\widetilde{\boldsymbol{G}_{4}}, where \boldsymbol{D}=\left(\begin{matrix}f_{1}\left(\alpha_{k+1}\right)&\cdots&f_{1}\left(\alpha_{n}\right)&e_{1}+a_{21}\alpha_{1}+a_{11}\alpha_{1}^{2}&e_{2}+a_{22}\alpha_{1}+a_{12}\alpha_{1}^{2}&e_{3}+a_{23}\alpha_{2}+a_{13}\alpha_{2}^{2}\\ f_{2}\left(\alpha_{k+1}\right)&\cdots&f_{2}\left(\alpha_{n}\right)&e_{1}+a_{21}\alpha_{2}+a_{11}\alpha_{2}^{2}&e_{2}+a_{22}\alpha_{2}+a_{12}\alpha_{2}^{2}&e_{3}+a_{23}\alpha_{2}+a_{13}\alpha_{2}^{2}\\ \vdots&&\vdots&\vdots&\vdots&\vdots\\ f_{k}\left(\alpha_{k+1}\right)&\cdots&f_{k}\left(\alpha_{n}\right)&e_{1}+a_{21}\alpha_{k}+a_{11}\alpha_{k}^{2}&e_{2}+a_{22}\alpha_{k}+a_{12}\alpha_{k}^{2}&e_{3}+a_{23}\alpha_{k}+a_{13}\alpha_{k}^{2}\\ \end{matrix}\right), \boldsymbol{F}=\left(\begin{matrix}\frac{\eta_{k+1}\eta_{1}^{-1}}{\alpha_{k+1}-\alpha_{1}}&\cdots&\frac{\eta_{n}\eta_{1}^{-1}}{\alpha_{n}-\alpha_{1}}&\left(e_{1}+a_{21}\alpha_{1}+a_{11}\alpha_{1}^{2}\right)\eta_{1}^{-1}&(e_{2}+a_{22}\alpha_{1}+a_{12}\alpha_{1}^{2})\eta_{1}^{-1}&(e_{3}+a_{23}\alpha_{2}+a_{13}\alpha_{2}^{2})\eta_{1}^{-1}\\ \frac{\eta_{k+1}\eta_{2}^{-1}}{\alpha_{k+1}-\alpha_{2}}&\cdots&\frac{\eta_{n}\eta_{2}^{-1}}{\alpha_{n}-\alpha_{2}}&(e_{1}+a_{21}\alpha_{2}+a_{11}\alpha_{2}^{2})\eta_{2}^{-1}&(e_{2}+a_{22}\alpha_{2}+a_{12}\alpha_{2}^{2})\eta_{2}^{-1}&(e_{3}+a_{23}\alpha_{2}+a_{13}\alpha_{2}^{2})\eta_{2}^{-1}\\ \vdots&&\vdots&\vdots&\vdots&\vdots\\ \frac{\eta_{k+1}\eta_{k}^{-1}}{\alpha_{k+1}-\alpha_{k}}&\cdots&\frac{\eta_{n}\eta_{k}^{-1}}{\alpha_{n}-\alpha_{k}}&(e_{1}+a_{21}\alpha_{k}+a_{11}\alpha_{k}^{2})\eta_{k}^{-1}&(e_{2}+a_{22}\alpha_{k}+a_{12}\alpha_{k}^{2})\eta_{k}^{-1}&(e_{3}+a_{23}\alpha_{k}+a_{13}\alpha_{k}^{2})\eta_{k}^{-1}\\ \end{matrix}\right), \boldsymbol{V}=\left(\begin{matrix}\eta_{1}&0&\cdots&0\\ 0&\eta_{2}&\cdots&0\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&\eta_{k}\end{matrix}\right), and \widetilde{\boldsymbol{G}_{4}}=\left(\begin{matrix}\begin{matrix}1&0&\cdots&0\\ 0&1&\cdots&0\\ \vdots&\vdots&&\vdots\\ 0&0&\cdots&1\end{matrix}&\boldsymbol{F}\end{matrix}\right). It’s easy to prove that \boldsymbol{C} and \boldsymbol{V} are both nonsingular over \mathbb{F}_{q} , and so \overline{\boldsymbol{G}_{4}} and \widetilde{\boldsymbol{G}_{4}} are both the generator matrices of \mathrm{RL}_{k}(\boldsymbol{\alpha},\boldsymbol{A}_{3\times 3}). Note that \boldsymbol{A}_{3\times 3}\in\mathrm{GL}_{3}\left(\mathbb{F}_{q}\right) , it means that a_{11},a_{12} and a_{13} are not all equal to zero, and then without loss of generality, we can suppose that a_{13}\neq 0 . Thus, if \widetilde{\boldsymbol{G}_{4}}