## 3 Polar Codes for the Multi-Way Relaying System
### Systematic Polar Encoding for the Multi-Way Relaying System  
For any non-systematic linear block code with generator matrix \(\mathbf{G}_{nonsys}\), there exists a systematic equivalent code with systematic generator matrix \(\mathbf{G}_{sys}\)[55], satisfying the following relation:  
\[\mathbf{G}_{nonsys}=\mathbf{B}\mathbf{G}_{sys} \tag{32}\]  
where \(\mathbf{B}\) is a \(K\times K\) invertible matrix. A code and its systematic equivalent form have the same codewords. Only the mappings of the information vector to codewords are different. These mappings are related through a linear reversible transformation represented by the matrix \(\mathbf{B}\) of (32).  
We define \(\mathbf{G}_{AA}\) as the \(K\times K\) submatrix of \(\mathbf{G}_{N}\) of (20) that consists of elements \(G_{i,j}\) with \(i\in\mathcal{A},j\in\mathcal{A}\). The matrix \(\mathbf{G}_{N}\) is lower triangular with diagonal elements \(G_{d,d}=1\), \(1\leq d\leq N\). The diagonal elements of \(\mathbf{G}_{AA}\) are \(G_{i,j}\) with \(i\in\mathcal{A}\), which are also diagonal elements of \(\mathbf{G}_{N}\). Therefore, the diagonal elements of \(\mathbf{G}_{AA}\) are also all equal to \(1\), and \(\mathbf{G}_{AA}\) is invertible. The systematic encoder in [35] chooses \(\mathbf{B}=\mathbf{G}_{AA}\). However, with this selection, the information bits are located at all bit indices in \(\mathcal{A}\) of the codeword \(\mathbf{x}\), which we denote as \(\mathbf{x}_{A}\). In our system, the bits transmitted by the terminals \(\mathbf{m}_{T}\) are located at the first \(K\) bit indices of \(\mathbf{x}\). Therefore, the columns of \(\mathbf{G}_{A}\) are first permuted before the construction of the equivalent systematic generator matrix. We define the resultant matrix from permuting the columns of \(\mathbf{G}_{A}\) as \(\mathbf{G}_{Ap}\), which has the following form:  
\[\mathbf{G}_{Ap}=\begin{bmatrix}\mathbf{G}_{AA}&\mathbf{G}_{AA^{c}}\end{bmatrix} \tag{33}\]  
where \(\mathbf{G}_{AA^{c}}\) is a \(K\times L\) submatrix of \(\mathbf{G}_{N}\) that consists of all elements \(G_{ij}\) with \(i\in\mathcal{A},j\in\mathcal{A}^{c}\). The systematic generator matrix of the system is formed as follows:  
\[\mathbf{G}_{sys}=\mathbf{G}_{AA}^{-1}\mathbf{G}_{Ap}=\mathbf{G}_{AA}^{-1} \begin{bmatrix}\mathbf{G}_{AA}&\mathbf{G}_{AA^{c}}\end{bmatrix}=\begin{bmatrix} \mathbf{I}_{K\times K}&\mathbf{G}_{AA}^{-1}\mathbf{G}_{AA^{c}}\end{bmatrix}= \begin{bmatrix}\mathbf{I}_{K\times K}&\mathbf{P}_{K\times L}\end{bmatrix} \tag{34}\]  
The codeword \(\mathbf{x}\) can be obtained from either \(\mathbf{m}_{T}\) or \(\mathbf{m}_{A}\):  
\[\mathbf{x}=\mathbf{m}_{T}\mathbf{G}_{sys}=\mathbf{m}_{A}\mathbf{G}_{Ap}= \mathbf{m}_{A}\mathbf{G}_{AA}\mathbf{G}_{sys} \tag{35}\]  
Therefore, the information bits transmitted by the terminals, \(\mathbf{m}_{T}\), and the information bits of the original non-systematic polar code, \(\mathbf{m}_{A}\), are related by the following:  
\[\mathbf{m}_{T}=\mathbf{m}_{A}\mathbf{G}_{AA} \tag{36}\]  
Encoding at the terminals is performed using \(\mathbf{m}_{T}\), while polar decoding retrieves \(\mathbf{m}_{A}\). However, after \(\mathbf{m}_{A}\) is recovered using the SC or SCL algorithm, \(\mathbf{m}_{T}\) can be obtained from (36). Notice that (36) can also be viewed as an encoding of \(\mathbf{m}_{A}\) using the generator matrix \(\mathbf{G}_{AA}\), which can be implemented recursively as in polar encoding.