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:2401.16709

A Random Coding Approach to Performance Analysis of the Ordered Statistic Decoding with Local Constraints

Jifan Liang, Xiao Ma

Published Jan 30, 2024• 9 citations
arXivHTMLPDF

Abstract

This paper is concerned with the ordered statistic decoding with local constraints (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 the average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) or a two-way flipping pattern tree (FPT) algorithm with 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 with a saddlepoint approach 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 by random coding approach is numerically effective and powerful. Simulation results also show that the RS codes decoded by the LC-OSD can approach the random coding union (RCU) bounds, verifying the efficiency and universality of the LC-OSD.

DOI
10.48550/arxiv.2401.16709

Related papers

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

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

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

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

Gaussian Elimination-Free OSD via Pre-Stored Matrices

Yiwen Wang, Qianfan Wang, X B Zheng +2 more

This paper proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by utilizing multiple pre-stored systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We also propose a saddlepointbased numerical method to evaluate a tight upper bound of the FER. Furthermore, leveraging our saddlepoint approximation method, we address two critical challenges to optimize the proposed decoding algorithms: 1) Matrix-selection criteria are evaluated across sum-reliability, max-min-reliability and coveragemaximization rules. We demonstrate that the introduced sumreliability rule yields the best performance among the considered methods, and exhibits the smallest gap to the ML performance; 2) Number of pre-stored matrices is set by our saddlepoint analysis, which determines the minimal number of SGMs needed to approach the ML performance. Numerical results and analysis demonstrate that the proposed algorithms are effective across various coding schemes including random linear codes and BCH codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for random linear codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD.

IEEE Wireless Communications and Networking Conference•Apr 13, 2026•1 citation
This paper is concerned with the ordered statistic decoding with local constraints (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 the average number of searches. The former is achieved by performing the serial list Viterbi algorithm (SLVA) or a two-way flipping pattern tree (FPT) algorithm with 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 with a saddlepoint approach 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 by random coding approach is numerically effective and powerful. Simulation results also show that the RS codes decoded by the LC-OSD can approach the random coding union (RCU) bounds, 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.
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.
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 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.
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 proposes an improved ordered statistics decoding (OSD) algorithm, termed OSD with pre-stored systematic matrices (PSM-OSD), which completely avoids online Gaussian elimination by utilizing multiple pre-stored systematic generator matrices (SGMs) and selecting one based on the received sequence for decoding. To further improve the search efficiency, the local-constraint mechanism is combined with the PSM-OSD, resulting in the LC-PSM-OSD. We also propose a saddlepointbased numerical method to evaluate a tight upper bound of the FER. Furthermore, leveraging our saddlepoint approximation method, we address two critical challenges to optimize the proposed decoding algorithms: 1) Matrix-selection criteria are evaluated across sum-reliability, max-min-reliability and coveragemaximization rules. We demonstrate that the introduced sumreliability rule yields the best performance among the considered methods, and exhibits the smallest gap to the ML performance; 2) Number of pre-stored matrices is set by our saddlepoint analysis, which determines the minimal number of SGMs needed to approach the ML performance. Numerical results and analysis demonstrate that the proposed algorithms are effective across various coding schemes including random linear codes and BCH codes. Moreover, the results show that the proposed LC-PSM-OSD can closely approach the finite-length capacity over almost all code rates for random linear codes, and outperforms conventional OSD, guessing codeword decoding (GCD), and LC-GCD.