🔢 mathematics

Codes for Metastability-Containing Addition

本文通过建立用于保留不确定性的码率上界，并设计一种能够防止由亚稳态比特引起的不精确性放大的渐近最优可恢复码，来解决以区间表示的不确定值添加这一挑战。

原作者： Johannes Bund, Christoph Lenzen, Moti Medina

发布于 2026-02-09

📖 1 分钟阅读🧠 深度阅读

原作者： Johannes Bund, Christoph Lenzen, Moti Medina

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

以下是使用简单语言和日常类比对该论文进行的解释。

问题所在：添加“模糊”数字

想象一下，你正在尝试将两个数字相加，但你并不知道它们的精确值。你只知道它们落在某个微小的范围内。

数字 A 在 25 到 26 之间。
数字 B 正好是 37。

在理想世界中，你只需将范围相加即可： $25+37=62$ 且 $26+37=63$ 。因此，你的答案是“在 62 到 63 之间”。这被称为区间加法（interval addition）。

然而，在计算机芯片的世界里，情况变得很混乱。有时，信号（位/bit）会陷入一种被称为**亚稳态（metastability）**的混乱状态。这就像一个处于“开”和“关”之间中间状态的灯开关。它可能会稳定在 0，也可能稳定在 1，但现在它是“X”（未知）。

论文指出，如果你尝试使用计算机进行数学运算的标准方式（二进制代码）来添加这些“模糊”数字，这种混乱就会爆炸式增长。

类比： 想象你正在尝试叠加两张模糊的照片。如果你使用标准的相机滤镜，模糊感并不会只停留在原处，而是会扩散到整个画面。输入端的一个模糊像素可能会让整个输出图像变得无法阅读。在论文的例子中，一个不稳定的位将一个清晰的答案（62）变成了一个完全靠猜的答案（0 到 127 之间的任何数字）。

目标：一种“防模糊”的代码

研究人员想要找到一种新的编写数字的方式（编码），使得在相加时，“模糊性”（不确定性）不会恶化。他们称之为保持精度（preserving precision）。

他们还希望有一种方法可以观察混乱的结果并说：“好吧，尽管这个结果是模糊的，但我仍然可以肯定地告诉你，答案是在 62 到 63 之间。”他们称之为可恢复性（recoverability）。

解决方案：“混合”代码

团队发明了一种新的编写数字的方式，称为混合代码（Hybrid Code）。把它想象成一个用于数字的两部分地址系统：

“粗略”部分（邻里区域）： 这部分使用一种特殊的代码，称为格雷码（Gray Code）。在格雷码中，当你计数增加（1, 2, 3...）时，你一次只改变一个位。这就像你在一条街上行走，每次只把门牌号改变一位数字。这确保了如果你对自己的位置稍有困惑，你也只会对你的邻居感到困惑，而不是对整个城市感到困惑。
“精细”部分（门牌号）： 这部分使用一元码（Unary Code）。想象一排电灯开关。要表示数字 3，你打开前三个开关（111000）。要表示 4，你打开前四个（111100）。这种方式非常冗余（使用许多位），但它非常鲁棒（健壮）。如果其中一个开关卡在中间（亚稳态），你仍然可以准确判断出你处于哪个数值范围。

它们如何协同工作：
混合代码将这两者结合在一起。格雷码部分告诉你在“大局”上的位置（邻里区域），而一元码部分则提供“细节”（具体的门牌号）。

神奇之处： 研究人员设计了一种机制，使得格雷码部分的“模糊性”由一元码部分的稳定性来处理，反之亦然。
结果： 当你使用这种代码添加两个模糊数字时，结果中的“模糊性”正好等于输入的模糊性之和。它不会发生爆炸式增长。

权衡：冗余

为了实现这一点，你必须付出代价：冗余（Redundancy）。

标准二进制： 要写数字 100，你需要 7 位（$1100100$）。
混合代码： 为了使用这种新的安全特性来编写数字 100，你需要更多的位（用于邻里区域的 7 位 + 用于门牌细节的额外位）。

论文证明了一个数学规则：你无法在不增加额外位数的情况下，拥有一个既完美精确又完美可恢复的代码。 如果你想处理一定程度的“模糊性”，你必须使用额外的空间来存储这些信息。

电路：如何进行加法

论文还描述了如何构建一个物理电路（机器）来进行这种加法。

转换： 首先，机器将混合代码转换为标准二进制数字（以便使用普通的计算器）。
加法： 它对数字进行相加。
转回： 它将结果转换回混合代码。
安全网： 他们设计了机器，即使输入信号处于“卡住”（亚稳态）的状态，机器也不会崩溃或输出垃圾数据。它会输出一个与输入最匹配的最佳“模糊”答案。

论文中提到的现实世界案例

作者提到了一个使用该技术的特定领域：容错时钟同步（Fault-tolerant Clock Synchronization）。

想象一个试图达成精确时间一致的计算机网络。它们使用传感器来测量时间差。
由于物理限制，这些传感器可能会有轻微的偏差（模糊）。
计算机需要将这些测量值相加以调整它们的时钟。
使用标准数学，微小的误差可能会累积成巨大的错误。使用这种新的混合代码，计算机可以添加测量值，并确切知道其最终时间估计值的误差范围，而不会让误差爆炸。

总结

