Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2309.11836 · Entropy

Pre-Configured Error Pattern Ordered Statistics Decoding for CRC-Polar Codes

Xuanyu Li, Kai Niu, Yuxin Han, Jincheng Dai, Zhiyuan Tan, Zhiheng Guo

Published Sep 30, 2023• 6 citations
arXivHTMLPDF

Abstract

In this paper, we propose a pre-configured error pattern ordered statistics decoding (PEPOSD) algorithm and discuss its application to short cyclic redundancy check (CRC)-polar codes. Unlike the traditional OSD that changes the most reliable independent symbols, we regard the decoding process as testing the error patterns, like guessing random additive noise decoding (GRAND). Also, the pre-configurator referred from ordered reliability bits (ORB) GRAND can better control the range and testing order of EPs. An offline-online structure can accelerate the decoding process. Additionally, we also introduce two orders to optimize the search order for testing EPs. Compared with CRC-aided OSD and list decoding, PEPOSD can achieve a better trade-off between accuracy and complexity.

DOI
10.3390/e25101405

Related papers

Guessing Error Pattern Ordered Statistic Decoding for Short Polar Codes

Yuxin Han, Kai Niu, Xuanyu Li

Polar codes have been used to guarantee high reliability in communication due to their excellent performance. In this letter, we propose a guessing error pattern ordered statistic decoding (GEPOSD) algorithm to further improve the performance of short polar codes. It outperforms the widely used cyclic redundancy check-aided successive cancellation list (CA-SCL) decoding under a code length of 64. The GEPOSD algorithm utilizes a strategy based on the maximum a posteriori probability rule to select the error pattern on the most reliable independent bits. Subsequently, an error pattern set is extended using a tree search approach. To minimize computational complexity, we introduce two early stopping criteria that limit the number of error patterns tested in decoding. The simulation results show that the complexity of GEPOSD is significantly reduced compared to the original OSD algorithm.

IEEE Communications Letters•Sep 28, 2023•3 citations

Segmented CRC-Aided Order Statistical Decoding with Multiple Biases for Short Polar Codes

Hao Tang, Ming Zhan, Liangxi Liu +4 more

With the advent of 5th generation (5G) mobile communication era, higher requirements are put forward for ultra-reliable and low-latency transmission compared with 4G, especially in the field of short packet communication. In this paper, we propose a segmented cyclic redundancy check aided order statistical decoding algorithm with multiple biases (BIAS- SCRC-OSD) for short polar codes. This algorithm constructs multiple information sets by repeatedly adding bias value, and selects more effective information sets to improve the decoding performance. For further improving the decoding performance, we change the original cyclic redundancy check (CRC) into segment check. The simulation results show that a suitable bias value can significantly improve the decoding performance with a small increase in computational complexity. Compared with the original CRC-aided order statistical decoding (OSD) algorithm, the proposed algorithm has a gain of about 0.8 dB at target bit error rate (BER) 10-4with code rate R = 0.5 and code length N = 64.

International Conference on Information Science and Technology•May 21, 2021•0 citations

Belief Propagation List Ordered Statistics Decoding of Polar Codes

Guy Mogilevsky, David Burshtein

It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.

arXiv:2102.07994•Feb 16, 2021•0 citations

SCL-GRAND: Lower complexity and better flexibility for CRC-Polar Codes

Xuanyu Li, Kai Niu, Jincheng Dai +2 more

Guessing random additive noise decoding (GRAND) is a recently proposed decoding algorithm which can achieve the error performance of maximum likelihood (ML) decoding. However, GRAND and its variants are only suitable for some short codes with high code rates and have large average query numbers. To mitigate these problems, we propose a successive cancellation list (SCL)-GRAND decoding algorithm for the cyclic redundancy check concatenated polar (CRC-polar) codes. The proposed decoder first divides the received sequence into two subblocks. Then SCL is used to decode the upper subblock and output several candidates into the candidate list. For each candidate, GRAND is used to decode the lower subblock and finally choose the most-likely codeword as the decoded result. Since the SCL is integrated into the SCL-GRAND algorithm, this algorithm can achieve lower complexity and better flexibility than the original GRAND.

