《Information》：New Efficient Decoder of Linear Block Codes Based on Information Sets, Hash Techniques, and Machine Learning Models
编辑推荐：
纠错码提高了发射机和接收机之间交换数据的可靠性；实现高效快速的译码是一个重大挑战。在这项工作中，研究人员提出了一种高效、快速且高性能的译码器，命名为FastSyndISD。所提出译码器的第一个版本使用哈希技术，从接收码字的伴随式中快速找到允许纠错的信息集。与H
纠错码提高了发射机和接收机之间交换数据的可靠性；实现高效快速的译码是一个重大挑战。在这项工作中，研究人员提出了一种高效、快速且高性能的译码器，命名为FastSyndISD。所提出译码器的第一个版本使用哈希技术，从接收码字的伴随式中快速找到允许纠错的信息集。与HSDec、LRDec和EL-BoostDec相比，哈希信息集显著降低了空间复杂度，而不是所有可纠正的错误。第二个版本利用机器学习模型（决策树）从接收码字的伴随式中快速找到能够实现纠错的信息集。该第二个版本不需要存储哈希表，因为信息集由决策树分类器模型确定。所提出的FastSyndISD译码器在误码率（BER）方面的性能非常令人鼓舞。实际上，它成功纠正了所有权重等于或小于所分析码的纠错能力的错误。此外，与各种其他译码器的比较突出了其有效性。还对其空间复杂度、时间复杂度以及影响其性能的因素进行了详细研究，旨在在减少计算时间和内存使用的同时实现最优BER。该比较证明了所提出译码器的显著成功。
**论文解读文章**
**研究背景与动机**
在现代通信系统中，纠错码通过引入冗余来确保数据在不可靠信道上的完整性，其中线性分组码（如BCH码和QR码）因其高效的多错纠正能力而尤为重要。译码的核心问题是从接收词中恢复最可能传输的码字，信息集译码（ISD）作为一种通用概率译码方法，通过猜测无错误位置子集（信息集）来重构码字。然而，经典ISD需要遍历大量信息集，导致计算复杂度随码长和错误数呈指数增长，限制了其实际应用。现有基于哈希的译码器（如HSDec）和基于机器学习的译码器（如LRDec、EL-BoostDec）虽有一定改进，但面临内存占用高、对长冗余码学习困难等问题。为此，研究人员提出一种结合哈希技术与机器学习模型的高效译码器FastSyndISD，旨在通过单个信息集直接定位错误，消除迭代循环，显著降低时间与空间复杂度。该成果发表在《Information》。
**主要关键技术方法**
FastSyndISD的核心思想是将接收码字的伴随式直接映射到对应的信息集索引，从而仅需调用一次信息集译码函数。第一个版本采用哈希技术，构建一维哈希表，其中每个伴随式的十进制值对应一个信息集索引（若该伴随式对应可纠正错误），否则标记为-1。第二个版本基于决策树分类器，训练数据集包含所有可纠正错误的伴随式（X）及其对应信息集索引（Y），决策树最大深度为n?k，在训练阶段达到100%准确率后，用于实时预测信息集。两种方法均避免了经典ISD中M次迭代，复杂度分别降至O((k2+n+8)·n+1)和O((k2+n+8)·n+k+MD)，其中MD为决策树深度。
**研究结果**
- **4.1 FastSyndISD在若干长度15和31的BCH码上的性能**：在加性高斯白噪声（AWGN）信道下，采用BPSK调制，FastSyndISD对BCH(15,7,5)码在信噪比（SNR）8.5 dB时达到10??的误码率（BER），对BCH(31,21,5)和BCH(31,16,7)码则在约7.5 dB达到相同BER。
- **4.2 FastSyndISD与其他译码器的比较**：与LRDec、2LRDec、EL-BoostDec相比，FastSyndISD对BCH(63,51,5)码的BER性能显著优于LRDec，与2LRDec和EL-BoostDec性能相同，但能完美译码BCH(63,39,9)码，而后者因类别数过多（637,393类）无法学习。FastSyndISD通过将伴随式关联到信息集（仅514类）大幅降低了学习难度。与NBP、DRN译码器比较，FastSyndISD对BCH(63,51,5)码性能优于NBP，与DRN相同但执行时间更短。与CEBP、NLMS、LMS译码器比较，FastSyndISD对BCH(63,45,7)码和QR(47,24,11)码优于LMS，接近CEBP和NLMS水平。与Deep Neural Decoder及Multiloss版本比较，FastSyndISD对BCH(63,45,7)码优于无Multiloss版本，接近含Multiloss版本。与Nachmani Decoder和HSDec比较，FastSyndISD对BCH(63,45,7)码优于Nachmani Decoder，接近HSDec但内存需求更低（HSDec需81.79 MB，FastSyndISD仅4.47 MB）。与BP、Neural BP、Neural TAMS比较，FastSyndISD对BCH(63,51,5)码显著优于三者。
- **4.3 FastSyndISD译码器内存与时间复杂度的实证研究**：内存方面，对于BCH(63,39,9)码（n?k=24），决策树版本占用内存低于哈希表版本（决策树节点数较少）。时间方面，FastSyndISD相较于经典ISD（HISD）的复杂度降低倍数（CRR）非常显著，例如对BCH(63,39,9)码，HISD的运算次数是FastSyndISD_Hash的505倍以上，证明哈希与机器学习模型显著减少了时间开销。
**讨论与结论**
FastSyndISD的核心创新在于将伴随式与信息集关联，而非直接关联可纠正错误，从而大幅降低学习难度和存储需求。哈希版本提供恒定时间查找，决策树版本无需存储哈希表，二者均能纠正所有可纠正错误（权重≤纠错能力t）。与多种现有译码器（如LRDec、HSDec、NBP等）的比较表明，FastSyndISD在BER性能、执行速度和内存占用上均具优势，尤其适用于冗余部分较大的线性分组码。
**研究结论**：本文提出了一种用于二进制线性分组码的先进译码方法FastSyndISD，其在误码率（BER）性能上表现卓越，能够检测并纠正所研究码的所有可纠正错误。该方法通过将伴随式与信息集链接，而非与可纠正错误关联，降低了学习过程和存储数据的复杂度。哈希技术通过直接定位信息集提升译码效率，避免大量计算。详细的比较分析证明了其优越的速度和纠错性能。未来工作将聚焦于开发该译码器的软判决版本并将其推广至更多线性分组码家族。
