View PDF HTML (experimental)

Abstract:The radius-one limited permutation channel $\operatorname{LPC}_{\infty}(1)$ maps a transmitted word to any word obtained by an arbitrary set of pairwise disjoint adjacent transpositions. This is the $r=1$ case of the $\ell_\infty$-limited permutation channel of Langberg et al., and is also the zero-error version of simultaneous adjacent-swap errors. We study zero-error block-concatenation codes for this channel.
Our first contribution is a $q$-ary two-stage local criterion for certifying free block-concatenation codes. The criterion replaces the global all-length confusability problem by finitely many local checks between blocks: a same-length truncated-ball test and a second-stage prefix test for unequal lengths. In the binary case, it yields explicit block-concatenation codes of rates $0.649872$, $0.652018$, and $0.653618$. The best construction improves the previous string-concatenation rate $0.642805$ and comes within $0.013049$ of the known upper bound $2/3$.
Although the criterion is only sufficient, we prove that it is rate-complete: for every alphabet size $q$, the supremum of $q$-ary block rates certified by the criterion is exactly the $q$-ary zero-error capacity $C_0^{(q)}$. Thus it imposes no asymptotic rate loss. We also give an exact product-automaton verifier which decides, for a fixed prefix-free binary block set, whether the induced finite-length codes are correcting for all lengths.
Finally, motivated by feedback settings, we study error detection. We prove a $q$-ary pairing upper bound and give a $q$-ary local detecting criterion. In the binary case, we construct a detecting block-concatenation code of rate $0.756707$, compared with the upper bound $\frac12\log_2 3\approx0.792481$.

Submission history

From: Aryeh Lev Zabokritskiy Yohananov [view email]
[v1] Thu, 25 Jun 2026 11:38:25 UTC (44 KB)