# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 3 Polar Code Construction Using the Information Bottleneck Method
### Information Bottleneck vs. Tal and Vardy Construction  
In this section, polar code construction using the information bottleneck method and the Tal and Vardy method are compared. The working principle behind both construction methods is the same: Compress the output alphabet of bit channels at each level \(j\) while keeping the loss of mutual information caused by the compression as small as possible. In fact, the _degrading merge_ procedure of [PERSON] and [PERSON]'s construction ([23] Algorithm C) is known as the modified agglomerative information bottleneck algorithm in the information bottleneck circle [36]. However, since [PERSON] and [PERSON]'s construction method also uses the Bhattacharyya parameter for designating a bit channel to be frozen or not, it is a fusion of the information bottleneck method and [PERSON]'s approximation [13]. Some further differences between the two methods are as follows. The rule used to choose the quantized alphabet size \(|\mathcal{T}|\) in [PERSON] and [PERSON]'s method is different than that used in the information bottleneck method. [PERSON] and [PERSON]'s method chooses \(|\mathcal{T}|\) such that the bounds obtained from degrading and upgrading merge are very close, and thus, the values \(|\mathcal{T}|=256\) or \(512\) are suggested. On the other hand, the choice of \(|\mathcal{T}|\) in the information bottleneck method is driven by tracking the amount of relevant mutual information retained during the density evolution across the levels of a polar code. For that purpose, the rate of preserved mutual information for quantizing the \(i\)th (intermediate) bit channel at a level \(j\) is defined as \(R_{i,j}=I(V_{i,j};T_{i,j})/I(V_{i,j};\mathbf{Y}_{i,j})\), where \(I(V_{i,j};T_{i,j})\) is the preserved mutual information after compression and \(I(V_{i,j};\mathbf{Y}_{i,j})\) is the mutual information before the compression. Then, the rate of mutual information preservation \(R_{j}\) for the \(j\)th level is defined as the mean of the \(R_{i,j}\) values. For a codeword length of \(N=2^{n}\), the overall rate of information preservation is computed as a cumulative product, \(R_{cum}\):  
\[R_{cum}=R_{1}\times R_{2}\times\cdots\times R_{n}. \tag{20}\]  
Figure 7 shows the evolution of \(R_{cum}\) over the levels in the polar code structure for different compressed cardinalities \(|\mathcal{T}|\). Considering a polar code with length \(N=512\), already for a quite small number of 16 clusters, approximately 98% of relevant information is preserved over all levels. Increasing the number of clusters further to 32 yields only a small gain, i.e., 99% of relevant information is preserved. Hence, the information bottleneck construction method is computationally more efficient than [PERSON]'s method due to the use of small values of \(|\mathcal{T}|\). The information bottleneck construction method benefits from the availability of different algorithms and hence offers to choose an algorithm according to the problem at hand, e.g., an information bottleneck algorithm with a nonbinary relevant variable can be chosen for constructing nonbinary polar codes. Another difference between the two construction methods is that while [PERSON]'s method incorporates the channel quantizer into the merging operations at level \(j=1\), the information bottleneck method separates the channel quantizer design from the code structure. This adds flexibility to the information bottleneck construction method and facilitates construction of polar codes for other channel models or modulation schemes. For instance, replacing the channel quantizer of Section 2.4 with the one from [37], i.e., designed using the information bottleneck method for an AWGN channel with 16-QAM input symbols, the construction method can be adapted for constructing a polar codes for a higher order modulation scheme. Figure 7: Plot of the cumulative product \(R_{cum}\) indicating the amount of mutual information preserved over the levels of a half-rate polar code with \(N=512\) depending on the number of clusters \(|\mathcal{T}|\).