排列不变二进制编码的最优构造方法及相关检索关键词

你遇到的核心问题是循环移位等价类的唯一编码问题：常规顺序二进制编码的任意循环移位结果都会被识别为不同值，完全无法适配无固定起始位的识别场景；你提到的按置位比特（hot bits）数量编号的方案确实编码效率极低，n位长度下最多只能表示n+1个对象，远达不到理论容量上限。

最优编码方案选型 #

• 首先明确n位编码的理论容量上限：n位二进制串的循环移位等价类总数由项链计数公式计算，表达式为(1/n) * Σ_{d|n} φ(d) * 2^(n/d)，其中φ为欧拉函数，d取n的所有正因数。以4位长度编码为例，总共有8个互不重叠的循环移位等价类，而按置位比特数计数的方案仅能表示0~4共5个对象，容量差距随编码位长增加会快速拉大。
• 达到理论容量上限的实用编码方案为项链码（Necklace Code）：构造逻辑是对每个循环移位等价类，选取字典序最小的二进制串作为该类的唯一代表元，所有代表元构成的码集天然具备循环移位不变性——识别时无论收到的编码移位了多少位，只要归到对应等价类匹配代表元，就能唯一映射到目标对象，没有容量浪费。
• 如果场景有抗干扰、校验需求，可以选择固定权重的项链码（即限定每个编码的置位比特总数一致），或者基于德布鲁因序列构造的带同步信息的循环不变码，这类编码已经在旋转位置传感器、环形条码、无锚点RFID识别等场景有成熟工程落地。
• 你最初想到的按置位比特数编号的方案，本质是项链码的一个极小子集，仅利用了“置位比特数不同的串一定不属于同一循环等价类”的特性，完全浪费了同比特数下不同等价类的编码容量，因此效率极低。

自主研究检索关键词 #

• 基础理论方向：循环移位不变码（Cyclic Shift Invariant Code）、项链计数（Necklace Counting）、项链码（Necklace Code）、Lyndon字（Lyndon Word，项链码的核心构造基础）、二进制串循环等价类
• 工程落地方向：无起始位帧同步编码、旋转位置编码、环形条码编码、无锚点RFID识别编码
• 延伸参考方向：德布鲁因序列（De Bruijn Sequence）、循环纠错码

内容的提问来源于stack exchange，提问作者Mr Squid