# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 3 Polar Code Construction Using the Information Bottleneck Method
### [PERSON]'s Construction  
The key step of [PERSON]'s construction method is the _degrading_ procedure which merges the elements in the output alphabet of a binary input discrete memoryless symmetric channel. Assume that the output alphabet \(\mathcal{Y}\) of the channel characterized by \(p(y|x)\) in Figure 1 has \(|\mathcal{Y}|\) elements which we wish to reduce to \(|\mathcal{T}|<|\mathcal{Y}|\). The target alphabet size \(|\mathcal{T}|\) is referred to as the fidelity parameter in [23] and denoted by \(\mu\). The output alphabet size is reduced by one, if two elements \(y_{a},y_{b}\in\mathcal{Y}\) are merged into a single element \(y_{ab}\). The output alphabet becomes \(\mathcal{Y}\setminus\{y_{a},y_{b}\}\cup\{y_{ab}\}\), and the transition probabilities are updated as:  
Figure 6: Information bottleneck graph of a polar code with length \(N=4\). The outputs of the bit channel experienced by each node \(v_{i,j}\) are clustered into a compressed random variable \(T_{i,j}=t_{i,j}\in\{0,\ldots,|\mathcal{T}|-1\}\), where \(i=0,1,\ldots,N-1\) indicates the stage, while \(j=0,\ldots,n\) represents the level in the code structure. \[p(y|x)= \begin{cases}p(y_{a}|x)+p(y_{b}|x)&y=y_{ab}\\ p(y|x)&\text{otherwise}.\end{cases}  \tag{19}\]  
Such a merging always causes a loss in the capacity of the channel amounting to \(\delta I\geq 0\). [PERSON]'s degrading merge procedure chooses the elements to be merged wisely; the pair of elements to be merged is selected such that their merging will cause the smallest amount of loss \(\delta I\). Such a degrading merge is performed repeatedly, until the output alphabet size of the channel is reduced to the desired value of \(|\mathcal{T}|\). The bit channels synthesized from such a channel using Equations (2) and (3) will have an output alphabet size of \(|\mathcal{T}|^{2}\) and \(2|\mathcal{T}|^{2}\), respectively. The aforementioned degrading merge is applied to each bit channel such that their output alphabet sizes are reduced to \(|\mathcal{T}|\). For constructing a polar code with \(N>2\), the degrading merge is used after application of the polarization transform at each level, and the output alphabet size of the (intermediate) bit channels is kept restricted to \(|\mathcal{T}|\). Equation (11) is then used to compute the error probability of each degraded bit channel, which serves as an upper bound on the error probability of the unquantized bit channel. [PERSON] and [PERSON] performed the degrading merge in an efficient way by exploiting the symmetry of the channel. Firstly, the elements of \(\mathcal{Y}\) are sorted with respect to their LLRs. In the sorted output alphabet, only pairs of consecutive elements need to be considered for merging ([23], Theorem 8). Secondly, due to the channel symmetry, for each \(y\in\mathcal{Y}\) there exists a \(\bar{y}\in\mathcal{Y}\), referred to as the _conjugate_ of \(y\), such that \(p(y|x=0)=p(\bar{y}|x=1)\). This fact is exploited in the sense that computations for mergers are done for half of the channel output alphabet \(\mathcal{Y}^{+}\), where:  
\[\mathcal{Y}^{+}=\left\{y\in\mathcal{Y}:\log p(y|x=0)/p(y|x=1)>0\right\}.\]  
When a pair \(y_{a},y_{b}\in\mathcal{Y}^{+}\) is merged into \(y_{ab}\), their conjugates \(\bar{y}_{a},\bar{y}_{b}\in\mathcal{Y}\setminus\mathcal{Y}^{+}\) are also merged into \(\bar{y}_{ab}\). The final code construction algorithm computes the upper bounds on the error probabilities of the bit channels using the degrading merge procedure and also computes the Bhattacharyya parameter for each bit channel. The smallest of the two is then considered for including a bit channel into information set \(\mathcal{A}\). In order to track the inaccuracy introduced by the quantization, another approximation, namely, the _upgrading_ merge is used. For every bit channel which is quantized using the degrading merge, the upgrading merge synthesizes another bit channel, with alphabet size \(|\mathcal{T}|\), which is _upgraded_, i.e., its probability of error is equal or smaller than that of the channel under consideration.