IEEE Information Theory Workshop (ITW)

Order Skipping Ordered Statistics Decoding and its Performance Analysis

Xihao Li, Wenhao Chen, Li Chen, Yuan Li, Huazi Zhang

Published Nov 24, 2024• 3 citations

Abstract

This paper proposes a reduced complexity ordered statistics decoding (OSD) algorithm for linear block codes, the namely order skipping (OS)-OSD algorithm. An approximated correlation distance lower bound (CDLB) is derived by utilizing likelihood of the received symbols over the least reliable positions (LRPs). It enables the assessment of whether the higher-order decoding can yield a more likely codeword estimation. If not, they can be skipped. Error-correction performance of the OSOSD is analyzed. In particular, the decoding error probability of OS-OSD with order one is theoretically characterized. Our simulation results verify that the OS-OSD can achieve a significant complexity reduction over the state-of-the-art OSD without compromising the decoding performance.

DOI: 10.1109/itw61385.2024.10807042

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, 20230 citations

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

Saif E. A. Alnawayseh, Pavel Loskot

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.

EURASIP Journal on Wireless Communications and NetworkingOct 16, 201213 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, 202239 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 LettersFeb 12, 202153 citations

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

Jifan Liang, Xiao Ma

May 10, 20233 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.16709Jan 30, 20246 citations