基于左零空间引导的秩完成反馈的BATS码解码方法

《Entropy》：BATS Code Decoding Method Based on Left-Nullspace-Guided Rank-Completion Feedback

　　

BATS码的BP解码可能在没有剩余批满足满行秩条件时停止。为了恢复BP解码，研究人员提出了一种重要包引导的左零空间秩完成（LNRC）方法。LNRC首先识别与最多未解码批连接但未恢复的源包，将其称为重要包，并用作引导包以定位包含它的未解码批作为修复候选。对于所选秩亏缺为1的批，目的地计算一个非零左零向量，并选择一个提供缺失独立方向的局部修复坐标。目的地通过可靠的反向反馈控制链路发送相应的全局源包索引和有限域系数，源端通过可靠的前向修复数据链路返回缩放后的修复包。相关联的完成列将目标剩余传输矩阵的秩增加1，并使该批可BP解码。因此，LNRC利用目标未解码批的列空间结构来选择修复坐标，而不是仅根据连接的未解码批数量来选择重要包。在相同编码冗余下，仿真表明LNRC实现了比传统重要包反馈更低的分组错误率（PER），在评估的设置中平均相对PER降低约0.40–12.17%。

论文解读文章

**研究背景与问题**
在多跳擦除网络、无线中继网络和传感器网络中，可靠数据传输是通信系统的核心问题。由于链路噪声、拥塞和衰落等因素，数据包可能在传输过程中丢失。传统重传机制依赖反馈信道，但在长距离、多跳或高丢包场景下，频繁反馈会带来显著延迟和控制开销。喷泉码（Fountain codes）无需反馈即可实现数据传输，其置信传播（BP）解码具有高可靠性和低复杂度，适用于长块长。然而，在通用网络中，若中间节点仅执行存储转发，则无法达到最优网络传输速率。随机线性网络编码（Random Linear Network Coding，RLNC）允许中间节点线性重组接收的数据包，从而提升多跳网络的可达传输速率。BATS码（一种结合喷泉码和RLNC的码）融合了两者优势，无需反馈即可提供高网络传输速率和低编译码复杂度，其外码随机选择源包并生成线性组合，内码允许中间节点在相同批内进行随机线性重编码，因此具有良好的可实现性。在目的地，BATS解码相当于求解由接收批组成的有限域线性方程组。高斯消元可恢复源包，但全局消元不适合作为低开销解码方案。BP解码通过识别转移矩阵满行秩的批，恢复其源包并将其代入邻接批，可能触发级联解码。然而，当每个剩余批的转移矩阵秩小于其剩余度时，BP解码停止。现有研究通过解码算法优化和反馈辅助恢复来解决该停止条件。反馈辅助方法引入额外编码包或源包，为剩余解码图增加有效约束。传统重要包反馈（Important Packet feedback）在BP解码停止后，计算每个未恢复源包连接的未解码批数量，将连接最多未解码批的源包作为重要包，源端通过可靠前向修复数据链路返回该包。但该选择准则未显式利用指定剩余批的列空间结构，对于秩亏缺为1的剩余批，所请求的源包是否能立即解码取决于其在剩余转移矩阵列空间中的局部坐标，因此无法提供确定的秩完成保证。为此，研究人员提出了基于左零空间引导的秩完成（LNRC）方法，以恢复BP解码。

**研究内容与结论**
研究人员提出了LNRC方法，将重要包作为引导包以缩小候选批搜索范围，利用所选剩余批左零向量的非零支撑集确定局部修复坐标，从而保证修复包对应的完成列位于现有列空间之外，使目标剩余转移矩阵达到满行秩。在相同编码冗余下，通过蒙特卡洛仿真对比了标准BP解码、传统重要包反馈和LNRC。仿真结果表明，在五种评估设置下，LNRC的平均相对分组错误率（PER）降低约0.40%–12.17%，且附加计算开销远小于BP解码本身。该研究的意义在于提供了一种确定性秩完成机制，在不增加额外物理修复包格式的前提下，通过左零空间认证的修复坐标选择提升了BATS码的BP解码恢复能力，为反馈辅助网络编码解码提供了新思路。论文发表在《Entropy》。

**关键技术方法**
LNRC方法包含两阶段修复选择机制。第一阶段：BP解码停止后，识别重要包（连接最多未解码批的未恢复源包）作为引导包，缩小候选批搜索范围，仅考虑与该引导包关联且秩亏缺为1（即剩余转移矩阵秩小于剩余度1）的未解码批。第二阶段：对所选目标批，计算一个非零左零向量，在其非零支撑集中选择一个局部修复坐标，映射为全局源包索引，并通过可靠反向反馈控制链路发送该索引及有限域系数。源端通过可靠前向修复数据链路返回缩放后的修复包，目的地将对应的完成列附加到目标批的剩余转移矩阵，使其秩增加1并达到满行秩。该过程仅依赖单批的剩余转移矩阵，运算量小，且不改变普通BP迭代流程。

