# 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
for\(i=1:L\)do
2:for\(j=0:2^{q}-1\)do \(d[i][j]\gets W(y_{i}\mid j)\)
4:endfor
5:endfor
6:\(\mathcal{Y}^{\prime}\leftarrow\mathcal{Y}\) while\(|\mathcal{Y}^{\prime}|>\mu\)do
7:\(\{y_{1},y_{2}\}\leftarrow\texttt{GetOutputwithMinDeltaC}(Q)\) for\(j=0:2^{q}-1\)do
8:\(d[y_{\text{merge}}][j]=d[y_{1}][j]+d[y_{2}][j]\) endfor
9:\(\mathcal{Y}^{\prime}\leftarrow y_{\text{merge}}\) \(\mathcal{Y}^{\prime}\leftarrow\mathcal{Y}^{\prime}\setminus\{y_{1},y_{2}\}\)
10:endwhile
11: Construct \(Q\) according to the probabilities. 12:return\(Q\)
```  
**Algorithm 2** The degrade function  
_Example:_ Given an \(N=8,K=4\), MR-based non-binary polar code over GF(8) and the quantization level \(\mu=8\). Table 1 lists the transition probabilities of the 6-th synthesized channel \(Q_{8}^{6}(y\mid v^{\prime})\). Assuming that \(C(Q_{8}^{6})=2\) bits, there are three patterns for the 6-th channel to carry two information bits, \((1,1,0),(1,0,1)\), and \((0,1,1)\). When \(\mathbf{T}^{(6)}=(1,1,0)\), \(v^{\prime}\in\{0,1,2,3\}\), according to Equations (22) and (23), we can calculate that \(P_{(1,1,0)}=0.134275\). Similarly, when \(\mathbf{T}^{(6)}=(1,0,1)\), \(v^{\prime}\in\{0,1,4,5\}\), \(P_{(1,0,1)}=0.1346\), and when \(\mathbf{T}^{(6)}=\{0,1,1\}\), \(v^{\prime}\in\{4,5,6,7\}\), \(P_{(0,1,1)}=0.13455\). Therefore, the 18-th and 19-th bits are selected as information bits. Figure 3 shows the synthesized channel capacities of 16-ary polar codes over the AWGN channel with binary phase shift keying (BPSK) modulation, where \(N=32\), the signal-to-noise ratio (SNR) is 3.0 dB, and \(\mu=32\). Since the sum capacities of each synthesized channel in Figures 2 and 3 are equal, we can directly compare the differences in their symbol channel capacities. Obviously, the two approaches produce different results. The capacity calculation under the erasure channel is simple but not precise. On the contrary, the CD construction is more complex but yields more accurate results. ```
0: The transition probability \(Q_{N}^{(j)}(y|v)\) of \(j\)-th synthesized channel, where \(y\in\mathcal{Y},|\mathcal{Y}|=\mu,v\in\mathrm{GF}(2^{q})\), \(j\)-th synthesized channel carried information bits \(i\). \(\mathrm{T}^{(j)}\). \(\mathrm{P}_{T}\gets 0\) \(\mathrm{P}_{max}\gets 0\) \(\mathrm{P}_{min}\gets 1\) for\(k=0:2^{q}-1\)do if\(\sum_{m=1}^{q}b_{k,m}=i\)then
6:\(\mathrm{P}_{T}\gets 0\) for\(y=y_{1}:y_{\mu}\)do \(\mathrm{P}_{\mathrm{max}}\gets 0\) for\(v=0:2^{q}-1\)do if\(IsVlegal(v,k)=1\)then if\(Q_{N}^{(j)}(y|v)>P_{\mathrm{max}}\)then
12:\(\mathrm{P}_{T}\gets\mathrm{P}_{T}+P_{\mathrm{max}}\) \(\mathrm{P}_{\mathrm{max}}=Q_{N}^{(j)}(y\mid v)\) else \(\mathrm{P}_{T}\gets\mathrm{P}_{T}+P_{\mathrm{max}}\) endif endif endfor endfor \(\mathrm{P}_{T}\gets\mathrm{P}_{T}/2^{i}\) if\(\mathrm{P}_{T}<P_{\mathrm{min}}\)then \(\mathrm{P}_{\mathrm{min}}\gets\mathrm{P}_{T}\) for\(m=1:q\)do
24:\(\mathrm{T}_{m}^{(j)}\gets b_{k,m}\) endfor endif
27:endif endfor return\(\mathrm{T}^{(j)}\)
```  
**Algorithm 3** Obtain information bit set of \(j\)-th synthesized channel  
```
0:\(v\),\(k\). \(result\). \(result\gets 1\) for\(m=1:q\)do if\(b_{k,m}=0\)then
4:if\(b_{v,m}\
eq 0\)then \(result\gets 0\) break endif
8:endif endfor return\(result\)
```  
**Algorithm 4** IsVlegal  
```
0:\(v\),\(k\). \(result\gets 1\) for\(m=1:q\)do if\(b_{k,m}=0\)then
4:if\(b_{v,m}\
eq 0\)then \(result\gets 0\) break endif
8:endif endfor return\(result\)
```  
**Algorithm 5** IsVlegal  
```
0:\(v^{\prime}\)

### Error-Probability-Based Bit-Level Construction

Although the CD construction achieves high accuracy with a large quantization level \(\mu\), it also leads to a high complexity. To reduce the complexity of the construction algorithm, we consider an error-probability-based bit-level construction for MC construction. Meanwhile, we make all the synthesized channels carry information bits with the same pattern. For example, if the \(j\)-th synthesized channel carries \(0<i<q\) bits, its input symbol \(v_{j}\in\{0,1,\ldots,2^{i}-1\}\). Consider an \((N,K,\mathcal{A})\) non-binary polar code over GF(\(2^{q}\)).