Neural decoders were introduced as a generalization of the classic Belief Propagation (BP) decoding algorithms, where the Trellis graph in the BP algorithm is viewed as a neural network, and the weights in the Trellis graph are optimized by training the neural network. In this work, we propose a novel neural decoder for cyclic codes by exploiting their cyclically invariant property. More precisely, we impose a shift invariant structure on the weights of our neural decoder so that any cyclic shift of inputs results in the same cyclic shift of outputs. Extensive simulations with BCH codes and punctured Reed-Muller (RM) codes show that our new decoder consistently outperforms previous neural decoders when decoding cyclic codes. Finally, we propose a list decoding procedure that can significantly reduce the decoding error probability for BCH codes and punctured RM codes. For certain high-rate codes, the gap between our list decoder and the Maximum Likelihood decoder is less than $0.1$dB. Code available at https://github.com/cyclicallyneuraldecoder/CyclicallyEquivariantNeuralDecoders
Neural decoders were introduced as a generalization of the classic Belief Propagation (BP) decoding algorithms, where the Trellis graph in the BP algorithm is viewed as a neural network, and the weights in the Trellis graph are optimized by training the neural network. In this work, we propose a novel neural decoder for cyclic codes by exploiting their cyclically invariant property. More precisely, we impose a shift invariant structure on the weights of our neural decoder so that any cyclic shift of inputs results in the same cyclic shift of outputs. Extensive simulations with BCH codes and punctured Reed-Muller (RM) codes show that our new decoder consistently outperforms previous neural decoders when decoding cyclic codes. Finally, we propose a list decoding procedure that can significantly reduce the decoding error probability for BCH codes and punctured RM codes. For certain high-rate codes, the gap between our list decoder and the Maximum Likelihood decoder is less than 0.1dB. Code available at https://github.com/cyclicallyneuraldecoder/CyclicallyEquivariantNeuralDecoders
The cyclically equivariant neural decoder was recently proposed in [Chen-Ye, International Conference on Machine Learning, 2021] to decode cyclic codes. In the same paper, a list decoding procedure was also introduced for two widely used classes of cyclic codes—BCH codes and punctured Reed-Muller (RM) codes. While the list decoding procedure significantly improves the Frame Error Rate (FER) of the cyclically equivariant neural decoder, the Bit Error Rate (BER) of the list decoding procedure is even worse than the unique decoding algorithm when the list size is small. In this paper, we propose an improved version of the list decoding algorithm for BCH codes and punctured RM codes. Our new proposal significantly reduces the BER while maintaining the same (in some cases even smaller) FER. More specifically, our new decoder provides up to 2dB gain over the previous list decoder when measured by BER, and the running time of our new decoder is 15% smaller. Code available at github.com/improvedlistdecoder/code
Transformers have recently emerged as effective neural decoders, capable of capturing complex interdependencies and delivering strong performance. Cyclic codes, including BCH codes, Reed-Solomon codes, and Reed-Muller codes, are fundamental in practical channel coding applications. In this work, we propose a novel approach for Transformer-based neural decoders specifically designed for cyclic codes. By leveraging the relational properties among the parity-check matrix, Tanner graph, and mask matrix, we integrate these with the inherent algebraic structure of cyclic codes. We then identify a cyclic shift reuse property that can be effectively applied to both parameter matrices and self-attention matrices. Extensive simulations on BCH codes demonstrate that our method reduces the total number of parameters by up to 64.4% compared to prior Transformer-based decoders while achieving comparable decoding performance. Additionally, our method decreases the computational cost of self-attention by up to 10.6%. Finally, through experiments across various dimensions, we explore the effect of embedding dimensions on performance and provide insights into the relationship between embedding dimensions and code positions.
This paper proposes a quasi-BP decoding scheme for BCH codes that preserves the parallelizable structure of belief propagation while exploiting code automorphisms and optimized redundant parity-check matrices. To eliminate the computationally expensive tanh and tanh−1 functions in check node updates, we further introduce a neural-network-based variant that replaces them with a lightweight convolutional neural network trained under a triple-constraint loss function enforcing non-negativity and order consistency. Simulation results for three BCH codes demonstrate that quasi-BP decoding achieves competitive frame error rate performance, with a gap within 0.25 decibels compared with belief propagation decoding of an LDPC code of similar blocklength. The neural-network-based variant incurs negligible performance loss while enabling stable deployment with arithmetic operations on hardware accelerators. Concatenation with an ordered statistics decoding variant further bridges the gap to the maximum-likelihood bound. Hence, the proposed schemes offer a viable path toward high-throughput, low-latency decoding of BCH codes in next-generation communication systems.
Neural belief propagation (NBP) decoding can improve the performance of belief propagation (BP) decoding for high-density parity check (HDPC) codes, at the expense of higher memory storage requirement and computational complexity due to the addition of trainable weight coefficients. To reduce the high storage requirement of NBP, the cyclically equivariant neural BP (CENBP) algorithm makes full use of the cyclically invariant property of the cyclic code, optimizes and reuses the weight coefficients of the NBP algorithm, at the expense of further increasing the computational complexity of NBP. In this paper, we propose low-complexity, in terms of both memory storage requirement and computational complexity, NBP and CENBP decoding algorithms based on Tensor Ring (TR) decomposition. First, in order to reduce the memory storage and computational complexity of the NBP algorithm, we propose a TR-based compression algorithm to compress the messages and mathematical calculations in the NBP decoding algorithm, called TR-NBP algorithm. Second, to address the high computational complexity of the CENBP algorithm, we propose to apply TR decomposition-based compression to the odd layers of the CENBP decoding algorithm, called TR-CENBP, to reduce the computational complexity, and further reduce the required memory storage requirement of the CENBP algorithm. Furthermore, we use TR decomposition-based compression to simplify the mathematical computations associated with thetanhfunction in the NBP algorithm to further reduce the complexity of the hardware implementation. Experimental results show that direct compression of BP algorithm using TR decomposition results in significant performance degradation and our proposed low complexity TR-NBP algorithm and TR-CENBP algorithm can greatly reduce both the memory storage requirement and computation complexity, without significant performance degradation for typical BCH and LDPC codes.
Polar codes are the first class of error correcting codes that provably achieve the channel capacity at infinite code length. They were selected for use in the fifth generation of cellular mobile communications (5G). In practical scenarios such as 5G, a cyclic redundancy check (CRC) is concatenated with polar codes to improve their finite length performance. This is mostly beneficial for sequential successive-cancellation list decoders. However, for parallel iterative belief propagation (BP) decoders, CRC is only used as an early stopping criterion with incremental error-correction performance improvement. In this paper, we first propose a CRC-polar BP (CPBP) decoder by exchanging the extrinsic information between the factor graph of the polar code and that of the CRC. We then propose a neural CPBP (NCPBP) algorithm which improves the CPBP decoder by introducing trainable normalizing weights on the concatenated factor graph. Our results on a 5G polar code of length 128 show that at the frame error rate of 10-5and with a maximum of 30 iterations, the error-correction performance of CPBP and NCPBP are approximately 0.25 dB and 0.5 dB better than that of the conventional CRC-aided BP decoder, respectively, while introducing almost no latency overhead.
Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief propagation (BP) iterations into a deep neural network and the parameters are trained in a data-driven manner. NBP decoders have been shown to improve upon classical decoding algorithms. In this paper, we investigate the generalization capabilities of NBP decoders. Specifically, the generalization gap of a decoder is the difference between empirical and expected bit-error-rate(s). We present new theoretical results which bound this gap and show the dependence on thedecoder complexity, in terms of code parameters (blocklength, message length, variable/check node degrees), decoding iterations, and the training dataset size. Results are presented for both regular and irregular parity-check matrices. To the best of our knowledge, this is the first set of theoretical results on generalization performance of neural network based decoders. We present experimental results to show the dependence of generalization gap on the training dataset size, and decoding iterations for different codes.