# 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  
As for the symbol-level construction of non-binary polar codes over GF(2\({}^{\text{f}}\)), the \(K\) most reliable channels are used to carry the information symbols, and each channel carries one symbol of \(q\) bits. However, at finite block lengths, the capacities of considerably many synthesized channels lie in the range \([1,q-1]\); i.e., they are not bad enough to be frozen but are not good enough to carry \(q\) bits per symbol. Through simulations, we found that they are capable of carrying \(i\)-bit partial symbols for a certain integer \(1\leq i<q\), where \(i\) is determined by the channel capacity of each synthesized channel, as shown in Figure 2. For the 2\({}^{\text{f}}\)-ary erasure channel with erasure probability \(\epsilon\), the erasure probability of each synthesized channel can be calculated by  
\[ \begin{split}&\epsilon\left(W_{N}^{(2)}\right)=\epsilon\left(W_{ N/2}^{(j)}\right)^{2}\\ &\epsilon\left(W_{N}^{(2j-1)}\right)=2\epsilon\left(W_{N/2}^{(j)} \right)-\epsilon\left(W_{N/2}^{(j)}\right)^{2},\end{split}  \tag{12}\]  
with \(\epsilon(W_{1}^{1})=\epsilon\). The channel capacity of each synthesized channel is \(C(W_{N}^{(j)})=q(1-\epsilon(W_{N}^{(j)}))\) bits. As an example, Figure 2 shows the synthesized channel capacities of 16-ary polar codes over the erasure channel, where \(N=32\) and the erasure probability \(\epsilon=0.4\). For a conventional symbol-level construction, we choose \(K\) synthesized channels with the largest capacity \(C(W_{N}^{(j)})\) to carry the information symbols. In order to make full use of every synthesized channel, it is reasonable to make the \(j\)-th channel carry \(i\) bits  
Figure 1: Factor graph of the MR-based polar codes over GF(4). if \(\lfloor C(W_{N}^{(j)})\rfloor\geq i\). We propose a bit-level construction that considers both performance and complexity. Assuming that \(I(j)\) is the number of bits carried over the \(j\)-th channel, we set  
\[I(j)=\lfloor C(W_{N}^{(j)})\rfloor, \tag{13}\]  
where \(\lfloor C\rfloor=\max\{m\in\mathbb{Z}|m\leq C\}\). Then, we sort each synthesized channel in descending order based on \(C(W_{N}^{(j)})\) and generate the information symbol set \(\mathcal{A}_{1}\) for bit-level construction, such that \(|\mathcal{A}_{1}|\geq K\) and  
\[\sum_{j\in\mathcal{A}_{1}}I(j)=Kq(bits). \tag{14}\]  
Note that Equation (14) always holds if \(Kq\) information bits can be transmitted correctly at a given channel state. Although the constructions developed for erasure channels remain functionally valid in AWGN channels, their performance is suboptimal. For enhanced accuracy, we use the CD method [18; 19] to obtain the lower bound of the channel capacity of each synthesized channel. Since the kernel matrix \(\mathbf{G}_{2}\) is different from that in [19], the channel transformations \(W^{-}\) and \(W^{+}\) can be defined by  
\[W^{-}(y_{1},y_{2}\mid v_{1})\triangleq\frac{1}{2^{q}}\sum_{p_{2}=0}^{2^{q}-1}W (y_{1}\mid v_{1}+\alpha_{h}v_{2})W(y_{2}\mid v_{2}), \tag{15}\]  
\[W^{+}(y_{1},y_{2},v_{1}\mid v_{2})\triangleq\frac{1}{2^{q}}W(y_{1}\mid v_{1}+ \alpha_{h}v_{2})W(y_{2}\mid v_{2}). \tag{16}\]  
Let \(W:\mathcal{X}\rightarrow\mathcal{Y}\) be a DMC, and let \(y_{1},y_{2}\) be two output symbols. Define the channel \(Q:\mathcal{X}\rightarrow\mathcal{Y}\setminus\{y_{1},y_{2}\}\cup\{y_{\rm merge}\}\) and the transition probabilities  
\[Q(y|x)=\left\{ \begin{array}{ll}W(y|x),&\text{if }y\in y\setminus\{y_{1},y_{2} \}\\ W(y_{1}|x)+W(y_{2}|x),&\text{if }y=y_{\rm merge}\end{array} \right.. \tag{17}\]  
Figure 2: Synthesized channel capacities of non-binary polar codes over the erasure channel. \(Q\) is obtained from \(W\) by replacing \(\{y_{1},y_{2}\}\) with a new symbol \(y_{merge}\). Then, \(Q\preccurlyeq W\) denote that \(Q\) is degraded with respect to \(W\)[18; 19]. For MR-based non-binary polar codes, we need to optimize the degraded channel by attaining the smallest rate loss over all \(Q\):  
\[\inf_{ \begin{subarray}{c}Q:Q\preccurlyeq W\\ |\text{output}(Q)|\leq\mu\end{subarray} }C(W)-C(Q).