# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 4 Information Bottleneck Polar Decoders
### Lookup Tables for Decoding on a Building Block  
In Section 3.1, the distributions \(p(t_{i}|\mathbf{y}_{i})\) and \(p(u_{i}|t_{i})\), \(i\in\{0,1\}\), were obtained from \(p(u_{i},\mathbf{y}_{i})\) using the information bottleneck method on the building block of Figure 1. The joint distribution, \(p(u_{i},\mathbf{y}_{i})\), of a bit channel embeds the relation of its output \(\mathbf{y}_{i}\) to its input \(u_{i}\), i.e., knowing \(\mathbf{y}_{i}\), one can figure out whether \(u_{i}=0\) or \(u_{i}=1\) is more probable. By ensuring that \(I(U_{i};T_{i})\approx I(U_{i};Y_{i})\), the information bottleneck method strives to preserve this relation when compressing and mapping the event space of \(\mathbf{Y}_{i}\) onto that of \(T_{i}\). Therefore, knowing the value of \(T_{i}=t_{i}\) (i.e., the label of the cluster to which the channel output belongs) after using the mapping \(p(t_{i}|\mathbf{y}_{i})\), we can figure out the most likely value of the channel input.  
The deterministic mapping \(p(t_{i}|\mathbf{y}_{i})\) in tabular form is referred to as the _decoding_ table for the bit \(u_{i}\), e.g., Figure 8a shows the decoding table for \(u_{0}\). The decoding table of \(u_{0}\) is essentially a quantizer of the bit channel \(p(y_{0},y_{1}|u_{0})\) which produces the cluster index \(t_{0}\in\mathcal{T}\) when the outputs of the underlying AWGN channel are put in clusters \(y_{0}\) and \(y_{1}\) by the channel quantizer. Typically, the cluster index alone does not provide any meaning for the relevant quantity. However, due to the symmetry of the bit channel, the knowledge of \(t_{0}\) can be used for a hard decision on \(u_{0}\) since half of the \(|\mathcal{T}|\) clusters correspond to \(u_{0}=0\) and the remaining half to \(u_{0}=1\). In order to perform soft decision estimation, the conditional distribution \(p(u_{0}|t_{0})\) is used to compute the LLR \(L_{u_{0}}(t_{0})\) as:  
\[L_{u_{0}}(t_{0})=\log\frac{p(t_{0}|u_{0}=0)}{p(t_{0}|u_{0}=1)}=\log\frac{p(u_{ 0}=0|t_{0})}{p(u_{0}=1|t_{0})}, \tag{21}\]  
where the second equality in Equation (21) is due to equiprobable input, i.e., \(p(u_{0})=0.5\). Equation (21) is tabulated with exemplary values in Figure 8b and referred to as the _translation_ table since it translates the cluster indices \(t_{0}\in\{0,1,...,|\mathcal{T}|-1\}\) to LLRs \(L_{u_{0}}(t_{0})\). It can be seen in the translation table of Figure 8b that \(\hat{u}_{0}=1\) is most likely for all the bit channel outputs \(\mathbf{y}_{0}\) put in the cluster \(t_{0}=0\), i.e., the largest LLR magnitude with a negative sign. When the decoding table lookup produces \(t_{0}=1\), \(\hat{u}_{0}=1\) is still more probable but with less confidence, i.e., smaller LLR magnitude. The lookup tables of Figure 8 can be used to decode \(u_{0}\) as follows:  
1. Use the decoding table \(p(t_{0}|\mathbf{y}_{0})\) of Figure 8a to determine the cluster index to which the observed channel output \(\mathbf{y}_{0}\) belongs. For example, \(t_{0}=|\mathcal{T}|-1\) when \(y_{0}=y_{1}=0\).
2. Use \(t_{0}\) from step 1 for a hard decision on \(u_{0}\) or translate it into an LLR value using the translation table of Figure 8b. For the example of \(t_{0}=|\mathcal{T}|-1\), \(\hat{u}_{0}=0\) and \(L_{u_{0}}(t_{0})\)= 2.19.  
The bit \(u_{1}\) can also be decoded in a similar fashion using its decoding and translation tables \(p(t_{1}|\mathbf{y}_{1})\) and \(p(u_{1}|t_{1})\), respectively. Similarly to conventional SC decoding, the decoding table of \(u_{1}\) assumes the knowledge of \(u_{0}\) from the previous decoding stage. Thus, the decoding on a building block can be done using lookup tables instead of computations according to Equations (6a) and (6b). The decoding tables \(p(t_{0}|\mathbf{y}_{0})\) and \(p(t_{1}|\mathbf{y}_{1})\) have \(|\mathcal{Y}|^{2}\) and \(2\cdot|\mathcal{Y}|^{2}\) integer valued entries, respectively. Both the translation tables have only \(|\mathcal{T}|\) real valued entries, i.e., LLRs.