Source-linked AI summary
Optimal $k$-Deletion Correcting Codes
Jin Sima, Jehoshua Bruck
TL;DR
Deterministic k-deletion codes with optimal-order redundancy remained elusive despite the known O(k log N) redundancy bound. This paper combines a VT generalization on constrained sequences with concatenated coding and a single synchronization pattern; its construction achieves 8k log n+o(log n) redundancy.
Problem
A deterministic k-deletion code construction attaining the known O(k log N) optimal-order redundancy remained elusive.
Source: §I · p. 1Method
The construction generalizes VT checks for constrained sequences and combines blockwise concatenated coding with a single synchronization pattern.
Source: §I · pp. 1–2Results
Redundancy is 8k log n+o(log n), with encoding O(n^(2k+1)) and decoding O(n^(k+1)) for length-n messages.
Source: §I · p. 1, §VI · p. 12Takeaways & Limitations
The construction is optimal redundancy-wise, not cardinality-wise; finding optimal cardinality appears nontrivial even for k=1.
Source: §I · p. 1Optimal cardinality remains unresolved and appears nontrivial even for k=1.
Source: §I · p. 1
Abstract
from arXiv · showhide
Levenshtein introduced the problem of constructing $k$-deletion correcting codes in 1966, proved that the optimal redundancy of those codes is $O(k\log N)$, and proposed an optimal redundancy single-deletion correcting code (using the so-called VT construction). However, the problem of constructing optimal redundancy $k$-deletion correcting codes remained open. Our key contribution is a solution to this longstanding open problem. We present a $k$-deletion correcting code that has redundancy $8k\log n +o(\log n)$ and encoding/decoding algorithms of complexity $O(n^{2k+1})$ for constant $k$.
I. INTRODUCTION
The paper presents a k-deletion code with 8k log n+o(log n) redundancy and encoding and decoding algorithms with stated polynomial complexities. Its construction combines a VT generalization for constrained sequences with block coding and a single synchronization pattern.
I. INTRODUCTION
- Levenshtein established O(k log N) optimal-order redundancy and a single-deletion VT code, but deterministic optimal-order k-deletion construction remained elusive.The paper states its optimality is redundancy-wise, not cardinality-wise; optimal cardinality appears nontrivial even for k=1.Source: §I · p. 1
- N=n+8k log n+o(log n) yields redundancy 8k log n+o(log n), with encoding O(n^(2k+1)) and decoding O(n^(k+1)).The theorem specifies recovery of every length-n message from any length N−k subsequence of its encoding.Source: §I · p. 1
- For k=t/2, higher-order parity checks work when protected sequences have at least k positions between adjacent 1s.This generalizes the two-deletion case, where such checks work for sequences with no adjacent 1s.Source: §I · p. 1
- A single synchronization pattern separates blocks and may itself be destroyed or generated by deletions or insertions, improving on.The construction uses concatenated coding, with blocks protected by inner codes and their combined data by an outer code.Source: §I · pp. 1–2
II. OUTLINE AND PRELIMINARIES
The construction protects a synchronization vector and then recovers the original sequence, using separate recovery steps for k-dense and arbitrary sequences. Its outline combines deletion-ball properties, hashes, and a reversible transformation.
II. OUTLINE AND PRELIMINARIES
- If c′ lies in c’s k-deletion ball and the vectors f(1sync(c)) match, then the synchronization vectors are identical.The deletion ball consists of sequences sharing a length n − k subsequence with c.Source: §II · p. 2
- Modulo operations reduce the synchronization-vector protection to a hash whose size is O(k log n), after Lemma 1 establishes its recoverability.The outline presents this compression as the step from O(k^2 log n) to O(k log n) redundancy.Source: §II · p. 2
- A k-dense sequence can be recovered from its synchronization vector, a length n − k subsequence, and a 4k log n + o(log n)-bit hash.The sequence is k-dense when the zero runs in its synchronization vector satisfy the stated length bound.Source: §II · p. 3
- A reversible map transforms any n-bit sequence into a k-dense sequence by adding 3k + 3⌈log k⌉ + 15 bits.The map is computable in poly(n, k) time, and its output determines the original sequence.Source: §II · p. 3
- For fixed k, short-sequence deletion recovery uses hashes on ⌈log n⌉-bit blocks, with each block hash sized 2k log log n + O(1) bits.The blocks are padded with zeros if needed, and their hashes are concatenated.Source: §II · p. 3
III. PROTECTING THE SYNCHRONIZATION VECTORS
The synchronization vector remains recoverable after deletions because changes to it are bounded and its separated 1 entries support higher-order parity checks. The proof uses this structure to establish uniqueness from the checks.
III. PROTECTING THE SYNCHRONIZATION VECTORS
- The section combines the deletion-ball bound with parity-check uniqueness to recover the synchronization vector from f(1sync(c)).The proof first bounds the synchronization-vector deletion ball and then applies higher-order parity checks to the separated 1 entries.Source: §III · pp. 3–4
- If c′ is in the k-deletion ball of c, then 1sync(c′) is in the 3k-deletion ball of 1sync(c).A single deletion can cause at most two deletions and one insertion in the synchronization vector; the proof considers cases where a pattern is destroyed or generated, or neither.Source: §III · pp. 3–4
- For sequences in R3k, matching the higher-order parity checks after up to 3k deletions implies the sequences are identical.R3k requires at least 3k−1 zeros between consecutive 1 entries.Source: §III · p. 4
- The parity-check argument rules out a nonzero matrix A when Ax = 0, forcing the corresponding tail-count differences to vanish.The proof uses nonzero columns of A to form a square submatrix whose determinant is positive, contradicting a nonzero solution.Source: §III · pp. 6–7
A. Proof of Lemma 1
The proof of Lemma 1 bounds the synchronization-vector discrepancy after deletions, then uses equality of f to establish equality of the vectors.
A. Proof of Lemma 1
- After the deletion-ball bound, the difference between the numbers of 1 entries in corresponding suffixes of synchronization vectors is at most 3k.The suffix counts are compared for every index i.Source: A. Proof of Lemma 1 · p. 7
- If f(1sync(c)) = f(1sync(c′)), the corresponding parity-check values are congruent, and the proof uses Proposition 2 to conclude that the synchronization vectors match.The cited argument first obtains equality of the parity-check values from the congruences.Source: A. Proof of Lemma 1 · p. 7
B. Proof of Lemma 2
Lemma 2 compresses the synchronization-vector hash by choosing a modulus that avoids divisors associated with competing sequences. This makes matching residues sufficient for recovery.
B. Proof of Lemma 2
- The proof chooses p(c) so it divides none of the nonzero differences between M(f(1sync(c))) and competing sequences’ encoded values.Lemma 1 ensures these differences are nonzero for other sequences in c’s k-deletion ball.Source: B. Proof of Lemma 2 · p. 7
- The number of divisors used to select p(c) is bounded by 2^o(log n), using the stated divisor bound.The bound is expressed in terms of k and n in the proof.Source: B. Proof of Lemma 2 · p. 7
- If c′ lies in c’s k-deletion ball and the encoded values match modulo p(c), then c′ = c.The selected modulus does not divide any nonzero difference, so matching residues force the difference to be zero.Source: B. Proof of Lemma 2 · p. 7
IV. HASH FOR k dense SEQUENCES
For a k-dense sequence with its synchronization vector known, Hash_k enables recovery after k deletions using 4k log n + o(log n) bits. It hashes blocks and uses Reed-Solomon redundancy to correct block-hash errors caused by deletions.
IV. HASH FOR k dense SEQUENCES
- The synchronization-vector 1 positions split the sequence into blocks of length at most L, whose H hashes form a sequence protected against 2k symbol-substitution errors.The Reed-Solomon redundancy is applied to the sequence of block hashes.Source: §IV · p. 7
- 4k log n + o(log n) bits suffice for Hash_k to recover a k-dense sequence from its length n−k subsequence when its synchronization vector is known.The construction’s block hashes are protected by Reed-Solomon redundancy.Source: §IV · pp. 7–8
- Aligning synchronization positions in the received subsequence yields block estimates, and each deletion affects at most two good intervals, so at most 2k block hashes are erroneous.The Reed-Solomon decoder corrects those errors, after which the original blocks and sequence can be recovered.Source: §IV · p. 8
V. TRANSFORMATION TO k dense SEQUENCES
The section constructs reversible transformations that make sequences satisfy two properties sufficient for k-density. One transformation creates frequent synchronization patterns; another removes such patterns from selected short blocks.
V. TRANSFORMATION TO k dense SEQUENCES
- A sequence satisfying Properties 1 and 2 is k-dense, with consecutive synchronization-vector 1 positions at most B + R + 1 apart.Property 1 supplies a pattern after the pattern-free interval supplied by Property 2.Source: §V · p. 8
- T1 maps any length-n sequence to a recoverable sequence of length n + 2⌈log k⌉ + 10 satisfying Property 1.It scans for blocks without the required run, encodes them with φ, and appends recovery information.Source: §V · p. 9
- T1’s encoding and decoding are reversible, and its stated computation time is O(n^2 k log n log^2 k).The transformation preserves the sequence length apart from its fixed added overhead.Source: §V · pp. 9–10
- T2 reversibly maps a length-(3k + ⌈log k⌉ + 4) block containing the specified run to a block one bit shorter with no such run.The stated computation time is O(k^2 log k).Source: §V · p. 10
A. Proof of Lemma 4
The transformation T combines T1 with block replacements using T2 to produce a reversible k-dense sequence. It preserves both defining properties and has polynomial complexity in n and k.
A. Proof of Lemma 4
- T starts with T1(c), then replaces selected blocks from length-R intervals with T2-encoded middle blocks to enforce Property 2.Its output length remains n + 3k + 3⌈log k⌉ + 15.Source: A. Proof of Lemma 4 · pp. 10–11
- The resulting sequence retains Property 1 and satisfies Property 2, so Proposition 3 establishes that it is k-dense.The construction uses T2 blocks to create the required pattern-free subintervals.Source: A. Proof of Lemma 4 · p. 11
- The encoding procedure has complexity at most O(n^2 k^2 log k log n), hence polynomial in n and k.The bound follows from O(n^2) iterations, each taking O(k log k R) time.Source: A. Proof of Lemma 4 · p. 11
- The transformation is reversible: its decoder reverses the encoding operations and recovers c from T(c).The stated decoding procedure identifies inserted material using its ending marker.Source: A. Proof of Lemma 4 · p. 11
VI. ENCODING
The encoder concatenates the transformed sequence T(c) with two redundancy components. Together, they allow recovery after k deletions, with redundancy 8k log n + o(log n).
VI. ENCODING
- The encoding is E(c) = (T(c), R′(c), R′′(c)), where R′ contains synchronization and block-hash information and R′′ contains a repeated hash of R′.T(c) is the transformation defined in Lemma 4.Source: §VI · p. 11
- 8k log n + o(log n) is the redundancy of E(c), with R′ contributing 8k log n + o(log n) and R′′ contributing o(log n).The construction recovers R′ using R′′, then recovers T(c) using R′ and the synchronization vector.Source: §VI · p. 12
- Encoding takes O(n^(2k+1)) time, while decoding takes O(n^(k+1)) time.The respective costs come from brute-force searches for p(T(c)) and for the correct synchronization vector.Source: §VI · p. 12
VII. CONCLUSION AND FUTURE WORK
The conclusion states that the paper constructs a k-deletion correcting code with optimal-order redundancy and identifies two open directions: improving algorithmic complexity and achieving systematic codes with optimal redundancy.
VII. CONCLUSION AND FUTURE WORK
- The constructed k-deletion correcting code achieves optimal-order redundancy.Source: §VII · p. 12
- Finding encoding and decoding algorithms with O(N^O(1)) complexity for this code remains open.Source: §VII · p. 12
- Constructing a systematic k-deletion code with optimal redundancy also remains an open problem.Source: §VII · p. 12