# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 3 Polar Code Construction Using the Information Bottleneck Method
### Information Bottleneck Construction  
The information bottleneck construction method starts by quantizing the AWGN channel using the quantizer of Section 2.4. The quantizer is designed for a target noise variance \(\sigma_{N}^{2}\) in Equation (14), computed from the design \(E_{b}/N_{0}\) of the polar code. As a result, the quantized AWGN channel becomes a binary input discrete memoryless channel with output alphabet size of \(|\mathcal{Y}|\) and transition probabilities \(p(y|x)\) in the building block of Figure 1. The output alphabets of the bit channels of \(u_{0}\) and \(u_{1}\) have sizes \(|\mathcal{Y}_{0}|\cdot|\mathcal{Y}_{1}|=|\mathcal{Y}|^{2}\) and \(|\mathcal{U}_{0}|\cdot|\mathcal{Y}_{0}|\cdot|\mathcal{Y}_{1}|=2\cdot|\mathcal{ Y}|^{2}\), respectively. The goal here is to quantize both of the bit channels using the information bottleneck method and reduce their output alphabets to a desired size \(|\mathcal{T}|\), which is chosen to be a power of 2. Initially, the two bit channels defined over the building block of Figure 1 are casted to the information bottleneck setup of Figure 3a. For the bit channel of \(u_{i}\), with \(i\in\{0,1\}\), output \(\mathbf{y}_{i}\) is the observation which we use to infer input \(u_{i}\). Therefore, the multivariate random variable \(\mathbf{Y}_{i}\) is the observed random variable, while the bit channel input is the relevant random variable, i.e., \(U_{i}\). Our goal here is to cluster the realizations of the observed variable \(\mathbf{Y}_{i}\) to a new compressed random variable \(T_{i}=t_{i}\in\{0,1,\ldots,|\mathcal{T}|-1\}\), while minimizing the quantization loss in terms of mutual information \(I(U_{i};\mathbf{Y}_{i})-I(U_{i};T_{i})\) as much as possible. The information bottleneck graphs for quantization of the two bit channels are depicted in Figure 5.  
An information bottleneck algorithm requires the joint distribution \(p(u_{i},\mathbf{y}_{i})\) relating the relevant and the observed random variables. For the bit channel of \(u_{0}\), we have:  
\[p(u_{0},y_{0},y_{1})=\sum_{x_{0}}\sum_{x_{1}}\sum_{u_{1}}p(u_{0},u_{1},x_{0},x_ {1},y_{0},y_{1}), \tag{16}\]  
where, from the factor graph in Figure 1:  
\[p(u_{0},u_{1},x_{0},x_{1},y_{0},y_{1})=p(y_{0}|x_{0})\cdot p(y_{1}|x_{1})\cdot p (x_{0}|u_{0},u_{1})\cdot p(x_{1}|u_{1})\cdot p(u_{0})\cdot p(u_{1}). \tag{17}\]  
Here, \(p(y_{i}|x_{i})\) and \(p(u_{i})=0.5\) for \(i\in\{0,1\}\) are the channel transition probabilities and priors, respectively, while \(p(x_{0}|u_{0},u_{1})\in\{0,1\}\) and \(p(x_{1}|u_{1})\in\{0,1\}\) are deterministic mappings according to \(x_{0}=u_{0}\oplus u_{1}\) and \(x_{1}=u_{1}\), respectively. Applying the selected information bottleneck algorithm to the joint distribution \(p(u_{0},\mathbf{y}_{0})\) will return the distributions \(p(u_{0}|t_{0})\) and \(p(t_{0})\), as well as the clustering \(p(t_{0}|\mathbf{y}_{0})\), which maps the observed sequence, \(\mathbf{y}_{0}\), onto a cluster index \(t_{0}\in\mathcal{T}\). Hence, the \(|\mathcal{Y}|^{2}\) outputs of the bit channel are quantized into \(|\mathcal{T}|\) clusters. The joint distribution of bit channel of \(u_{1}\) equals:  
\[p(u_{1},y_{0},y_{1},u_{0})=\sum_{x_{0}}\sum_{x_{1}}p(u_{0},u_{1},x_{0},x_{1},y _{0},y_{1}). \tag{18}\]  
Figure 5: Information bottleneck graph for (**a**) the bit channel of \(u_{0}\) which maps outputs \(y_{0},y_{1}\) onto \(|\mathcal{T}|\) clusters, labeled \(t_{0}\), treating \(u_{0}\) as the relevant variable. (**b**) The bit channel of \(u_{1}\) which maps the outputs \(y_{0},y_{1},u_{0}\) onto \(|\mathcal{T}|\) clusters, labeled \(t_{1}\), treating \(u_{1}\) as the relevant variable. The information bottleneck algorithm produces the distributions \(p(u_{1}|t_{1})\), \(p(t_{1})\) and \(p(t_{1}|\mathbf{y}_{1})\) for the joint distribution of Equation (18). The mapping \(p(t_{1}|\mathbf{y}_{1})\) clusters the \(2\cdot|\mathcal{Y}|^{2}\) outputs of the bit channel into \(|\mathcal{T}|\) clusters. Thus, the output alphabet of both the bit channels is compressed to size \(|\mathcal{T}|\).