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

IEEJ Transactions on Electronics Information and Systems

Proposal of SGRAND Algorithm with Less List Size of Noise Pattern Candidate Growth while Keeping ML Property

Taro Kumamoto, Shogo Usami, Souichi Takahira

Published Nov 30, 2023• 0 citations
Publisher

Abstract

To achieve ultra-high reliability and ultra-low latency required for Beyond 5G or 6G, low error rate decoding method is needed with short code lengths and high code rates. Additionally, a universal decoding method that can be applied to any code which appears in the future be desirable. The maximum likelihood decoding is the best decoding method in information theory, but it is considered difficult to implement due to its huge computational requirements. Recently, Soft GRAND (SGRAND) has been proposed as an effective decoding method for any high-rate, short code length block code in any continuous channel. This method obtains the same decoding result as the maximum likelihood decoding by checking the most likely noise sequantially. However, SGRAND has a problem in which the size of the noise candidate list held internally increases linearly with each noise check. This paper proposes a method to reduce the size of the candidate list in SGRAND, while maintaining the same decoding results as maximum likelihood decoding, by modifying the noise candidate generation algorithm in SGRAND.

DOI
10.1541/ieejeiss.143.1083

Related papers

Soft Maximum Likelihood Decoding using GRAND

Amit Solomon, Ken R. Duffy, Muriel Médard

Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we propose a development of a previously described hard detection ML decoder called Guessing Random Additive Noise Decoding (GRAND). We introduce Soft GRAND (SGRAND), a ML decoder that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on Cyclic Redundancy Check (CRC)-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G New Radio (NR), comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-the-art soft-information decoder specific to CA-Polar codes.

arXiv:2001.03089•International Conference on Communications•Jun 1, 2020•119 citations

Soft-Output (SO) GRAND and Iterative Decoding to Outperform LDPC Codes

Peihong Yuan, Muriel Médard, Kevin Galligan +1 more

We establish that a large, flexible class of long, high redundancy error correcting codes can be efficiently and accurately decoded with guessing random additive noise decoding (GRAND). Performance evaluation demonstrates that it is possible to construct simple product codes with lengths of approximately 200 to 4000 bits and rates between 0.2 and 0.8 that outperform low-density parity-check (LDPC) codes from the 5G New Radio standard in both AWGN and fading channels. The concatenated structure enables many desirable features, including: low-complexity hardware-friendly encoding and decoding; significant flexibility in length and rate through modularity; and high levels of parallelism in encoding and decoding that enable low latency. Central is the development of a method through which any soft-input (SI) GRAND algorithm can provide soft-output (SO) in the form of an accurate a-posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that each element of the list is correct. The distinguishing feature of soft-output GRAND (SOGRAND) is the provision of an estimate that the correct decoding has not been found, even when providing a single decoding. Per-block SO can be converted into accurate per-bit SO by a weighted sum that includes a term for the SI. Implementing SOGRAND adds negligible computation and memory to the existing decoding process, and using it results in a practical, low-latency alternative to LDPC codes.

arXiv:2310.10737•IEEE Transactions on Wireless Communications•Jan 24, 2025•27 citations

Soft-Decision Randomized Likelihood Decoding

A. D. Lebedinskaya, Kirill Shabunov

Ultra-reliable low-latency communications (URLLC) scenario for 6G drives the interest in studying and development of existing and new universal decoding algorithms capable of providing near-optimum error-correcting performance for short block length codes with ultimate goal of providing low latency and moderate complexity. In this paper we consider a new universal decoding technique based on randomized likelihood (RL) rule that may be implemented for practical use in the future. U sing this rule we get the message estimate as a single sample of the message vector from a posterior distribution of messages given the received signal. A soft-decision implementation of RL decoding algorithm is suggested. After suggesting further complexity optimization, the new algorithm is compared to other well-known universal decoders, such as ordered-statistics decoding (OSD) and guessing random additive noise decoding (GRAND). The simulation results for short codes with different rates are provided for binary-input additive white Gaussian noise (BAWGN) communication channel.

International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON)•Sep 30, 2024•0 citations

Improving Short-Block LDPC Decoding Using Perturbation-Based Rescue with Maximum Likelihood Based Candidate Validation

Haider Abdulkarim, Hussein Khaleel, Marwa K. Farhan

