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:2411.09803 · Conference on Information Sciences and Systems

Using a Single Parity-Check to Reduce the Guesswork of Guessing Codeword Decoding

Joseph Griffin, Peihong Yuan, Ken R. Duffy, Muriel Médard

Published Mar 19, 2025• 1 citation
arXivHTMLPDF

Abstract

Guessing Codeword Decoding (GCD) is a recently proposed soft-input forward error correction decoder for arbitrary binary linear codes. Inspired by recent proposals that leverage binary linear codebook structure to reduce the number of queries made by Guessing Random Additive Noise Decoding (GRAND), for binary linear codes that include a full-message single parity-check (SPC) bit, we show that it is possible to reduce the number of queries made by GCD by a factor of up to 2 with the greatest guesswork reduction realized at lower SNRs, without impacting decoding precision. Codes without a full-message SPC can be modified to include one by changing a column of the generator matrix to obtain a decoding complexity advantage, and we demonstrate that this can often be done without losing decoding precision. To practically avail of the complexity advantage, a noise effect pattern generator capable of producing sequences for given Hamming weights, such as the landslide algorithm developed for ORBGRAND, is necessary.

DOI
10.1109/ciss64860.2025.10944685

Related papers

Enhanced GCD Through ORBGRAND-AI: Exploiting Partial and Total Correlation in Noise

Jiewei Feng, Ken R. Duffy, Muriel Médard

There have been significant advances in recent years in the development of forward error correction decoders that can decode codes of any structure, including practical realizations in synthesized circuits and taped out chips. While essentially all soft-decision decoders assume that bits have been impacted independently on the channel, for one of these new approaches it has been established that channel dependencies can be exploited to achieve superior decoding accuracy, resulting in Ordered Reliability Bits Guessing Random Additive Noise Decoding Approximate Independence (ORBGRAND-AI). Building on that capability, here we consider the integration of ORBGRAND-AI as a pattern generator for Guessing Codeword Decoding (GCD). We first establish that a direct approach delivers mildly degraded block error rate (BLER) but with reduced number of queried patterns when compared to ORBGRAND-AI. We then show that with a more nuanced approach it is possible to leverage total correlation to deliver an additional BLER improvement of ~0.75$ dB while retaining reduced query numbers.

arXiv:2511.07376•IEEE Communications Letters•Jan 1, 2026•1 citation

Locally Constrained Guessing Codeword Decoding of Short Block Codes

Xiangping Zheng, Xiao Ma

This paper is concerned with a universal guessing codeword decoding (GCD) of linear block codes, referred to as locally constrained GCD (LC-GCD), which does not require the online Gaussian elimination (GE). Distinguished from the GCD algorithm, the proposed LC-GCD queries the partial error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix, typically reducing the number of queries. Moreover, we introduce a parallel implementation of the LC-GCD algorithm to reduce decoding latency without compromising performance. Numerical results show that the LC-GCD requires a fewer number of queries than the GCD without performance loss, indicating a lower complexity in general. The comparisons with other decoding algorithms are also provided to demonstrate the potential advantage in complexity of the LC-GCD.

IEEE Information Theory Workshop (ITW)•Nov 24, 2024•14 citations

Generalized Segmented GRAND for Guesswork Reduction in Turbo Product Decoding

Lukas Rapp, Jiewei Feng, Muriel Médard +1 more

Guessing random additive noise decoding (GRAND) can efficiently decode any moderately redundant code with near maximum likelihood (ML) performance via noise effect guessing. For binary linear codes, Rowshan and Yuan's Segmented GRAND was the first to show that constrained guessing can reduce guesswork. Although powerful, their approach requires a specific parity-check matrix structure that limits the number of constraints that can be exploited as well as the class of applicable codes. Here we introduce GSegGRAND, a generalization of Segmented GRAND that circumvents its limitations. Built on a novel parity check structure and a transformation that maps codes into this structure, GSegGRAND efficiently incorporates up to log2(n) constraints for a wide range of codes, reducing guesswork by an additional 75% over Segmented GRAND. To leverage that advantage for soft-output decoding, we derive an accurate soft-output (SO) equation for GSegGRAND by extending soft-output GRAND (SOGRAND) to incorporate constrained guessing. Applying this SO to turbo product decoding, GSegGRAND achieves up to 88% guesswork reduction, making it a promising candidate for low-latency decoding in future communication systems.

arXiv:2607.12147•Jul 13, 2026•0 citations

A Universal List Decoding Algorithm With Application to Decoding of Polar Codes

Xiangping Zheng, Xiao Ma