问题： 标准计算机数学在输入略有不确定（亚稳态）时会失效，导致错误爆炸。
解决方法： 一种新的“混合代码”，它混合了两种不同的数字表达方式。
益处： 它能控制不确定性的范围。如果你将两个带有微小误差的数字相加，结果会有一个微小的、可预测的误差，而不是巨大的误差。
代价： 你需要使用更多的位（更多的空间）来存储数字。
证明： 论文从数学上证明了如果不使用额外的位，你就无法做到这一点，并且他们的代码是实现这一目标最高效的方式。

技术摘要：包含亚稳态的加法编码

问题陈述
本文探讨了一个基本挑战：对带有不确定性的输入进行加法运算，特别是在模拟值对应的离散值测量容易产生亚稳态（metastability）的情况下。在标准数字电路中，亚稳态信号（用三值 $M$ 或 $X$ 表示）会破坏二进制表示。当这些不稳定的位干扰计算时，标准的二进制编码会导致不确定性的放大。例如，标准二进制加法器中单个亚稳态输入位可能会导致所有输出位都变为亚稳态，从而使结果完全失去信息量（例如，输出区间跨越了整个范围 $[0, 2^n-1]$ ）。

虽然一元（温度计）编码在亚稳态下能保持精度，但其电路规模和延迟呈指数级增长。相反，标准二进制码和格雷码（Gray codes）具有高速率（效率），但在发生亚稳态时无法保留输入区间的隐含上下界。核心问题在于设计一种编码方案，既能保持输入区间的精度（防止信息丢失），又能实现高速率（最小化冗余），并允许高效的电路实现。

方法论与定义
作者使用克莱尼三值逻辑（Kleene's ternary logic, $T = \{0, 1, M\}$ ）将该问题形式化，其中 $M$ 代表亚稳态信号。他们引入了两个关键属性来描述此类上下文中的编码：

保持性（Preservation）： 如果一个编码是 $k$ -保持的，则扩展码字（大小为 $k+1$ 的区间内所有码字的叠加）的分辨率不会引入原区间之外的新码字。这确保了输出的不确定性与输入的不确定性相匹配。
可恢复性（Recoverability）： 如果存在一个从所有二进制字符串（包括由于亚稳态导致的非码字）映射回原始区间范围的映射，则称该编码是 $k$ -可恢复的。这使得系统能够在亚稳态解决后，确定性地恢复出一个与输入不确定性一致的值。

论文建立了一个理论下界，证明任何 $k$ -可恢复的编码都需要冗余。具体而言，一个 $n$ 位 $k$ -可恢复编码最多只能编码 $2^{n-k}(k+1)$ 个值，这意味着速率上界为 $O(2^{n-k}k/n)$ 。

主要贡献与结果
主要贡献是设计了一种**“混合”编码**（ $\gamma^h_{n,k}$ ），该编码在满足保持性和可恢复性约束的同时，实现了渐近最优的速率。

混合编码构造： 该编码结合了 $n$ 位二进制反射格雷码（BRGC）部分和 $k$ 位一元温度计部分。一元编码的具体形式（即 $1^i0^{k-i}$ 或 $0^i1^{k-i}$ ）由 BRGC 部分的奇偶性决定。
性能保证： 该混合编码被证明是 $k$ -保持 且 $\lceil k/2 \rceil$ -可恢复 的。这意味着它可以容忍输入中最多 $k$ 个不稳定位而不放大输出的不精确度，并且可以确定性地恢复大小至多为 $\lceil k/2 \rceil$ 的区间。
电路实现： 作者为该编码设计了一个加法电路。
- 对于稳定输入，电路将 BRGC 和一元部分转换为二进制，执行标准二进制加法，然后将结果转回。该方案的规模为 $O(n+k)$ ，深度为 $O(\log n + \log k)$ 。
- 为了处理亚稳态输入（扩展码字），作者应用了已知的包含亚稳态（mc）的电路构造。利用 Ikenmeyer 等人的通用构造，他们获得了一个规模为 $(n+k)^{O(k)}$ 、深度为 $O(k \log n + \log k)$ 的纯组合逻辑 mc 加法器。或者，通过使用掩码寄存器（masking registers），可以实现规模为 $O(k(n+k))$ 、深度为 $O(\log n + \log k)$ 的电路。
最优性： 论文证明，该编码的速率与其为 $k$ -保持编码所推导出的理论上界相匹配，具有渐近最优性。

意义与主张
论文声称，这项工作弥合了在一元编码的低效性与二进制编码在亚稳态下的信息丢失之间的鸿沟。

理论意义： 它形式化了精度保持、可恢复性和编码速率之间的权衡，并证明了更高阶的可恢复性严格需要冗余。
实际应用： 作者强调了该编码在容错硬件时钟同步（特别是 Lynch-Welch 算法）中的应用。在这种背景下，时间数字转换器（TDC）产生的相位测量值最多包含一个亚稳态位。所提出的混合编码允许这些测量值在全亚稳态包含的数字方式下进行求和与平均（除以 2），而无需诉诸低效的一元加法器，或退回到会增加延迟的同步器。
未来展望： 作者推测，基于现有技术进行精心设计可以带来显著的延迟降低。他们建议，将这些编码与基于同步器的设计或掩码存储元件相结合，可以改善其与单纯基于同步器的方法相比的延迟-MTBF（平均故障间隔时间）权衡，尽管他们指出，定量的验证需要进一步的后仿真分析。

论文总结道，虽然混合编码引入了轻微的不对称性（容忍 $k$ 个不精确，但仅能恢复 $\lceil k/2 \rceil$ ），但它为不确定性下的加法提供了一种鲁棒且高效率的解决方案，使得数字控制回路即使在存在亚稳态输入时也能正常运行。