## 3 Polar Codes for the Multi-Way Relaying System
### Background on Polar Codes
\begin{split} L_{N}^{(2i-1)}(\mathbf{y}_{1}^{N},\mathbf{\hat{m}} _{1}^{2i-2})\approx\text{sign}(L_{N/2}^{(i)}(\mathbf{y}_{1}^{N/2},\mathbf{ \hat{m}}_{1,o}^{2i-2}+\mathbf{\hat{m}}_{1,e}^{2i-2}))\cdot\text{sign}(L_{N/2}^ {(i)}(\mathbf{y}_{N/2+1}^{N},\mathbf{\hat{m}}_{1,e}^{2i-2}))\\ \cdot\min(|L_{N/2}^{(i)}(\mathbf{y}_{1}^{N/2},\mathbf{\hat{m}}_{1,o}^{2i-2}+\mathbf{\hat{m}}_{1,e}^{2i-2})|,|L_{N/2}^{(i)}(\mathbf{y}_{N/2+1}^ {N},\mathbf{\hat{m}}_{1,e}^{2i-2})|)\\ L_{N}^{(2i)}(\mathbf{y}_{1}^{N},\mathbf{\hat{m}}_{1}^{2i-1})=(1-2\mathbf{ \hat{m}}_{2i-1})[L_{N/2}^{(i)}(\mathbf{y}_{1}^{N/2},\mathbf{\hat{m}}_{1,o}^{2 i-2}+\mathbf{\hat{m}}_{1,e}^{2i-2})]+L_{N/2}^{(i)}(\mathbf{y}_{N/2+1}^{N}, \mathbf{\hat{m}}_{1,e}^{2i-2})\end{split}  \tag{27}\]  
Figure 2: Encoder of a \((8,5)\) polar code. where \(\mathbf{m}_{1,\rho}^{2i-2}\) is the subvector of \(\mathbf{m}_{1}^{2i-2}\) with odd indices,and \(\mathbf{m}_{1,e}^{2i-2}\) is the subvector of \(\mathbf{m}_{1}^{2i-2}\) with even indices. The recursion continues until we reach the calculation of LLR of \(W_{1}^{(1)}\). In this case,  
\[L_{1}^{(1)}(y_{i})=\ln\frac{W(y_{i}|0)}{W(y_{i}|1)} \tag{29}\]  
is called the channel LLR, which can be calculated from the channel. A more detailed description of SC decoding can be found in [23]. The SCL algorithm is a modified version of SC decoding and follows a similar serial decoding process from \(m_{1}\) to \(m_{N}\). While SC decoding only considers the best decoding result, SCL decoding forms a list of \(L_{max}\) best possible decoding results. The decoding result in the SCL algorithm is named as a candidate path having a path metric. In the log domain, the path metric PM of the \(l\)th candidate path at the \(i\)th bit is defined as follows [54]:  
\[\text{PM}_{1}^{(i)}=-\ln p(\hat{\mathbf{m}}_{1}^{i}|\hat{\mathbf{y}}_{1}^{N}) =\sum_{j=1}^{i}\ln(1+e^{-(1-2\hat{\mathbf{m}}_{j})L_{N}^{(j)}}) \tag{30}\]  
A smaller path metric corresponds to a higher \(p(\hat{\mathbf{m}}_{1}^{i}|\hat{\mathbf{y}}_{1}^{N})\), which indicates a higher likelihood for that candidate path. The updating rule of the path metric at bit index \(i\) is as follows:  
\[\text{PM}_{1}^{(i)}= \begin{cases}\text{PM}_{1}^{(i-1)}&\text{if }\hat{m}_{i}= \frac{1}{2}(1-\text{sign}(L_{N}^{(i)}))\\ \text{PM}_{1}^{(i-1)}+|L_{N}^{(i)}|&\text{otherwise}\end{cases}  \tag{31}\]  
Equation (31) indicates that if the decoding result of list \(l\) for bit \(i\) does not coincide with the corresponding LLR, then a penalty \(|L_{N}^{(k)}|\) is added to the path metric. Before decoding \(m_{1}\), the initial path metrics are all set to \(0\). When decoding a frozen bit, the value \(0\) is appended to all candidate paths, and the path metrics are updated. When decoding an information bit \(m_{i}\), instead of making a hard decision using (26), the SCL decoder appends both possible decoding results of \(0\) or \(1\) to the identical copies of the current decoding candidates, which doubles the number of active candidate paths. When the number of candidate paths exceeds \(L_{max}\), only the \(L_{max}\) candidate paths with the lowest path metrics are kept, and others are pruned. After decoding \(m_{N}\), the active candidate path with the lowest path metric is selected to be the final decoding result. By using a lazy-copy technique to duplicate the candidate paths, the decoding complexity of SCL decoding is \(O(L_{max}N\text{log}N)\)[30].