Abstract Meeting the latency and reliability requirements of 5G Ultra-Reliable Low-Latency Communications (URLLC) is enabled through the adoption of short-block Low-Density Parity-Check (LDPC) codes. Traditional decoding of short-block LDPC using Belief Propagation (BP) may fail due to trapping sets, resulting in degraded decoding performance. This paper proposes a three-stage decoding algorithm that combines low-iteration BP decoding, a perturbation-based rescue process, and Maximum Likelihood (ML) based candidate validation to improve decoding reliability. When the low-iteration BP decoding stage fails to converge, the rescue stage perturbs the least reliable bits to generate multiple decoding candidates, which are subsequently evaluated using an ML-based metric to select the most likely candidate and reduce miscorrections. The proposed algorithm was evaluated through MATLAB simulations with a short-block LDPC configuration for 5G URLLC systems. QAM modulation was used and two channel models were considered, Additive White Gaussian Noise and flat Rayleigh fading. The performance was investigated for different numbers of perturbed bits and different coding rates. The results show improved decoding performance compared to standard LDPC, achieving coding gains exceeding 1 dB at low bit error rates while reducing decoding failures caused by trapping sets.

•Oct 12, 2026•0 citations

A Parallelization Strategy for GRAND With Optimality Guarantee by Exploiting Error Pattern Tree Representation

Li Wan, Huarui Yin, Wenyi Zhang

Parallelism has become a central concern in modern decoding frameworks aiming to meet stringent throughput and latency requirements. Guessing Random Additive Noise Decoding (GRAND) is a recently proposed decoding paradigm that tests candidate Error Patterns (EPs) until a valid codeword is found. Among its variants, Soft GRAND (SGRAND) achieves maximum-likelihood (ML) decoding but relies on real-time generation and likelihood ordering of EPs, making parallel execution nontrivial under the ML optimality constraint. In this work, we introduce a unified binary tree representation of EPs, termed the EP tree, which formalizes the hierarchical structure underlying SGRAND and Ordered Reliability Bits (ORB) GRAND algorithms, enabling structured organization of EPs and algorithmic-level parallel exploration. Building upon this unified framework, we propose a parallel design of SGRAND that preserves ML optimality while significantly reducing decoding complexity through pruning strategies and tree-based computation. Furthermore, we develop an enhanced ORBGRAND algorithm based on the same EP tree representation, improving decoding performance toward ML while retaining parallel efficiency. Numerical experiments show that the proposed parallel SGRAND achieves a 3.96× reduction in decoding latency compared with its serial counterpart, while the enhanced ORBGRAND achieves a 4.21× speedup, demonstrating the effectiveness of the unified tree-based framework and its strong potential for future algorithmic and hardware optimizations.