IEEE Wireless Communications and Networking Conference•Mar 1, 2023•7 citations

Improved ORB-GRAND for PAC Codes

Yueh Wang, Zhiping Shi, Ziyu Han +2 more

Polarization-adjusted convolutional (PAC) codes have been proposed to significantly improve error correction ability compared to polar codes by incorporating rate-1 convolutional precoding. However, the development of computationally efficient decoders for PAC codes is still an ongoing research area. Ordered Reliability Bit Guessing Random Additive Noise Decoding (ORB-GRAND), a universal near Maximum Likelihood (near-ML) decoder, has been introduced for decoding moderately redundant block codes by querying a list of putative test error patterns (TEP) in a fixed order, i.e. logistic weight order (LWO) and improved logistic weight order (iLWO). In this study, we undertake a comprehensive investigation into the performance of ORB-GRAND concerning high-rate PAC codes of short-to-medium length. Firstly, we conduct a comparative analysis between ORB-GRAND and successive cancellation list (SCL) decoding for PAC codes and integrate the Cyclic Redundancy Check (CRC) mechanism into ORB-GRAND. Distance properties of PAC and CRC-Aided PAC (CA-PAC) codes are explored to demonstrate the performance results. Secondly, we propose a novel TEP scheduling scheme in response to the distinctive reduction in BLER revealed by scheduling TEP in iLWO, particularly for short PAC codes under low Signal-to-Noise Ratio (SNR) conditions. This remarkable scheme demonstrates its efficacy by effectively mitigating the aforementioned BLER degradation while maintaining the exceptional performance of iLWO in high SNR conditions.

International Conference on Communication, Image and Signal Processing (CCISP)•Nov 17, 2023•1 citation

Ordered Statistic Decoding for Short Polar Codes

Daolong Wu, Ying Li, Xudong Guo +1 more

In this letter, the ordered statistic decoding (OSD) is considered to decode short polar codes. Since the number of tested codewords is high in the original OSD, a threshold-based OSD is proposed to reduce the complexity. The analysis shows that the threshold affects the OSD in two ways. One is the error floor in high signal-to-noise ratio (SNR) region while the other is the reduction of the number of tested codewords. The estimation on the BLER performance in high SNR region and the average number of tested codewords are discussed. After that, CRC-aided OSD is proposed to further improve the performance of polar codes. Simulation results show that a well-designed threshold-based OSD can reduce the complexity without significant performance loss. And a higher order OSD decoder is needed if OSD is used to decoding moderate or long polar codes. It is also illustrated that the CRC-aided OSD outperforms the CRC-aided list decoding when the code rate is high. When code rate is low, the result inverses.