This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.

arXiv:2405.03252•IEEE Transactions on Information Theory•Dec 2, 2024•18 citations

IGRAND Query Reduction using Even Codes

Arslan Riaz, Jiewei Feng, Kevin Galligan +3 more

Guessing Random Additive Noise Decoding (GRAND) algorithms can decode any moderate redundancy code of any structure, with integrated circuits demonstrating that it is possible to execute GRAND efficiently in hardware. By using GRAND as a component decoder, its remit has been extended to efficiently decode long, high redundancy product codes via the Iterative GRAND (IGRAND) algorithm in the hard detection setting. Here, by leveraging the property of even codebooks to split the noise effect search space into even and odd Hamming weights for the rows and columns in product code decoding, we demonstrate significant reductions in the number of queries IGRAND makes without any degradation in decoding performance. For IGRAND, we establish that the reduction in query numbers can be significantly higher than for the component code alone, resulting in significant efficiency gains. In particular, simulation results show that the average number of guesses reduces by a factor of 4 at a bit flip probability of $10^{-1.5}$ when the CRC $(64,53)^{2}$ codebook is used, without impacting on its decoding accuracy.

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Nov 1, 2025•3 citations

Leveraging Code Structure to Improve Soft Output for GRAND, GCD, OSD, and SCL

Jiewei Feng, Ken R. Duffy, Muriel Médard

In addition to a codeword, error correction decoders that provide blockwise soft output (SO) return an estimate of the likelihood that the decoding is correct. Following Forney, such estimates have traditionally only been possible for list decoders with the approximate soft output being the likelihood that a decoding is correct given it is assumed to be in the list. Recently, it has been established that Guessing Random Additive Noise Decoding (GRAND), Guessing Codeword Decoding (GCD), Ordered Statistics Decoding (OSD), and Successive Cancellation List (SCL) decoding can provide accurate soft output without the need for list decoding. Central to the improvement is the evaluation of an estimate of the likelihood that the correct decoding has not been found. We explore how binary linear codebook constraints can be leveraged to further enhance SO precision. We evaluate performance by adapting a forecasting statistic called the Brier Score. Results indicate that the SO generated by the approach is essentially as accurate as the maximum a posteriori estimate.

