# A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
## 3 The Threshold-Based OSD Decoding Algorithm  
In this section, we present our threshold-based OSD decoding algorithm, called TH-OSD, for decoding short polar codes. In the OSD-\(L\) algorithm, the ML codeword search is performed by testing all the candidate codewords which differ by no more than \(L\) bits from \(\overline{X}^{N}\) in the first \(K\) bits. The initial codeword \(\overline{X}^{N}\) is constructed from the \(K\) bits in the \(K\) MRIPs of the hard decision of \(Y^{N}\), that is, there should be very few errors in these positions. Since the reliabilities of the positions are in descending order, the bit positions with small indices are less likely to be flipped, and the bit positions with large indices are more likely to be flipped during the decoding process. The monotonicity of reliabilities helps to reduce the number of candidate codewords. Further, it is intuitive that the minimal \(f\) value decreases as SNR increases. The codeword with minimal \(f\) value, which is the final decoded codeword, likely emerges during the early stage of the decoding process. Thus, setting a threshold \(f_{th}\) for \(f\) and stopping the decoding process immediately once it encounters a codeword with an \(f\) value less than \(f_{th}\), reduces the number of codewords tested. Larger \(f_{th}\) values cause fewer codewords to be tested, but at the cost of higher WER. There is a tradeoff between WER and complexity when using this algorithm. For block codes up to length 128 with rates higher than 0.5, an order of \(\lfloor d_{min}/4\rfloor\) is sufficient to achieve the same error performance as MLD in practice [11]. The minimum codeword distance is 8 for polar codes with length 64 or 128 and rate 0.5 (cf. Lemma 3 [14]), thus flipping up to 2 bits is adequate for short codes. Thus, we use OSD-2 in our algorithm. Our algorithm performs the following steps. 1. Sort \(y_{1},y_{2},\cdots,y_{N}\) into the set \(y^{\prime}_{1},y^{\prime}_{2},\cdots,y^{\prime}_{N}\) based on their absolute values in descending order. The corresponding permutation is denoted by \(\pi_{1}\). We then reorder the columns of \(G\) using \(\pi_{1}\) to obtain a new matrix \(G_{1}\). 2. Use Gaussian elimination to obtain the reduced row echelon form of \(G_{1}\), denoted as matrix \(T\). Perform a column swap to move the \(K\) columns with pivot elements to the front of the matrix, denoted as \(G_{2}\), (\(\pi_{2}\) denotes the permutations of the column swapping process.) Next, reorder \(y^{\prime}_{1},y^{\prime}_{2},\cdots,y^{\prime}_{N}\) using \(\pi_{2}\) to obtain \(y^{\prime}_{1},y^{\prime}_{2},\cdots,y^{\prime}_{N}\). There is a one-to-one mapping between the original \(X^{N}\) and \(X^{\prime\prime N}\), which can be written as \(X^{N}=\pi_{1}^{-1}\left(\pi_{2}^{-1}\left(X^{\prime\prime N}\right)\right)\). Thus, decoding \(X^{\prime\prime N}\) is equivalent to decoding \(X^{N}\). 3. Use the first \(K\) bits of hard decision \(\overline{X}^{N}\) of \(Y^{\prime\prime N}\) as the initial message sequence, and use \(f\) of the codeword \(\overline{X}^{K}_{1}G_{2}\) as the current minimal \(f\) value, denoted as \(f_{min}\). Then, perform the OSD-2 flipping process by the pseudo code described in Algorithm 1.