# Bit-Level Construction for Multiplicative-Repetition-Based Non-Binary Polar Codes +
## 3 Bit-Level Construction for Non-Binary Polar Codes
### Capacity-Based Bit-Level Construction
The set of block error events under SC decoding is defined as

\[\mathcal{E}\triangleq\Big{\{}\Big{(}v_{1}^{N},y_{1}^{N}\Big{)}:\vartheta_{ \mathcal{A}}\Big{(}v_{1}^{N},y_{1}^{N}\Big{)}\
eq v_{\mathcal{A}}\Big{\}}. \tag{24}\]

Let \(P_{e}(N,K,\mathcal{A})=P(\mathcal{E})\) denote the BLER of the \((N,K,\mathcal{A})\) polar code. The set of block error events can be enlarged as \(\mathcal{E}\subset\bigcup_{j\in\mathcal{A}}\mathcal{E}_{j}\), where the single-symbol error event \(\mathcal{E}_{j}\) is defined as

\[ \begin{split}\mathcal{E}_{j}\triangleq&\Big{\{} \Big{(}v_{1}^{N},y_{1}^{N}\Big{)}:W_{N}^{(j)}\Big{(}y_{1}^{N},v_{1}^{j-1}\mid v _{j}\Big{)}\\ &\leq W_{N}^{(j)}\Big{(}y_{1}^{N},v_{1}^{j-1}\mid v_{j}\Big{)},v _{j}\
eq v_{j}\Big{\}}.\end{split}  \tag{25}\] \begin{table}
\begin{tabular}{c c c c c c c c} \hline \(\mathbf{Q_{8}^{6}(y\mid v^{\prime})}\) & \(\boldsymbol{v^{\prime}=0}\) & \(\boldsymbol{v^{\prime}=1}\) & \(\boldsymbol{v^{\prime}=2}\) & \(\boldsymbol{v^{\prime}=3}\) & \(\boldsymbol{v^{\prime}=4}\) & \(\boldsymbol{v^{\prime}=5}\) & \(\boldsymbol{v^{\prime}=6}\) & \(\boldsymbol{v^{\prime}=7}\) \\ \hline \(y=y_{3}\) & 0.03 & 0.0309 & 0.8362 & 0.026 & 0.014 & 0.0179 & 0.0298 & 0.0152 \\ \hline \(y=y_{4}\) & 0.018 & 0.0139 & 0.0156 & 0.0303 & 0.0299 & 0.0302 & 0.0266 & 0.8355 \\ \hline \(y=y_{5}\) & 0.014 & 0.018 & 0.03 & 0.015 & 0.029 & 0.03 & 0.837 & 0.027 \\ \hline \(y=y_{6}\) & 0.016 & 0.0302 & 0.018 & 0.014 & 0.0269 & 0.8349 & 0.03 & 0.03 \\ \hline \(y=y_{7}\) & 0.026 & 0.8355 & 0.03 & 0.031 & 0.016 & 0.03 & 0.0175 & 0.014 \\ \hline \(y=y_{8}\) & 0.0303 & 0.0152 & 0.0135 & 0.0183 & 0.8344 & 0.0277 & 0.03 & 0.0306 \\ \hline \end{tabular}
\end{table} 
Table 1: _Cont._

Figure 3: Synthesized channel capacities of non-binary polar codes over the AWGN channel. Let \(P_{e,i}(j)\) denote the symbol error probability when the \(j\)-th synthesized channel carries \(i\) bits. Obviously, \(P_{e,i_{1}}(j)\leq P_{e,i_{2}}(j)\) for any \(i_{1}<i_{2}\) and \(0\leq j<N\). \(P_{e,i}(j)\) can be easily obtained by the MC method and the CD method. For the CD method, a DMC is obtained from the synthesized channel \(Q_{N}^{(j)}\), and \(P_{e,i}(j)\) can be calculated by

\[P_{e,i}(j)=\frac{1}{2^{i}}\sum_{y\in\mathcal{Y}}\sum_{ \begin{subarray}{c}v=0,\\ v\
eq v_{\max}\end{subarray} }^{2^{i}-1}Q_{N}^{(j)}(y\mid v), \tag{26}\]

where

\[v_{\max}=\operatorname*{arg\,max}_{v\in\{0,1,\ldots 2^{i}-1\}}Q_{N}^{(j)}(y\mid v). \tag{27}\]

The BLER for bit-level construction under the SC decoding can be upper bounded as

\[P_{e}(N,K,\mathcal{A}_{1})=P(\mathcal{E})\leq\sum_{j\in\mathcal{A}_{1}}P( \mathcal{E}_{j})\approx\sum_{j\in\mathcal{A}_{1}}P_{e,I(j)}(j), \tag{28}\]

subject to (14). Our scheme aims to obtain an optimal information symbol set \(\mathcal{A}_{1}\) and number of carried bits \(I(j)\) to minimize the upper bound of the total probability \(P_{e}\). To address this problem, we compute a probability \(P_{b}(s)\), which represents the contribution to the upper bound of the error probability when selecting the \(s\)-th bit, namely \(\mathcal{A}_{1}\). \[P_{b}(s)=\frac{P_{e,i+1}(j)-P_{e,i}(j)}{1-P_{e,i}(j)} \tag{29}\]

where \(s=(j-1)q+i+1\), \(1\leq s\leq Nq\), and \(P_{e,0}(j)=0\). In the case of \(0<i<q\), \(P_{b}(s)\) is a conditional probability \(P(\hat{u}_{s}\
eq u_{s}|\hat{u}_{s-1}=u_{s-1},\ldots,\hat{u}_{s-i}=u_{s-i})\) when the \(j\)-th synthesized channel carries \(i+1\) bits. Consequently, the BLER under SC decoding can be further upper bounded as

\[P(\mathcal{E})\leq\sum_{j\in\mathcal{A}_{1}}P_{e,I(j)}(j)=\sum_{j\in\mathcal{ A}_{1}}\prod_{s\in\mathcal{B}}P_{b}(s)=P_{UB}, \tag{30}\]

where \(\mathcal{B}\) is the information bit set and \(|\mathcal{B}|=Kq\), and \(P_{UB}\) is the BLER upper bound under the SC decoding. We can use the upper bound of the error probability as a metric to generate \(\mathcal{A}_{1}\) and \(\mathcal{B}\) by choosing \(Kq\) bit indexes with the smallest \(P_{b}(s)\).