# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 2 Prerequisites
### Information Bottleneck Method  
The information bottleneck method [3; 4] is a generic clustering framework with its roots in the field of machine learning. Figure 3a visualizes the elementary setup of the framework. By designating a random variable \(X\) as the _relevant_ random variable, the principal aim of the information bottleneck method is to extract as much information about \(X\) contained in an _observation_\(Y\) as possible and capture this _relevant_ information in a _compression_ variable \(T\). More precisely, a compression mapping \(p(t|y)\) is determined, which maps the event space \(\mathcal{Y}\) of the observed random variable onto the event space \(\mathcal{T}\) of a compression variable, such that \(|\mathcal{T}|\ll|\mathcal{Y}|\) while \(I(X;T)\) is maximized. In other words, the framework aims to simultaneously minimize the _compression_ information \(I(Y;T)\) and maximize the relevant information \(I(X;T)\). The realizations of \(T\) are referred to as _clusters_ whose labels can be chosen arbitrarily. We label these clusters with unsigned integer values, i.e., \(\mathcal{T}=\{0,1,\ldots,|\mathcal{T}|-1\}\). The so-called information bottleneck graph [33] provides a compact visualization of this principle in Figure 3b where the observed random variable \(Y\) is compressed into \(T\), while retaining the relevant information about \(X\). This problem can be posed as a Lagrangian optimization problem and solved by minimizing the so-called information bottleneck functional [3]\[\mathcal{F}\{p(t|y)\}=I(Y;T)-\beta I(X;T). \tag{13}\]  
The non-negative Lagrangian multiplier \(\beta\) in (13) serves as trade-off parameter between information preservation and compression. In extreme cases, \(\beta\to\infty\) corresponds to maximum information preservation, while \(\beta\to 0\) corresponds to maximum compression. In this work, we are interested in obtaining the maximum relevant information \(I(X;T)\), i.e., \(\beta\to\infty\). The compression results from the choice of the (constrained) cardinality of \(T\), i.e., \(|\mathcal{T}|\). Note that after performing a mapping \(p(t|y)\), any physical meaning contained in \(Y\) is lost, i.e., the compression variable \(T\) on its own has no direct meaning and belongs purely to an abstract domain. Hence, a coupling between the relevant variable \(X\) and \(T\) is needed, which is given by \(p(x|t)\). Only with the distribution \(p(x|t)\) can the meaning of a cluster index \(t\) for a certain \(x\) be recaptured. Several information bottleneck algorithms exist which obtain the distributions \(p(t|y)\), \(p(x|t)\) and \(p(t)\) from the joint distribution \(p(x,y)\)[3; 4]. It can be shown that choosing \(\beta\to\infty\) yields a _deterministic_ clustering \(p(t|y)\in\{0,1\}\)[4]. A deterministic clustering is convenient from an implementation perspective as it can be realized as a static lookup table. An algorithm optimized for deterministic mappings that is used in this work is the modified sequential information bottleneck algorithm from [1; 2], whose Python implementation is available at [34]. The information bottleneck method is a generic framework in the sense that it can be used for quantization of an observed quantity in any problem where the joint distribution \(p(x,y)\) of observation \(y\) and relevant quantity \(x\) is available. With the appropriate joint distribution \(p(x,y)\) at hand, the framework has been used in the field of communication for channel estimation [35], to quantize the AWGN channel and the node operations of LDPC decoders [1; 2; 7], the bit channels of a polar code [25], as well as the decoding operations of SC and SCL decoding of polar codes [26]. Among these applications, we explain the AWGN channel quantization using the information bottleneck framework [1; 2] as an illustrative example in the following.