Papers for

storage system developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Reed solomon codes achieve optimal error correction with explicit construction

Explicit Reed-Solomon Subspace Designs: Optimal List and Line Decoding

Abstract: For any desired rate $R \in (0,1)$, and gap to list-decoding capacity $\varepsilon > 0$, we give an explicit $n^{O_{\varepsilon}(1)}$ time construction of Reed-Solomon codes over extension fields of size polynomial in the block length $n$ that can be list-decoded from a fraction $1-R-\varepsilon$ of errors with the optimal list-size of $O(\frac{1-R}{\varepsilon})$. We also give a simpler, strongly explicit construction of evaluation points for which the associated Reed-Solomon code can be list-decoded from $1-R-\varepsilon$ errors with list size $(1/\varepsilon)^{O(1/\varepsilon)}$. We provide a deterministic list-decoding algorithm for both constructions running in time $O_ε(1)\mathsf{poly}(n)$. In fact, our Reed-Solomon codes are near-optimal subspace-design codes over a subfield. Via known results, this directly implies the combinatorial list-decoding guarantee, as well as near-optimal list-recovery bounds. We also present a new reduction showing that the subspace-design guarantee also implies line decoding over the extension field itself, which then yields proximity gaps and mutual correlated agreement up to proximity parameter approaching the optimal $1-R$ radius. Compared to the recent algorithm of Brakensiek, Chen, Putterman, Zhang, and Zheng (2026), which list decodes every Reed-Solomon code over prime fields up to capacity, our approach achieves constant (in fact, near-optimal) list size rather than a polynomially growing one, at the cost of carefully choosing the code's evaluation points. In a companion paper, we show that these respective restrictions are unavoidable.

Mon 26 OctInformation TheoryComputational Complexity
The gist
Reed-Solomon codes help fix errors in digital data, but fixing lots of errors usually means dealing with many possible solutions. The authors figured out a way to explicitly pick special points for these codes that lets you fix nearly the maximum number of errors while keeping the number of possible solutions small and manageable. They also created efficient methods to decode these codes quickly. This improves on previous methods by making the problem easier to solve without losing error-correcting power.
Open → 2610.36215v1

Method computes rank of complex Hadamard error correction codes

The rank of $\mathbb{Z}_{2^s}$-linear Hadamard codes

Abstract: The canonical $\mathbb{Z}_{2^s}$-linear Hadamard codes are the Gray images of the $\mathbb{Z}_{2^s}$-additive codes. Their rank, the dimension of the binary linear span, was known in closed form only for $s\le 3$, and for $s \ge 4$ only through computer computations for small lengths. We give a method that computes the rank for every $s$. We show that the rank is a binomial polynomial in the type parameters, with coefficients $ρ_s(\boldsymbol{k})$ independent of the length. We compute all the coefficients for $s\le 5$, which yields explicit rank formulas over $\mathbb{Z}_4$ and $\mathbb{Z}_8$ (recovering the known ones), and over $\mathbb{Z}_{16}$ and $\mathbb{Z}_{32}$.

Mon 26 OctInformation Theory
The gist
Hadamard codes help detect and fix errors in digital data. The authors study a special kind called \(\mathbb{Z}_{2^s}\)-linear Hadamard codes, which were well understood only for small cases. They developed a method to calculate the rank, a key property, for all sizes, including very large ones. This rank follows a neat formula with consistent coefficients independent of code length. Their work provides exact formulas for larger code classes beyond previously known limits.
Open → 2610.34730v1

Study advances error correction bounds for codes from special curves

A study of the $m$th relative Feng-Rao distances with a special emphasis on $C_{ab}$ curves