**研究结果**
4.1 仿真设置
采用蒙特卡洛仿真，在有限域²（GF(2²)）上进行，批大小M=8，源包向量长度T=16，每个数据点平均300次独立运行。初始两跳BATS传输链路（图1）具有相同擦除概率e。修复请求使用可靠反向反馈控制链路，修复包使用可靠前向修复数据链路。渐近度分布情况使用K=1024，M=8，e=0.2；两种有限长度情况使用K=256，M=8，e=0.2和e=0.4，其度分布由有限长度优化程序生成。每个交付的修复包计入冗余计算，反向反馈控制链路上的请求比特不计入。

4.2 比较方法与评估指标
仿真比较三种方法：BP（无修复的标准BP解码，传输批数调整为最接近的可实现整数）；Important Packet（传统重要包反馈，通过可靠前向修复数据链路返回重要包）；LNRC（所提出的左零空间认证秩完成方法）。评估指标为分组错误率（PER），横轴为冗余R_rep，定义为LNRC使用的平均修复包数。每次试验中，Important Packet使用与LNRC相同的修复包冗余，BP则将该平均冗余转换为最接近的整数传输批数。

4.3 PER仿真结果
图3（K=1024, M=8, e=0.2）：LNRC与传统Important Packet反馈相比，平均相对PER降低约2.51%，在低冗余下增益最大，随R_rep增加而缩小。
图4（K=1024, M=8, e=0.1）：LNRC平均相对PER降低约0.40%，增益有限，与该设置下BP恢复能力较强及可修复的秩亏缺为1批数量较少一致。
图5（K=1024, M=8, e=0.3）：LNRC平均相对PER降低约2.58%，增益主要集中在低冗余区域。
图6（K=256, M=8, e=0.2）：有限长度情况，LNRC平均相对PER降低约8.30%，在低中冗余区域改善最显著。
图7（K=256, M=8, e=0.4）：LNRC平均相对PER降低约12.17%，为所有评估情况中最大改善，与更高擦除设置下剩余图中可修复秩亏缺为1批更普遍一致。

4.4 结果讨论
在五种评估情况下，LNRC在相同数据包等效冗余下均实现了低于传统Important Packet反馈的PER。性能差异源于修复选择规则：Important Packet直接返回重要包，而LNRC将其作为引导包，并通过左零向量非零支撑集确定局部修复坐标。增益由级联解码驱动：单次LNRC修复直接完成一个秩亏缺为1的批，触发级联BP解码，恢复的源包代入邻接剩余批，其秩亏缺不会增加且可能减少，从而使这些批变为可BP解码或进入后续修复轮次的候选集。级联解码增益的大小取决于剩余图结构，而非仅擦除概率。例如，K=1024, e=0.1时平均降低仅0.40%，而两种K=256情况分别达到8.30%和12.17%。高冗余下增益缩小，与BP解码后可修复秩亏缺为1批减少一致。这些结果表明块长、度分布、冗余以及秩亏缺为1批的普遍性共同影响LNRC增益。然而，这些增益以反馈辅助修复期间的额外计算为代价。附加计算主要发生在目的地，在BP解码停止并选定秩亏缺为1目标批后，每轮反馈中LNRC仅计算该单批剩余转移矩阵的一个非零左零向量，构建其非零支撑集并选择修复坐标。源端操作仅限于生成所请求的缩放修复包。表1量化了LNRC附加有限域计算量与相同冗余下一次BP解码平均计算量的比较：LNRC附加计算量远小于BP解码，在最低冗余下约10³次加法和乘法，最高冗余下约10²次，而一次BP试验需约10⁵次有限域操作。因此，LNRC以较小的目的地计算成本获得了性能提升。当前研究假设可靠反向反馈控制链路和可靠前向修复数据链路，若任一链路不可靠，则需重传或确认机制。全局候选搜索也可解决当前基于引导的局部搜索的覆盖限制。

**总结与结论**
本研究提出了LNRC以恢复BP解码停止后的解码过程。LNRC将重要包作为引导包以缩小候选批搜索范围，并通过所选秩亏缺为1剩余批的左零向量非零支撑集确定局部修复坐标。对于秩亏缺为1（d_i^(r) ? r_i^(r) = 1）的批，完成列r满足r ? span(S_i^(r))，成功修复后使剩余转移矩阵达到满行秩。源端返回相应的缩放修复包，因此LNRC的贡献在于左零空间认证的修复坐标选择，而非新的修复包格式。目标批解码后，恢复的源包被代入邻接剩余批，可能触发进一步BP解码。在五种评估情况下，LNRC在相同编码冗余下实现了比传统重要包反馈更低的分组错误率，平均相对PER降低约0.40%–12.17%。增益大小由块长、度分布、冗余以及可修复秩亏缺为1批的普遍性共同决定，而非仅擦除概率。仿真结果进一步证实，LNRC的附加计算开销与BP解码相比可忽略不计。当前方法假设可靠反向反馈控制链路和可靠前向修复数据链路，并使用基于引导的局部候选批搜索。未来工作将扩展LNRC至不可靠反向反馈控制和前向修复数据链路、多列秩完成以及更广泛的候选搜索（遍历更低排名引导包或全局检查剩余图）。