Low-Pathwidth GRAND: Exact Likelihood-Ordered Enumeration for BPSK Transmission over Correlated Gaussian Noise

想象一下，你正试图在一个嘈杂拥挤的房间里传递一条秘密信息。你大声喊出一系列词语，但风声、嘈杂的人声和回声扭曲了你的声音。听者必须猜测你原本想表达的是哪些词。在数字通信的世界里，这个“房间”是信道，这些“词语”是数据比特，而“噪声”则是将信号扰乱的随机干扰。解码器的目标就是尽管存在这种混乱，仍能找出原始信息。

几十年来，工程师们一直使用一种被称为“猜测随机加性噪声解码”（GRAND）的巧妙策略。GRAND 并不直接尝试猜测信息，而是反向操作：它猜测噪声可能是什么。它从最可能的噪声模式（如微风）开始，逐步过渡到不太可能的模式（如飓风）。如果它从接收到的信号中减去一个猜测的噪声模式后，结果是一个有效的消息，它就会停止并宣布胜利。其诀窍在于，为了使这一过程完美运行，解码器必须按照完全正确的顺序（即从概率最高到概率最低）来猜测噪声模式。

然而，当噪声不仅仅是随机静电，而是具有“相关性”时，情况就会变得非常棘手。想象一下，风并不仅仅是随机吹袭；如果某一时刻刮起了阵风，那么在下一秒很可能还会继续刮阵风。这在比特之间创造了一个复杂的连接网络，使得很难正确排列噪声模式的优先级。以往的方法试图通过忽略这些连接或将消息分解为小的、独立的块来简化问题，但这些捷径往往会导致错误的猜测。

本论文介绍了一种全新的、高精度的解码器，称为 低路径宽度 GRAND（LP-GRAND）。你可以把它想象成一位顶级侦探，他不仅是在猜测噪声，还在绘制整个噪声的“交互图”，以寻找检查可能性的完美顺序。作者展示了通过将噪声视为一种特定的数学形状（二次能量景观）并使用一种巧妙的“格形图”（trellis，一种逐步映射图），即使在噪声高度相关的情况下，也能按似然度顺序列出所有可能的噪声模式。他们从数学上证明，如果遵循此列表且不跳过任何一项，所找到的第一个有效消息保证是最佳答案。在针对特定编码的模拟中，这种新方法比以往基于“块”的捷径更频繁且更快地找到了正确的消息，证明了花时间绘制复杂的连接关系是值得的。

核心思想：绘制噪声迷宫

要理解 LP-GRAND 如何工作，让我们把噪声想象成一个巨大的、多维的迷宫。在一个简单的、“无记忆”的世界里，迷宫中的每条路径都是独立的；你在任何一点选择向左转还是向右转，都不需要担心之前的转向。但在一个“相关”的世界里，迷宫是扭曲的。在第 5 步向左转可能会迫使你在第 6 步向右转。这种扭曲正是让数学变得困难的原因。

作者意识到，对于特定类型的噪声（具有已知“精度矩阵”的高斯噪声），这个扭曲的迷宫可以被展平为一个结构化的、分层的地图，即格形图。如果噪声的连接是“稀疏”的（意味着它们只连接附近的比特，就像邻居互相交谈一样），那么这个地图就不会变得无限庞大。相反，它会保持在可控范围内，就像一个带有有限阶梯的梯子。

LP-GRAND 利用这个梯子进行“最佳优先”搜索。它不仅仅是在梯子上行走，还会计算每条路径的“能量代价”。能量越低，该噪声模式的可能性就越高。通过使用一种称为后缀动态规划的技术，解码器可以进行前瞻，准确知道接下来哪些路径是最容易探索的。这就像拥有一个 GPS，它不仅告诉你到出口的距离，还能告诉你访问每条可能的路线的精确顺序，以确保你首先找到最短的那条路。

为什么旧的捷径失败了

在此论文之前，工程师们通常通过将消息分解成小块，并假设一个块中的噪声不会影响下一个块，从而尝试简化问题。这就像是在解拼图时，忽略了拼图上的一块图像可能与相邻的一块图像相连的事实。

本文明确反对这些“基于块的近似方法”。作者指出，当噪声具有相关性时，这些捷径会遗漏“跨坐标相互作用”——即一个部分的噪声如何微妙地影响另一个部分的方式。在测试中，这些捷径经常首先猜错噪声模式，从而导致解码错误。论文表明，虽然这些捷径计算速度更快，但它们并不是“极大似然”（ML）最优的，这意味着它们不能保证找到绝对最佳的答案。相比之下，LP-GRAND 拒绝走捷径；它计算完整且相关的噪声的精确能量，确保它找到的第一个有效消息在数学上是最可能的。

结果：完美的匹配

作者不仅进行了理论推导，还对解码器进行了严格测试。他们在两种不同类型的编码上运行了模拟：一种是较小的 [20, 12] 编码，另一种是较大的 [64, 52] 编码。

在小型编码测试中，他们将 LP-GRAND 与“穷举”搜索进行了对比——后者是一种逐一检查每一个可能的消息以寻找最佳消息的方法。穷举法是金标准，但通常对于实际应用来说太慢了。在超过 10,000 帧的数据中，LP-GRAND 与穷举搜索的吻合率达到了 100%。它每次都能找到完全相同的“最佳”消息，证明了其对噪声模式的排序在数学上是完美的。

对于较大的 [64, 52] 编码，他们将 LP-GRAND 与流行的基于块的捷径（如 ORBGRAND-AI 和 ExactBlockProduct）进行了对比。在 2 dB 的信号质量下，LP-GRAND 的“块错误率”（BLER）比所有其他方法都要低。简单来说，它犯的错误更少。例如，对于一种特定的随机编码，LP-GRAND 的错误率约为 0.022，而最好的块近似方法的错误率约为 0.040。这意味着在这些测试中，LP-GRAND 的可靠性几乎是其他方法的两倍。

“路径宽度”的魔力

这个解码器的核心秘诀是一个被称为路径宽度的概念。想象噪声的连接是一个图中，点（比特）由线连接。如果图是一条长直线，路径宽度就很小。如果它是一个缠绕的线团，路径宽度就会非常大。作者表明，如果噪声矩阵具有“半带宽”（意味着它只连接距离较近的比特），那么路径宽度就足够小，足以构建一个可控的格形图。

他们在不同形状的图上进行了测试，如路径图、梯形图和二叉树。对于代表现实世界信道中常见噪声类型的“路径”和“梯形”形状，解码器表现完美。他们甚至测试了一个噪声连接被重新排列（置换）以使其不再处于整齐顺序的场景。通过使用一种称为逆 Cuthill–McKee (RCM) 的巧妙重排序技巧，他们仍然可以找到低路径宽度的结构并高效运行解码器。在一次针对打乱后的 64 比特编码的测试中，LP-GRAND 在所有 50 帧测试中都找到了正确消息，而基于块的方法则出现了 17 到 25 帧的错误。

总结

本文提出了一种针对特定且重要的噪声信道既精确又高效的解码器。它证明了，如果你愿意使用正确的数学地图，你无需在速度和准确性之间做选择。通过将噪声视为一种结构化的能量景观，并利用“低路径宽度”方法进行导航，LP-GRAND 保证了它找到的第一个有效消息就是最佳答案。虽然它比旧的捷径需要更复杂的设置，但模拟表明，对于相关噪声，这种额外的努力会带来显著减少的错误，使其成为未来高可靠通信系统的强大工具。