伪随机纠错码
内容提要
该文综述了分布式存储与传输中的多种编码方案，包括噪声下实值信号可靠重建、局部可恢复编码、Reed-Muller码子码解码、图压缩、语言模型水印及对抗性错误容错。多数方案借助凸优化或机器学习，实验证明性能优异。
延伸解读
编码方案的时间跨度与多样性
文章列举的编码方案从2006年延续至2023年，涵盖实值信号重建、分布式计算、局部可恢复编码、Reed-Muller码解码、图压缩、语言模型水印及对抗性错误容错等多个方向。这种时间跨度与主题多样性表明，编码理论在分布式存储与传输领域持续活跃，且不断吸收凸优化、机器学习等新工具。读者可借此了解该领域的研究脉络与热点变迁。
凸优化与机器学习在解码中的角色
多个方案借助凸优化或机器学习来提升解码性能。例如，实值信号重建仅涉及简单凸优化问题；Reed-Muller码子码解码采用基于机器学习的投影剪枝框架，以合理代价维持近乎全投影的解码率。这些方法降低了传统解码的复杂度，同时保持了高性能，反映了编码理论与优化、学习技术交叉融合的趋势。
分布式存储中的局部性与修复效率
针对分布式存储，文章介绍了局部可恢复编码（LRC）和简单查找修复方案。LRC通过特殊多项式构造实现局部恢复，并支持多个不相交恢复集，提升热数据可用性；另一种方案则实现简单查找修复且具有任意高数据传输速率，在云存储模拟中优于复制和标准Reed-Solomon编码。这些工作共同关注降低修复过程中的数据传输开销。
语言模型水印的鲁棒性与局限
文章提出在自回归语言模型中植入水印的方法，通过随机水印密钥映射样本生成文本，检测时对齐随机数序列。实验显示，在OPT-1.3B和LLaMA-7B中，即使40-50%的标记被破坏，仍可可靠检测（p≤0.01）。但对于Alpaca-7B，由于响应熵较低，仅约25%的响应可检测，且对某些自动释义攻击不够鲁棒。这表明水印效果受模型和文本特性影响。
Q&A
在噪声干扰下，如何实现实值信号的可靠传输和重建？
本文提出了两种解码方案，可以显著降低传输错误对信息重建的影响，且只涉及简单的凸优化问题。数值模拟表明，该方案表现优异。
局部可恢复编码（LRC）是如何实现热数据的高可用性的？
LRC使用特殊构造的多项式在有限域上进行编码，并通过多项式插值进行局部恢复。此外，还构造出具有多个不相交恢复集的编码，从而实现对热数据的高可用性。
Reed-Muller码的子码解码有哪些新方法？
本文研究了Reed-Muller (RM) 码的子码及其解码，并提供了一种基于机器学习的投影剪枝框架，能以合理的代价维持几乎等同于全投影情况的解码率。
如何对图数据进行高效压缩？
通过基于Pólya的urn模型的无参数模型，利用随机边编码(Random Edge Coding)方法进行图压缩，依靠位后编码(bits-back coding)从边列表中无需替换抽样边和节点。实验证明，Random Edge Coding可在现实世界的网络数据集上达到竞争性压缩性能，并可扩展到具有数百万节点和边的图。
如何在自回归语言模型中植入鲁棒的水印？
提出了一种在自回归语言模型中种植水印的方法，这些水印在不改变一定最大生成预算下的文本分布的情况下对扰动具有鲁棒性。通过使用随机水印密钥计算的随机数序列映射到语言模型的样本来生成带水印的文本。检测时，任何知道密钥的一方可以将文本与随机数序列对齐。用两种采样方案实例化：逆变换采样和指数最小采样。实验证明，在OPT-1.3B和LLaMA-7B模型中，即使破坏40-50%的标记，仍可可靠检测（p≤0.01）35个标记。对于Alpaca-7B模型，约25%的响应（中位长度约100个标记）可在p≤0.01下检测到，但水印对某些自动释义攻击不太鲁棒。
分布式存储系统中如何应对对抗性错误？
提出了一种基于最大秩距（MRD）码和最优修复最大距离可分（MDS）数组码的级联编码方案，以应对分布式存储系统中的对抗性错误，在保证数据容错性的同时，减少节点修复过程中的数据传输损失。该方案不仅可应对一次替换内容的对抗攻击，还可通过结合子空间签名机制，适应多次污染数据类型的对抗攻击。最后，还提出基于MRD码的构造方法，构建出可在本地修复并容忍对抗性错误的标量码。
