🔢 mathematics

Optimal Non-Binary Single-Track Gray Code

本文证明了对于素数 $p=3$ 和 $p=5$ ，存在长度为 $p^t$ 且包含 $p^{p^t}$ 个码字的非二进制单轨格雷码（Gray codes）在有限域 $\mathbb{F}_p$ 上是最优的，同时还提供了这些码在更大素数及非素数字母表大小下存在的条件。

原作者： Tuvi Etzion

发布于 2026-07-16

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Tuvi Etzion

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图追踪一个旋转的轮子，比如自行车轮或者巨大的工业风扇。你想知道轮子在每一瞬间的确切位置。为了实现这一点，工程师在轮子上涂上条纹，并使用传感器来读取它们。如果你使用标准的计数系统，当轮子正好处于两个数字之间时，传感器可能会产生混乱，因为多个条纹可能同时发生变化，从而导致“故障”，让计算机误以为轮子处于错误的位置。

为了解决这个问题，数学家们发明了一种特殊的编码，叫做格雷码（Gray code）。你可以把它想象成一种秘密语言，要从一个数字移动到下一个数字，你只能一次只改变一个单一的事物。这就像爬梯子，你只能向上或向下移动一级，绝不会一次跳两级。这确保了如果你的传感器出现轻微抖动，它们也只会看到一个微小的、无害的错误，而不是巨大的混乱。

现在，假设你想制造一个超精密的轮子，但你没有足够的空间为每一个传感器都涂上一条独立的轨道。你需要一种方法将所有信息压缩进一个更小的包里。这就是**单轨格雷码（Single-Track Gray Codes）**派上用场的地方。与其拥有许多不同的轨道，你只有一个被复制和偏移的单轨。这就像有一条长长的代码丝带缠绕在轮子上，但传感器从不同的角度来读取它。这种神奇之处在于，当从不同角度读取这条丝带时，它仍然遵循“一次只改变一件事”的规则。

长期以来，科学家们知道如何为简单的“是/否”（二进制）系统制作这些代码，但他们遇到了瓶颈：他们无法让这些代码适用于每一种可能的轮子尺寸，尤其是当轮子需要显示每一个位置而不遗漏任何位置时。他们也难以让这些代码在更复杂的系统（使用如 0, 1, 2, 3, 4 等数字的非二进制系统）中发挥作用。

这篇论文旨在打破这道墙。作者们在 T. Etzion 的带领下，已经找到了如何为使用 3 和 5 等质数作为字母表大小的系统构建这些特殊的“单轨”代码。他们不仅仅是在猜测；他们构建了一台数学机器——一个递归配方——证明了这些代码对于特定尺寸（长度为 $p^t$ ，其中 $p$ 是 3 或 5，且 $t$ 是任何大于或等于 2 的整数）的轮子是确实存在的。

以下是他们如何完成这项工作的过程，使用了几个生动的比喻：

构建模块：“自对偶”丝带

为了构建他们的代码，作者需要一种特殊的原料。想象你有一条带有数字图案的长纸带。现在，想象一个“魔镜”，它会将纸带上的每个数字加 1（即 0 变成 1，1 变成 2，而 2 则绕回 0）。

通常情况下，如果你观察原始纸带和镜像后的纸带，它们看起来会完全不同。但作者需要一种特殊的纸带，即如果你将镜像进行恰当的偏移，它看起来会与原始纸带完全相同。他们称之为自对偶序列（Self-Dual Sequences, SDS）。把它们想象成在特定的数学变换下具有完美对称性的丝带。

论文证明了你可以为使用 3 或限 5 个符号的系统创造出无穷无尽的这类丝带。他们通过展示一个逐步进行的配方来实现这一点：取一段小的丝带，添加一些额外的“风味”（数学术语称为 $Z$ 和 $Y$ ），然后，砰的一声——你就得到了一段更大的、完美的丝带。这就像分形：你取一个小的模式，应用一个规则，它就会成长为一个更大的模式，且依然保持其特殊的对称性。

组装流水线：将丝带缝合在一起

