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

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?

• In BEC decoding by BP makes progress in those situations, where only a single erased bit participates in a parity check. After all, on such an occasion the parity check allows you to solve for the value of the erased bit. It is a bit kludgy to think about this in terms of LLRs given that in a BEC the LLRs are either $\pm\infty$ or $0$. Feb 23 at 5:45

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".