PaperlayerView exact revision on arXiv

Source-linked AI summary

Insdel Decoding Algorithms for Maximum Distance Separable Codes

Bencheng Fan, Margreta Kuijper, Jingge Zhu

arXiv:2610.34511v1cs.ITmath.IT

TL;DR

Efficient decoding of MDS linear block codes for insertion and deletion errors remains a challenge. The paper develops a sliding-window bounded-distance decoder for general insdel errors, alongside faster algorithms for insertion-only and deletion-only cases. For optimal Reed–Solomon codes, the general method reaches the half-Singleton bound.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The introduction motivates insdel decoding through DNA-storage errors and the need for efficient decoding of Reed–Solomon codes beyond the mostly studied dimension-two case. It frames the half-Singleton bound as a benchmark and describes a gap in methods for higher-dimensional codes.

I. INTRODUCTION

  • DNA storage encodes digital information in synthetic DNA, whose synthesis and sequencing can introduce insertion and deletion errors.The introduction also notes high costs, slow read and write speeds, and high error rates as challenges.Source: §I · p. 1
  • Levenshtein showed that a code correcting t deletions can also correct t insertions and deletions.The study of insdel-correcting codes was pioneered by Levenshtein, Varshamov, and Tenengolts.Source: §I · p. 1
  • Optimal linear codes reach the half-Singleton bound on correctable insdel errors, and optimal Reed–Solomon codes have been constructed.The bound is stated as n − 2k + 1.Source: §I · p. 1
  • Most prior Reed–Solomon insdel decoding work addresses dimension two, with relatively few works for k ≥ 3.Banerjee et al. [1] give a polynomial-time method for optimal [n, k] Reed–Solomon codes when t · k = O(n).Source: §I · p. 1
  • The introduction states that the necessary condition for the method of Banerjee et al. [1] is significantly below the half-Singleton bound.The passage's displayed condition is incomplete, so no threshold is specified here.Source: §I · p. 1

A. Our Results

The paper generalizes earlier decoding methods to MDS codes with k ≤ n/2 fixed independently of n. It proposes a sliding-window algorithm for general insdel errors and faster algorithms for insertion-only and deletion-only cases.

A. Our Results

  • The general MDS algorithm corrects up to the code's error-correction capability in O(n^(k+3)) time using a sliding window.The paper assumes k ≤ n/2 is fixed independently of n.Source: A. Our Results · p. 1
  • For optimal [n, k] Reed–Solomon codes, the general method corrects errors up to the half-Singleton bound, exceeding the scope of [1].The bound is n − 2k + 1.Source: A. Our Results · p. 1
  • Separate deletion-only and insertion-only algorithms each correct up to the code's error-correction capability in O(n^(k+1)) time.Both are described as straightforward generalizations of methods from [6].Source: A. Our Results · p. 1

B. Organization

The paper first introduces definitions and known results, then presents its decoding algorithms and concludes with a summary.

B. Organization

II. PRELIMINARIES

The preliminaries define subsequences and insdel distance, relate distance to longest common subsequences, and state the distance-based correction condition. They also establish a brute-force decoder as a baseline, with O(n^(2k+2)) time.

II. PRELIMINARIES

  • The notation x_J selects entries of x at indices in J, while G_J denotes the generator-matrix columns at those indices.The paper also uses x(1 : m) for the first m entries.Source: §II · p. 2
  • A subsequence is obtained by deleting symbols, and a common subsequence is shared by two sequences.Source: §II · p. 2
  • A code with minimum insdel distance d corrects t insdel errors if and only if 2t < d.The minimum distance is bounded above by 2n − 4k + 4, with equality defining an optimal code.Source: §II · p. 2
  • The insdel distance between two sequences is determined by their lengths and longest common subsequence length.The preliminaries cite an O(n^2)-time algorithm for the longest common subsequence problem.Source: §II · p. 2
  • The brute-force decoder corrects up to ⌊(d−1)/2⌋ insdel errors in O(n^(2k+2)) time.It searches combinations of received and codeword indices, constructs candidate codewords, and checks their distance to the received sequence.Source: §II · pp. 2–3