拥有丝带只是成功的一半。你需要按照特定的顺序排列这些丝带，才能创建最终的代码。如果你只是把它们乱堆在一起，传感器就会产生混乱。

作者必须安排这些丝带的顺序，使得当你从一条丝带移动到下一条时，你只会在代码中改变一个单一的位置。这是最困难的部分。这就像是在排列一副扑克牌，每次你更换一张牌时，只能改变那一张牌的值，并且你必须最终回到起点而不会陷入僵局。

对于数字 3（三进制系统）和数字 5（五进制系统），作者找到了实现这一目标的方法。他们使用了一种聪明的“合并”技术。想象你有几组丝带。有些组非常相似，仅在一个微小的点上有所不同。作者展示了如何取出两组丝带，找到它们差异的精确位置，并将它们编织成一个更大的组，同时仍保持“一次只改变一件事”的规则。

他们证明了对于基于 3 和 5 的幂次（如 $3^2, 3^3, 5^2$ 等）的尺寸，你总能找到一种方法将这些丝带缝合在一起，形成一个全周期（full-period）代码。这意味着该代码可以表示每一个可能的可能位置（ $m^{m^t}$ 个码字），而不会有任何遗漏。

他们没做的事情（以及他们排除了什么）

了解这篇论文不是在说什么非常重要。

它不是适用于所有数字的魔杖： 作者明确指出，对于二进制系统（仅使用 0 和 1），除了 $n=2$ 以外，你无法制作全周期单轨代码。他们证明了对于更大的二进制轮子，这是不可能实现的。
它还不适用于所有质数： 虽然他们证明了它适用于 3 和 5，但他们承认，对于更大的质数（如 7, 11, 13），他们还没有找到这些“种子”丝带。他们怀疑这个配方是有效的，但他们需要先找到起始模式。
它主要不适用于非质数： 他们展示了一个针对尺寸 4 的特定示例，但他们的主要、严谨的证明是针对质数的。

结论

这篇论文不仅仅是暗示这些代码可能存在；它证明了它们对于基于 3 和 5 的无穷大家族尺寸是存在的。他们提供了数学“蓝图”（递归构造）和“入门套件”（用于 $p=3$ 和 $p=5$ 的种子）来构建它们。

对于好奇的青少年或正在设计高速传感器的工程师来说，这是一件大事。这意味着对于一整类全新的机器，我们现在可以制造出更小、更精密且更不易出错的编码器。作者们开启了一扇门，表明通过正确的数学工具，我们可以以以前被认为不可能的方式来组织信息。他们不仅仅是在草堆里找针；他们制造了一台可以在无数个草堆中寻找针的机器，只要那些草堆是由 3 和 5 组成的。

技术摘要：最优非二进制单轨格雷码 (Optimal Non-Binary Single-Track Gray Code)

问题陈述
本文研究了非二进制字母表上的单轨格雷码 (Single-Track Gray Codes, STGCs) 的构造问题。长度为 $n$ 、周期为 $P$ 的 STGC 是一个由 $P$ 个不同单词组成的循环列表，其中相邻的单词在恰好一个位置上不同，且该代码阵列的 $n$ 条轨道（列）是单个轨道的循环移位。虽然已知二进制 STGC 在全周期 ( $P=2^n$ ) 下仅在 $n=2$ 时存在，且对于 $n > 2$ 的最大周期受限于 $2^n - 2^n$ ，但本文研究了在更大字母表上此类代码的存在性。具体而言，本文旨在构造长度为 $n = p^t$ 且周期为 $P = p^{p^t}$ 的 STGC，其定义在有限域 $\mathbb{F}_p$ （其中 $p$ 为素数）上，这代表了这些参数下的全周期代码。

方法论
作者采用了基于非二进制自对偶序列 (Non-Binary Self-Dual Sequences, SDSs) 的递归构造策略。该方法通过以下步骤进行：