IEEE Communications Letters•Mar 7, 2016•50 citations
In this paper, we propose a pre-configured error pattern ordered statistics decoding (PEPOSD) algorithm and discuss its application to short cyclic redundancy check (CRC)-polar codes. Unlike the traditional OSD that changes the most reliable independent symbols, we regard the decoding process as testing the error patterns, like guessing random additive noise decoding (GRAND). Also, the pre-configurator referred from ordered reliability bits (ORB) GRAND can better control the range and testing order of EPs. An offline-online structure can accelerate the decoding process. Additionally, we also introduce two orders to optimize the search order for testing EPs. Compared with CRC-aided OSD and list decoding, PEPOSD can achieve a better trade-off between accuracy and complexity.
Polar codes have been used to guarantee high reliability in communication due to their excellent performance. In this letter, we propose a guessing error pattern ordered statistic decoding (GEPOSD) algorithm to further improve the performance of short polar codes. It outperforms the widely used cyclic redundancy check-aided successive cancellation list (CA-SCL) decoding under a code length of 64. The GEPOSD algorithm utilizes a strategy based on the maximum a posteriori probability rule to select the error pattern on the most reliable independent bits. Subsequently, an error pattern set is extended using a tree search approach. To minimize computational complexity, we introduce two early stopping criteria that limit the number of error patterns tested in decoding. The simulation results show that the complexity of GEPOSD is significantly reduced compared to the original OSD algorithm.
With the advent of 5th generation (5G) mobile communication era, higher requirements are put forward for ultra-reliable and low-latency transmission compared with 4G, especially in the field of short packet communication. In this paper, we propose a segmented cyclic redundancy check aided order statistical decoding algorithm with multiple biases (BIAS- SCRC-OSD) for short polar codes. This algorithm constructs multiple information sets by repeatedly adding bias value, and selects more effective information sets to improve the decoding performance. For further improving the decoding performance, we change the original cyclic redundancy check (CRC) into segment check. The simulation results show that a suitable bias value can significantly improve the decoding performance with a small increase in computational complexity. Compared with the original CRC-aided order statistical decoding (OSD) algorithm, the proposed algorithm has a gain of about 0.8 dB at target bit error rate (BER) 10-4with code rate R = 0.5 and code length N = 64.
It is shown how to combine ordered statistics decoding (OSD) with CRC-aided belief propagation list (CBPL) decoding of polar codes. Even when the reprocessing order of the OSD is as low as one, the new decoder is shown to significantly improve on CBPL. For reprocessing orders higher than one, we suggest partial reprocessing, where only error patterns associated with the least reliable part of the belief propagation decoded most reliable independent bits are considered. This type of partial reprocessing offers a trade-off between performance and computational complexity.
Guessing random additive noise decoding (GRAND) is a recently proposed decoding algorithm which can achieve the error performance of maximum likelihood (ML) decoding. However, GRAND and its variants are only suitable for some short codes with high code rates and have large average query numbers. To mitigate these problems, we propose a successive cancellation list (SCL)-GRAND decoding algorithm for the cyclic redundancy check concatenated polar (CRC-polar) codes. The proposed decoder first divides the received sequence into two subblocks. Then SCL is used to decode the upper subblock and output several candidates into the candidate list. For each candidate, GRAND is used to decode the lower subblock and finally choose the most-likely codeword as the decoded result. Since the SCL is integrated into the SCL-GRAND algorithm, this algorithm can achieve lower complexity and better flexibility than the original GRAND.
Polarization-adjusted convolutional (PAC) codes have been proposed to significantly improve error correction ability compared to polar codes by incorporating rate-1 convolutional precoding. However, the development of computationally efficient decoders for PAC codes is still an ongoing research area. Ordered Reliability Bit Guessing Random Additive Noise Decoding (ORB-GRAND), a universal near Maximum Likelihood (near-ML) decoder, has been introduced for decoding moderately redundant block codes by querying a list of putative test error patterns (TEP) in a fixed order, i.e. logistic weight order (LWO) and improved logistic weight order (iLWO). In this study, we undertake a comprehensive investigation into the performance of ORB-GRAND concerning high-rate PAC codes of short-to-medium length. Firstly, we conduct a comparative analysis between ORB-GRAND and successive cancellation list (SCL) decoding for PAC codes and integrate the Cyclic Redundancy Check (CRC) mechanism into ORB-GRAND. Distance properties of PAC and CRC-Aided PAC (CA-PAC) codes are explored to demonstrate the performance results. Secondly, we propose a novel TEP scheduling scheme in response to the distinctive reduction in BLER revealed by scheduling TEP in iLWO, particularly for short PAC codes under low Signal-to-Noise Ratio (SNR) conditions. This remarkable scheme demonstrates its efficacy by effectively mitigating the aforementioned BLER degradation while maintaining the exceptional performance of iLWO in high SNR conditions.
In this letter, the ordered statistic decoding (OSD) is considered to decode short polar codes. Since the number of tested codewords is high in the original OSD, a threshold-based OSD is proposed to reduce the complexity. The analysis shows that the threshold affects the OSD in two ways. One is the error floor in high signal-to-noise ratio (SNR) region while the other is the reduction of the number of tested codewords. The estimation on the BLER performance in high SNR region and the average number of tested codewords are discussed. After that, CRC-aided OSD is proposed to further improve the performance of polar codes. Simulation results show that a well-designed threshold-based OSD can reduce the complexity without significant performance loss. And a higher order OSD decoder is needed if OSD is used to decoding moderate or long polar codes. It is also illustrated that the CRC-aided OSD outperforms the CRC-aided list decoding when the code rate is high. When code rate is low, the result inverses.