arXiv:2510.01813•IEEE Transactions on Communications•Jan 1, 2026•1 citation

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•63 citations
To achieve ultra-high reliability and ultra-low latency required for Beyond 5G or 6G, low error rate decoding method is needed with short code lengths and high code rates. Additionally, a universal decoding method that can be applied to any code which appears in the future be desirable. The maximum likelihood decoding is the best decoding method in information theory, but it is considered difficult to implement due to its huge computational requirements. Recently, Soft GRAND (SGRAND) has been proposed as an effective decoding method for any high-rate, short code length block code in any continuous channel. This method obtains the same decoding result as the maximum likelihood decoding by checking the most likely noise sequantially. However, SGRAND has a problem in which the size of the noise candidate list held internally increases linearly with each noise check. This paper proposes a method to reduce the size of the candidate list in SGRAND, while maintaining the same decoding results as maximum likelihood decoding, by modifying the noise candidate generation algorithm in SGRAND.
Maximum Likelihood (ML) decoding of forward error correction codes is known to be optimally accurate, but is not used in practice as it proves too challenging to efficiently implement. Here we propose a development of a previously described hard detection ML decoder called Guessing Random Additive Noise Decoding (GRAND). We introduce Soft GRAND (SGRAND), a ML decoder that fully avails of soft detection information and is suitable for use with any arbitrary high-rate, short-length block code. We assess SGRAND's performance on Cyclic Redundancy Check (CRC)-aided Polar (CA-Polar) codes, which will be used for all control channel communication in 5G New Radio (NR), comparing its accuracy with CRC-Aided Successive Cancellation List decoding (CA-SCL), a state-of-the-art soft-information decoder specific to CA-Polar codes.
We establish that a large, flexible class of long, high redundancy error correcting codes can be efficiently and accurately decoded with guessing random additive noise decoding (GRAND). Performance evaluation demonstrates that it is possible to construct simple product codes with lengths of approximately 200 to 4000 bits and rates between 0.2 and 0.8 that outperform low-density parity-check (LDPC) codes from the 5G New Radio standard in both AWGN and fading channels. The concatenated structure enables many desirable features, including: low-complexity hardware-friendly encoding and decoding; significant flexibility in length and rate through modularity; and high levels of parallelism in encoding and decoding that enable low latency. Central is the development of a method through which any soft-input (SI) GRAND algorithm can provide soft-output (SO) in the form of an accurate a-posteriori estimate of the likelihood that a decoding is correct or, in the case of list decoding, the likelihood that each element of the list is correct. The distinguishing feature of soft-output GRAND (SOGRAND) is the provision of an estimate that the correct decoding has not been found, even when providing a single decoding. Per-block SO can be converted into accurate per-bit SO by a weighted sum that includes a term for the SI. Implementing SOGRAND adds negligible computation and memory to the existing decoding process, and using it results in a practical, low-latency alternative to LDPC codes.
Ultra-reliable low-latency communications (URLLC) scenario for 6G drives the interest in studying and development of existing and new universal decoding algorithms capable of providing near-optimum error-correcting performance for short block length codes with ultimate goal of providing low latency and moderate complexity. In this paper we consider a new universal decoding technique based on randomized likelihood (RL) rule that may be implemented for practical use in the future. U sing this rule we get the message estimate as a single sample of the message vector from a posterior distribution of messages given the received signal. A soft-decision implementation of RL decoding algorithm is suggested. After suggesting further complexity optimization, the new algorithm is compared to other well-known universal decoders, such as ordered-statistics decoding (OSD) and guessing random additive noise decoding (GRAND). The simulation results for short codes with different rates are provided for binary-input additive white Gaussian noise (BAWGN) communication channel.
Abstract Meeting the latency and reliability requirements of 5G Ultra-Reliable Low-Latency Communications (URLLC) is enabled through the adoption of short-block Low-Density Parity-Check (LDPC) codes. Traditional decoding of short-block LDPC using Belief Propagation (BP) may fail due to trapping sets, resulting in degraded decoding performance. This paper proposes a three-stage decoding algorithm that combines low-iteration BP decoding, a perturbation-based rescue process, and Maximum Likelihood (ML) based candidate validation to improve decoding reliability. When the low-iteration BP decoding stage fails to converge, the rescue stage perturbs the least reliable bits to generate multiple decoding candidates, which are subsequently evaluated using an ML-based metric to select the most likely candidate and reduce miscorrections. The proposed algorithm was evaluated through MATLAB simulations with a short-block LDPC configuration for 5G URLLC systems. QAM modulation was used and two channel models were considered, Additive White Gaussian Noise and flat Rayleigh fading. The performance was investigated for different numbers of perturbed bits and different coding rates. The results show improved decoding performance compared to standard LDPC, achieving coding gains exceeding 1 dB at low bit error rates while reducing decoding failures caused by trapping sets.
Parallelism has become a central concern in modern decoding frameworks aiming to meet stringent throughput and latency requirements. Guessing Random Additive Noise Decoding (GRAND) is a recently proposed decoding paradigm that tests candidate Error Patterns (EPs) until a valid codeword is found. Among its variants, Soft GRAND (SGRAND) achieves maximum-likelihood (ML) decoding but relies on real-time generation and likelihood ordering of EPs, making parallel execution nontrivial under the ML optimality constraint. In this work, we introduce a unified binary tree representation of EPs, termed the EP tree, which formalizes the hierarchical structure underlying SGRAND and Ordered Reliability Bits (ORB) GRAND algorithms, enabling structured organization of EPs and algorithmic-level parallel exploration. Building upon this unified framework, we propose a parallel design of SGRAND that preserves ML optimality while significantly reducing decoding complexity through pruning strategies and tree-based computation. Furthermore, we develop an enhanced ORBGRAND algorithm based on the same EP tree representation, improving decoding performance toward ML while retaining parallel efficiency. Numerical experiments show that the proposed parallel SGRAND achieves a 3.96× reduction in decoding latency compared with its serial counterpart, while the enhanced ORBGRAND achieves a 4.21× speedup, demonstrating the effectiveness of the unified tree-based framework and its strong potential for future algorithmic and hardware optimizations.
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.