Abstract: In the seminal paper [13], Farrán and Munuera introduced a method to establish generic information on the $m$th Feng-Rao distance via a function on arbitrary numerical semigroups that serves as a lower bound on the generalized Hamming weights of dual one-point algebraic geometry codes whenever the semigroup is Weierstrass. In the present paper, we study what we shall call the primary and dual, respectively, $m$th relative Feng-Rao distances, which serve as lower bounds on relative generalized Hamming weights of nested primary and dual, respectively, one-point codes under similar condition. A unified method for establishing generic formulas for $m$th relative Feng-Rao distances of general numerical semigroups is developed and for a large variety of numerical semigroups generated by two elements, closed formula expressions are established complementing Delgado et al.s work [8] on the $m$th Feng-Rao distances of such semigroups. Finally, for non-singular $C_{ab}$ curves, we develop a method to estimate the $m$th relative generalized Hamming weight of dual and primary one-point codes in those regions where the generic methods may fail to provide best possible results.

Mon 19 OctInformation Theory
The gist
This paper focuses on improving ways to estimate how well certain error-correcting codes perform. These codes are built from mathematical objects called numerical semigroups and special curves known as C_ab curves. The authors expand earlier work to provide better lower bounds on the ability to detect and correct multiple errors simultaneously in these codes. They develop formulas that work for a broad range of these structures and methods to handle tricky cases where generic approaches are less effective.
Open → 2610.26649v1

Universal coding method achieves near optimal data compression rates

Universal coding with the exhaustive peres transform

Abstract: Peres's iteration of von Neumann's procedure is completed into a bijection of $\bits^N$: the recursion runs to exhaustion, nothing is discarded, and every input splits into fair bits and residual bits. The residual strings form a complete prefix code that determines the number of ones of the input, so the fair bits are exactly uniform given the residual for every exchangeable law. For a Bernoulli source the likelihood factorises exactly, in decoding order, into a factor $1/2$ per fair bit and a Bernoulli factor per residual bit, with biases obtained by iterating two explicit maps. The number of fair bits per input symbol tends to the entropy almost surely, also on larger alphabets. Code B stores the fair bits and codes only the residual with an arithmetic coder; its ideal length is that of the two-part code, at most $\log\_2(N+1)+1$ bits above $-\log\_2\Pr\_θ(s)$ for every input $s$ and bias $θ$. Code C uses Rice codes instead. In experiments up to $N=2^{20}$ its mean regret stays below $200$ bits, where a Rice coder on the raw input loses a fixed fraction of the entropy on skewed sources. For sources with memory, the Burrows--Wheeler transform of the reversed string arranges all context orders in one tree of intervals; coding the leaves of a pruned tree as Bernoulli strings adapts to every Markov order up to its depth, and on suffix-closed trees the leaf weights determine the split points.

Mon 19 OctInformation Theory
The gist
Data compression works best when it can extract all the randomness from a source without losing information. The authors complete and refine a coding procedure that fully uses all input bits to produce perfectly fair (random) bits and a small residue carrying source information. For simple sources like biased coin flips, their method compresses close to the theoretical limit by separating random and structured parts efficiently. They also adapt this approach for more complex, memory-dependent data using the Burrows–Wheeler transform, building codes that adjust to different patterns automatically.
Open → 2610.26396v1

Decoding bias improves count estimates in set reconciliation protocols

Decoding Failure Biases IBLT Count Measurements: A Gaussian-Selection Law at the Peeling Threshold

