# A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
## 5 Performance and Complexity Analysis  
### WER Performance Analysis  
It is clear that the threshold in TH-OSD controls the decoding error correcting performance and the decoding time. When the threshold approaches 0 (i.e., \(p_{th}\) tends to 0), TH-OSD's error performance and decoding complexity approaches OSD's. When the threshold approaches infinity (i.e., \(p_{th}\) tends to 1), TH-OSD's error performance and decoding complexity approaches the performance of OSD-0,  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline
**SNR(dB)** & **1** & **1.5** & **2** & **2.5** & **3** & **3.5** & **4** & **4.5** \\ \hline \(f_{th}\) & 5.1573 & 4.1801 & 3.3512 & 2.6543 & 2.0743 & 1.5971 & 1.2096 & 0.8995 \\ \hline \end{tabular}
\end{table}
Table 1: Threshold values when \(p_{th}=0.7\) and codeword length \(N=64\).  
Figure 1: The empirical CDF of \(f\) and the Gaussian approximation for different SNR values with codeword length \(N=64\).  
which takes the hard decision of the \(K\) MRIPs and treats the corresponding codeword as the decoding result. Thus, the performance curve of TH-OSD lies between the curves of OSD-0 and OSD-\(i\). However, the error correcting performance curve of OSD-0 is quite a loose upper-bound of the performance of TH-OSD. In the following, we derive a tighter upper-bound of the WER performance of TH-OSD.  
However, assuming an all-zero codeword, we analyze the events where TH-OSD and OSD give different codewords. These decoding events fall into three categories. The first category consists of the events when the OSD decoding result is incorrect. The second category consists of the events when the OSD decoding result is correct but with the discrepancy value exceeding the threshold. The last category consists of the events when the OSD decoding result is correct but with the discrepancy value of the decoded codeword less than the threshold. The probability of the events in the first category (correct TH-OSD value) is negligible. In any event from the second category, TH-OSD gives the same codeword as OSD does since every tested codeword will have a discrepancy value larger than the given threshold. All the events contributing to the error performance gap between TH-OSD and OSD lie in the third category. If an event in which TH-OSD gives an incorrect codeword but OSD gives the correct codeword occurs, then there must exist a codeword in the candidate codeword list whose discrepancy value is smaller than the given threshold. This codeword has to be encountered before the all-zero codeword. In view of these contributing events, we can express the gap as  
\[Gap=\left\{\overrightarrow{0}=\underset{C\in L_{c}}{\arg\min}f(C),\exists C \
eq\overrightarrow{0},f(C)\leq f_{th},C\text{ is met before } \overrightarrow{0}\right\}, \tag{8}\]  
where \(L_{c}\) denotes the list of the candidate codewords, and \(\overrightarrow{0}\) denotes the all-zero codeword.  
Finally, we establish the upper-bound of the probability of the events in Equation (8). After the derivations (found in the Appendix B), we obtain  
\[P_{Gap}(f_{th})\leq\sum_{d=0}^{N-K-d_{H}+1}P_{D}(d)A(d,f_{th}), \tag{9}\]  
where \(d_{H}\) is the minimum codeword weight, \(d\) indicates the \(K\)th MRIP found at index \(K+d\), and \(P_{D}(d)\) is the probability of \(D=d\) (obtained via Monte Carlo simulations). The definition of \(A(d,f_{th})\) can be found in Appendix B.