## 3 Polar Codes for the Multi-Way Relaying System
### Complexity Analysis of Polar Codes and Comparison  
The encoding process of polar codes in the MWRN considered in this work is identical to the process described in Section 2; thus, the encoding complexity is the same. For the decoding process, each terminal first performs a reverse permutation of the received signal vector \(\mathbf{y}\). The complexity of the reverse permutation is \(O(N)\). Since we use the original SC and SCL decoders, the complexities of SC and SCL decoding in our system are still \(O(N\text{log}N)\)[23] and \(O(L_{max}N\text{log}N)\)[30]. For the final polar re-encoding process, we use the recursive structure of polar encoding, which has a complexity of \(O(N\text{log}N)\). In summary, the total decoding complexity at each terminal is \(O(N\text{log}N)\) for SC decoding and \(O(L_{max}N\text{log}N)\) for SCL decoding. The complexity at each node when employing polar codes is presented in Table 4.  
Next, we analyze the number of required operations at each step for polar codes with SC decoding. The indices used for the reverse permutation are pre-stored in a table; thus, the reverse permutation step only requires \(N\) table look-ups. Calculating one channel LLR using (40) requires three multiplications and two additions; thus, calculating the total \(N\) channel LLRs requires \(3N\) multiplications and \(2N\) additions. According to (27), each term requires three comparisons and one multiplication, and each term in (28) requires one  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Encoding** & **Decoding** \\ \hline Terminal & - & \(O(N\text{log}N)\) for SC, \(O(L_{max}N\text{log}N)\) for SCL \\ \hline Relay & \(O(K)\) & - \\ \hline \hline \end{tabular}
\end{table}
Table 4: Complexity at each node when employing polar codes.  
Figure 3: BEC channel model.  
comparison and one addition. There are \(N/2\text{log}_{2}N\) terms; hence, (27) requires \(N/2\text{log}_{2}N\) multiplications and \(3N/2\text{log}_{2}N\) additions, and (28) requires \(N/2\text{log}_{2}N\) multiplications and \(N/2\text{log}_{2}N\) additions in total. The bit decision step in (26) requires \(N\) table look-ups to check whether the bit is frozen and \(K\) LLR comparisons for the decision of information bits. The re-encoding process consists of \(\text{log}_{2}N\) stages. At each stage, there are \(N/2\) additions. The total number of operations of each step for SC decoding is summarized in Table 5. For SCL decoding, the number of operations is related to the location of frozen bits and the path metrics, which is about \(L_{max}\) times of SC decoding.  
The total number of required operations for polar codes with ML and SC decoding, as well as LDPC codes with log-BP decoding, is summarized in Table 6. For example, a \((512,416)\) polar code requires 3840 multiplications and 5632 additions to decode a codeword using the SC technique. The \((437,361)\) LDPC code in [12] has \(d_{c}=20\) and \(d_{v}=3.48\). When ignoring the operations in the initializations, the log-BP decoder requires 8740 multiplications and 42,898 additions for one iteration. This indicates that even when \(I_{max}=1\), the total number of operations required by polar codes with SC decoding is much lower than that of LDPC codes with log-BP decoding. The SC decoding complexity behaves as \(N\text{log}_{2}N\), which in general, is lower than the complexities of the other two algorithms, log-BP and ML. Therefore, the low decoding complexity of polar codes make them attractive for MWRN applications.