近期，我室白宝明教授课题组陈超副教授在Reed-Solomon（RS）码快速译码方面取得重要研究进展，在国际信息论领域顶级期刊《IEEE Transactions on Information Theory》发表高水平论文《Two Fast Erasure Decoding Algorithms for Reed–Solomon Codes Based on LCH-FFT》，这是在此期刊上接连发表的第二篇论文，此前在该期刊上也发表了题为《Parallel Welch–Berlekamp Algorithm》的论文。该系列成果解决了RS码译码复杂度高、硬件实现效率低等问题，将RS码纠删译码复杂度降至目前已知最优水平，并设计了适合高速硬件实现的并行关键方程求解架构，为下一代高速通信和大容量存储系统提供了关键的译码技术支撑。

研究背景

Reed-Solomon码是一类从距离角度而言最优的码，称为最大距离可分（MDS）码，自1960年提出以来，凭借其优异的纠错和纠删能力，已成为卫星通信、光纤通信、5G/6G移动通信、数据存储、分布式存储、深空探测、高速以太网等几乎所有现代信息系统的标准编码方案。

随着全球数据流量的爆炸式增长，传统（N，K）RS码译码算法的复杂度瓶颈日益凸显。经典的高斯消元法复杂度高达O(K³)，难以满足大规模数据处理的需求；基于快速傅里叶变换（FFT）的算法虽然将复杂度降低到了O(N log N)，但在二元扩域上长期缺乏真正高效的FFT实现。直到2014年Lin、Chung和Han提出LCH-FFT算法，才首次在二元扩域上实现了真正的O(N log N)复杂度FFT，为RS码的快速编译码带来了革命性的机遇。然而，基于LCH-FFT的现有译码算法仍存在优化空间，尤其是在低码率和高码率场景下的针对性优化，以及硬件并行实现方面的挑战，亟待进一步突破。

研究亮点

一、提出两种理论最优复杂度的快速纠删译码算法

针对低码率和高码率RS码的不同特性，团队提出了两种基于LCH-FFT的快速纠删译码算法，分别将主译码步骤的复杂度从O(N log N)降低到了O(N log K)（适用于低码率RS码，K/N≤0.5）和O(N log(N-K))（适用于高码率RS码，K/N≥0.5）。这是目前RS码纠删译码已知的理论最优复杂度。

为了支撑这两种算法，团队还推导了全新的分块多项式插值公式及其两个重要推论。该插值公式将传统的拉格朗日插值推广到了分块插值的情况，不仅为快速译码算法奠定了坚实的理论基础，其本身也具有独立的学术价值，可广泛应用于多项式求值、插值等代数计算领域。

二、提出并行Welch-Berlekamp算法，突破硬件实现瓶颈

RS码纠错译码的核心是求解Welch-Berlekamp（WB）关键方程。传统WB算法采用串行执行方式，差异计算和多项式更新依次进行，导致关键路径长、硬件并行度低，难以满足高速应用的需求。

团队从有理插值问题的基本数学性质出发，推导出了并行Welch-Berlekamp（PWB）算法，首次实现了差异计算和多项式更新的并行执行，大幅缩短了关键路径。该算法与传统WB算法在数学上完全等价，但更适合硬件实现，其地位类似于Reformulated Inversionless Berlekamp-Massey（RiBM）算法相对于传统Berlekamp-Massey算法，为RS码译码的高速硬件实现提供了新的方法。

三、提出早期终止机制，显著降低平均计算量

团队首次系统深入地研究了WB算法的早期终止特性，引入了“不完全错误位置多项式”的新概念，严格证明了当错误数e不超过码的纠错能力t时，PWB算法最晚可以在第(t+e)次迭代后终止，而无需完成全部2t次迭代。

基于这一重要发现，团队提出了早期终止并行Welch-Berlekamp（EPWB）算法。在实际应用中，由于错误数通常远小于纠错能力，该算法可以显著降低平均计算量，进一步提升译码效率。值得注意的是，这一早期终止机制同样适用于传统的WB算法，填补了该领域的研究空白。

四、设计频域算法和高效脉动阵列架构，实现硬件加速

为了更好地与LCH-FFT结合，进一步提升整体译码效率，团队将PWB和EPWB算法扩展到了频域，提出了频域并行Welch-Berlekamp（FPWB）和频域早期终止并行Welch-Berlekamp（FEPWB）算法。频域算法通过更新多项式的求值结果来代替更新多项式系数，能够充分利用LCH-FFT的快速计算能力，大幅降低整体译码复杂度。

图1 FPWB算法脉动阵列整体架构及处理单元结构

基于FPWB算法，团队设计了一种高效的脉动阵列架构。该架构由差异计算（DC）块和错误位置更新（ELU）块组成，具有规则的模块化结构、低实现成本和极短的关键路径。与现有主流的RiBM和ePIBMA架构相比，FPWB/FEPWB架构的关键路径同样仅为一个乘法器和一个加法器，但结合LCH-FFT后，整体译码复杂度显著降低，更适合高速大规模集成电路实现。

五、吞吐量实现大幅提升

为了验证所提算法的实际性能，团队基于单指令多数据流（SIMD）技术实现了所有算法，并开发了专门的RS码译码库XD-RS。实验在Intel Core i7-9700处理器上进行，测试了RS(256,K)码在不同码率下的吞吐量性能，并与当前最先进的RS码译码库（包括Intel的ISA-L、Jerasure、基于LCH-FFT的Leopard-RS以及基于Reed-Muller变换的RMT-RS）进行了全面对比。

结果显示，XD-RS库在SSE和AVX2指令集下均实现了显著的吞吐量提升。在AVX2指令集下，当码率为0.5（K=128）时，XD-RS库的吞吐量超过4000MB/s，是传统ISA-L库的2倍以上，是Leopard-RS库的1.5倍以上；在高码率（K=248）和低码率（K=16）场景下，吞吐量优势更加明显，最高可达5000MB/s以上。

图2 SSE指令集下RS(256,K)码译码吞吐量对比

图3 AVX2指令集下RS(256,K)码译码吞吐量对比

应用前景

该系列成果解决了RS码快速译码的若干核心技术难题，所提出的算法和架构具有广泛的应用前景。在通信领域，可用于未来移动通信的物理层编码、卫星通信的高速数据传输、光纤通信的前向纠错、深空探测的遥测遥控等场景；在存储领域，可用于数据中心的分布式存储系统、固态硬盘（SSD）的纠错编码、云存储的冗余编码、磁带存储的错误恢复等场景。对在对吞吐量和时延要求极高的下一代信息系统中，该成果有望发挥重要作用。