# A Low-Complexity Ordered Statistics Decoding Algorithm for Short Polar Codes
## Appendix B Upper-Bound on the Gap  
In the following derivations, we assume that an all-zero codeword is sent and that \((y_{1},y_{2},\cdots,y_{N})\) denotes the received vector. We begin with the gap and make progressive simplifications. \[ \begin{split} P_{Gap}(f_{th})&\leq\Pr\left\{ \overrightarrow{0}=\operatorname*{arg\,min}_{C\in L_{c}}f(C),|N^{-}_{MRIP}| \leq i,\exists C\
eq\overrightarrow{0},f(C)\leq f_{th},C\text{ is met before } \overrightarrow{0}\right\}\\ &\leq\Pr\left\{\overrightarrow{0}=\operatorname*{arg\,min}_{C \in L_{c}}f(C),|N^{-}_{MRIP}|\leq i,\exists C\
eq\overrightarrow{0},f(C)\leq f _{th}\right\}\\ &=\sum_{d=0}^{N-K-d_{H}+1}\mathrm{P}_{D}(d)\Pr\left\{|N^{-}_{MRIP }|\leq i,\exists C\
eq\overrightarrow{0},f(C)\leq f_{th}|D=d\right\}\\ &=\sum_{d=0}^{N-K-d_{H}+1}\mathrm{P}_{D}(d)A(d,f_{th})\end{split}  \tag{10}\]  
where \(|N^{-}_{MRIP}|\) denotes the number of negative values in the MRIPs, and \(d_{H}\) is the minimum codeword weight. \(K+d\) is the index of the last MRIP. \(L_{c}\) is the candidate codeword list. \(A(d,f_{th})\) can be expressed and further bounded as follows:  
\[ \begin{split} A(d,f_{th})&=\Pr\left\{|N^{-}_{MRIP}| \leq i,\exists C\
eq\overrightarrow{0},f(C)\leq f_{th}|D=d\right\}\\ &\leq\sum_{j=1}^{i}\binom{K}{j}\Pr\left\{|N^{-}_{MRIP}|=j,\exists C \
eq\overrightarrow{0},f(C)\leq f_{th}|D=d\right\}\\ &=\sum_{j=1}^{i}\binom{K}{j}\int_{0}^{f_{th}}\Pr\left\{|N^{-}_{ MRIP}|=j,\exists C\
eq\overrightarrow{0},f(C)\leq f_{th},y_{K+d}=x|D=d \right\}\mathrm{d}x\\ &=\sum_{j=1}^{i}\binom{K}{j}\int_{0}^{f_{th}}B_{j,d}(x)\mathrm{d }x\end{split}  \tag{11}\]  
We used union bound in the second step in Equation (11). \(B_{j,d}(x)\) is the probability density function of the event that a codeword chosen from the candidate list has a discrepancy less than \(f_{th}\) while \(j\) out of the \(K\) MRIPs are negative and the \((K+d)\)th received value is \(x\). \(B_{j,d}(x)\) can be further bounded by the following equations:  
\[ \begin{split} B_{j,d}(x)\leq&\frac{N!}{(K+d-1)!(N-K- d)!}\mathrm{T}(x)^{K+d-1}\left(1-\mathrm{T}(x)\right)^{j}\left(1-\mathrm{F}_{|y|} (x)\right)^{K+d-1}\\ &\cdot\mathrm{F}_{|y|}(x)^{N-K-d}\frac{1}{\sqrt{2\pi}\sigma}e^{- \frac{(x-1)^{2}}{2\sigma^{2}}}\mathrm{G}_{\sigma,f_{th}}(x)\end{split}  \tag{12}\]  
where \(\mathrm{T}(x)\) represents the probability that a Gaussian random variable \(y\sim N(1,\sigma^{2})\) is positive under the condition \(|y|\geq x\); \(\mathrm{F}_{|y|}\) is the CDF of random variable \(|y|\); and \(\mathrm{G}_{\sigma,f_{th}}(x)\) represents the probability that a codeword has a discrepancy less than \(f_{th}\) under the condition \(y+K+d=x\) and \(j\) out of the \(K\) MRIPs are negative. Since the non-zero codeword we considered here flips at least one MRIP, and its weight is at least \(d_{H}\), \(\mathrm{G}_{\sigma,f_{th}}(x)\) can be approximately bounded by  
\[\mathrm{G}_{\sigma,f_{th}}(x)\leq\mathrm{Q}\left(\frac{\mu^{\prime}(x)-f_{th}+x }{\sigma^{\prime}(x)}\right) \tag{13}\]where \(\mu^{\prime}(x)\) and \(\sigma^{\prime}(x)\) are the mean and variance of the portion of the discrepancy of a codeword \(C\) (\(C\) has one \"\(1\)\" in the first \((K+d)\) positions and \((d_{H}-1)\) \"\(1\)\"s in the remaining \((N-K-d)\) positions) contributed by the last \((N-K-d)\) positions.