基于分组策略的低复杂度三层GII编码器

《Electronics》：Low-Complexity Three-Layer GII Encoders Based on a Grouping Strategy

　　

广义集成交织（GII）码已成为分布式存储系统中一种引人注目的编码解决方案，因为它们在纠错能力和修复局部性之间实现了良好的权衡。与传统两层GII码相比，三层GII码可以进一步提升局部性。然而，三层GII编码器存在递归依赖性，其中每个子码字的编码依赖于所有先前的子码字，导致显著的乘累加（MAC）开销和增加的硬件复杂度。本文提出了一种分组策略，充分利用三层GII码固有的分层结构，从而减少MAC运算次数。基于该策略，开发了相应的编码器架构。综合结果表明，所提出的编码器可以有效地降低面积成本和面积延迟积（ADP），分别最高达25.5%和36.7%。

纠错码（ECC）是现代通信和存储系统中不可或缺的组成部分。广义集成交织（GII）码作为一类纠错码，在纠错能力与修复局部性之间提供了有利的折衷，因而非常适用于分布式存储系统。相比传统两层GII码，三层GII码能够进一步改善局部性，但其传统编码算法在编码每个子码字时依赖于所有先前子码字，导致显著的乘累加（MAC）开销和硬件复杂度。针对这一问题，研究人员在《Electronics》上提出了一种基于分组策略的低复杂度三层GII编码器。该研究首先利用三层GII码固有的层次结构设计分组策略：将每个第二层组视为一个两层GII码进行独立编码，然后通过计算修正项补偿第三层嵌套约束，从而将MAC运算量大幅降低。基于该策略，论文进一步开发了相应的编码器架构，在不增加生成码字所需时钟周期数的前提下，降低了面积成本和面积延迟积（ADP）。综合结果表明，所提编码器最高可减少25.5%的面积成本和36.7%的ADP，为三层GII码在分布式存储等场景中的实际应用提供了低复杂度硬件实现方案。

研究采用的主要关键技术包括：利用线性反馈移位寄存器（LFSR）实现Reed-Solomon（RS）编码器，构成子码字编码内核；通过初等块级行变换修改嵌套矩阵，将其下三角部分转换为块上三角形式，从而得到跨组修正系数；提出的分组策略将每个第二层组视为一个两层GII码，使用传统两层编码算法（参数退化为两层）完成组内编码；随后，修正单元（CU）根据推导的线性组合计算跨组修正项并累加到相应组上。硬件架构保持子码字并行、符号串行的组织方式，并限制每个MAC单元（MAU）的输入仅来自同一第二层组，同时引入修正单元。设计基于TSMC 65nm标准单元库，使用Synopsys Design Compiler进行逻辑综合，在100 MHz固定时钟和最大可达时钟频率下评估性能。研究选取了12个代表性三层GII码作为验证对象，覆盖不同参数范围，所有码均定义在GF(2⁸)上。

研究结果如下。

3.1 分组策略：研究人员通过修改嵌套矩阵，使第二层组与第三层嵌套约束解耦。具体为，对每个第二层组独立执行两层GII编码，然后对需要第三层校正的组计算修正项。修正项可表示为先前各组中间子码字的线性组合，系数由高斯消元得到。这种策略使每个子码字的编码依赖范围从所有先前子码字缩减至同组内的部分子码字以及少数指定子码字，从而显著减少MAC操作。

3.2 基于分组策略的编码器架构：在所提架构中，所有m个子码字并行处理，每个子码字符号串行输入。每个MAU的输入被限制在同一个第二层组内，同时为需要跨组校正的第二层组增加一个修正单元（CU）。相比传统架构，单个MAU及其对应CU的总输入符号数大幅下降。例如，文中示例中MAU1的输入从6个符号降至3个（包括CU），最大输入符号数（排除目标符号）从11个降至5个。

4 示例与评估结果：论文给出了12个三层GII码实例，参数覆盖较小的m、λ以及较大的情况，所有码定义在GF(2⁸)上。符号级乘法与加法次数比较显示，所提算法在所有12个码上都低于传统算法。

4.1 复杂度分析：对MAC运算的计算复杂度进行分析。传统算法作为两层编码的直接扩展，其MAC复杂度较高。所提算法分为两个阶段：第一阶段对每个第二层组进行两层GII编码，第二阶段计算各修正项。渐进上界表明所提算法复杂度更低，但文中指出，由于硬件架构是符号串行-子码字并行，n不影响算术数据通路，因此渐进分析仅作参考。符号级运算计数比较直接说明了优势。

4.2 综合结果：所有编码器以Verilog HDL进行RTL描述，并用Synopsys Design Compiler在TSMC 65nm工艺下综合。在固定100 MHz时钟下，所提编码器面积最高降低25.5%，功耗也相应降低。在各自最大可达时钟频率下，所提编码器通常能运行在更高频率，且ADP最高降低36.7%。面积分解显示，所提设计主要简化了RS编码器之外的MAC相关逻辑，因此当RS编码器面积占比较小时，整体收益更显著。

讨论部分指出，已有工作尚未专门研究降低三层GII-RS编码算法的复杂度。所提设计的一个局限是当组成RS码的纠错能力较大时，RS编码器本身占面积比例较高，收益减弱；但在分布式存储中，码的纠错能力通常较小，因此该局限影响有限。此外，GII-RS与GII-BCH编码器结构差异大，此前针对两层GII-BCH编码器的优化不适用于当前问题。所提分组策略未来或可扩展到三层GII-BCH，但需重新设计算法和架构。

研究结论可翻译为：本文提出了一种基于分组的三层GII码编码算法以及相应的低复杂度编码器架构。通过利用码固有的层次结构，所提算法减少了与MAC运算相关的计算开销，而无需增加生成一个码字所需的时钟周期数。针对12个代表性码的运算次数分析和前端综合结果表明，所提编码器的面积成本和ADP分别最高可降低25.5%和36.7%。