# 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
\tag{18}\]  
Let \(j\leq N=2^{n}\) be a nonnegative integer with binary representation \(\langle b_{j,1},b_{j,2},\ldots,b_{j,n}\rangle_{2}\). The degradation procedure is described in more detail in Algorithms 1 and 2, where GetOutputwithMinDeltaC(Q) is a search function that finds \(y_{1}\) and \(y_{2}\) with the smallest capacity difference from \(Q\). After that, we obtain the transition probability \(Q_{N}^{(j)}(y|v)\) of the \(j\)-th synthesized channel. We define  
\[Q_{N}^{(j)}(v\mid y)=\frac{Q_{N}^{(j)}(y\mid v)}{\sum_{v_{0}\in\text{GF}(2^{ \prime})}Q_{N}^{(j)}(y\mid v_{0})}, \tag{19}\]  
and  
\[P_{Q_{N}^{(j)}}(y)=\frac{1}{2^{q}}\sum_{v_{0}\in\text{GF}(2^{\prime})}Q_{N}^{ (j)}(y\mid v_{0}). \tag{20}\]  
Then, we have  
\[C(Q_{N}^{(j)})=H(V)-\sum_{y\in\mathcal{Y}}H(V|Y=y)P_{Q_{N}^{(j)}}(y). \tag{21}\]  
Since the \(C(Q_{N}^{(j)})\) in (21) is the lower bound of the \(j\)-th synthesized channel, we set \(I(j)=\lfloor C(Q_{N}^{(j)})+\delta\rfloor\), where \(\delta\) represents the difference between the capacity and the lower bound, \(0\leq\delta\leq 0.1\). Then, we sort each synthesized channel in descending order based on \(C(W_{N}^{(j)})\) and generate the symbol information set \(\mathcal{A}_{1}\), \(|\mathcal{A}_{1}|\geq K\) and \(\sum_{j\in\mathcal{A}_{1}}I(j)=Kq(bits)\). In addition, we need to determine which bit index carries information when \(0<i<q\). Let \(\Upsilon_{m}^{(j)}=1\) represent the information bit carried by the \(m\)-th index of the \(j\)-th synthesized channel, and \(\mathbf{T}^{(j)}=(T_{1}^{(j)},T_{2}^{(j)},\ldots,T_{q}^{(j)})\) represents the pattern of \(j\)-th synthesized channel carrying \(i\) information bits, where \(wt(\mathbf{T}^{(j)})=i\) represents the number of ones in \(\mathbf{T}^{(j)}\). According to the conditional probability \(Q_{N}^{(j)}(y|v)\) of the \(j\)-th synthesized channel, the error probability under the maximum likelihood decoding of pattern \(\mathbf{T}^{(j)}\) can be calculated by  
\[P_{\mathbf{T}^{(j)}}=\frac{1}{2^{i}}\sum_{y\in\mathcal{Y}}\sum_{ \begin{subarray} {c}v^{\prime}\\ v^{\prime}+\mu^{\prime}_{\text{max}}\end{subarray} }Q_{N}^{(j)}(y\mid v^{ \prime}), \tag{22}\]  
where  
\[v^{\prime}_{\text{max}}=\arg\max_{v^{\prime}}Q_{N}^{(j)}(y\mid v^{\prime}), \tag{23}\]  
denotes the decoding result. The pattern \(\mathbf{T}^{(j)}\) with the minimum error probability will be selected, and if \(T_{m}^{(j)}=1\), the \(((j-1)\times q+m)\)-th bit is an information bit. The details are shown in Algorithms 3 and 4, where \(\langle b_{k,m}\rangle_{2}\) is the binary representation of a nonnegative integer \(k\), and \(P_{\text{max}}\) represents the probability that \(Q_{N}^{(j)}(y\mid v^{\prime}_{\text{max}})\), \(P_{\text{min}}\) is the smallest error probability when the synthesized channel is carrying \(i\) bits. The encoder of bit-level-construction-based non-binary polar codes is the same as for symbol-level construction. At the decoder, Algorithm 4 is also used to search for a valid decoding symbol when decoding the synthesized channel carrying \(i\) bits. ```
0: DMC \(W\), a bound of output size \(\mu\), code length \(N=2^{n}\), channel index \(j\) with binary representation \(\langle b_{j,1},b_{j,2},\ldots,b_{j,n}\rangle_{2}\). 0: A DMC \(Q_{N}^{(j)}\) that is degraded with respect to the synthesized channel \(W_{N}^{(j)}\). 1:\(Q\leftarrow\texttt{ degrade}(W,\mu)\)
2:for\(i=1:n\)do
3:if\(b_{j,i}=0\)then
4:\(W\gets Q^{-}\)
5:else
6:\(W\gets Q^{+}\)
7:endif
8:\(Q\leftarrow\texttt{ degrade}(W,\mu)\)
9:endfor
10:return\(Q\)
```  
**Algorithm 1** Degrading procedure of synthesized channels  
```
0: DMC \(W:\mathcal{X}\rightarrow\mathcal{Y}\), where \(|\mathcal{Y}|=L\), a bound of output size \(\mu\). 0: A degrade channel \(Q:\mathcal{X}\rightarrow\mathcal{Y}^{\prime}\), where \(|\mathcal{Y}^{\prime}|\leq\mu\).