Optimization of Degree Distributions for the Binary Erasure Channel

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