arXiv:2503.16677•Mar 20, 2025•0 citations
Guessing Codeword Decoding (GCD) is a recently proposed soft-input forward error correction decoder for arbitrary binary linear codes. Inspired by recent proposals that leverage binary linear codebook structure to reduce the number of queries made by Guessing Random Additive Noise Decoding (GRAND), for binary linear codes that include a full-message single parity-check (SPC) bit, we show that it is possible to reduce the number of queries made by GCD by a factor of up to 2 with the greatest guesswork reduction realized at lower SNRs, without impacting decoding precision. Codes without a full-message SPC can be modified to include one by changing a column of the generator matrix to obtain a decoding complexity advantage, and we demonstrate that this can often be done without losing decoding precision. To practically avail of the complexity advantage, a noise effect pattern generator capable of producing sequences for given Hamming weights, such as the landslide algorithm developed for ORBGRAND, is necessary.
There have been significant advances in recent years in the development of forward error correction decoders that can decode codes of any structure, including practical realizations in synthesized circuits and taped out chips. While essentially all soft-decision decoders assume that bits have been impacted independently on the channel, for one of these new approaches it has been established that channel dependencies can be exploited to achieve superior decoding accuracy, resulting in Ordered Reliability Bits Guessing Random Additive Noise Decoding Approximate Independence (ORBGRAND-AI). Building on that capability, here we consider the integration of ORBGRAND-AI as a pattern generator for Guessing Codeword Decoding (GCD). We first establish that a direct approach delivers mildly degraded block error rate (BLER) but with reduced number of queried patterns when compared to ORBGRAND-AI. We then show that with a more nuanced approach it is possible to leverage total correlation to deliver an additional BLER improvement of ~0.75$ dB while retaining reduced query numbers.
This paper is concerned with a universal guessing codeword decoding (GCD) of linear block codes, referred to as locally constrained GCD (LC-GCD), which does not require the online Gaussian elimination (GE). Distinguished from the GCD algorithm, the proposed LC-GCD queries the partial error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix, typically reducing the number of queries. Moreover, we introduce a parallel implementation of the LC-GCD algorithm to reduce decoding latency without compromising performance. Numerical results show that the LC-GCD requires a fewer number of queries than the GCD without performance loss, indicating a lower complexity in general. The comparisons with other decoding algorithms are also provided to demonstrate the potential advantage in complexity of the LC-GCD.
Guessing random additive noise decoding (GRAND) can efficiently decode any moderately redundant code with near maximum likelihood (ML) performance via noise effect guessing. For binary linear codes, Rowshan and Yuan's Segmented GRAND was the first to show that constrained guessing can reduce guesswork. Although powerful, their approach requires a specific parity-check matrix structure that limits the number of constraints that can be exploited as well as the class of applicable codes. Here we introduce GSegGRAND, a generalization of Segmented GRAND that circumvents its limitations. Built on a novel parity check structure and a transformation that maps codes into this structure, GSegGRAND efficiently incorporates up to log2(n) constraints for a wide range of codes, reducing guesswork by an additional 75% over Segmented GRAND. To leverage that advantage for soft-output decoding, we derive an accurate soft-output (SO) equation for GSegGRAND by extending soft-output GRAND (SOGRAND) to incorporate constrained guessing. Applying this SO to turbo product decoding, GSegGRAND achieves up to 88% guesswork reduction, making it a promising candidate for low-latency decoding in future communication systems.
This paper is concerned with a guessing codeword decoding (GCD) of linear block codes, which is optimal and typically requires a fewer number of searches than the naive exhaustive search decoding (ESD). Compared with the guessing random additive noise decoding (GRAND), which is only efficient for high-rate codes, the GCD is efficient for not only high-rate codes but also low-rate codes. We prove that the GCD typically requires a fewer number of queries than the GRAND. Compared with the conventional ordered statistics decoding (OSD), the GCD does not require the online Gaussian elimination (GE). In addition to limiting the maximum number of searches, we suggest limiting the radius of searches in terms of soft weights or tolerated performance loss to further reduce the decoding complexity, resulting in the so-called truncated GCD. The performance gap between the truncated GCD and the optimal decoding can be upper bounded approximately by the saddlepoint approach or other numerical approaches. The derived upper bound captures the relationship between the performance and the decoding parameters, enabling us to balance the performance and the complexity by optimizing the decoding parameters of the truncated GCD. We also introduce a parallel implementation of the (truncated) GCD algorithm to reduce decoding latency without compromising performance. Another contribution of this paper is the application of the GCD to the polar codes. We propose a multiple-bit-wise decoding algorithm over a pruned tree for the polar codes, referred to as the successive-cancellation list (SCL) decoding algorithm by GCD. First, we present a strategy for pruning the conventional polar decoding tree based on the complexity analysis rather than the specific bit patterns. Then we apply the GCD algorithm in parallel aided by the early stopping criteria to the leaves of the pruned tree. Simulation results show that, without any performance loss as justified by analysis, the proposed decoding algorithm can significantly reduce the decoding latency of the polar codes.
Guessing Random Additive Noise Decoding (GRAND) algorithms can decode any moderate redundancy code of any structure, with integrated circuits demonstrating that it is possible to execute GRAND efficiently in hardware. By using GRAND as a component decoder, its remit has been extended to efficiently decode long, high redundancy product codes via the Iterative GRAND (IGRAND) algorithm in the hard detection setting. Here, by leveraging the property of even codebooks to split the noise effect search space into even and odd Hamming weights for the rows and columns in product code decoding, we demonstrate significant reductions in the number of queries IGRAND makes without any degradation in decoding performance. For IGRAND, we establish that the reduction in query numbers can be significantly higher than for the component code alone, resulting in significant efficiency gains. In particular, simulation results show that the average number of guesses reduces by a factor of 4 at a bit flip probability of 10−1.510^{-1.5}10−1.5 when the CRC (64,53)2(64,53)^{2}(64,53)2 codebook is used, without impacting on its decoding accuracy.
In addition to a codeword, error correction decoders that provide blockwise soft output (SO) return an estimate of the likelihood that the decoding is correct. Following Forney, such estimates have traditionally only been possible for list decoders with the approximate soft output being the likelihood that a decoding is correct given it is assumed to be in the list. Recently, it has been established that Guessing Random Additive Noise Decoding (GRAND), Guessing Codeword Decoding (GCD), Ordered Statistics Decoding (OSD), and Successive Cancellation List (SCL) decoding can provide accurate soft output without the need for list decoding. Central to the improvement is the evaluation of an estimate of the likelihood that the correct decoding has not been found. We explore how binary linear codebook constraints can be leveraged to further enhance SO precision. We evaluate performance by adapting a forecasting statistic called the Brier Score. Results indicate that the SO generated by the approach is essentially as accurate as the maximum a posteriori estimate.