Logo der Uni Stuttgart
Optimization of Degree Distributions for the AWGN Channel

Optimization of degree distributions for the Additive White Gaussian Noise (AWGN) channel, see lecture notes "Modern Error Correction".

The design goal is usually to maximize the rate of the code for a certain target SNR (or an equivalent $\mu_c$). This corresponds to utilizing the least amount of redundancy for successful transmission. Maximizing the rate $r_d$ for a given $\rho(Z)$ (with maximum check node degree $\mathtt{c}_{\max}$) corresponds to maximizing the expression $\sum_{i=2}^{\mathtt{v}_{\max}}\frac{\lambda_i}{i}$, which is again linear in $\lambda_i$. We can thus formulate a linear program that finds those $\lambda_i$ ($i\in\{2,3,\ldots,\mathtt{v}_{\max}\}$) that maximize the rate $r_d$ for a given $\epsilon$. As a constraint, we use EXIT charts where the $J$-function interrelates mutual information and mean of the Gaussian distribution and is defined as \begin{equation*} J(\mu) = 1 - \int\limits_{-\infty}^{\infty} \frac{e^{-(\tau-\mu)^2/(4\mu)}}{\sqrt{4\pi\mu}} \log_2\left(1+e^{-\tau}\right)d\tau \end{equation*} and can be conveniently approximated by \begin{equation*} J(\mu) \approx \left(1 - 2^{-H_1(2\mu)^{H_2}}\right)^{H_3}\quad \text{and}\quad J^{-1}(I) = \frac{1}{2}\left(-\frac{1}{H_1}\log_2\left(1-I^{\frac{1}{H_3}}\right)\right)^{\frac{1}{H_2}} \end{equation*} with $H_1 = 0.3073$, $H_2 = 0.8935$, $H_3 = 1.1064$.

The degree distribution is obtained by solving the following linear program \begin{equation*} \begin{aligned} & \underset{\lambda_2,\ldots,\lambda_{\mathtt{v}_{\max}}}{\text{maximize}} & & \sum_{i=2}^{\mathtt{v}_{\max}}\frac{\lambda_i}{i} \\ & \text{subject to} & & \lambda_i \geq 0, \quad \forall i \in\{2,3,\ldots,\mathtt{v}_{\max}\} \\ & & & \sum_{i=2}^{\mathtt{v}_{\max}}\lambda_i = 1 \\ & & & \sum_{i=2}^{\mathtt{v}_{\max}}\lambda_i\cdot J\left(\mu_c + (i-1)J^{-1}\left(\frac{j}{D}\right)\right) > \\ & & & \qquad \quad 1 - J\left(\frac{1}{\mathtt{c}-1}J^{-1}\left(1-\frac{j}{D}\right)\right),\quad\forall j \in \{0,\ldots,D-1\}\\ & & & \lambda_2 \leq \frac{e^{\frac{\mu_c}{4}}}{(\mathtt{c}-1)} \end{aligned} \end{equation*}

This linear program works by first fixing an average check node degree $\mathtt{c}$ (note that in this example, we only allow for integer check node degrees) and for a given $\mu_c$, we sweep through our range of interest and select the $\mathtt{c}$ leading to the largest rate $r_d$, i.e., to the largest $\sum\frac{\lambda_i}{i}$.

For the optimization, we fix a threshold $T_{\Delta}$, and employ the following iterative binary search procedure:

  1. We start with $\mu_c=10$, and set $\Delta_{\mu} = 10$
  2. We sweep through $\mathtt{c}$, carry out the optimization and select that $\mathtt{c}$ leading to the largest $r_d = 1 - \left(\mathtt{c}\sum\frac{\lambda_i}{i}\right)^{-1} =: r_{d,\max}$
  3. If that $r_{d,\max} > r_{\text{target}}$ ($r_d$ from step 2), then set $\mu_c \leftarrow \mu_c - \frac{\Delta_{\mu}}{2}$, otherwise set $\mu_c \leftarrow \mu_c + \frac{\Delta_{\mu}}{2}$
  4. If $\Delta_{\mu} \geq T_{\Delta}$, set $\Delta_{\mu}\leftarrow \frac{\Delta_{\mu}}{2}$ and go to Step 2)
  5. Pick the best $\mathtt{c}$ from step 2) and the corresponding $\lambda_i$'s