Source-linked AI summary
Codes Correcting a Burst of Deletions or Insertions
Clayton Schoeny, Antonia Wachter-Zeh, Ryan Gabrys, Eitan Yaakobi
TL;DR
Burst insertion/deletion errors motivate codes that correct clustered edits, but prior burst-deletion constructions remain above the asymptotic redundancy lower bound. The paper develops improved constructions and non-asymptotic bounds, extends the models, and shows corresponding insertion and deletion models are equivalent.
Problem
The paper addresses the gap between the asymptotic redundancy lower bound log(n)+b−1 and the prior construction redundancy b(log(n/b + 1)) for correcting b consecutive deletions.
Method
The paper derives a non-asymptotic code-size bound, constructs burst-deletion-correcting codes, extends the construction to consecutive bursts of at most b, and studies non-consecutive bursts for b=3,4.
Results
The main construction has redundancy at most log(n)+(b−1)log(log(n))+b−log(b), and the paper proves equivalence between the corresponding deletion and insertion models.
Takeaways & Limitations
The results provide improved binary codes for burst deletions and transfer directly to the corresponding burst-insertion models.
Abstract
from arXiv · showhide
This paper studies codes that correct bursts of deletions. Namely, a code will be called a $b$-burst-deletion-correcting code if it can correct a deletion of any $b$ consecutive bits. While the lower bound on the redundancy of such codes was shown by Levenshtein to be asymptotically $\log(n)+b-1$, the redundancy of the best code construction by Cheng et al. is $b(\log (n/b+1))$. In this paper we close on this gap and provide codes with redundancy at most $\log(n) + (b-1)\log(\log(n)) +b -\log(b)$. We also derive a non-asymptotic upper bound on the size of $b$-burst-deletion-correcting codes and extend the burst deletion model to two more cases: 1) A deletion burst of at most $b$ consecutive bits and 2) A deletion burst of size at most $b$ (not necessarily consecutive). We extend our code construction for the first case and study the second case for $b=3,4$. The equivalent models for insertions are also studied and are shown to be equivalent to correcting the corresponding burst of deletions.
I. INTRODUCTION
The paper studies binary codes correcting clustered insertion/deletion errors, focusing on fixed-length consecutive deletion bursts and related burst models. It addresses a gap between the asymptotic redundancy lower bound and previous constructions, while also establishing insertion–deletion equivalences.
- Motivation: Burst insertion/deletion errors arise in synchronization systems and cluster in disconnected, intermittent, and low-bandwidth environments.Applications include synchronization in wireless sensor networks and satellite communication devices.
- Problem: A b-burst-deletion-correcting code corrects any deletion of exactly b consecutive bits.The paper also defines bursts of at most b consecutive deletions and non-consecutive bursts of size at most b.
- Prior bounds: Levenshtein’s asymptotic bound implies minimum redundancy of approximately log(n)+b−1 bits.This follows from an asymptotic upper bound on code cardinality.
- Prior constructions: The best cited prior construction has redundancy b(log(n/b + 1)), leaving a significant gap from the lower bound.The paper presents its construction as an improvement over Cheng et al.’s construction.
- Scope: The paper introduces two additional deletion-burst models and extends all three models to insertions.The models include bursts of at most b consecutive deletions and non-consecutive bursts of size at most b.
1) Single-deletion-correcting codes:
The section reviews single-deletion-correcting codes and related burst-deletion constructions, then establishes equivalence between deletion and insertion correction for corresponding burst models.
- VT-codes correct either a single deletion or insertion, and V T0(n) has redundancy at most log(n+1).
- Existing burst constructions encode codewords as arrays so a burst deletion becomes one deletion in each row.
- The reviewed constructions use row restrictions or positional information to help correct deletions whose locations are known within one or two adjacent positions.
- The paper also discusses codes for at most b arbitrary-position deletions, with redundancy c · b^2 log(b) log(n) for some constant c.
- Deletion-burst correction is equivalent to insertion-burst correction for exact, at-most-b, and non-consecutive bursts.
IV. AN UPPER BOUND ON THE CODE SIZE
This section derives an explicit upper bound on the size of binary b-burst-deletion-correcting codes using a hypergraph matching and fractional-transversal argument.
- The resulting redundancy lower bound is roughly log(n) + b −1.
- The proof identifies code size with the matching number of a hypergraph and bounds that matching number through a fractional transversal.
- The constructed fractional-transversal weighting is verified to satisfy the required constraints.
- The maximum cardinality of a binary b-burst-deletion-correcting code is upper bounded by n−2b+1.
- For b = 1, the bound coincides with the known single-deletion upper bound, and for sufficiently large n it matches Levenshtein’s asymptotic upper bound.
V. CONSTRUCTION OF b-BURST-DELETION-CORRECTING CODES
The proposed construction arranges codewords in b rows and exploits the shared locations of deletions across rows to approach the redundancy lower bound.
- The construction targets redundancy better than prior results and close to the stated lower bound.
- A burst of b transmitted bits deletes exactly one bit from each row of the b-row codeword array.
- Because the burst spans at most two columns, deletion-position information in one row constrains the positions in the remaining rows.
- The first row uses a VT-code with maximum run length log(2n), enabling deletion correction while locating the deletion within a bounded consecutive range.
- The remaining b−1 rows use shifted VT-codes that correct a deletion when its position is known within log(2n) + 1 consecutive positions.
B. Run-length Limited (RLL) VT-Codes
This section combines VT single-deletion correction with a run-length constraint, limiting the longest runs so deletion locations can be localized more precisely. The resulting RLL-VT codes retain single-deletion correction while requiring at most logarithmic redundancy.
- Motivation: A VT decoder can locate the run containing a deletion but not necessarily the exact deleted position, motivating a bound on the longest run.The construction therefore limits the longest run in the first row of the codeword array.
- RLL constraint: An f(n)-RLL(n) vector has every run of 0s or 1s bounded by f(n).The associated set of all such vectors is denoted S_n(f(n)).
- RLL constraint: The log(2n)-RLL(n) constraint has redundancy at most 1 bit for all n and asymptotically approaches log(e)/2 ≈ 0.36.A union-bound argument gives at least half of all length-n vectors satisfying the constraint.
- Parameter choice: Using one additional redundancy bit guarantees that encoded vectors have no run longer than log(2n).The paper selects log(2n) because a smaller bound substantially increases redundancy, while a larger one provides no benefit.
- RLL-VT construction: The RLL-VT code VTa,f(n)(n) is defined as the intersection of a VT code with the set of vectors satisfying the run-length constraint.Because it is a VT subcode, it remains single-deletion-correcting.
- RLL-VT construction: For all n, some VTa,log(2n)(n) code has redundancy at most log(n + 1) + 1 bits.The construction uses the partition of binary vectors into n + 1 VT codebooks and the pigeonhole principle.
C. Shifted VT-Codes
Shifted VT codes exploit approximate deletion locations to correct a single deletion within a bounded positional window. They are then combined with run-limited VT codes across an array to construct codes correcting bursts of deletions.
- Burst-deletion construction: The array construction decodes the first row with an RLL-VT code and uses its result to localize deletions in the remaining rows.The remaining rows then use shifted VT codes with positional uncertainty bounded by log(n/b)+2.
- Definition: A P-bounded single-deletion-correcting code corrects a deletion when its location is known within P consecutive positions.This positional side information is the setting targeted by shifted VT codes.
- Construction: The shifted VT code is a VT variant designed to use approximate positional information about the deleted bit.Its additional parity constraint helps determine whether the deleted bit was 0 or 1.
- Correctness: Every SVTc,d(n, P) code is P-bounded single-deletion-correcting.The proof rules out two distinct codewords sharing a common length-(n−1) subsequence with deletion locations within P positions.
- Redundancy: Some SVTc,d(n, P) code has redundancy at most log(P) + 1 bits.The 2P shifted VT codes partition the binary vectors, so the pigeonhole principle guarantees a sufficiently large code.
- Burst-deletion construction: The combined code is a b-burst-deletion-correcting code, with a sufficiently large-n redundancy bound stated in Corollary 2.Theorem 5 establishes correction for the construction, while Corollary 2 summarizes its redundancy.
VI. CORRECTING A BURST OF LENGTH AT MOST b (CONSECUTIVELY)
The paper constructs codes correcting deletion bursts of at most b consecutive bits by combining level-specific codes with run-length constraints and shifted VT-codes. The construction corrects every such burst while improving the dependence of redundancy on b relative to the baseline.
- Construction: The construction intersects CL(n) with level-specific codes for bursts of sizes 3 through b, using the largest resulting intersection.Each level partitions the space, while CL(n) handles the two-deletion case.
- Construction: The universal RLL constraint limits runs in the first row of each level so shifted VT-codes can decode deletions in the remaining rows.The constraint is imposed on transformed first rows Ai(x)1 for 3 ≤ i ≤ b.
- Redundancy analysis: The universal RLL constraint has redundancy at most log(log(b)) − 1 bits.This bound is given for the Nb-URLL(n,b) constraint.
- Redundancy analysis: The selected vector a yields a VT construction with redundancy at most (b − 2) log(n) + log(log(b)) bits.The vector is chosen from the allowed range 0 ≤ ai ≤ n/i for 3 ≤ i ≤ b.
- Correctness: Theorem 6 proves correction of every consecutive deletion burst of size at most b.The decoder first determines the burst size from the received length, then decodes the first row and the remaining rows.
- Comparison: For sufficiently large n, the resulting redundancy has a log(n) term linear in b rather than quadratic in b for the baseline code.The paper states that Corollary 4 is substantially lower than the baseline redundancy.
VII. CORRECTING A BURST OF LENGTH AT MOST b (NON-CONSECUTIVELY)
The paper extends its scope from bursts of exactly b consecutive deletions to bursts containing at most b consecutive deletions. This requires correcting every burst size a with a ≤ b, under the stated divisibility assumption.
- Model: A burst of at most b consecutive deletions must correct every consecutive burst size a for a ≤ b.The section assumes (b!) divides n.
A. A 2-Deletion-1-Insertion-Burst Correcting Code
This section introduces a code for a burst consisting of two deletions followed by an insertion at the same position. The construction is proved correct and has redundancy below log(n) + 3.
- Model: A (2,1)-burst deletes two consecutive bits and inserts one bit at the same position.The paper denotes the resulting error set by D2,1(x).
- Construction: The code C2,1(n,a,c) is constructed for n ≥ 4, a ∈ Z2n−1, and c ∈ Z4.It is also a single-deletion-correcting code.
- Correctness: The construction is proved to correct every (2,1)-burst by showing that distinct codewords have disjoint received-error sets.The proof establishes D2,1(x) ∩ D2,1(y) = ∅ for distinct codewords.
- Redundancy: The redundancy of C2,1(n,a,c) is at most log(4(2n − 1)) < log(n) + 3.The bound holds for all n ≥ 4 with suitable a and c.
B. Correcting a Burst of Length at most b
The paper uses the (2,1)-burst code to construct codes correcting non-consecutive deletion bursts for b = 3 and b = 4. It proves correction guarantees with explicit redundancy bounds, while leaving b > 4 open.
- b = 3: For b = 3, Construction 6 corrects every non-consecutive deletion burst of size at most three.The cases include one deletion, three consecutive deletions, and two separated deletions handled through (2,1)-burst correction.
- b = 3: The b = 3 construction has redundancy at most 4 log(n) + 2 log(log(n)) + 6.The code combines VT-code and C2,1 partitions through a pigeonhole argument.
- b = 4: For b = 4, Construction 7 corrects every non-consecutive deletion burst of size at most four.The proof handles cases by distributing the deletions across rows as single deletions or (2,1)-bursts.
- b = 4: The b = 4 construction has redundancy at most 7 log(n) + 2 log(log(n)) + 4.The redundancy follows from the same pigeonhole-principle strategy used for b = 3.
- Scope: Efficient constructions for non-consecutive deletion bursts of size b > 4 remain an open problem.The paper states that its construction idea cannot currently be extended beyond b = 4.
VIII. CONCLUSION AND OPEN PROBLEMS
The paper constructs burst-deletion-correcting codes with improved redundancy and extends the model to additional deletion-burst settings. It also identifies open problems concerning tighter bounds, broader constructions, and multiple bursts.
- Conclusion: log(n) + (b−1) log(log(n)) + b − log(b) bits is the achieved redundancy bound for binary b-burst-deletion-correcting codes.The paper also derives a non-asymptotic upper bound on their cardinality.
- Conclusion: The construction extends to consecutive deletion bursts of size at most b and studies non-consecutive bursts of size at most b for b = 3, 4.
- Open Problems: Open problems include better redundancy bounds for the two extended models and generalizing the constructions to more than one deletion or insertion burst.
- Open Problems: Further open directions include constructing codes for arbitrary b in the non-consecutive model and improving lower bounds for the two extended models.
APPENDIX A CALCULATING THE VALUE OF N(n, b, i)
This appendix develops combinatorial and encoding tools used in the paper, including counting burst-deletion ball sizes and enforcing a bounded-run-length constraint with reversible redundancy encoding.
- Calculating N(n, b, i): N(n, b, i) counts length-n binary vectors whose b-burst deletion ball has size i.
- Calculating N(n, b, i): The counting argument arranges vectors into a b × n array, relates deletion-ball size to row runs, and counts binary vectors by their number of runs.
- Calculating N(n, b, i): The lemma for these counts is proved by induction on b, using the b = 2 base case and Vandermonde’s identity.
- Run-Length Encoding: Algorithm 1 encodes vectors so every run has length at most ⌈log(n)⌉ + 3 while preserving unique reconstruction with one additional bit.
- Run-Length Encoding: Long runs are replaced by blocks containing a marker, the run position in binary, and a delimiter, allowing reconstruction from the right.
APPENDIX C DECODER OF SHIFTED VT CODES
The shifted-VT decoder uses positional information from the first codeword-array row to localize each remaining deletion, then restores the deleted bit through weighted-sum differences.
- Decoder Operation: u is obtained from decoding the first array row, while a, the weighted-sum parameter, and P are known to the decoder in advance.
- Decoder Operation: The decoder computes the deleted bit value from parity and determines its position using the weighted-sum difference Δ.
- Decoder Operation: The decoder receives a length-(n−1) vector and uses u and P to identify the P−1 positions whose alignment is uncertain.
- Decoder Operation: If the deleted bit is 0, the decoder inserts it at the first position left of Δ 1s; if it is 1, it uses Δ−u−wt(ŷ) modulo P to locate the insertion.
- Decoder Operation: In the worked example, the decoder inserts the deleted ninth bit and reconstructs the original SVT0(16) codeword.