Abstract: In a self-sizing set-reconciliation protocol, a small first-round Invertible Bloom Lookup Table (IBLT) sketch attempts peeling decoding; after failure, the protocol estimates the difference count $d$ from the count energy and sizes the second round from a lower quantile of the measurement. This quantile must be computed conditionally on failure: the measurement and peeling success are determined by the same random mapping, so conditioning can shift the measurement law. In the ideal peeling model, inside the critical window where failure has nondegenerate probability, the standardized energy and a statistic of the unsigned mapping that governs the peeling outcome (the precritical score) have a joint Gaussian limit with correlation $η_kρ^2$, $ρ$ being the sign imbalance and $η_k$ a closed-form constant. The measurement conditional on failure is thus a bivariate normal truncated to a half-plane, which we call the Gaussian-selection law. Since $η_k$ changes sign between $k=4$ and $k=5$, under one-sided imbalance the unconditional threshold undercovers exactly when $k\ge5$ and is conservative for $k=3,4$. The key tool is a quenched CLT for a signed quadratic form on a random overlap graph; under asymptotically balanced signs, conditioning on any unsigned mapping event that is permutation-invariant and has probability bounded away from zero leaves the standard normal limit unchanged. After failure the protocol observes the total sign; inverting the selection law yields an upper confidence bound for $d$, asymptotically conservative in the critical window and, when $d/\sqrt M\to\infty$, along the whole load axis. The experiments use analytic constants, none fitted; the unconditional threshold carries a selection error that does not vanish with scale, while the corrected selection-law threshold matches per-configuration empirical quantiles.

Thu 15 OctData Structures and AlgorithmsInformation Theory
The gist
When computers try to compare sets of items efficiently, they use small data summaries called IBLT sketches that may sometimes fail to decode correctly. The authors study how this failure influences the measurement of the difference between sets. They find that this measurement is shifted in a predictable way and describe it using a special kind of probability model called a Gaussian-selection law. This helps improve the estimate of how different the sets are after a decoding failure, making protocols more reliable and predictable.
Open → 2610.21418v1

VT codes show easier list decoding for insertions than deletions

On the Average List Size of VT Codes under Two Insertions or Two Deletions

Abstract: Levenshtein's classical theorem shows that any code that can uniquely decode from \(t\) deletions can also uniquely decode from \(t\) insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code \(\mathcal{C}\) of length \(n\) that uniquely corrects \(t'\) insertions (or deletions), we are interested in the average number of codewords returned by a \(t\)-insertion (or deletion) list decoder, where \(t' < t\). Focusing on the case of \(t'=1\) and \(t=2\), we find that under two insertions, this quantity is at most \((n+12)/4\) for any VT code of length \(n\), whereas under two deletions it is at least \(n/2 - 10\) when averaged over all length-\(n\) VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.

Sun 11 OctInformation Theory
The gist
When fixing errors in data, some errors are insertions (extra bits added) and some are deletions (bits missing). The paper studies a special kind of code called VT codes to see how many possible original messages come up when there are two errors, either insertions or deletions. The authors find that for two insertions, the average number of possible messages is about half as many as for two deletions. This means it's generally easier to narrow down the original message when errors are insertions rather than deletions.
Open → 2610.15767v1

New codes break linearity for improved sum-rank error correction

Breaking linearity in the sum-rank metric: MSRD codes from switched $σ$-rational normal curves

Abstract: We construct a family of scalar-closed, non-additive maximum sum-rank distance codes (MSRD) by switching norm components of a $σ$-rational normal curve and lifting the resulting point set through a linearized Reed--Solomon syndrome map. We characterize the admissible switches by a multiplicative stability condition on the norm classes. In particular, for $1 \leq n_i \leq m$, $N=n_1+\ldots+n_{\ell}$ and $2\leqδ\leq N-1$, every partition of $\mathbb{F}_q^*$ satisfying a specific condition, referred to as Condition $(\diamond)$, yields a code in $\mathbb{F}_{q^m}^{N}$ of size $q^{m(N-δ+1)}$ and minimum sum-rank distance $δ$; the code is non-additive whenever a curve component is retained. For $\ell\geq2$ these appear to be the first non-additive MSRD codes in the literature, all previously known families with more than one block being $\mathbb{F}_q$-linear. Moreover, every code of the family has the same sum-rank weight distribution as an $\mathbb{F}_{q^m}$-linear MSRD code with the same parameters, although the geometry of the switched set distinguishes it from linearized Reed--Solomon codes. In the single-block case, an explicit rank isometry identifies the construction with the cone codes of Durante, Grimaldi and Longobardi.