III. MAIN RESULTS

The section presents an insdel decoder for [n, k] MDS codes and derives optimal Reed-Solomon decoding up to the half-Singleton bound.

III. MAIN RESULTS

  • The section presents an insdel decoding algorithm for [n, k] MDS codes.It also derives algorithms for optimal [n, k] Reed-Solomon codes up to n−2k+1 insdel errors.Source: §III · p. 3
  • The received sequence length ℓ is known, but the numbers of insertions r and deletions s are unknown.Source: §III · p. 3
  • For optimal [n, k] Reed-Solomon codes, the derived algorithms address up to the half-Singleton bound, n−2k+1 errors.Source: §III · p. 3

A. Decoding MDS Codes Against Insdel Errors

A sliding-window algorithm decodes [n, k] MDS codes within half their minimum insdel distance, and its optimal Reed-Solomon special case reaches the half-Singleton bound.

A. Decoding MDS Codes Against Insdel Errors

B. Decoding MDS Codes for Deletions

The deletion-only algorithm decodes MDS codewords by testing candidate reconstructions against the received subsequence. It corrects up to ⌊(d−1)/2⌋ deletions in O(n^{k+1}) time.

B. Decoding MDS Codes for Deletions

  • The deletion-only setting requires y to be a subsequence of the transmitted codeword.The algorithm is described as a generalization of the authors’ earlier method [6].Source: B. Decoding MDS Codes for Deletions · p. 4
  • ⌊(d−1)/2⌋ deletions are corrected in O(n^{k+1}) time by Algorithm 4 for an [n, k] MDS code.If deletions exceed this bound, the algorithm returns FALSE.Source: B. Decoding MDS Codes for Deletions · p. 4
  • The algorithm reconstructs candidates from the first k received symbols and selected generator-matrix columns, accepting a candidate when y is its subsequence.It tests column-index combinations up to k + ⌊(d−1)/2⌋.Source: B. Decoding MDS Codes for Deletions · p. 4

C. Decoding MDS Codes for Insertions

The insertion-only algorithm reconstructs a codeword that is a subsequence of the received sequence. For an [n, k] MDS code, it corrects up to ⌊(d−1)/2⌋ insertions in O(n^{k+1}) time.

C. Decoding MDS Codes for Insertions

  • The insertion-only setting requires the transmitted codeword to be a subsequence of y.The algorithm generalizes the authors’ earlier method [6].Source: C. Decoding MDS Codes for Insertions · p. 5
  • ⌊(d−1)/2⌋ insertions are corrected in O(n^{k+1}) time by Algorithm 5 for an [n, k] MDS code.If insertions exceed this bound, the algorithm returns FALSE.Source: C. Decoding MDS Codes for Insertions · p. 5
  • The algorithm selects k positions among the first k + ⌊(d−1)/2⌋ received symbols, reconstructs a codeword, and tests whether it is a subsequence of y.It returns the first candidate satisfying the subsequence test.Source: C. Decoding MDS Codes for Insertions · p. 5

IV. CONCLUSIONS

The paper presents efficient insdel bounded-distance decoding algorithms for [n, k] MDS codes, including specialized algorithms for insertion-only and deletion-only errors.

IV. CONCLUSIONS

  • The general insdel decoder runs in O(n^{k+3}) time, improving on the brute-force method’s O(n^{2k+2}) time.Source: §IV · p. 5
  • The insertion-only and deletion-only algorithms each run in O(n^{k+1}) time.Source: §IV · p. 5
  • The methods use the MDS property and do not require codes to be optimal in the insdel setting.The authors identify exploiting Reed-Solomon algebraic properties as a possible route to more efficient decoding.Source: §IV · p. 5

AI STATEMENT

The authors state that AI tools were not used to produce any part of the manuscript.

AI STATEMENT

  • The manuscript’s planning, analysis, and writing were carried out entirely by the human authors.Source: AI STATEMENT · p. 6
Loading 2610.34511v1…