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

EURASIP Journal on Wireless Communications and Networking

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

Saif E. A. Alnawayseh, Pavel Loskot

Published Oct 16, 2012• 13 citations
Publisher

Abstract

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.

DOI
10.1186/1687-1499-2012-314

Related papers

Order Statistics Based List Decoding Techniques for Linear Binary Block Codes

Saif E. A. Alnawayseh, Pavel Loskot

The order statistics based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of the list of the test error patterns is considered. The original order statistics decoding is generalized by assuming segmentation of the most reliable independent positions of the received bits. The segmentation is shown to overcome several drawbacks of the original order statistics decoding. The complexity of the order 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 order statistics decoding in terms of both the bit error rate performance as well as the decoding complexity.

arXiv:1101.5025•Jan 26, 2011•0 citations

Probability-Based Ordered-Statistics Decoding for Short Block Codes

Chentao Yue, Mahyar Shirvanimoghaddam, Giyoon Park +3 more

This letter proposes an efficient probability-based ordered-statistics decoding (PB-OSD) algorithm for short block-length codes. In PB-OSD, we derive two probabilistic measures on the codeword estimates and test error patterns, respectively referred to as the success probability and promising probability. Based on these probabilities, a stopping criterion and a discarding criterion are developed to reduce the number of test error patterns and limit the decoding complexity. To further reduce the complexity, we propose a tree-based search strategy to find the most likely test error patterns in reprocessing stage of the OSD algorithm. Simulation results show that PB-OSD significantly reduces the decoding complexity under the same error performance, compared to the original OSD algorithm.

IEEE Communications Letters•Feb 12, 2021•53 citations

Segmentation-Discarding Ordered-Statistic Decoding for Linear Block Codes

Chentao Yue, Mahyar Shirvanimoghaddam, Yonghui Li +1 more

In this paper, we propose an efficient reliability based segmentation-discarding decoding (SDD) algorithm for short block-length codes. A novel segmentation- discarding technique is proposed along with the stopping rule to significantly reduce the decoding complexity without a significant performance degradation compared to ordered statistics decoding (OSD). In the proposed decoder, the list of test error patterns (TEPs) is divided into several segments according to carefully selected boundaries and every segment is checked separately during the reprocessing stage. Decoding is performed under the constraint of the discarding rule and stopping rule. Simulations results for different codes show that our proposed algorithm can significantly reduce the decoding complexity compared to the existing OSD algorithms in literature.

arXiv:1901.02603•Globecom•Dec 1, 2019•42 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

Box and match soft decision decoding of linear block codes with iterative information set reduction

M.P.C. Fossorier, A. Valembois

The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.

IEEE Information Theory Workshop (ITW)•Aug 27, 2003•6 citations

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

Jifan Liang, Xiao Ma

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.

arXiv:2401.16709•Jan 30, 2024•6 citations
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.
The order statistics based list decoding techniques for linear binary block codes of small to medium block length are investigated. The construction of the list of the test error patterns is considered. The original order statistics decoding is generalized by assuming segmentation of the most reliable independent positions of the received bits. The segmentation is shown to overcome several drawbacks of the original order statistics decoding. The complexity of the order 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 order statistics decoding in terms of both the bit error rate performance as well as the decoding complexity.
This letter proposes an efficient probability-based ordered-statistics decoding (PB-OSD) algorithm for short block-length codes. In PB-OSD, we derive two probabilistic measures on the codeword estimates and test error patterns, respectively referred to as the success probability and promising probability. Based on these probabilities, a stopping criterion and a discarding criterion are developed to reduce the number of test error patterns and limit the decoding complexity. To further reduce the complexity, we propose a tree-based search strategy to find the most likely test error patterns in reprocessing stage of the OSD algorithm. Simulation results show that PB-OSD significantly reduces the decoding complexity under the same error performance, compared to the original OSD algorithm.
In this paper, we propose an efficient reliability based segmentation-discarding decoding (SDD) algorithm for short block-length codes. A novel segmentation- discarding technique is proposed along with the stopping rule to significantly reduce the decoding complexity without a significant performance degradation compared to ordered statistics decoding (OSD). In the proposed decoder, the list of test error patterns (TEPs) is divided into several segments according to carefully selected boundaries and every segment is checked separately during the reprocessing stage. Decoding is performed under the constraint of the discarding rule and stopping rule. Simulations results for different codes show that our proposed algorithm can significantly reduce the decoding complexity compared to the existing OSD algorithms in literature.
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.
The order statistic decoding (OSD) algorithm is a probabilistic list decoding algorithm which allows to achieve practically optimum soft decision decoding of binary linear block codes of length up to 128. Recently, matching techniques were applied to the OSD algorithm to reduce both the worst case and average complexities of decoding at the expense of memory. The corresponding box-and-match algorithm (BMA) allows to achieve near optimum decoding of codes of length up to 192. In this work, we investigate the application of iterative information set reduction to the BMA, which provides further refinements in the trade-offs between error performance and decoding complexity.
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.