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 Information Theory Workshop (ITW)

Locally Constrained Guessing Codeword Decoding of Short Block Codes

Xiangping Zheng, Xiao Ma

Published Nov 24, 2024• 14 citations
Publisher

Abstract

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.

DOI
10.1109/itw61385.2024.10806923

Related papers

Partially Constrained GRAND of Linear Block Codes

Yixin Wang, Jifan Liang, Xiao Ma

This paper is concerned with a search-number-reduced guessing random additive noise decoding (GRAND) algorithm for linear block codes, called partially constrained GRAND (PC-GRAND). In contrast to the original GRAND, which guesses error patterns without constraints, the PC-GRAND guesses only those error patterns satisfying partial constraints of the codes. In particular, the PC-GRAND takes partial rows of the parity-check matrix as constraints for generating candidate error patterns and the remaining rows as checks for validating the candidates. The number of searches can be reduced when the serial list Viterbi algorithm (SLVA) is implemented for searching over a trellis specified by the partial parity-check matrix. This is confirmed by numerical results. Numerical simulations are also provided for comparison with other decoding algorithms. The parallel implementation of PC-GRAND is also presented in this paper.

arXiv:2308.14259•International Conference on Computer and Communication Systems (ICCCS)•Apr 19, 2024•8 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

A Low-Complexity Ordered Statistic Decoding of Short Block Codes

Jifan Liang, Yiwen Wang, Suihua Cai +1 more

This letter is concerned with a generalized ordered statistic decoding (OSD) algorithm, called locally constrained OSD (LC-OSD). Instead of order-$t$reprocessing on the most reliable independent bits, the LC-OSD searches for test error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix. We derive several early stopping criteria that can be used to reduce the number of searches. Numerical results show that the LC-OSD algorithm with the proposed stopping criteria has much lower time complexity than the original OSD but incurs negligible performance loss.

IEEE Communications Letters•Nov 17, 2022•52 citations

Local Constraint-Based Ordered Statistics Decoding for Short Block Codes

Yiwen Wang, Jifan Liang, Xiao Ma

In this paper, we propose a new ordered statistics decoding (OSD) for linear block codes, which is referred to as local constraint-based OSD (LC-OSD). Distinguished from the conventional OSD, which chooses the most reliable basis (MRB) for re-encoding, the LC-OSD chooses an extended MRB on which local constraints are naturally imposed. A list of candidate codewords is then generated by performing a serial list Viterbi algorithm (SLVA) over the trellis specified with the local constraints. To terminate early the SLVA for complexity reduction, we present a simple criterion which monitors the ratio of the bound on the likelihood of the unexplored candidate codewords to the sum of the hard-decision vector’s likelihood and the up-to-date optimal candidate’s likelihood. Simulation results show that the LC-OSD can have a much less number of test patterns than that of the conventional OSD but cause negligible performance loss. Comparisons with other complexity-reduced OSDs are also conducted, showing the advantages of the LC-OSD in terms of complexity.

IEEE Information Theory Workshop (ITW)•Nov 1, 2022•39 citations

A Random Coding Approach to Performance Analysis of the Locally Constrained Ordered Statistic Decoding

Jifan Liang, Xiao Ma

This paper is concerned with the locally constrained ordered statistic decoding (LC-OSD) of binary linear block codes, which is a near maximum-likelihood decoding algorithm. Compared with the conventional OSD, the LC-OSD significantly reduces both the maximum and average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) over a trellis for local constraints on the test error patterns, while the latter is achieved by incorporating tailored early termination criteria. The main objective of this paper is to explore the relationship between the performance of the LC-OSD and decoding parameters, such as the constraint degree and the maximum list size. To this end, we approximate the local parity-check matrix as a totally random matrix and then estimate the performance of the LC-OSD by analyzing the performance of random codes over the channels associated with the most reliable bits (MRBs). The random coding approach enables us to derive an upper bound on the performance and predict the average rank of the transmitted codeword in the list delivered by the LC-OSD. This allows us to balance the constraint degree and the maximum list size for the average (or maximum) time complexity reduction. Simulation results show that the approximation is numerically effective and the random coding approach is powerful. Simulation results also show that the LC-OSD is comparable to other existing decoding algorithms, including soft guessing random additive noise decoding (SGRAND), verifying the efficiency and universality of the LC-OSD.

•May 10, 2023•3 citations

A Random Coding Approach to Performance Analysis of the Locally Constrained Ordered Statistic Decoding

Jifan Liang, Xiao Ma

