# Coarsely Quantized Decoding and Construction of Polar Codes Using the Information Bottleneck Method
## 2 Prerequisites
### Polar Codes  
A polar code with length \(N=2^{n}\), where \(n=1,2\dots\), is described by its \(N\times N\) generator matrix  
\[\mathbf{G}_{N}=\mathbf{F}^{\otimes n}\mathbf{B}, \tag{1}\]  
where matrix \(\mathbf{F}= \begin{bmatrix}1&1\\ 0&1\end{bmatrix} \) and \(\mathbf{B}\) is the _bit reversal_ permutation matrix [13]. While the encoding follows \(\mathbf{x}=\mathbf{G}_{N}\mathbf{u}\), the FFT-like structure of \(\mathbf{F}^{\otimes n}\) allows efficient encoding with a complexity of \(O(N\log_{2}N)\). For a code rate of \(K/N\), \((N-K)\) bits in the encoder input \(\mathbf{u}=[u_{0},\dots,u_{N-1}]^{T}\) are set to fixed values, e.g., \(0\)'s, and referred to as _frozen_ bits. The values and location of the frozen bits are known to the decoder. The remaining \(K\) positions in \(\mathbf{u}\), specified in the _information_ set, \(\mathcal{A}\), carry the information bits. The matrix \(\mathbf{F}\) serves as the building block of polar codes in the sense that all the processing steps required for encoding, code construction, and decoding are defined over it. From an encoding perspective, \(\mathbf{F}\) encodes the bits in \(\mathbf{u}=[u_{0},u_{1}]^{T}\) into codeword \(\mathbf{x}=[x_{0},x_{1}]^{T}\), which is received as \(\mathbf{y}=[y_{0},y_{1}]^{T}\) after transmission through a symmetric discrete memoryless channel described by transition probabilities \(p(y|x)\). Figure 1 depicts the factor graph of this elementary setup of polar codes. The key concept of polar codes lies in the definition of virtual bit channels between each element in \(\mathbf{u}\) and the channel output, \(\mathbf{y}\). Two bit channels are defined over the building block. The first bit channel, described by transition probabilities \(p(y_{0},y_{1}|u_{0})\), is established between \(\mathbf{y}_{0}=[y_{0},y_{1}]^{T}\) and \(u_{0}\) and ignores \(u_{1}\):  
\[p(\mathbf{y}_{0}|u_{0})=\frac{1}{2}\sum_{u_{1}\in\{0,1\}}p(y_{0}|u_{0}\oplus u _{1})p(y_{1}|u_{1}). \tag{2}\]  
Figure 1: Factor graph of the building block (dashed rectangle) of a polar code along with the transmission channel. The second virtual channel, described by transition probabilities \(p(y_{0},y_{1},u_{0}|u_{1})\), treats \(u_{1}\) as input and \(\mathbf{y}_{1}=[y_{0},y_{1},u_{0}]^{T}\) as output, assuming the true knowledge of \(u_{0}\):  
\[p(\mathbf{y}_{1}|u_{1})=\frac{1}{2}p(y_{0}|u_{0}\oplus u_{1})p(y_{1}|u_{1}). \tag{3}\]  
If \(P_{e}\), \(P_{e}^{0}\), and \(P_{e}^{1}\) are the probabilities of error of the physical channel, the bit channel of \(u_{0}\) and the bit channel of \(u_{1}\), respectively, then \(P_{e}^{0}\geq P_{e}\geq P_{e}^{1}\)[13]. Hence, the setup of Figure 1 transforms two instances of the physical channel into qualitatively different synthetic channels. Figure 2 shows the factor graph of a polar code for \(N=4\), where the transmission channel is implicitly included, i.e., the right-most variable nodes correspond to received coded bits. The code structure is composed of the building blocks arranged in vertical columns, referred to as _levels_, \(j\), with right-most being \(j=1\) and left-most being \(j=n\). Within a level \(j\), variable nodes to the left of the check nodes are labeled with \(j\), while those on the right of the check nodes are labeled with the level \(j-1\). Thus, every variable node has a label \(v_{i,j}\) with \(i=0,1,\ldots,N-1\) and \(j=0,\ldots,n\). Then, \(v_{i,n}\) are the encoder inputs \(u_{i}\) and \(v_{i,0}\) are the channel outputs \(y_{i}\). It can be seen in Figure 2 that bit channels of a polar code are obtained after recursive application of the polarizing transform of Figure 1. Each application of the polarization transform at level \(j\) in the code structure manufactures a pair of bit channels from a pair of qualitatively similar (bit) channels from level \(j-1\), similar to Equations (2) and (3), where the bit channel corresponding to the upper branch is worse, while the one corresponding to the lower branch is better.