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

IEEE International Symposium on Information Theory (ISIT)

Partial Ordered Statistics Decoding with Enhanced Error Patterns

Marwan Jalaleddine, Huayi Zhou, Jiajie Li, Warren J. Gross

Published Jun 25, 2023• 13 citations
Publisher

Abstract

Guessing Random Additive Noise Decoding (GRAND) excels at decoding high-rate codes but struggles to decode low-rate codes with reasonable complexity. Ordered Statistics Decoding (OSD) specifically excels in decoding short codes irrespective of rates; however, OSD necessitates the use of Gaussian elimination which introduces additional time, space and computational complexity. Partial Ordered Statistics Decoding (POSD) was proposed to reduce the time, space, and computational complexity of OSD; however, the current partition-based POSD has poor decoding performance since it does not generate test error patterns across partitions. In this paper, we propose to improve the decoding performance of POSD by incorporating test error patterns inspired by GRAND methods. This work offers a trade-off between performance and complexity compared to existing decoders such as GRAND and OSD. We enhance POSD by optimizing the scheduling of Test Error Patterns (TEPs) and show that our technique can be applied to any code in a standard form. At a target BER 10−4with eBCH (128,64) the enhanced error patterns achieve more than 0.6 dB gain in performance compared to the POSD with partition-based error patterns. Moreover, at a target frame error rate of 10−5, POSD uses 10× less binary operations compared to GRAND when decoding eBCH (128,64) and RLC(128,64) codes. With BCH (127,29) and RLC(128,32), at a target frame error rate of 10−2, POSD with enhanced error patterns with a maximum number of queries (MQ) of 104achieves up to a 2 dB gain to its GRAND equivalent which is using 107maximum number of queries.

DOI
10.1109/isit54713.2023.10206555

Related papers

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

Xuanyu Li, Kai Niu, Yuxin Han +3 more

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.

arXiv:2309.11836•Entropy•Sep 30, 2023•7 citations

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•4 citations

Performance Analysis and Optimal Design of ORB-Type GRAND Algorithms

Li Wan, Wenyi Zhang

Guessing Random Additive Noise Decoding (GRAND) performs decoding by sequentially guessing channel error patterns (EPs). Ordered Reliability Bits GRAND (ORBGRAND) is a notable instance suitable for efficient implementation, as it schedules EPs solely according to the ranking of soft channel outputs. In this paper, we generalize this principle to a broader class of GRAND algorithms whose testing order depends only on reliability ranking, referred to as ORB-type GRAND. We develop a unified analytical framework based on a key quantity termed the average guessing posterior (AGP), which captures the effectiveness of each EP and reduces decoding into an ordering problem over the EP space. For random code ensembles, we derive exact expressions for the block error rate (BLER), stopping-time distribution, and average number of tests under a fixed test budget. The analysis separates target-miss and target-preemption errors and shows that ordering EPs by non-increasing AGP is optimal over the EP set under consideration. For fixed linear block codes, we derive the BLER expression that isolates the code-dependent target-preemption term and characterize this term through higher-order weight relationships of codeword tuples, with a computable first-order upper bound as a useful special case. Guided by these insights, we formulate ReShuffled-ORBGRAND (RS-ORBGRAND) as an offline AGP-based reshuffling scheme. Numerical results for the Bose--Chaudhuri--Hocquenghem (BCH)$(127,113)$ code show that RS-ORBGRAND consistently improves existing ORB-type GRAND algorithms and lies within $0.1$~dB of a maximum-likelihood decoding lower-bound benchmark at a BLER of $10^{-6}$.

arXiv:2606.28030•Jun 26, 2026•3 citations

Reducing ORBGRAND Latency via Partial Gaussian Elimination

Li Wan, Wenyi Zhang

Guessing Random Additive Noise Decoding (GRAND) is a universal framework for decoding all block codes by testing candidate error patterns (EPs). Ordered Reliability Bits GRAND (ORBGRAND) facilitates parallel implementation of GRAND by exploiting log-likelihood ratio (LLR) rankings but still suffers from high tail latency under unfavorable channel conditions, limiting its use in real-time systems.We propose an elimination-aided ORBGRAND scheme that reduces decoding latency by integrating the Rank of the Most Reliable Erroneous (RMRE) bit with a partial Gaussian-elimination (GE) filtering mechanism. The scheme groups and jointly verifies EPs that share the same RMRE, and once a valid EP is identified, the ORBGRAND search is resumed. By leveraging prior GE steps to filter out unnecessary guesses, this approach significantly reduces the number of EPs to be tested, thereby lowering both average and worst-case latency while maintaining error-correction performance.Simulation results show that compared to the original OR-BGRAND, the elimination-aided ORBGRAND filters out more than 50% of EPs and correspondingly reduce overall computational complexity, all with no loss in block error rate. This demonstrates that this approach is suitable for ultra-reliable low-latency communication scenarios.

