CS Paper Radar

On Twisted Roth-Lempel Codes

Huiyue Lei, Haojie Gu, Jun Zhang, Haiyan Zhou

cs.IT ·submitted 2026-09-15 15:14 UTC · v1

Abstract

In 1989, Roth and Lempel constructed a well-known family of non-Reed-Solomon maximum distance separable (MDS) codes. For decades, this family of codes has attracted extensive research attention due to its algebraic structure, low-complexity decoding, and broad applications in cryptography and data storage. In this paper, we present a class of twisted Roth-Lempel codes. We investigate their minimum distance, MDS and NMDS properties. Specifically, we determine the necessary and sufficient conditions for the TRL codes to have minimum distance n-k or n-k+1. Furthermore, we determine the necessary and sufficient conditions for the TRL code to be an MDS or NMDS code. Moreover, we show that the dimension of the Schur square of the TRL code is at least 2k+1, and thus the TRL code is a non-RS code inequivalent to the corresponding RL code.

Closest papers

Nearest neighbours by meaning across the whole index.

Generalized Hamming Weights and Subcode Support Weight Distributions of Twisted Reed-Solomon Codes

cs.IT ·2026-10-12 ·Chao Liu, Hao Chen, Dabin Zheng, Yaqi Chen
similarity 0.77
Abstract · 38 pages

In this paper, we determine the generalized Hamming weight hierarchies of two classes of twisted Reed--Solomon (TRS) codes. For TRS codes with one twist, we first determine all possible values of the generalized Hamming weights. We then give a complete characterization of the weight hierarchy in terms of the minimum distance of the dual code. Explicit conditions are derived for the minimum distances of the code and its dual, which make the whole weight hierarchy explicitly computable. As special cases, the obtained results recover several known characterizations for TRS codes to be MDS, NMDS codes, and $s$-gap AMDS codes. For TRS codes with two twists, we similarly determine the complete generalized Hamming weight hierarchy. In this case, the higher generalized Hamming weights are determined by the first two generalized Hamming weights of the dual code, for which explicit rank conditions are also obtained. In addition, we further determine the subcode support weight distributions of this class of single-twist TRS codes. More precisely, for each $1 \le r \le k$, we derive an explicit formula for the number of $r$-dimensional subcodes with a prescribed support size, thereby giving a complete description of the support distribution of subcodes.

0.22

Reed-Solomon Codes at Capacity: Algorithmic List-Decoding and Proximity Gaps

cs.CC cs.IT ·2026-10-06 ·Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi
publishedhighly cited similarity 0.77
Abstract

Understanding the limits of list-decodability of Reed-Solomon codes has been one of the most important open problems in algebraic coding theory. Recently, Brakensiek, Chen, Putterman, Zhang, and Zheng, in a remarkable breakthrough, showed that Reed-Solomon (RS) codes over fields of large characteristic are algorithmically list-decodable all the way up to capacity. Building on this result, Jeronimo subsequently extended these techniques to solve the proximity-gaps question for RS codes. In this article, we give a unified and transparent exposition of these results.

0.51

Two variants of Twisted Reed-Solomon Codes

cs.IT ·2026-09-14 ·Haojie Gu, Huiyue Lei, Jun Zhang
similarity 0.75
Abstract

Generalized Reed-Solomon codes and twisted generalized Reed-Solomon codes provide important sources of maximum distance separable codes. In this paper, we study two variants obtained by introducing column twists and simultaneous row-column twists into Reed-Solomon-type evaluation codes. For the column-twisted family, we provide necessary and sufficient conditions for the code to be MDS in terms of explicit subset product conditions. Under the stated parameter assumptions, the Schur square has dimension 2k+1, which leads to MDS codes that are not equivalent to Reed-Solomon codes. For the row-column twisted family, we establish necessary and sufficient conditions for the MDS property in terms of elementary symmetric functions. The larger Schur-square dimension provides a further distinction from both Reed-Solomon codes and known twisted families, thereby yielding new non-RS MDS codes. Finally, explicit parity-check matrices and dual descriptions are obtained for both code families. These results provide a foundation for subsequent studies of self-orthogonality, hull dimensions, and applications to quantum-code constructions.

0.36

New Constructions of Additive MDS TRS Codes

cs.IT ·2026-08-19 ·Anuj Kumar Bhagat, Ankit Yadav, Ritumoni Sarma
similarity 0.74
Abstract

Additive codes over finite fields generalize linear codes, and additive MDS codes provide a natural extension of linear MDS codes. In this article, we study additive twisted Reed--Solomon (TRS) codes and obtain new constructions of additive MDS codes. First, for additive TRS codes with twist $t=2$ and an arbitrary hook, we establish necessary and sufficient conditions for the codes to be additive MDS, thereby generalizing the results in Section 3 of [Jiayu Ma et al., New families of additive non-Reed-Solomon MDS codes]. In particular, we show that the existence of an additive MDS TRS code with $t=2$ and hook $h=0$ yields codes of larger lengths than those obtained for $t=2$ and $h=k-1$ in [Jiayu Ma et al., New families of additive non-Reed-Solomon MDS codes]. Next, we consider additive TRS codes with twist vector $\mathbf{t}=(1,2)$ and hook vector $\mathbf{h}=(0,0)$, and derive necessary and sufficient conditions for them to be additive MDS. We further establish the existence of such codes. Using the Schur square technique, we obtain mild conditions under which the constructed families are inequivalent to additive Reed--Solomon (RS) codes. Finally, we determine parity-check matrices for both families of additive MDS codes considered in this article.

