A $q$-ary Local Criterion for the Radius-One Limited Permutation Channel and Almost-Optimal Binary Block-Concatenation Codes

Abstract

The radius-one limited permutation channel ${\mathrm{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 $\frac{1}{2}{\log }_{2}3\approx 0.792481$.

36 pages