arXiv:2602.01174•International Conference on Communications•May 24, 2026•0 citations

A Fixed Latency ORBGRAND Decoder Architecture With LUT-Aided Error-Pattern Scheduling

Carlo Condo

Guessing Random Additive Noise Decoding (GRAND) is a universal decoding algorithm that has been recently proposed as a practical way to perform maximum likelihood decoding. It generates a sequence of possible error patterns and applies them to the received vector, checking if the result is a valid codeword. Ordered reliability bits GRAND (ORBGRAND) improves on GRAND by considering soft information received from the channel. Both GRAND and ORBGRAND have been implemented in hardware, focusing on average performance, sacrificing worst case throughput and latency. In this work, an improved pattern schedule for ORBGRAND is proposed. It provides$> 0.5$dB gain over the standard schedule at a block error rate$\le 10^{-5}$, and outperforms more complex GRAND flavors with a fraction of the complexity. The proposed schedule is used within a novel code-agnositic decoder architecture: the decoder guarantees fixed high throughput and low latency, making it attractive for latency-constrained applications. It outperforms the worst-case performance of decoders by orders of magnitude, and outperforms many best-case figures. Decoding a code of length 128, it achieves a throughput of 79.21 Gb/s with 58.49 ns latency, yielding better energy efficiency and comparable area efficiency with respect to the state of the art.

arXiv:2111.08134•IEEE Transactions on Circuits and Systems I Regular Papers•Feb 17, 2022•69 citations

Ordered statistics-based list decoding techniques for linear binary block codes

Saif E. A. Alnawayseh, Pavel Loskot

The ordered statistics-based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of a list of the test error patterns is considered. The original ordered-statistics decoding (OSD) is generalized by assuming segmentation of the most reliable independent positions (MRIPs) of the received bits. The segmentation is shown to overcome several drawbacks of the original OSD. The complexity of the ordered statistics-based decoding is further reduced by assuming a partial ordering of the received bits in order to avoid the complex Gauss elimination. The probability of the test error patterns in the decoding list is derived. The bit error rate performance and the decoding complexity trade-off of the proposed decoding algorithms is studied by computer simulations. Numerical examples show that, in some cases, the proposed decoding schemes are superior to the original OSD in terms of both the bit error rate performance as well as the decoding complexity.

