# A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
## 4 A Threshold Determination Method  
In this section, we propose a method to determine the threshold used in our TH-OSD algorithm. We first analyze the probability distribution of \(f\) values obtained from the OSD decoding procedure. Without loss of generality, we assume an all-zero codeword is transmitted. After BPSK modulation and transmission over an AWGN channel, the received sequence \(Y^{N}\) follows a joint Gaussian distribution with each element \(y_{i}\sim N(1,\sigma^{2}),i=1,2,\cdots,N\). Since it is hard to derive the actual probability distribution of \(f\), we instead derive the probability distribution of \(f\) using the flipping method to obtain the all-zero codeword. We denote this value as \(f_{0}\) and express it as  
\[f_{0}=\sum_{i=1}^{N}r_{i} \tag{3}\]  
where \(r_{i}\) is the value that the \(i\)th received bit contributes to the total discrepancy value \(f\). The relation between \(r_{i}\) and \(y_{i}\) is expressed as  
\[r_{i}=\left\{ \begin{aligned} -y_{i},& y_{i}<0\\ 0,& y_{i}\geq 0\end{aligned} \right. \tag{4}\]  
where \(r_{i},i=1,2,\cdots,N\) are independent and identically distributed (IID) random variables. Thus, their sum, \(f_{0}\), has an expectation \(\sum_{i=1}^{N}\mathrm{E}(r_{i})=N\cdot\mathrm{E}(r)\) and a variance \(\sum_{i=1}^{N}\mathrm{Var}(r_{i})=N\cdot\mathrm{Var}(r)\) where \(\mathrm{E}(r)\) and \(\mathrm{Var}(r)\) are the expectation and variance of \(r_{i},i=1,2,\cdots,N\), respectively. Using Equation (4) and the fact that \(y_{i}\sim N(1,\sigma^{2})\), we can determine \(\mathrm{E}(r)\) and \(\mathrm{Var}(r)\) using a standard calculation. Following the full derivation (cf. Appendix A), we obtain the final results:  
\[\mathrm{E}(f_{0})=N\left(-\mathrm{Q}\left(\frac{1}{\sigma}\right)+\frac{\sigma }{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^{2}}}\right) \tag{5}\]  
\[\mathrm{Var}(f_{0})=N\left((1+\sigma^{2})\mathrm{Q}\left(\frac{1}{\sigma} \right)-\frac{\sigma}{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^{2}}}-\left(\mathrm{Q} \left(\frac{1}{\sigma}\right)-\frac{\sigma}{\sqrt{2\pi}}e^{-\frac{1}{2\sigma^ {2}}}\right)^{2}\right) \tag{6}\]  
where \(\mathrm{Q}(x)\) is the tail probability of the standard normal distribution \(N(0,1)\). The relationship between \(f\) and \(f_{0}\) merits further analysis. If the OSD decoding produces the correct codeword, then \(f=f_{0}\); otherwise \(f<f_{0}\). Thus, normally the cumulative distribution function (CDF) curve of \(f\) will be located slightly to the left of the CDF curve of \(f_{0}\). When the SNR increases, the two distribution curves will gradually move closer to each other. According to the central limit theorem (CLT), the distribution \(\mathrm{F}(f_{0})\) converges to a normal distribution with the same mean and variance. In most scenarios, a codeword length of 30 (\(N=30\)) is sufficient for using the CLT approximation [15]. Thus, it is reasonable to use a normal distribution to approximate \(\mathrm{F}(f_{0})\) since the codewords in question have a minimum length of 64. This phenomenon can also be verified by simulation. Figure 1 shows the comparison between the empirical CDF curve of \(f\) using the OSD-2 method and the Gaussian approximation of \(f_{0}\) for various SNR values. The figure shows that the Gaussian approximations are close to and located slightly to the right of the empirical CDF curve. This observation is also consistent with our analysis. Having the approximate distribution of \(f\), our threshold determination method works as follows. After choosing a percentage value \(p_{th},0\leq p_{th}\leq 1\), we set threshold according to Equation (7), meaning that the actual \(f\) will be less than \(f_{th}\) with a probability greater than \(p_{th}\). \[f_{th}(\sigma,p_{th})=\mathrm{Q}^{-1}(1-p_{th})\cdot\sqrt{\mathrm{Var}(f_{0}) }+\mathrm{E}(f_{0}) \tag{7}\]  
If the actual \(f\) is greater than \(f_{th}\), TH-OSD and OSD produce the same decoding result. As \(p_{th}\) increases, the threshold \(f_{th}\) decreases, and, as \(p_{th}\) decreases, \(f_{th}\) increases.