Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets
In the authors' words
A literal-systematic -ary code leaves its information symbols unchanged and appends deletion-prone checks. For , a known lower bound requires three such checks to correct two arbitrary deletions. We give a uniform construction meeting this minimum over a power-of-two alphabet , with polynomial-time encoding and decoding. It combines boundary authentication, symmetric field checks, and a pointwise computable coloring of a sparse conflict graph. For one adjacent burst of length at most two, we give a closed-form construction with three check symbols over . Alphabet size and fixed-alphabet bit redundancy remain separate objectives.
Main resultLimitation the authors admit
Appeared: Thursday, October 1. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 37 pages