pipette
ENEnglish

Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets

Valery Grishin, Aryeh Lev Zabokritskiy

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 1 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 37 pages