How is belief propagation and Galleger's algorithm implemeted for BEC?

Question

In BEC, we know for certain that the bits are either correct or erasure thus when we compute the log likelihood ratio (LLR) in belief propagation can only be inf, -inf and 0.

How can we implement the BP for a channel that is binary erasure?

I also tried to do the Galleger's algorithm. Here i do the bits-fliping to 1 or -1 whenever the incoming message of the check node is erased, 0.

Does it mean that the algorithm can only correct 50% of the error bit? Is this the way to implement the Galleger's algorithm for BEC?

Answer 1

You can still write loglikelihood for channel LLRs and can run the BP algorithm as well. Assume that you have an erasure channel with an erasure probabilty of $0<\epsilon<1$.

In case erasing event occurs for the bit $d_i$ and received as $r_i=e$ where $e$ denotes the erased symbols, therefore the channel LLR will be written as $$ L_c(d_i|r_i=e) = \log \left( \frac{\Pr\left\{d_i=0 | r_i=e\right\}}{\Pr\left\{d_i=1 | r_i=e\right\}} \right) = \log \left( \frac{\epsilon}{\epsilon} \right) = 0$$ If no erasing occurs and $r_i=0$ $$ L_c(d_i|r_i=1) = \log \left( \frac{\Pr\left\{d_i=0 | r_i=0\right\}}{\Pr\left\{d_i=1 | r_i=0\right\}} \right) = \log \left( \frac{1}{0} \right)= \infty$$ If no erasing occurs and $r_i=1$ $$ L_c(d_i|r_i=1) = \log \left( \frac{\Pr\left\{d_i=0 | r_i=1\right\}}{\Pr\left\{d_i=1 | r_i=1\right\}} \right) = \log \left( \frac{0}{1} \right)= -\infty$$

After calculating the channel LLRs, you can send them to the BP decoder. For practical purposes $\infty$ and $-\infty$ can be replaced with $+1$ and $-1$ "only for min-sum algorithm".