Recursively Extended Permutation Codes under Chebyshev Distance
Hirobe, Kasai · cs.IT,math.IT · 2026-09-05 · 原文
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 furt
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
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.
2. 领域脉络
本文类目：cs.IT、math.IT，属于其所在研究脉络的最新进展。
3. 机制拆解
The central question is how large such a code can be for a prescribed length and minimum distance.
4. 证据与数字
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).
5. 反例与边界
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.
6. 跨领域连接与意外收获
横跨 2 个类目（cs.IT、math.IT），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。