# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 5 Space-Efficient Information Bottleneck Successive Cancellation List Decoder
### Message Alignment for Successive Cancellation List Decoder  
Recall that the cluster indices \(t_{i}\) take values from the same finite alphabet \(\mathcal{T}=\{0,1,\ldots,|\mathcal{T}|-1\}\) regardless of the decoding stage \(i\), e.g., we can have \(t_{14}=1\) and \(t_{83}=1\). However, the appropriate  
Figure 9: Translation tables of an information bottleneck decoder with \(|\mathcal{T}|=16\) for different bit channels of a half-rate polar code with \(N=128\), design \(E_{b}/N_{0}=3\) dB. \(u_{14}\) is a frozen bit while \(u_{83}\), and \(u_{124}\) are information bits. translation table, obtained from the conditional distribution \(p(u_{i}|t_{i})\) according to Equation (21), translates the cluster index \(t_{i}\) into an LLR \(L_{u_{i}}(t_{i})\). Now let us make some notational changes. We separate the stage subscript from the cluster index and express \(t_{i}\) as a pair \([t,i]^{T}\). In our new notation, \(t_{14}=1\) and \(t_{83}=1\) are expressed as \([1,14]^{T}\) and \([1,83]^{T}\), respectively. We drop the subscript \(i\) from the bit \(u_{i}\) altogether such that a bit value is denoted by \(u\) regardless of the decoding stage \(i\). Thus, the use of distinct translation tables with this new notation can be stated as follows; a correct translation of a cluster index \(t\in\{0,1,\ldots,|\mathcal{T}|-1\}\) into an LLR \(L_{u}(t)\) requires the knowledge of the decoding stage \(i\in\{0,1,\ldots,N-1\}\). In other words, we observe \(t\) and \(i\) and infer the value of bit \(u\). This task of message alignment can be treated as an information bottleneck problem; the pair \(\mathbf{y}^{*}=[t,i]^{T}\) is the observed quantity, while the bit \(u\) is the relevant quantity, depicted in the information bottleneck graph of Figure 10. Casting the problem to the setup of Figure 3a, \(U\) becomes the binary relevant random variable, while \(\mathbf{Y}^{*}\) is the observed random variable with \(|\mathbf{\mathcal{Y}}^{*}|=N\cdot|\mathcal{T}|\). We wish to compress \(\mathbf{Y}^{*}\) into a new variable \(T^{*}\) with realizations \(t^{*}\in\mathcal{T}^{*}=\{0,1,\ldots,|\mathcal{T}^{*}|-1\}\) such that \(I(U;T^{*})\) is maximized. We refer to \(|\mathcal{T}^{*}|\) as the alignment cardinality. The application of an information bottleneck algorithm requires the joint distribution of the observation and the relevant quantity, i.e., \(p(u,\mathbf{y}^{*})\). This joint distribution is given by:  
\[p(u,\mathbf{y}^{*})=p(u,t,i)=p(i)p(u,t|i)=\frac{1}{N}p(u_{i},t_{i}), \tag{22}\]  
where \(p(u_{i},t_{i})\) is available from the information bottleneck decoder construction via density evolution and \(p(i)=\frac{1}{N}\) since there are \(N\) translation tables, each occurring once. The algorithm returns the distributions \(p(u|t^{*})\) and \(p(t^{*})\), as well as the mapping \(p(t^{*}|\mathbf{y}^{*})\), which clusters the pairs \([t,i]^{T}\) to \(t^{*}\). The alignment mapping \(p(t^{*}|\mathbf{y}^{*})\) needs not to be implemented as an extra table lookup and can be incorporated in the decoding tables at the \(j=n\) level. The mapping \(p(t^{*}|\mathbf{y}^{*})\) is used to replace the cluster indices \(\mathbf{y}^{*}=[t,i]^{T}=t_{i}\) in the decoding tables of the decision level, i.e., \(p(t_{i}|\mathbf{y}_{i,n})\), with the cluster indices \(t^{*}\). In other words, the decoding tables at the decision level are _aligned_. As a result, the aligned cluster indices \(t^{*}\) are translated using a single new translation table obtained from \(p(u|t^{*})\) in line with Equation (21). Figure 11 depicts the aligned translation table for the polar code of Section 5.1 obtained for \(|\mathcal{T}^{*}|=16\). Figure 11: Translation table for aligned decoding tables at the decision level with \(|\mathcal{T}^{*}|=16\) for the polar code with \(N=128\), rate = 0.5 and design \(E_{b}/N_{0}=3\) dB. Figure 10: Information bottleneck graph for the alignment of the translation tables of a polar code.