Source-linked AI summary
A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
Neehar Verma, Camilla Hollanti, Razane Tajeddine
TL;DR
Insertion/deletion errors disrupt alignment, motivating codes that can recover data despite such errors. The paper proves rate and error-correction bounds for linear-code list decoding and gives a construction for single-insdel correction. For fields of size q ≥3, the error bound is strict when the code lacks the all-ones vector.
Problem
Insertion/deletion errors disrupt transmitted-to-received alignment, and the paper addresses the limited understanding of linear-code list decoding against these errors.
Source: §I · p. 1Method
The paper proves single-error rate and generalized error-correction bounds for fixed list size, then constructs codes attaining the optimal rate for single-insdel correction.
Source: B. List decoding of insdel errors · p. 3, §III · p. 4, §IV · p. 10Results
An [n, k] linear code can correct at most n − L/(L+1)k + 1 insdel errors, with a strict bound when it does not contain the all-ones vector.
Source: B. List decoding of insdel errors · p. 3, §III · pp. 8–9Takeaways & Limitations
The single-insdel construction attains the optimal rate for each fixed list size; achieving the generalized bounds in Corollaries 8 and 11 remains future work.
Source: §IV · p. 10, §V · p. 12
Abstract
from arXiv · showhide
We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.
I. INTRODUCTION
The introduction motivates coding for insertion/deletion errors in DNA storage, where errors disrupt alignment and can change message length. It places list decoding against the background of Singleton-type bounds.
I. INTRODUCTION
- Insdel errors remove or add symbols at unknown positions, disrupting coordinate alignment and potentially changing message length.DNA synthesis and sequencing are described as inherently susceptible to these errors.Source: §I · p. 1
- Coding theory for reliable storage and communication has renewed relevance with efficient DNA synthesis and sequencing enabling DNA-based archival storage.Surveys – and an information-theoretic perspective are cited as complementary background.Source: §I · p. 1
- List decoding allows a bounded list of candidate codewords, relaxing unique decoding and permitting parameters beyond the Singleton bound.The generalized Singleton bound gives the relaxed constraints.Source: §I · pp. 1–2
A. Unique decoding of insdel errors
Prior work established insdel bounds and constructions, with non-linear codes achieving rates unavailable to linear codes. Linear-code rate restrictions motivate this paper’s focus on their capabilities.
A. Unique decoding of insdel errors
- Explicit efficiently decodable codes correct a δ-fraction of insdel errors at rate 1 −δ −ε, essentially attaining the Singleton-bound optimum.This result is reported for codes not necessarily constrained by linearity.Source: A. Unique decoding of insdel errors · p. 2
- Linear codes correcting a δ-fraction of insdel errors have rate at most 1−δ/2+o(1), the alphabet-independent half-Singleton bound.The bound corresponds to correcting at most n−2k+1 insdel errors.Source: A. Unique decoding of insdel errors · p. 2
- A linear code correcting a single deletion has rate at most 1/2, while non-linear codes can achieve rate one.For linear codes not containing the all-ones vector, the half-Singleton bound is strict.Source: A. Unique decoding of insdel errors · p. 2
- Random Reed–Solomon codes and randomized algebraic-geometry code families approach the half-Singleton bound under the stated field-size regimes –[29].The cited results progress from large fields to substantially smaller linear-sized fields and then constant-sized fields.Source: A. Unique decoding of insdel errors · p. 2
B. List decoding of insdel errors
Prior insdel list-decoding work largely studied non-linear codes, while linear-code results remained limited. This paper develops fixed-list-size bounds and an optimal-rate construction for linear codes over fields of size at least three.
B. List decoding of insdel errors
- Earlier insdel list-decoding studies developed Johnson-type bounds, examined Varshamov–Tenengolts codes, and derived binary insertion capacity –[39].Explicit constructions were also reported for polynomially bounded and constant-sized lists [17],,,.Source: B. List decoding of insdel errors · pp. 2–3
- For linear codes, prior work connected list recoverability with insdel list decoding and used polynomially bounded lists to circumvent the single-deletion rate restriction,.The latter work gives binary random linear-code results and explicit concatenated constructions with reasonably sized lists and rate approaching one.Source: B. List decoding of insdel errors · p. 3
- For fixed L, a linear code over a field of size q ≥3 has single-insdel list-decoding rate at most L/(L+1), recovering the unique-decoding restriction at L = 1.The paper also bounds correctable errors by n − L/(L+1)k + 1 and shows strictness when the code lacks the all-ones vector.Source: B. List decoding of insdel errors · p. 3
- The paper gives a simple construction attaining the maximum possible rate/distance tradeoff for single-insdel correction at any fixed list size.Its stated results apply to linear codes over fields of size q ≥3.Source: B. List decoding of insdel errors · p. 3
II. NOTATION AND PRELIMINARIES
The preliminaries set the code parameters and edit-distance framework used to state insdel correction and list decoding. They recall the existing half-Singleton bound before introducing list decoding.
II. NOTATION AND PRELIMINARIES
- An [n, k, d]_q linear code is a subspace parameterized by length n, dimension k, and minimum Hamming distance d, with d ≤ n − k + 1.Codes meeting this Singleton bound are maximum distance separable (MDS).Source: §II · p. 3
- Edit distance is the minimum number of insertions and deletions needed to convert one string into another.The edit ball B(y, r) consists of strings at edit distance at most r from y.Source: §II · pp. 3–4
- An [n, k] linear code can correct at most n−2k +1 insdel errors, the non-asymptotic half-Singleton bound.The recalled single-insdel rate restriction says a code of rate at least 1/2 cannot correct a single insertion or deletion.Source: §II · p. 4
- A code is (δ, L)-list decodable when every received word has at most L codewords within edit distance δn.The definition uses edit balls around received words.Source: §II · p. 4
III. GENERALIZED HALF-SINGLETON BOUND
The section derives list-decoding limits for linear codes over fields of size q ≥ 3, extending the half-Singleton rate restriction to fixed list size L. It gives an asymptotic rate bound and a stricter result for codes that do not contain the all-ones vector.
III. GENERALIZED HALF-SINGLETON BOUND
- A linear code with rate greater than L/(L+1) cannot list decode a single insertion/deletion with list size L.The result holds over fields of size q ≥ 3 and recovers the unique-decoding rate restriction when L = 1.Source: §III · pp. 4, 7
- The proof constructs a common received word for at least L + 1 distinct codewords, contradicting list size L.The argument combines L−2|B|+1 codewords with additional codewords associated with positions in B.Source: §III · p. 8
- For q = 2, the main bounds need additional conditions: the one-error result applies when the code has Hamming distance d > 1, and the multi-error result when d > t.For L ≥ 3, a binary single-parity-check code with d = 1 gives a counterexample.Source: §III · p. 8
- As n tends to infinity, a code that is (δ, L)-list decodable has rate at most L/(L+1)(1−δ) + o(1).Source: §III · p. 9
- If the all-ones vector is not in the code, the one-error list-decoding bound is strict for q ≥ 3.The corresponding multi-error strict bound is stated for t ≤ n−k.Source: §III · pp. 9–10
IV. OPTIMAL CONSTRUCTION
The paper gives explicit constructions over fields of size q ≥3 that attain the optimal rate for list decoding a single insertion/deletion error at any fixed list size. Construction 14 provides a concrete family, with the proof addressing deletion and insertion cases.
IV. OPTIMAL CONSTRUCTION
- The explicit constructions attain the bound for single-insdel list decoding over fields of size q ≥3 and any fixed list size L.The construction section identifies its codes as attaining the bound; the conclusion describes the achieved rate as optimal.Source: §IV · p. 10
- Construction 14 gives an [2(L+1), 2L] code that is (1/(2L+1), L)-list decodable for L ≥2.The field must have q ≥3.Source: §IV · p. 10
- The proof eliminates candidate deletion-coordinate tuples and rules out the remaining insertion-coordinate possibilities.The deletion argument concludes that the code corrects one deletion with list size at most L; the insertion argument treats L>2 and the remaining L=2 case.Source: §IV · p. 11
V. CONCLUSION
The paper concludes with an upper bound on the rate of linear codes over fields of size q ≥3 for insdel list decoding and an optimal-rate single-insdel construction. It leaves constructions attaining the bounds in Corollaries 8 and 11 as future work.
V. CONCLUSION
- The paper provides an upper bound on the rate of linear codes over F_q, q ≥3, capable of list decoding insertion and deletion errors.Source: §V · p. 12
- The paper gives a code construction attaining the optimal rate for any list size when correcting a single insdel error.Source: §V · p. 12
- Constructing codes that achieve the bounds in Corollaries 8 and 11 remains future work.Source: §V · p. 12
AI USAGE
The authors report using ChatGPT for grammatical edits, readability improvements, proof sanity checks, and a binary counterexample, while taking responsibility for the manuscript's claims.
AI USAGE
- ChatGPT was used to check grammatical errors and improve the article's readability.Source: AI USAGE · p. 14
- ChatGPT was also used for proof sanity checks and to provide the binary counterexample in Remark 9.Source: AI USAGE · p. 14
- The authors state that they take full responsibility for all manuscript claims.Source: AI USAGE · p. 14