# A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
## 1 Introduction  
Since polar coding's introduction by [PERSON] in 2009, the method has attracted a considerable amount of research attention as the first theoretically proven method for achieving channel capacity. In his pioneering paper, [PERSON] proposed a decoding algorithm called \"successive cancellation\" (SC) to prove the capacity-achieving property of polar codes [1]. The SC decoding algorithm uses the recursive structure of polar codes to achieve a complexity of \(O(N\log N)\), where \(N\) is the codeword length. However, the performance of polar codes with a finite code length is unsatisfactory with the suboptimal SC decoding algorithm. Several alternative decoding methods have been proposed to improve performance. Among these, the list SC decoding method (SCL) [2] and the stack SC decoding method (SCS) [3] show the most significant improvement in the word error rate (WER) with a complexity of \(O(LN\log N)\), where \(L\) is the SCL list size or the SCS stack depth. Unlike SC, which keeps only the most likely path causing error propagation once a bit is decoded incorrectly, SCL and SCS each use a list to store the most likely paths for avoiding error propagation, which improves performance. [PERSON] et al. [4] proposed a log-likelihood ratio (LLR)-based SCL decoding algorithm to simplify the original SCL method. Unlike the original SCL method, which tracks a pair of likelihoods for a decoding path, the LLR-based SCL uses only LLRs to compute a path-metric for a decoding path. [PERSON] et al. [5] proposed another performance enhancement for SCL/SCS using cyclic redundancy check (CRC) bits to identify the correct path.  
As noted previously, SC decoding is suboptimal and performs unsatisfactorily when used with short polar codes. Maximum likelihood decoding (MLD) achieves optimal error correction performancebut with exponential complexity that is unacceptable in most cases. Researchers have investigated MLD further to avoid the exponential complexity. [PERSON] et al. [6] proposed a soft decoding algorithm for linear block codes by generating a set of candidate codewords containing the maximum likelihood (ML) codeword and improved it in [7]. [PERSON] et al. [8] proposed a two-stage decoding algorithm with a similar idea. [PERSON] et al. [9] proposed a sphere decoding algorithm that searches for the ML codeword with complexity \(O(N^{3})\). [PERSON] et al. [10] proposed an ordered statistics decoding (OSD)-based algorithm, with a complexity of \(O(NK^{2})\), using a threshold for the reliability of every received symbol to reduce the number of tested codewords.  
The OSD method itself is a type of most reliable independent position (MRIP) soft-decision decoding method [11]. The MRIP-based decoding methods are usually efficient for short codes. In this paper, we propose a threshold-based OSD decoding algorithm by setting a threshold on the discrepancy value of a codeword to reduce complexity while maintaining a WER close to MLD for short liner block codes and apply this algorithm on short polar codes. Simulation results show performance is consistent with our theoretical analysis. Especially in low signal-to-noise ratio (SNR) environments, our proposed algorithm reduces a large proportion of tested codewords when compared with the original OSD algorithm at the price of a slight WER performance loss. Applying list decoding further narrows this performance gap.  
We organize our paper as follows: Section 2 introduces some concepts relating to polar codes, codeword likelihood, and the OSD decoding algorithm. In Section 3, we describe our proposed algorithm. Section 4 presents a method to determine the threshold value. Section 5 presents analyses of performance and complexity. Section 6 describes some methods to improve the WER performance of our proposed algorithm. Section 7 presents an extension of the proposed algorithm in longer polar codes. Section 8 shows our simulation results. Finally, Section 9 gives our conclusions.