Abstract:We study recursively extended permutation (REP) codes under the Chebyshev distance. An REP code is built by repeatedly inserting an allowed symbol in the first coordinate and relabeling the remaining symbols. The central question is how large such a code can be for a prescribed length and minimum distance. A condition imposed separately at every extension step is sufficient to preserve distance, but it is not necessary because later extensions can increase distances. To obtain an upper bound despite this difficulty, we count the extension steps that preserve code size but are needed to remove the remaining distance shortfall. Tracking pairwise-disjoint intervals associated with codeword pairs gives a lower bound on the number of these steps. For $n>d\ge1$, this argument proves that the maximum size of a length-$n$ REP code with minimum distance at least $d$ is $\prod_{j=0}^{n-1}(\lfloor j/d\rfloor+1)$. This value equals the size of the corresponding direct product group permutation code. The recursive representation also yields a coordinate-order sequential encoder with complexity $O(n\log n)$. When the allowed insertion symbols at each step differ pairwise by at least $d$, it further yields a bounded-distance decoder with complexity $O(n\log^2 n)$.
From: Kenta Kasai [view email]
[v1]
Thu, 5 Dec 2024 13:19:48 UTC (238 KB)
[v2]
Wed, 10 Sep 2025 00:27:21 UTC (245 KB)
[v3]
Sat, 5 Sep 2026 05:37:38 UTC (243 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。