# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 2 Prerequisites
### Information Bottleneck Method
It is important to point out that such a channel quantizer is an integral part of the information bottleneck decoders designed for LDPC and polar codes, i.e., the decoders assume that the physical channel output is clustered into a finite number of bins by a quantizer designed using the information bottleneck method or another principle. Let \(x\in\{0,1\}\) be a coded bit which is modulated into transmit symbols \(s(x)\) using BPSK as \(s(x)=1-2x\). The symbol \(s(x)\) is affected by an AWGN with variance \(\sigma_{N}^{2}\), resulting in continuous channel  
Figure 3: (**a**) Information bottleneck setup, where \(I(X;T)\) is the relevant information, \(I(X;Y)\) is the original mutual information, and \(I(Y;T)\) is the compression information. The goal is to determine the mapping \(p(t|y)\) which maximizes \(I(X;T)\) and minimizes \(I(Y;T)\). (**b**) Information bottleneck graph for the elementary setup of (**a**). The realizations of \(Y\) are mapped onto those of \(T\) such that their relevance to \(X\) is preserved, i.e., \(I(X;T)\approx I(X;Y)\), and \(|\mathcal{T}|<|\mathcal{Y}|\). output \(\tilde{y}\). Then, for the channel quantizer design using the information bottleneck, the observed and the relevant quantities are channel output \(\tilde{y}\) and transmitted code bit \(x\), respectively. The compression variable is labeled \(Y\) such that the quantized channel output is \(y\in\mathcal{Y}=\{0,1,\ldots,|\mathcal{Y}|-1\}\). For the a priori distribution of \(p(x)=1/2\), the joint distribution \(p(x,\tilde{y})\) is given by:  
\[p(x,\tilde{y})=\frac{1}{2\sqrt{2\pi\sigma_{N}^{2}}}\exp\left(-\frac{(\tilde{y }-s(x))^{2}}{2\sigma_{N}^{2}}\right). \tag{14}\]  
The distribution \(p(\tilde{y},x)\) is fed into the modified sequential information bottleneck algorithm [1; 2], which determines the mapping \(p(y|\tilde{y})\) that divides the AWGN channel output into \(|\mathcal{Y}|\) clusters such that \(I(X;Y)\) is maximized. Note that the selected algorithm works only with discrete random variables. Therefore, the continuous channel output is first discretized using a fine uniform resolution. Figure 4 illustrates the relevant information preserving clustering of AWGN channel output into \(|\mathcal{Y}|=8\) clusters for noise variance \(\sigma_{N}^{2}=0.5\). The algorithm randomly initializes the cluster boundaries in a symmetric manner as exemplarily depicted in Figure 4a and computes the mutual information \(I(X;Y)\) for the resulting compressed joint distribution \(p(x,y)\). The clusters are labeled such that the left-most cluster is \(y=0\), while the right-most cluster is \(y=7\). When the event space \(\tilde{\mathcal{Y}}\) is sorted with respect to its LLRs \(2\tilde{y}/\sigma_{N}^{2}\), as is the case in Figure 4, each cluster is a subset of contiguous elements of \(\tilde{\mathcal{Y}}\). Then, the task of finding the desired clustering \(p(y|\tilde{y})\) reduces to optimizing the cluster boundaries due to the _separating hyperplane condition_[5]. The algorithm, therefore, adjusts each cluster boundary such that \(I(X;Y)\) is maximized and updates the distributions \(p(x,y)\) and \(p(y|\tilde{y})\). The algorithm stops when \(I(X;Y)\) does not increase further and returns the mapping \(p(y|\tilde{y})\), the distribution \(p(y)\), and \(p(x|y)\). Figure 4b shows the optimized boundaries of quantization bins or clusters which assign all channel outputs \(\tilde{y}<-0.99\) to cluster \(y=0\), \(-0.99\leq\tilde{y}<-0.56\) to cluster \(y=1\), and so on. The quantizer does not assign any real valued representative to each quantization bin but instead produces the index \(y\) of the cluster in which \(\tilde{y}\) falls. Should the quantizer be used with a decoder that requires LLRs as input, the cluster indices \(y\) can be translated into channel level LLRs as:  
\[L_{x}^{ch}(y)=\log\frac{p(y|x=0)}{p(y|x=1)}=\log\frac{p(x=0|y)}{p(x=1|y)}, \tag{15}\]  
where the distribution \(p(x|y)\) is delivered by the information bottleneck algorithm along with the quantizer mapping \(p(y|\tilde{y})\).