## 3 Polar Codes for the Multi-Way Relaying System
### Background on Polar Codes
Using operations performed over the binary field \(\mathbb{GF}(2)\), we can express the original polar encoded codeword as follows:  
\[\mathbf{x}=\mathbf{m}\mathbf{G}_{N}=\mathbf{m}_{A}\mathbf{G}_{A}+\mathbf{m}_{ A^{c}}\mathbf{G}_{\mathcal{A}^{c}} \tag{21}\]  
where \(\mathbf{G}_{A}\) is the submatrix of \(\mathbf{G}_{N}\) that contains all the rows of \(\mathbf{G}_{N}\) with indices in \(\mathcal{A}\), \(\mathbf{G}_{\mathcal{A}^{c}}\) is the submatrix of \(\mathbf{G}_{N}\) that contains all the rows of \(\mathbf{G}_{N}\) with indices in \(\mathcal{A}^{c}\), and \(\mathbf{m}\) is an input vector containing information bits and frozen bits. When all the frozen bits are set to 0, (21) becomes:  
\[\mathbf{x}=\mathbf{m}_{A}\mathbf{G}_{A} \tag{22}\]  
showing that \(\mathbf{G}_{A}\) is the generator matrix. When encoding with (22), \(\mathbf{m}_{A}\) does not appear in the resultant codeword \(\mathbf{x}\); thus, the original polar codes are non-systematic and cannot be used for our multi-way relaying system. \(\mathbf{G}_{nonsys}\triangleq\mathbf{G}_{A}\) is defined as the non-systematic generator matrix of polar codes. As an example, consider an \((8,5)\) polar code with frozen bits set \(\mathcal{A}^{c}=\{1,2,3\}\) and information bits set \(\mathcal{A}=\{4,5,6,7,8\}\). The polar encoding for this code is shown in Figure 2. The encoding process of an \((N,K)\) polar code consists of \(\log_{2}N+1\) stages denoted by \(S_{0},S_{1},S_{2}\ldots S_{\log_{2}N}\). The input to the encoder \(\mathbf{m}\) is at \(S_{0}\). At each subsequent stage, there are \(N/2=4\) binary additions. For this \((8,5)\) polar code,  
\[\mathbf{G}_{N}=\mathbf{F}^{\bigotimes 3}= \begin{bmatrix}\mathbf{F}&0&0&0\\ \mathbf{F}&\mathbf{F}&0&0\\ \mathbf{F}&0&\mathbf{F}&0\\ \mathbf{F}&\mathbf{F}&\mathbf{F}&\mathbf{F}\end{bmatrix} = \begin{bmatrix}1&0&0&0& 0&0&0&0\\ 1&1&0&0&0&0&0&0\\ 1&1&1&1&0&0&0&0\\ 1&0&0&0&1&0&0&0\\ 1&1&0&0&1&1&0&0\\ 1&0&1&0&1&0&1&0\\ 1&1&1&1&1&1&1&1\end{bmatrix}  \tag{23}\]The nonsystematic generator matrix \(\mathbf{G}_{nonsys}\) selects the rows in \(\mathcal{A}\) of \(\mathbf{G}_{N}\), i.e., the last five rows to transmit information bits:  
\[\mathbf{G}_{nonsys}= \begin{bmatrix}1&1&1&1&0&0&0&0\\ 1&0&0&0&1&0&0&0\\ 1&1&0&0&1&1&0&0\\ 1&0&1&0&1&0&1&0\\ 1&1&1&1&1&1&1\end{bmatrix}  \tag{24}\]  
Reed-Muller (RM) codes [52] are closely related to polar codes. Both codes with codeword length \(N\) use the same matrix \(\mathbf{G}_{N}\) for code construction. While the generator matrix of polar codes selects the most reliable rows with the lowest error probabilities of \(\mathbf{G}_{N}\) based on the specific channel and SNR, the generator matrix of \((r,n)\) RM codes with order \(r\) and codeword length \(N=2^{n}\) selects the rows of \(\mathbf{G}_{N}\) with Hamming weights \(w\geq 2^{n-r}\). Equivalently, polar codes freeze the least-reliable channels, while RM codes freeze the channels with the lowest Hamming weights. Consequently, polar codes have a better error performance, since the code design is channel-specific to improve error performance, while RM codes have a higher minimum Hamming distance. The Log likelihood ratio (LLR) for the \(i\)th bit channel is given by the following:  
\[L_{N}^{(i)}(\mathbf{y},\mathbf{\hat{m}}_{1}^{i-1})\triangleq\ln\frac{W_{N}^{(i )}(\mathbf{y},\mathbf{\hat{m}}_{1}^{i-1}|m_{i}=0)}{W_{N}^{(i)}(\mathbf{y}, \mathbf{\hat{m}}_{1}^{i-1}|m_{i}=1)} \tag{25}\]  
With SC decoding, each bit is decoded successively from \(m_{1}\) to \(m_{N}\). The decoder employs the following decision rule for the \(i\)th bit:  
\[\hat{m}_{i}= \begin{cases}0&\text{if }i\in\mathcal{A}^{c}\\ 0&\text{if }L_{N}^{(i)}(\mathbf{y},\mathbf{\hat{m}}_{1}^{i-1})\geq 0,i\in \mathcal{A}\\ 1&\text{if }L_{N}^{(i)}(\mathbf{y},\mathbf{\hat{m}}_{1}^{i-1})<0,i\in \mathcal{A}\end{cases}  \tag{26}\]  
The calculation of (25) can be performed recursively in the log domain [53]:  
\[