This paper is concerned with the locally constrained ordered statistic decoding (LC-OSD) of binary linear block codes, which is a near maximum-likelihood decoding algorithm. Compared with the conventional OSD, the LC-OSD significantly reduces both the maximum and average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) over a trellis for local constraints on the test error patterns, while the latter is achieved by incorporating tailored early termination criteria. The main objective of this paper is to explore the relationship between the performance of the LC-OSD and decoding parameters, such as the constraint degree and the maximum list size. To this end, we approximate the local parity-check matrix as a totally random matrix and then estimate the performance of the LC-OSD by analyzing the performance of random codes over the channels associated with the most reliable bits (MRBs). The random coding approach enables us to derive an upper bound on the performance and predict the average rank of the transmitted codeword in the list delivered by the LC-OSD. This allows us to balance the constraint degree and the maximum list size for the average (or maximum) time complexity reduction. Simulation results show that the approximation is numerically effective and the random coding approach is powerful. Simulation results also show that the LC-OSD is comparable to other existing decoding algorithms, including soft guessing random additive noise decoding (SGRAND), verifying the efficiency and universality of the LC-OSD.

•May 11, 2023•0 citations
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.
This paper is concerned with a search-number-reduced guessing random additive noise decoding (GRAND) algorithm for linear block codes, called partially constrained GRAND (PC-GRAND). In contrast to the original GRAND, which guesses error patterns without constraints, the PC-GRAND guesses only those error patterns satisfying partial constraints of the codes. In particular, the PC-GRAND takes partial rows of the parity-check matrix as constraints for generating candidate error patterns and the remaining rows as checks for validating the candidates. The number of searches can be reduced when the serial list Viterbi algorithm (SLVA) is implemented for searching over a trellis specified by the partial parity-check matrix. This is confirmed by numerical results. Numerical simulations are also provided for comparison with other decoding algorithms. The parallel implementation of PC-GRAND is also presented in this paper.
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.
This letter is concerned with a generalized ordered statistic decoding (OSD) algorithm, called locally constrained OSD (LC-OSD). Instead of order-tttreprocessing on the most reliable independent bits, the LC-OSD searches for test error patterns using the serial list Viterbi algorithm (SLVA) over a trellis specified by a local parity-check matrix. We derive several early stopping criteria that can be used to reduce the number of searches. Numerical results show that the LC-OSD algorithm with the proposed stopping criteria has much lower time complexity than the original OSD but incurs negligible performance loss.
In this paper, we propose a new ordered statistics decoding (OSD) for linear block codes, which is referred to as local constraint-based OSD (LC-OSD). Distinguished from the conventional OSD, which chooses the most reliable basis (MRB) for re-encoding, the LC-OSD chooses an extended MRB on which local constraints are naturally imposed. A list of candidate codewords is then generated by performing a serial list Viterbi algorithm (SLVA) over the trellis specified with the local constraints. To terminate early the SLVA for complexity reduction, we present a simple criterion which monitors the ratio of the bound on the likelihood of the unexplored candidate codewords to the sum of the hard-decision vector’s likelihood and the up-to-date optimal candidate’s likelihood. Simulation results show that the LC-OSD can have a much less number of test patterns than that of the conventional OSD but cause negligible performance loss. Comparisons with other complexity-reduced OSDs are also conducted, showing the advantages of the LC-OSD in terms of complexity.
This paper is concerned with the locally constrained ordered statistic decoding (LC-OSD) of binary linear block codes, which is a near maximum-likelihood decoding algorithm. Compared with the conventional OSD, the LC-OSD significantly reduces both the maximum and average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) over a trellis for local constraints on the test error patterns, while the latter is achieved by incorporating tailored early termination criteria. The main objective of this paper is to explore the relationship between the performance of the LC-OSD and decoding parameters, such as the constraint degree and the maximum list size. To this end, we approximate the local parity-check matrix as a totally random matrix and then estimate the performance of the LC-OSD by analyzing the performance of random codes over the channels associated with the most reliable bits (MRBs). The random coding approach enables us to derive an upper bound on the performance and predict the average rank of the transmitted codeword in the list delivered by the LC-OSD. This allows us to balance the constraint degree and the maximum list size for the average (or maximum) time complexity reduction. Simulation results show that the approximation is numerically effective and the random coding approach is powerful. Simulation results also show that the LC-OSD is comparable to other existing decoding algorithms, including soft guessing random additive noise decoding (SGRAND), verifying the efficiency and universality of the LC-OSD.
This paper is concerned with the locally constrained ordered statistic decoding (LC-OSD) of binary linear block codes, which is a near maximum-likelihood decoding algorithm. Compared with the conventional OSD, the LC-OSD significantly reduces both the maximum and average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) over a trellis for local constraints on the test error patterns, while the latter is achieved by incorporating tailored early termination criteria. The main objective of this paper is to explore the relationship between the performance of the LC-OSD and decoding parameters, such as the constraint degree and the maximum list size. To this end, we approximate the local parity-check matrix as a totally random matrix and then estimate the performance of the LC-OSD by analyzing the performance of random codes over the channels associated with the most reliable bits (MRBs). The random coding approach enables us to derive an upper bound on the performance and predict the average rank of the transmitted codeword in the list delivered by the LC-OSD. This allows us to balance the constraint degree and the maximum list size for the average (or maximum) time complexity reduction. Simulation results show that the approximation is numerically effective and the random coding approach is powerful. Simulation results also show that the LC-OSD is comparable to other existing decoding algorithms, including soft guessing random additive noise decoding (SGRAND), verifying the efficiency and universality of the LC-OSD.