0.23

Extension of MDS Codes over Finite Fields

cs.IT ·2026-10-22 ·Puyin Wang, Jinquan Luo
hot direction similarity 0.74
Abstract

In this paper, we investigate extending of $[n,k,n-k+1]$ non-Reed--Solomon(non-RS) MDS codes to $[n+1,k,n-k+2]$ non-RS MDS codes. We develop a practical iterative algorithm for constructing longer MDS codes while preserving their non-RS structure. The proposed algorithm is inspired by the meet-in-the-middle algorithm in cryptanalysis. On average, it requires at most $O(kq^k)$ multiplications, compared with $O\left(\binom{n}{k-1} q^{k-1} k^3\right)$ multiplications for generic exhaustive search. Applying the proposed algorithm to several known families of MDS codes, including elliptic-curve, twisted Reed--Solomon, column-twisted Reed--Solomon, cyclic, and missing-monomial MDS codes over fields of order at most $32$, we obtain new MDS codes of increased lengths that remain inequivalent to Reed--Solomon codes. In particular, we construct $[9,4,6]$ codes over $\F_9$ and $\F_{13}$, each with Schur-square dimension $9$. Over $\F_{17}$, we obtain two inequivalent $[10,4,7]$ codes with Schur-square dimensions $9$ and $10$, respectively. The latter is the dual of an extended $[10,6,5]$ code, demonstrating that the method also applies when $k>n/2$. For these dimension-four codes, the Schur-square dimensions $9$ and $10$ exceed both that of RS code (Schur-square dimension $7$) and those of specific elliptic-curve and column-twisted Reed--Solomon families (Schur-square dimension $8$). Some of these parameters of non-RS MDS codes have not been reported before.

0.46

Insdel Decoding Algorithms for Maximum Distance Separable Codes

cs.IT ·2026-10-25 ·Bencheng Fan, Margreta Kuijper, Jingge Zhu
similarity 0.74
Abstract

In this paper, we focus on decoding MDS linear block codes for insdel errors. Building on our recent work for two-dimensional Reed-Solomon codes, we present a decoding algorithm for bounded distance decoding for the general insertion-and-deletion scenario that can be used for any MDS code of rate at most half. Our algorithm employs a sliding window and has a time complexity smaller than brute-force decoding. In particular, for optimal Reed-Solomon codes, it corrects insdel errors up to the half-Singleton bound, which exceeds the scope of existing methods. Additionally, for the special cases of insertion-only and deletion-only insdel error patterns, we present two different algorithms with a time complexity smaller than our general algorithm.

0.19

NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes

cs.CC ·2026-09-24 ·Daqing Wan, Jun Zhang
theory similarity 0.71
Abstract · 31 pages

For an $[n,K]$ Reed--Solomon code, the covering radius is $n-K$. Gandikota, Ghazi, and Grigorescu proved deterministic NP-hardness of bounded-distance decoding when the decoding radius is $d$ below the covering radius for every $1\le d\le c\log n/\log\log n$, where $c>0$ is an absolute constant. We prove that, for every fixed rational $0<α<1/2$, bounded-distance decoding is NP-complete under deterministic polynomial-time many-one reductions over explicitly represented finite extension fields for the additive gap $d=\lfloor n^α\rfloor$ below the covering radius. The hard codes have odd block length~$n$, dimension $K=(n+1)/2-d$, decoding radius $(n-1)/2$, and rate tending to $1/2$. The alphabet size is subexponential in the evaluation set size: for a fixed $0<η<1$ depending only on $α$, it is $2^{Θ(n^η\log n)}=2^{o(n)}$. The proof passes through moments subset sum on $n-1$ nonzero field elements, with required subset size $(n-1)/2$ and $d$ prescribed moments. The arithmetic ingredient is a uniform positive-completion theorem over prime fields $\mathbb{F}_q$ with $q\ge d^{2+ρ}$, for any fixed $ρ>0$. A sharper form follows from a higher-dimensional point-count estimate based on Deligne's theorem; the weaker form used in our reduction is proved more elementarily using additive-character orthogonality, the one-variable Weil bound, a moment identity of order $2d$, and Newton identities. A universal completion pool, an extension-field quotient construction, and a deterministic linear-size simultaneous power condenser complete the reduction.

0.10

Constructions of Secure Convertible Codes

cs.IT ·2026-10-26 ·Manasa Suresh B P, Vinayak Ramkumar, Myna Vajha
similarity 0.71
Abstract

Secure convertible codes, introduced by Zhang and Rashmi, achieve secrecy capacity under a passive eavesdropper model in which an eavesdropper is allowed to access any $\ell$ symbols from the initial and final codewords. In this paper, we construct two families of access-optimal secure convertible codes. The first family of codes based on Maximum Rank Distance (MRD) codes is constructed for all parameters in the merge and split regimes and requires a large field size. The second family of codes, constructed using Generalized Reed-Solomon codes, uses smaller fields but is applicable only for certain parameters in the merge and split regimes.

0.13