Abstract:We study deletion-correcting codes in the space of length-$n$ multisets over a $q$-ary alphabet. We present an explicit cyclic Sidon-type construction for arbitrary alphabet size $q$ and deletion radius $t$, defined by a single congruence modulo $t(t+1)^{q-2}+1$. The construction has redundancy at most $\log_q(t(t+1)^{q-2}+1)$ and admits linear-time online decoding for fixed $q$ and $t$ after finite preprocessing. We prove that its syndrome classes are asymptotically balanced and compare several general upper bounds. For a single deletion, we show that the natural sum-modulo construction is asymptotically optimal for every fixed $q$. We also obtain exact results for $q=3$ and $q=4$, including uniqueness results for optimal codes in the relevant parameter ranges, and formulate conjectures for prime alphabets.
From: Aryeh Lev Zabokritskiy Yohananov [view email]
[v1]
Fri, 9 Jan 2026 08:48:32 UTC (34 KB)
[v2]
Mon, 13 Jul 2026 17:28:45 UTC (50 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。