arXiv:1101.5025•EURASIP Journal on Wireless Communications and Networking•Oct 16, 2012•13 citations
Guessing Random Additive Noise Decoding (GRAND) excels at decoding high-rate codes but struggles to decode low-rate codes with reasonable complexity. Ordered Statistics Decoding (OSD) specifically excels in decoding short codes irrespective of rates; however, OSD necessitates the use of Gaussian elimination which introduces additional time, space and computational complexity. Partial Ordered Statistics Decoding (POSD) was proposed to reduce the time, space, and computational complexity of OSD; however, the current partition-based POSD has poor decoding performance since it does not generate test error patterns across partitions. In this paper, we propose to improve the decoding performance of POSD by incorporating test error patterns inspired by GRAND methods. This work offers a trade-off between performance and complexity compared to existing decoders such as GRAND and OSD. We enhance POSD by optimizing the scheduling of Test Error Patterns (TEPs) and show that our technique can be applied to any code in a standard form. At a target BER 10−4with eBCH (128,64) the enhanced error patterns achieve more than 0.6 dB gain in performance compared to the POSD with partition-based error patterns. Moreover, at a target frame error rate of 10−5, POSD uses 10× less binary operations compared to GRAND when decoding eBCH (128,64) and RLC(128,64) codes. With BCH (127,29) and RLC(128,32), at a target frame error rate of 10−2, POSD with enhanced error patterns with a maximum number of queries (MQ) of 104achieves up to a 2 dB gain to its GRAND equivalent which is using 107maximum number of queries.
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.
Guessing Random Additive Noise Decoding (GRAND) performs decoding by sequentially guessing channel error patterns (EPs). Ordered Reliability Bits GRAND (ORBGRAND) is a notable instance suitable for efficient implementation, as it schedules EPs solely according to the ranking of soft channel outputs. In this paper, we generalize this principle to a broader class of GRAND algorithms whose testing order depends only on reliability ranking, referred to as ORB-type GRAND. We develop a unified analytical framework based on a key quantity termed the average guessing posterior (AGP), which captures the effectiveness of each EP and reduces decoding into an ordering problem over the EP space. For random code ensembles, we derive exact expressions for the block error rate (BLER), stopping-time distribution, and average number of tests under a fixed test budget. The analysis separates target-miss and target-preemption errors and shows that ordering EPs by non-increasing AGP is optimal over the EP set under consideration. For fixed linear block codes, we derive the BLER expression that isolates the code-dependent target-preemption term and characterize this term through higher-order weight relationships of codeword tuples, with a computable first-order upper bound as a useful special case. Guided by these insights, we formulate ReShuffled-ORBGRAND (RS-ORBGRAND) as an offline AGP-based reshuffling scheme. Numerical results for the Bose--Chaudhuri--Hocquenghem (BCH)(127,113)(127,113)(127,113) code show that RS-ORBGRAND consistently improves existing ORB-type GRAND algorithms and lies within 0.10.10.1~dB of a maximum-likelihood decoding lower-bound benchmark at a BLER of 10−610^{-6}10−6.
Guessing Random Additive Noise Decoding (GRAND) is a universal framework for decoding all block codes by testing candidate error patterns (EPs). Ordered Reliability Bits GRAND (ORBGRAND) facilitates parallel implementation of GRAND by exploiting log-likelihood ratio (LLR) rankings but still suffers from high tail latency under unfavorable channel conditions, limiting its use in real-time systems.We propose an elimination-aided ORBGRAND scheme that reduces decoding latency by integrating the Rank of the Most Reliable Erroneous (RMRE) bit with a partial Gaussian-elimination (GE) filtering mechanism. The scheme groups and jointly verifies EPs that share the same RMRE, and once a valid EP is identified, the ORBGRAND search is resumed. By leveraging prior GE steps to filter out unnecessary guesses, this approach significantly reduces the number of EPs to be tested, thereby lowering both average and worst-case latency while maintaining error-correction performance.Simulation results show that compared to the original OR-BGRAND, the elimination-aided ORBGRAND filters out more than 50% of EPs and correspondingly reduce overall computational complexity, all with no loss in block error rate. This demonstrates that this approach is suitable for ultra-reliable low-latency communication scenarios.
Guessing Random Additive Noise Decoding (GRAND) is a universal decoding algorithm that has been recently proposed as a practical way to perform maximum likelihood decoding. It generates a sequence of possible error patterns and applies them to the received vector, checking if the result is a valid codeword. Ordered reliability bits GRAND (ORBGRAND) improves on GRAND by considering soft information received from the channel. Both GRAND and ORBGRAND have been implemented in hardware, focusing on average performance, sacrificing worst case throughput and latency. In this work, an improved pattern schedule for ORBGRAND is proposed. It provides>0.5> 0.5>0.5dB gain over the standard schedule at a block error rate≤10−5\le 10^{-5}≤10−5, and outperforms more complex GRAND flavors with a fraction of the complexity. The proposed schedule is used within a novel code-agnositic decoder architecture: the decoder guarantees fixed high throughput and low latency, making it attractive for latency-constrained applications. It outperforms the worst-case performance of decoders by orders of magnitude, and outperforms many best-case figures. Decoding a code of length 128, it achieves a throughput of 79.21 Gb/s with 58.49 ns latency, yielding better energy efficiency and comparable area efficiency with respect to the state of the art.
The ordered statistics-based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of a list of the test error patterns is considered. The original ordered-statistics decoding (OSD) is generalized by assuming segmentation of the most reliable independent positions (MRIPs) of the received bits. The segmentation is shown to overcome several drawbacks of the original OSD. The complexity of the ordered statistics-based decoding is further reduced by assuming a partial ordering of the received bits in order to avoid the complex Gauss elimination. The probability of the test error patterns in the decoding list is derived. The bit error rate performance and the decoding complexity trade-off of the proposed decoding algorithms is studied by computer simulations. Numerical examples show that, in some cases, the proposed decoding schemes are superior to the original OSD in terms of both the bit error rate performance as well as the decoding complexity.