# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 4 Information Bottleneck Polar Decoders
### Information Bottleneck Successive Cancellation List Decoder  
Having replaced the decoding steps on a single building block with table lookups, we proceed to demonstrate successive cancellation list decoding on the code of Figure 2 using lookup tables. For each variable node \(v_{i,j}\), \(0\leq i<N\) and \(1\leq j\leq n\), in Figure 2, the decoding table \(p(t_{i,j}|\mathbf{y}_{i,j})\) and the translation table \(p(v_{i,j}|t_{i,j})\) is available from application of the information bottleneck framework to the whole structure of Figure 2. Assume that the decoding list size is \(N_{L}=2\) and \(\mathcal{A}=\{1,2,3\}\), i.e., only \(u_{0}=0\) is frozen. With the right-most variable nodes, i.e., \(v_{i,0}\) loaded with quantizer output \(y_{i}\), \(i=0,1,2,3\), the decoding starts with the frozen bit \(u_{0}\). Although the value of \(u_{0}\) is known, its LLR \(L_{u_{0}}(t_{0})\) is required for the path metric update according to Equation (9). Therefore, cluster index \(t_{0,2}\) needs to be known from the decoding table \(p(t_{0,2}|\mathbf{y}_{0,2})=p(t_{0,2}|t_{0,1},t_{2,1})\). In order to obtain the yet unknown cluster values \(t_{0,1}\) and \(t_{2,1}\), the decoding tables \(p(t_{0,1}|\mathbf{y}_{0,1})=p(t_{0,1}|y_{0,y_{1}})\) and \(p(t_{2,1}|\mathbf{y}_{2,1})=p(t_{2,1}|\mathbf{y}_{2,y_{3}})\) are used, respectively. Once the cluster values \(t_{0,1}\) and \(t_{2,1}\) are obtained, the decoding table \(p(t_{0,2}|\mathbf{y}_{0,2})\) is used to get the value of \(t_{0,2}\). The translation table \(p(u_{0}|t_{0,2})\) is used to translate \(t_{0,2}\) to LLR \(L_{u_{0}}(t_{0})\), which is used to update path metric \(M_{0,0}\). In the next decoding stage, the first information bit \(u_{1}\) is decoded. The cluster index \(t_{1,2}\) is obtained from the decoding table \(p(t_{1,2}|\mathbf{y}_{1,2})=p(t_{1,2}|t_{0,1},t_{2,1},u_{0})\), for which all the three inputs are known from the previous decoding stage. The translation table \(p(u_{1}|t_{1,2})\) is used to translate \(t_{1,2}\) to LLR \(L_{u_{1}}(t_{1})\). Instead of using Equation (5) for the information bit, the decoder extends the existing decoding path with both possible decisions \(\hat{u}_{1}=0\) and \(\hat{u}_{1}=1\) and updates the path metrics \(M_{1,l}\), \(l\in\{0,1\}\) for both paths using \(L_{u_{1}}(t_{1})\) in (9). Similar steps are taken to estimate the remaining bits, i.e., \(u_{2}\) and \(u_{3}\). At each decoding stage \(i\in\mathcal{A}\), the number of decoding paths in the list doubles, and for \(i\geq 2\), the decoding list size will exceed the maximum allowed value \(N_{L}=2\). Therefore, \(N_{L}\) of the decoding paths having the largest path metric are dropped from the decoding list. The schedule of computations in the lookup table-based decoder is the same as in a conventional SCL decoder. However, all the computations, except the path metric update, are replaced by table lookups. Further, the inputs and outputs of all the decoding tables are unsigned integers, i.e., \(0,1,\ldots,|\mathcal{T}|-1\) with \(|\mathcal{T}|\) being a small number. The translation tables hold LLR values, i.e., real numbers. For a polar code of length \(N\), \(2N-2\) distinct decoding tables are required. It is important to note that the translation tables are required only at the decision level, i.e., \(j=n\), in the information bottleneck SCL decoders when an LLR value is needed for Equation (9). Therefore, we require only  
Figure 8: (a) Clustering \(p(t_{0}|\mathbf{y}_{0})\) that maps the \(|\mathcal{Y}_{0}|\cdot|\mathcal{Y}_{1}|\) outputs of the bit channel of \(u_{0}\) to \(|\mathcal{T}|\) clusters, written as a lookup table. (b) Translation table of \(u_{0}\) obtained from the conditional distribution \(p(u_{0}|t_{0})\) as in Equation (21). translation tables.