## 3 Polar Codes for the Multi-Way Relaying System  
### Background on Polar Codes  
Let \(W:\mathcal{X}\rightarrow\mathcal{Y}\) be a binary-input discrete memoryless channel (B-DMC) with input and output alphabets \(\mathcal{X}=\{0,1\}\) and \(\mathcal{Y}=\mathbb{R}\) (the set of real numbers), respectively. The transition probability of the channel is denoted by \(W(y|x)\), where \(x\in\mathcal{X},y\in\mathcal{Y}\). Let the subvector \((m_{i},\ldots m_{j})\) of \(\mathbf{m}\) be denoted by \(\mathbf{m}_{i}^{j}\). If \(i>j\), then \(m_{i}^{j}\) is the null vector. There are two parameters that indicate the channel quality for polar codes: the symmetric capacity \(I(W)\) and the Bhattacharyya parameter \(Z(W)\). These are defined in [23] as follows:  
\[I(W)=\sum_{y\in\mathcal{Y}}\sum_{x\in\mathcal{X}}\frac{1}{2}W(y|x)\text{log} \frac{W(y|x)}{\frac{1}{2}W(y|0)+\frac{1}{2}W(y|1)} \tag{15}\]  
\[Z(W)=\sum_{y\in\mathcal{Y}}\sqrt{W(y|0)W(y|1)} \tag{16}\]  
where the logarithm is taken with a basis of 2. The symmetric capacity \(I(W)\) is the highest rate for reliable communication with equal input probabilities, and the Bhattacharyya parameter \(Z(W)\) is an upper bound to the error probability under ML decoding when transmitting over W. It was shown in [23] that for any B-DMC, the following two inequalities hold:  
\[I(W)\geq\text{log}\frac{2}{1+Z(W)} \tag{17}\]  
\[I(W)\leq\sqrt{1-Z(W)^{2}} \tag{18}\]  
Based on (17) and (18), \(I(W)\approx 1\) iff \(Z(W)\approx 0\), which indicates that the channel is reliable. Polar codes exploit the channel polarization phenomenon. In channel polarization, \(N\) independent copies of a B-DMC employing channel combining and channel splitting are \begin{table}
\begin{tabular}{c c c c c} \hline \hline  & **Multiplication** & **Addition** & **Comparison** & **Table Look-Up** \\ \hline Initialization & \(3N\) & \(2N\) & - & - \\ \hline Update & \(L(q_{uv}(z))\) & - & \(6(3d_{c}-4)LI_{max}\) & \(2(3d_{c}-4)LI_{max}\) & \(2(3d_{c}-4)LI_{max}\) \\ \hline Update & - & \(Ld_{c}(d_{v}-1)I_{max}\) & - & - \\ \hline Tentative LLRs & - & \(Ld_{c}d_{v}I_{max}\) & \(NI_{max}\) & - \\ \hline \(\hat{\mathbf{x}}\cdot\mathbf{H}^{T}\) & \(Nd_{c}I_{max}\) & \(N(d_{c}-1)I_{max}\) & - & \(NLI_{max}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Number of operations at each step of low-density parity check (LDPC) codes with log-belief propagation (BP) decoding. transformed into \(N\) synthesized bit channels \(\{W_{N}^{(i)}:1\leq i\leq N\}\), where \(W_{N}^{(i)}\) denotes the \(i\)-th such synthesized channel. As \(N\) tends to infinity, the symmetric capacity \(I(W_{N}^{(i)})\) tends towards 0 or 1; hence, it is polarized. The transition probability of the \(i\)th bit channel \(W_{N}^{(i)}\) is as follows [23]:  
\[W_{N}^{(i)}(\mathbf{y}_{1}^{N},\mathbf{m}_{1}^{i-1}|m_{i})=\sum_{\mathbf{m}_{i +1}^{N}}\frac{1}{2^{N-1}}W_{N}(\mathbf{y}_{1}^{N}|\mathbf{m}_{1}^{N}) \tag{19}\]  
For an \((N,K)\) polar code, the information bits are arranged to be located at the \(K\) most reliable bit locations and are transmitted over the best \(K\) bit channels. The other \(N-K\) bits are called frozen bits, and their values are known to the decoder. Frozen bits do not carry information and are set to fixed values. In this work, all frozen bits are set to 0. The process of selecting the information bit indices of polar codes is called the construction of polar codes. We define set \(\mathcal{A}\) as the collection of all information bit indices of a polar code. We denote the information bits of the polar code by \(\mathbf{m}_{A}\) and the frozen bits by \(\mathbf{m}_{A^{c}}\). The encoding matrix of a \((N,K)\) polar code is as follows [23]:  
\[\mathbf{G}_{N}=\mathbf{F}^{\bigotimes\log_{2}N} \tag{20}\]  
where \(\mathbf{F}= \begin{bmatrix}1&0\\ 1&1\end{bmatrix} \) is the fundamental building matrix (called the kernel matrix), and \(\bigotimes n\) denotes the \(n\)th-fold Kronecker product of a matrix.