Performance study of non-binary belief propagation for decoding Reed-Solomon codes

This paper presents a soft decoding scheme based on the binary representations transferred from the parity-check matrices (PCMs) for Reed-Solomon (RS) codes. Referring to the modified binary PCM that has a systematic part and a high-density part corresponding to the least reliable variable nodes (LRVNs) and the most reliable variable nodes (MRVNs), respectively, an informed dynamic scheduling method, called Nested-Polling Residual Belief Propagation (NP-RBP), is applied to the corresponding Tanner graph. As with the popular adaptive BP (ABP) decoding approach, adaptation in a binary PCM based on the reliability of variable nodes is also conducted in the proposed NP-RBP decoding. The NP-RBP enables the LRVNs to receive significant updates and limits the correlation accumulation from the short cycles in the MRVNs. In order to enhance the error-rate performance for long codes, a bit-flipping (BF) technique is conducted in order to correct a selection of the errors in the MRVNs such that the propagation of these errors in the subsequent NP-RBP process can be avoided. The resultant decoder is termed NP-RBP-BF. For short codes such as the (31, 25) and (63, 55) RS codes, NP-RBP is able to provide an error-rate performance close to the maximum-likelihood (ML) bound. A more significant improvement can be observed for long codes. For instance, when the proposed NP-RBP-BF decoding is applied to the (255, 239) RS code, it can provide a gain of about 0.4 dB compared to the ABP decoding and the performance gap to the ML bound can be narrowed to about 0.25 dB at a frame error rate of $2\times 10^{-3}$ .This paper presents a soft decoding scheme based on the binary representations transferred from the parity-check matrices (PCMs) for Reed-Solomon (RS) codes. Referring to the modified binary PCM that has a systematic part and a high-density part corresponding to the least reliable variable nodes (LRVNs) and the most reliable variable nodes (MRVNs), respectively, an informed dynamic scheduling method, called Nested-Polling Residual Belief Propagation (NP-RBP), is applied to the corresponding Tanner graph. As with the popular adaptive BP (ABP) decoding approach, adaptation in a binary PCM based on the reliability of variable nodes is also conducted in the proposed NP-RBP decoding. The NP-RBP enables the LRVNs to receive significant updates and limits the correlation accumulation from the short cycles in the MRVNs. In order to enhance the error-rate performance for long codes, a bit-flipping (BF) technique is conducted in order to correct a selection of the errors in the MRVNs such that the propagation of these errors in the subsequent NP-RBP process can be avoided. The resultant decoder is termed NP-RBP-BF. For short codes such as the (31, 25) and (63, 55) RS codes, NP-RBP is able to provide an error-rate performance close to the maximum-likelihood (ML) bound. A more significant improvement can be observed for long codes. For instance, when the proposed NP-RBP-BF decoding is applied to the (255, 239) RS code, it can provide a gain of about 0.4 dB compared to the ABP decoding and the performance gap to the ML bound can be narrowed to about 0.25 dB at a frame error rate of$2\times 10^{-3}$.

IEEE Journal on Selected Areas in Information TheoryJan 1, 20231 citation

Improved Belief Propagation Decoding Algorithm for Short Polar Codes

Shajeel Iqbal, Adnan Ahmed Hashmi, GoangSeog Choi

Wireless Personal CommunicationsApr 22, 20173 citations

Algorithm of multithreshold decoding for non-binary self-orthogonal concatenated codes

V. V. Zolotarev, Yerzhan N. Seitkulov, Gennady V. Ovechkin +3 more

Non-binary multithreshold decoding (qMTD) for q-ary self-orthogonal codes (qSOC) is considered. The SER performance of qMTD is shown to be close to the results provided by optimum total search methods, which are not realizable for non-binary codes in general. qMTD decoders are compared with different decoders for Reed-Solomon codes. The performance provided with qMTD in some cases is unattainable with classical decoders for arbitrary long Reed-Solomon codes. The result of concatenation of qSOC with simple to decode outer codes is described. Method of improving of qMTD decoder's performance for qSOC is offered. Some simulated results obtained by using these two decoding techniques (the base and modified ways) are presented as well. Comparison of the results showed that the change in the threshold element's algorithm can significantly improve speed of qMTD work. It's shown that for a larger gain this modification qMTD should be used after conventional decoding iterations.Non-binary multithreshold decoding (qMTD) for q-ary self-orthogonal codes (qSOC) is considered. The SER performance of qMTD is shown to be close to the results provided by optimum total search methods, which are not realizable for non-binary codes in general. qMTD decoders are compared with different decoders for Reed-Solomon codes. The performance provided with qMTD in some cases is unattainable with classical decoders for arbitrary long Reed-Solomon codes. The result of concatenation of qSOC with simple to decode outer codes is described. Method of improving of qMTD decoder's performance for qSOC is offered. Some simulated results obtained by using these two decoding techniques (the base and modified ways) are presented as well. Comparison of the results showed that the change in the threshold element's algorithm can significantly improve speed of qMTD work. It's shown that for a larger gain this modification qMTD should be used after conventional decoding iterations.

IEEE International Conference on Application of Information and Communication Technologies (AICT)Oct 1, 20141 citation

Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes

Ryuhei Mori, Toshiyuki Tanaka

Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.Polar codes, introduced by Arıkan, achieve symmetric capacity of any discrete memoryless channels under low encoding and decoding complexity. Recently, non-binary polar codes have been investigated. In this paper, we calculate error probability of non-binary polar codes constructed on the basis of Reed-Solomon matrices by numerical simulations. It is confirmed that 4-ary polar codes have significantly better performance than binary polar codes on binary-input AWGN channel. We also discuss an interpretation of polar codes in terms of algebraic geometry codes, and further show that polar codes using Hermitian codes have asymptotically good performance.

arXiv:1007.3661IEEE Information Theory Workshop (ITW)Aug 1, 201094 citations

Near optimum universal belief propagation based decoding of LDPC codes

J. Chen

IEEE Transactions on CommunicationsJan 1, 200219 citations

2\times 10^{-3}