## 3 Information Bottleneck Decoders for Irregular LDPC Codes Using Message Alignment
### Message Alignment--An Information-Theoretic Perspective  
In Figure 5a we noted by comparing the cross and dot markers that providing the node degree \(d\) together with the respective cluster index \(t\) is required to recover the proper belief on the relevant bit \(X\). However, this approach would result in a very impractical decoder that is tailored to the actual connections between variable nodes and check nodes in a particular code. We propose to solve the underlying message alignment problem using information-theoretical concepts. Therefore, in this subsection, we first derive an information-theoretic formulation of the message alignment problem.  
Figure 5: Averaged and original cluster meaning of variable nodes with degree two and four (**a**) without and (**b**) with message alignment.  
From an information theoretic point of view, \(I(X;T,D)\) upper-bounds the information on \(X\) of a node receiving an incoming discrete message \(t\). Rewriting \(I(X;T,D)\) using the chain rule of mutual information yields  
\[I(X;T,D)=I(X;D|T)+I(X;T), \tag{5}\]  
where \(I(X;T)\) is the information about \(X\) obtained by receiving \(T\) alone and \(I(X;D|T)\) is the _additional_ information gained by also providing the node degree if the cluster index is already known. In turn, if \(I(X;D|T)\approx 0\), from an information-theoretic point of view, conveying the delivering node degree \(d\) in addition to the cluster index yields no information gain about \(X\). Thus, we propose a message mapping construction which minimizes \(I(X;D|T)\) such that exchanging the node degree _in addition_ to the cluster index yields no information gain. Expanding \(I(X;T,D)\) for a variable node yields  
\[I(X;D|T) =\sum_{t\in T}\sum_{d=2}^{\omega_{\text{max}}}\omega_{d}p_{d}(t)D_ {KL}\{p_{d}(x|t)||p_{\bar{d}}(x|t)\} \tag{6}\] \[=\mathbb{E}_{t,d}\left[D_{KL}\{p_{d}(x|t)||p_{\bar{d}}(x|t)\} \right], \tag{7}\]  
where \(D_{KL}\{.||.\}\) denotes the Kullback-Leibler divergence.  
The result from (7) has a direct intuitive link to Figure 5a. If the cross and dot markers would nearly superimpose for a particular cluster, the change in meaning introduced by averaging would be negligible. Similarly, in this case the Kullback-Leibler divergence between \(p_{d}(x|t)\) and \(p_{\bar{d}}(x|t)\) would also be small. If this holds on average for all clusters and node degrees, \(I(X;D|T)\approx 0\). Motivated by the observation that similar meanings are expressed by different cluster indices paired with (7), our general idea is to map the different \(t_{d}\) onto a variable \(z_{d}\) such that the meanings \(p_{d}(x|z)\) are aligned. Consequently, we define message alignment as a reordering strategy described by a deterministic mapping \(p_{d}(z|t)\) to obtain  
\[\min_{p_{d}(z|t)}\mathbb{E}_{z,d}\left[D_{KL}\{p_{d}(x|z)||p_{\bar{d}}(x|z)\} \right],\forall d. \tag{8}\]  
That is, message alignment assigns those indices \(t_{d}\) with meanings \(p_{d}(x|t)\) to a new cluster index \(z_{d}\) which represents approximately the same meaning with respect to \(X\). Figure 5b depicts the aligned meanings after application of the message alignment algorithm presented in the next subsection. As a consequence, \(I(X;D|Z)\approx 0\) and now \(z\) instead of \(t\) is exchanged over the edges of the Tanner graph.