# Adaptive Learned Belief Propagation for Decoding Error-Correcting Codes
## 5 Adaptive Learned Message Passing Algorithms
### Parallel Decoders  
_Architecture_: In parallel decoders, \(g(. )\) is found through searching. Here, \(\gamma^{(t)}\) takes value in a discrete set \(\mathcal{X}_{t}=\left\{x_{1}^{(t)},x_{2}^{(t)},\cdots,x_{K_{t}}^{(t)}\right\}\), \(K_{t}\in\mathbb{N}\), and thus \(\boldsymbol{\gamma}\in\mathcal{X}:=\prod_{t=1}^{T}\mathcal{X}_{t}=\left\{ \boldsymbol{\gamma}_{1},\cdots,\boldsymbol{\gamma}_{t}\right\}\). The parallel decoders consist of \(\
u\) independent decoders \(\boldsymbol{\hat{y}}_{i}=\mathcal{D}_{\boldsymbol{\gamma}_{i}}(\mathbf{y})\), \(i\in[\
u]\), running concurrently. Since \(\Pr(\boldsymbol{\hat{y}}_{i}\
eq\mathbf{c})\) in (13) is generally intractable, a sub-optimal \(g(. )\) is selected as follows. At the end of decoding by \(\mathcal{D}_{\boldsymbol{\gamma}_{i}}\), the syndrome \(\boldsymbol{s}_{i}=\boldsymbol{\hat{y}}_{i}H^{\mathsf{T}}\) is computed. Let  
\[i^{*}=\text{argmin}_{i\in[\
u]}\left\{||\boldsymbol{s}_{i}||_{H}:\ \boldsymbol{s}_{i}= \boldsymbol{\hat{y}}_{i}H^{\mathsf{T}}\right\}, \tag{14}\]  
be the index of the decoder whose syndrome has the smallest Hamming weight. Then, \(g(\mathbf{y})=\boldsymbol{\gamma}_{i^{*}}\), and \(\boldsymbol{\hat{y}}=\mathcal{D}_{\boldsymbol{\gamma}_{i^{*}}}(\mathbf{y})\). In practice, the search can be performed up to depth \(T_{1}=5\) iterations. However, the BP decoder often has to run for more iterations. Thus, a WBP decoder with weights \(\boldsymbol{\gamma}_{i^{*}}\) can continue the output with \(T_{2}\) iterations. **Remark 2**: _The decoder obtained via (14) is generally sub-optimal. Minimizing \(\|\boldsymbol{s}_{i}\|_{H}\) does not necessarily minimize the number of errors. However, for random codes, the decoder obtained from (14) outperforms the static decoder._  
**Remark 3**: _If \(D_{\boldsymbol{\gamma}_{1}}\) and \(D_{\boldsymbol{\gamma}_{2}}\) yield the same number of errors, the decoder with the smaller weight vector is selected, which tends to output smaller LLRs._  
_Obtaining \(x_{k}^{(t)}\) from the distribution of weights._: The values of \(x_{k}^{(t)}\) can be determined by dividing a sub-interval in \([0,1]\) uniformly. The resulting parallel WMS decoder outperforms WMS; however, the performance can be improved by choosing \(x_{k}^{(t)}\) based on the probability distribution of the weights. The probability distribution of the channel noise induces a distribution on \(\mathbf{y}\) and consequently on \(\boldsymbol{\gamma}=g(\mathbf{y})\). Let \(\Gamma^{(t)}\) be a random variable representing \(\gamma^{(t)}\). Denote the corresponding mean by \(\theta^{(t)}\), standard deviation by \(\sigma^{(t)}\), and the cumulative distribution function by \(C_{t}(. )\triangleq C_{\Gamma^{(t)}}(.)\). For \(\epsilon>0\), set  
\[x_{k}^{(t)}=\inf\Bigl{\{}x:C_{t}(x)>\frac{\epsilon}{2}+(k-1)\frac{1-\epsilon}{ K_{t}}\Bigr{\}}. \tag{15}\]  
The numbers \(x_{1}^{(t)}<x_{2}^{(t)}<\cdots<x_{K_{t}}^{(t)}\) partition the real line into intervals such that \(\Pr\Bigl{(}\Gamma^{(t)}\in[x_{1}^{(t)},x_{K_{t}}^{(t)}]\Bigr{)}=1-\epsilon\) and \(\Pr\Bigl{(}\Gamma^{(t)}\in[x_{k}^{(t)},x_{k+1}^{(t)}]\ \big{|}\ \Gamma^{(t)}\in[x_{1}^{(t)},x_{K_{t}}^{(t)}] \Bigr{)}=\frac{1}{K_{t}}\). In practice, \(\Gamma^{(t)}\) has a distribution close to Gaussian, in which case \(x_{k}^{(t)}\) values are given by the explicit formulas in Lemma 1. **Lemma 1**: _Let \(\Gamma^{(t)}\) have a cumulative distribution function \(C_{t}(. )\) that is continuous and strictly monotonic. For \(k\in[K_{t}]\),_  
\[x_{k}^{(t)}=C_{t}^{-1}\biggl{(}\frac{\epsilon}{2}+(k-1)\frac{1-\epsilon}{K_{t} }\biggr{)}.\]  
_If \(\Gamma^{(t)}\) has a Gaussian distribution with a mean \(\theta^{(t)}\) and standard deviation \(\sigma^{(t)}\), then_  
\[x_{k}^{(t)}=\theta^{(t)}+\sqrt{2}\sigma^{(t)}\ \text{erfc}^{-1}\Bigl{(}2- \epsilon-\frac{2(k-1)(1-\epsilon)}{K_{t}}\Bigr{)}, \tag{16}\]  
_where erfc is the complementary error function._Proof. : The proof is based on elementary calculus. _Obtaining the distribution of weights_: To apply (15) or (16), \(C_{t}(. )\) is required.