Thu 8 OctInformation Theory
The gist
When sending or storing information, it's important to detect and fix errors efficiently. The authors found new ways to build special error-correcting codes called maximum sum-rank distance (MSRD) codes that are not limited by usual linear structures. These new codes work better when data is split into multiple parts and help correct errors more flexibly without losing performance. Their construction uses mathematical curves and switching techniques previously unknown in this setting.
Open → 2610.11887v1

New codes correct substring edits with less added data

Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes

Abstract: A $k$-substring edit in a sequence first deletes a substring of length at most $k$, and then inserts a sequence of length at most $k$ at the same position. A code that can correct a $k$-substring edit is called a $k$-substring edit code. In this paper, we develop a new localization method and use it to construct a $q$-ary $k$-substring edit correcting code with $\log n+8\log\log n+o(\log\log n)$ bits of redundancy for any fixed $q\ge2$ and $k\ge1$, where $n$ is the code length. For the binary alphabet, this improves upon the redundancy $\log n+16k\log\log n+o(\log\log n)$ obtained by Li \emph{et al}. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy $\log n+O_{q,k}(1)$, which is optimal up to an additive constant. As corollaries, for all fixed $q\ge2$ and $1\le t\le T$, we obtain $q$-ary $(\le t)$-burst-deletion correcting codes and $(t,T)$-localized deletion correcting codes with redundancies $\log n+O_{q,t}(1)$ and $\log n+O_{q,T}(1)$, respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For $(\le t)$-burst-deletion correction with $t\ge2$, such redundancy had previously been achieved only for $q=t=2$ by Levenshtein in 1967.

Mon 5 OctInformation Theory
The gist
Sometimes parts of digital messages get mixed up by losing some bits and adding others in the same spot. The authors found better ways to design codes that can fix these mistakes using fewer extra bits than before. Their method works for different alphabets and sizes of edits. This helps ensure messages can be corrected more efficiently when parts are deleted and replaced by bits of a different length. They also made codes that handle related types of deletions optimally.
Open → 2610.05696v1

Codes improve correction of insertions and deletions in data transmission

Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound

Abstract: We study codes correcting adversarial insertions and deletions with list size $L$ fixed independently of the block length. We derive new achievable-rate bounds for binary codes and upper bounds over every fixed alphabet of size $q\ge2$, retaining explicit dependence on $L$. We establish a combinatorial reduction that trades $L$ units of insertion budget for one unit of deletion budget in the decoding guarantee, without changing the code or increasing the list size. Consequently, asymptotic bounds for mixed errors with insertion fraction $γ$ and deletion fraction $δ$ follow from insertion-only lower bounds at $γ+Lδ$ and deletion-only upper bounds at $δ+γ/L$. For binary unique decoding, we strictly improve Levenshtein's classical asymptotic rate lower bound for every deletion fraction $0<δ<1/2$ for which the classical rate expression is nonnegative. At $δ=0.1$, the lower bound increases from approximately $0.162009$ to $0.180431$, a relative increase of about $11.37\%$. Our framework also yields insertion and deletion lower bounds for every fixed list size. The existence proofs combine the Lovász local lemma with sampling from words having a specified number of runs, where a run is a maximal block of equal symbols. Generating functions provide refined bounds on the probability that $L+1$ sampled words share an allowed received word. We also derive a Levenshtein-type upper bound by run counting and, separately, a higher-order Elias bound using intersections and unions of the position sets used to embed $L+1$ codewords in a common supersequence. The latter recovers Yasunaga's asymptotic unique-decoding bound at $L=1$ and strictly improves the Haeupler--Shahrasbi--Sudan insertion bound for every fixed $L$ and $0<γ<q-1$. Numerical comparisons quantify the gains and remaining gaps.

