Optimization of degree distributions for the Binary Erasure Channel (BEC), see lecture notes "Modern Error Correction".

The design goal is usually to maximize the rate of the code for a certain target $\epsilon$. 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$.

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 \epsilon\left(1-\rho\left(1-\frac{j}{D}\right)\right)^{i-1}-\frac{j}{D} \leq 0,\quad \forall j \in \{1,\ldots, D\} \\ & & & \lambda_2 \leq \frac{1}{\epsilon\rho^\prime(1)} = \frac{1}{\epsilon\sum_{i=2}^{\mathtt{c}_{\max}}(i-1)\rho_i} \end{aligned} \end{equation*}

This linear program works by first fixing an average check node degree $\mathtt{c}_{\text{avg}}$ and for a given $\epsilon$, we sweep through our range of interest and select the $\mathtt{c}_{\text{avg}}$ leading to the largest rate $r_d$, i.e., to the largest $\sum\frac{\lambda_i}{i}$. Remember that \begin{equation*} r_d = 1 - \frac{1}{\mathtt{c}_{\text{avg}}\sum\frac{\lambda_i}{i}} \end{equation*}

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

1. We start with $\epsilon=0.5$, and set $\Delta_{\epsilon} = 0.5$
2. We sweep through $\mathtt{c}_{\text{avg}}$, carry out the optimization, and select that $\mathtt{c}_{\text{avg}}$ leading to the largest $r_d = 1 - \left(\mathtt{c}_{\text{avg}}\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 $\epsilon \leftarrow \epsilon + \frac{\Delta_{\epsilon}}{2}$, otherwise set $\epsilon \leftarrow \epsilon - \frac{\Delta_{\epsilon}}{2}$
4. If $\Delta_{\epsilon} \geq T_{\Delta}$, set $\Delta_{\epsilon}\leftarrow \frac{\Delta_{\epsilon}}{2}$ and go to Step 2)
5. Pick the best $\mathtt{c}_{\text{avg}}$ from step 2) and the corresponding $\lambda_i$'s