# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 2 Prerequisites
### Successive Cancellation List Decoder  
The SC decoder works on the structure of Figure 2 and estimates the bit values \(u_{i}\) in a sequential manner from \(i=0\) to \(N-1\). At each decoding stage \(i\), \(\hat{u}_{i}\) is determined as:  
Figure 2: Structure of a polar code with \(N=4\). The graph is partitioned into \(n=\log_{2}N=2\) levels. The node labels, \(v_{i,j}\) indicate the vertical stage, \(i=0,1,\ldots,N-1\), and horizontal level, \(j=0,\ldots,n\). For all \(i\), \(v_{i,0}=y_{i}\), i.e., the channel output at level \(j=0\), while \(v_{i,2}=u_{i}\), i.e., the encoder input bits at level \(j=2\). \[\hat{u}_{i}= \begin{cases}u_{i}&i\
otin\mathcal{A}\\ 0&i\in\mathcal{A}\text{ and }L_{u_{i}}(\mathbf{y}_{i})\geq 0\\ 1&i\in\mathcal{A}\text{ and }L_{u_{i}}(\mathbf{y}_{i})<0,\end{cases}  \tag{5}\]  
where \(L_{u_{i}}(\mathbf{y}_{i})=\log\frac{p(\mathbf{y}_{i}|u_{i}=0)}{p(\mathbf{y}_{ i}|u_{i}=1)}\) is the LLR of the bit \(u_{i}\), and \(\mathcal{A}\) denotes the information set. When ties in the case of \(L_{u_{i}}(\mathbf{y}_{i})=0\) are broken randomly, Equation (5) is a maximum likelihood decoding of the \(i\)th bit channel. The LLR \(L_{u_{i}}(\mathbf{y}_{i})\) is computed from subsequent levels in recursive steps as follows:  
\[L_{v_{i,j}}(\mathbf{y}_{i,j})= \begin{cases}L_{v_{i,j-1}}(\mathbf{y}_{i,j-1}) \boxplus L_{v_{i,j-1}}(\mathbf{y}_{i,n,j-1})&\text{$i$ is even}\\ b_{i,j-1}L_{v_{i,j-1}}(\mathbf{y}_{i,n,j-1})+L_{v_{i,n,j-1}}(\mathbf{y}_{i,n,j- 1})&\text{$i$ is odd},\end{cases}  \tag{6a}\]  
with \(i=\lfloor\frac{i}{2}\rfloor+\lfloor\frac{i}{2}\rfloor 2^{j-1},i\prime=i +2^{j-1}\) and \(b_{i,j}=(-1)^{\delta_{i-1,j}}\), where the bit value \(\delta_{i-1}\) is available from the previous decoding stages. \(\mathbf{y}_{i,j}\) represents output of the intermediate bit channel experienced by \(v_{i,j}\). The \(\boxplus\) operator for two LLR values \(L_{1}\) and \(L_{2}\) is defined as [32]:  
\[L_{1}\boxplus L_{2}=\log\frac{1+e^{L_{1}}e^{L_{2}}}{e^{L_{1}}+e^{L_{2}}}. \tag{7}\]  
The LLR values \(L_{v_{i,0}}(\mathbf{y}_{i,0})\) in the recursion are given by the channel LLRs:  
\[L_{x_{i}}^{ch}(y_{i})=\log\frac{p(y_{i}|x_{i}=0)}{p(y_{i}|x_{i}=1)}. \tag{8}\]  
The successive cancellation list decoder can be viewed as \(N_{L}\) successive cancellation decoders working in parallel. In SCL decoding, every time an estimate \(\hat{u}_{i}\) for \(i\in\mathcal{A}\) has to be made, the decoder proceeds as an SC decoder for both possible decisions of \(\hat{u}_{i}\), instead of using Equation (5). The decoder maintains a list of possible decoding results where the number of decoding paths doubles after estimation of each information bit. If at any stage, the number of decoding paths in the list exceeds the maximum allowed list size, \(N_{L}\), the decoder retains only the \(N_{L}\) most likely decoding paths, dropping the rest. The likelihood of path \(l\in\{0,1,\ldots,N_{L}-1\}\) in the list at stage \(i\) is captured by the path metric \(M_{i,l}\)[27]:  
\[M_{i,l}=M_{i-1,l}+\ln(1+e^{-(1-2\hat{u}_{i,l})L_{u_{i}}(\mathbf{y}_{i})_{l}}), \tag{9}\]  
where \(M_{i-1,l}\) is the metric of the \(l\)th path at decoding stage \(i-1\), \(\hat{u}_{i,l}\) is the bit value with which the path is being extended, and \(L_{u_{i}}(\mathbf{y}_{i})_{l}\) is the LLR value \(L_{v_{i,j-n}}(\mathbf{y}_{i,j=n})\) for the \(l\)th path according to Equation (6). The path with the smallest metric is the most likely decoding path. The path increment \(\Delta M_{i,l}=\ln(1+e^{-(1-2\hat{u}_{i,l})L_{u_{i}}(\mathbf{y}_{i})})\) is well-approximated as [27]:  
\[\Delta M_{i,l}= \begin{cases}0&\text{if }\hat{u}_{i,l}=\frac{1}{2}(1-\text{sign}(L _{u_{i}}(\mathbf{y}_{i}))\\ |L_{u_{i}}(\mathbf{y}_{i})|&\text{otherwise},\end{cases}  \tag{10}\]  
where \(\text{sign}(L_{u_{i}}(\mathbf{y}_{i}))\) denotes the sign of the LLR value \(L_{u_{i}}(\mathbf{y}_{i})\). After the last decoding stage, i.e., \(i=N-1\), the most likely decoding path from the list is selected as the decoder output.