Fri 18 SeptInformation Theory
The gist
Some communication errors happen when extra bits are added or some are missing, which makes fixing messages tricky. The authors look at codes that can handle a fixed number of possible corrections even as messages get longer. They found better ways to measure how much data can be safely sent while fixing such errors, especially for binary codes. Their methods improve on old estimates and help understand how to balance deleting and inserting errors with a fixed limit on possible outputs. This could make communication over noisy channels more reliable.
Open → 2609.21395v1

Complete decoding method revealed for special error-correcting codes

Norm-One Torus Decompositions and Decoding of Gashkov-Sidel'nikov Codes

Abstract: Let $q=3^m$, let $K=\mathbb F_{q^2}$, and let \[\mathcal T=\{x\in K^*:\operatorname{N}_{K/\mathbb F_q}(x)=1\}.\] For both cyclic and constacyclic Gashkov-Sidel'nikov codes, we show that the set of signed parity-check column labels is precisely $\mathcal T$. Consequently, the decoding problem separates into two stages: determining the minimum error weight associated with a syndrome $S$ and constructing an error vector attaining this minimum. We identify the former quantity with the minimum additive length of $S$ with respect to $\mathcal T$ and determine it exactly by the norm and the quadratic character of $\mathbb F_q$. We also determine the complete coset-weight distribution and recover the known covering radius $3$. For the constructive part, we use quadratic-character sums and Weil bounds to construct a coset leader for every syndrome of coset weight three. The resulting procedures give complete maximum-likelihood decoders.

Thu 17 SeptInformation Theory
The gist
The paper studies a particular family of error-correcting codes called Gashkov-Sidel'nikov codes used in digital communication. It shows how to break down the decoding problem into two parts: finding the smallest number of errors that caused a problem, and then fixing those errors exactly. The authors identify mathematical properties that let them do this efficiently and provide a full method for maximum-likelihood decoding, guaranteeing the best possible error correction.
Open → 2609.20402v1

Convolutional codes with guaranteed error protection from cyclic codes

Convolutional Codes from Cyclic Codes with Guaranteed Free and Local Minimum Distances

Abstract: This paper presents an algebraic method to construct convolutional codes with guaranteed \emph{free and local minimum distances} without limit based on cyclic codes of odd lengths. The constructions are simple but effective, and no computer search is needed. For any two positive integers $r$ and $t$ with $1 \leq r < t$, a rate-$r/t$ convolutional code $\mathcal{C}_{\text{convol}}$ can be constructed by using a chain of $r$ cyclic codes $\mathcal{C}_0, \mathcal{C}_1, \ldots, \mathcal{C}_{r-1}$ of the same length $n$ which satisfy the inclusion condition, $\mathcal{C}_0 \supset \mathcal{C}_1 \supset \ldots \supset \mathcal{C}_{r-1}$. Such a convolutional code $\mathcal{C}_{\text{convol}}$ is composed of a \emph{semi-infinite chain of identical local codes} confined in a diagonal band of width $n$. Each local code $\mathcal{C}_{\text{local}}$ of $\mathcal{C}_{\text{convol}}$ is formed from the $r$ cyclic codes in the code chain and is a specially localized subcode of the \emph{mother code} $\mathcal{C}_0$ in the code chain. The minimum distance $d_{\text{local}}$ of each local code of $\mathcal{C}_{\text{convol}}$ is lower bounded by the minimum distance $d_0$ of the mother code $\mathcal{C}_0$ in the code chain. The local structure of $\mathcal{C}_{\text{convol}}$ allows it to be decoded based on a designed parity-check matrix of the mother code $\mathcal{C}_0$ using a sliding window decoding scheme.

Tue 8 SeptInformation Theory
The gist
This paper shows a way to create special error-correcting codes, called convolutional codes, that always have strong protections against errors. They do this by building on simpler cyclic codes arranged in a sequence with a nesting property. The resulting codes have predictable minimum error distances to catch mistakes both globally and locally, and can be decoded efficiently in sliding windows. The method doesn’t need complex computer searches and applies to codes of odd lengths.
Open → 2609.08296v1