Title: Parallelism Empowered Guessing Random Additive Noise Decoding Show Chinese title

Title: 并行性增强的猜测随机加性噪声解码

Abstract: Advances in parallel hardware platforms have motivated the development of efficient universal decoders capable of meeting stringent throughput and latency requirements. Guessing Random Additive Noise Decoding (GRAND) is a recently proposed decoding paradigm that sequentially tests Error Patterns (EPs) until finding a valid codeword. While Soft GRAND (SGRAND) achieves maximum-likelihood (ML) decoding, its inherently sequential nature hinders parallelism and results in high decoding latency. In this work, we utilize a unified binary tree representation of EPs, termed the EP tree, which enables compact representation, efficient manipulation, and parallel exploration. Building upon this EP tree representation, we propose a parallel design of SGRAND, preserving its ML optimality while significantly reducing decoding latency through pruning strategies and tree-based computation. Furthermore, we develop a hybrid GRAND algorithm that enhances Ordered Reliability Bits (ORB) GRAND with the EP tree representation, thereby achieving ML decoding with minimal additional computational cost beyond ORBGRAND while retaining parallel efficiency. Numerical experiments demonstrate that parallel SGRAND achieves a $3.75\times$ acceleration compared to serial implementation, while the hybrid enhanced method achieves a $4.8\times$ acceleration, with further gains expected under hardware mapping. Show Chinese abstract

Abstract: 随着并行硬件平台的进步，推动了高效通用解码器的发展，这些解码器能够满足严格的吞吐量和延迟要求。猜测随机加性噪声解码（GRAND）是一种最近提出的解码范式，它依次测试错误模式（EPs），直到找到一个有效的码字。虽然软GRAND（SGRAND）实现了最大似然（ML）解码，但其固有的顺序性质阻碍了并行性，并导致高解码延迟。在本工作中，我们利用了EPs的统一二叉树表示，称为EP树，这使得表示更加紧凑，操作更加高效，并支持并行探索。基于这种EP树表示，我们提出了一种SGRAND的并行设计，在保持ML最优性的同时，通过剪枝策略和基于树的计算显著降低了解码延迟。此外，我们开发了一种混合GRAND算法，将有序可靠性位（ORB）GRAND与EP树表示相结合，从而在超越ORBGRAND的额外计算成本最小的情况下实现ML解码，同时保持并行效率。数值实验表明，并行SGRAND相比串行实现获得了$3.75\times$的加速，而混合增强方法获得了$4.8\times$的加速，在硬件映射下有望获得进一步的提升。