推广二进制构造法： 本文将现有的二进制 STGC 构造定理（特别是涉及自对偶序列的前期工作中关于定理 2 的部分）推广到非二进制字母表 $\mathbb{Z}_m$ 。这种推广（定理 4）需要对 $r$ 个两两不等价、周期为 $m^n$ 的 SDS 进行排序，使得连续的序列在恰好 $m$ 个坐标上不同，并满足关于移位算子 $E$ 和差集 (difference set) 的特定条件。
SDS 的递归生成： 生成 $\mathbb{Z}_p$ $Z_{p}$ （其中 $p$ $p$ 为奇素数）上 SDS 的核心组成部分是一个递归方法。
- 基础情况： 对于给定的周期 $p^t$ ，一个 SDS 的形式为 $[X, X+1, \dots, X+(p-1)]$ 。
- 递归步骤： 为了从周期为 $p^t$ 的 SDS 构造周期为 $p^{t+1}$ 的 SDS，作者使用一个基词 $Z$ （从零开始）和辅助词 $Y_1, \dots, Y_{p-2}$ 来定义一个新的词 $V$ 。新的 SDS 由 $[V, V+1, \dots, V+(p-1)]$ 构成。
- 组合计数： 本文证明了该构造产生的不同 SDS 的确切数量为 $p^{p^t - t - 1}$ ，这是通过枚举 $Z$ 和 $Y$ 向量的选择来实现的。
排列与合并： 关键挑战在于将生成的这些 SDS 排列成一个序列，以满足 STGC 的相邻条件（即在最终代码中恰好在一个坐标上不同）。
- 作者定义了关于连续 SDS 在何处产生差异的属性 (P1) 和 (P2)。
- 文中描述了一个复杂的合并过程（针对 $p=3$ 进行了详细说明），其中会对 SDS 的组件进行组合。这涉及按权重对单词进行划分，并合并列表 $A(Z, Y)$ ，使得生成的 SDS 序列能够维持所需的差异属性。
- 合并逻辑确保了差集位置 $D_{p^{t+1}}$ 覆盖了所有必要的索引 $\{0, 1, \dots, p^t - 1\}$ 。

主要贡献与结果

存在性证明： 本文证明了对于特定的素数 $p=3$ 和 $p=5$ ，长度为 $n = p^t$ 且周期为 $P = p^{p^t}$ 的全周期非二进制 STGC 在所有 $t \ge 2$ 时均存在。
递归框架： 它提供了一个适用于任何奇素数 $p$ 的通用递归构造框架。该构造依赖于是否存在一个“合适的种子 (appropriate seed)”——即一种满足初始排列属性的、所有周期为 $p^2$ （或对于 $p=3$ 为周期 27）的 SDS 的特定排列。
特定种子： 作者提供了 $p=3$ （729 个周期为 27 的 SDS）和 $p=5$ （见附录 A 和 B）所需的种子，从而完成了这两个案例的构造。
非素数字母表： 本文指出，虽然主要关注素数域，但已有迹象表明此类代码也可能存在于非素数大小的字母表中（如示例 3 中针对 $m=4$ 的演示）。

意义与主张
本文声称提出了仅有的两类全周期单轨格雷码无限族（针对 $p=3$ 和 $p=5$ ）。其意义在于克服了二进制代码中的局限性，即在 $n > 2$ 时不存在全周期 STGC。通过利用非二进制字母表，作者实现了包含长度为 $n$ 的所有可能单词的代码（ $P = p^{p^t}$ ），这对于需要高分辨率的量化和编码应用而言是优化的。

作者谦虚地表示，对于素数 $p > 5$ ，该构造在理论上是有效的，但需要发现合适的种子（即周期为 $p^2$ 的 SDS 的排列）。他们指出，为更大的素数寻找这些种子，以及将“补码循环寄存器 (complemented cycling register)”推广到非二进制字母表，是未来的主要研究方向。本文并未声称已解决所有素数或非素数规模的问题，而是为 $p=3$ 和 $p=5$ 建立了存在性，并勾勒出了其他情况的路径。

构建模块：“自对偶”丝带

组装流水线：将丝带缝合在一起

他们没做的事情（以及他们排除了什么）

结论

类似论文