[Math] How do factor graph and sum-product algorithm work

Question

I'm reading a tutorial on factor graph and its sum-product algorithm. The tutorial is at http://www.isiweb.ee.ethz.ch/papers/arch/aloe-2004-spmagffg.pdf. What I don't understand is the example on page 19. I don't know how they come up with these number! Could you please help me understand where the numbers come from? Thank you.

Answer 1

Disclaimer: I have absolutely no knowledge of parity check codes.

---

Everything up to figure c) is just the factor graph formulation of the given example problem.

To get to figure d), the message update rules given in Table 1 below the example are used. For convenience, I copy-pasted these here from the source:

For the calculation of the upper message $(0.5, 0.5)$, we employ the first update rule (equality node): $\mu_Z(0) = 0.9 \cdot 0.1=0.09$ and $\mu_Z(1) = 0.1 \cdot 0.9 = 0.09$. This, normalized to total probability $1$, is equivalent to the given value of $(0.5,0.5)$. [A "suitably scaled" version of the message, cf. the source.]

For the calculation of the lower message $(0.82, 0.18)$, we employ the second update rule (addition modulo 2) to directly obtain this result: $\mu_z(0) = \mu_X(0) \cdot \mu_Y(0) + \mu_X(1) \cdot \mu_Y(1) = 0.9 \cdot 0.9 + 0.1 \cdot 0.1 = 0.82$, and equivalently for $\mu_Z(1)=0.18$.

To get to figure e), we employ these update rules again, but with different incoming messages for each node:

• For the calculation of the leftmost downgoing message $(0.5, 0.5)$, we have the two incoming messages $(0.5, 0.5)$ from the equality node and $(0.9, 0,1)$ from the second received zero digit, cf. fig. c). Plugging these into the update equation of the addition modulo two node yields $(0.5, 0.5)$ again, as displayed in the figure.
• The same is true for the second downgoing message $(0.5, 0.5)$, except that this time the second incoming message next to the one from the equality node is the message from the first received zero digit, which is again $(0.9, 0.1)$.
• For the calculation of the third downgoing message $(0.976, 0.024)$, we have the two incoming messages $(0.82, 0.18)$ from the addition node and $(0.9, 0.1)$ from the rightmost received zero digit. Plugging these into the update equation of the equality node yields $(0.738, 0.018)$, which, normalized to total probability $1$ yields $(0.976, 0.024)$, as displayed in the figure.
• Equivalently, the final downgoing message $(0.336, 0.664)$ is calculated from the incoming messages $(0.82, 0.18)$ and $(0.1, 0.9)$.

Finally, the a posteriori probabilities displayed in figure f) are calculated by multiplication of the two messages (ingoing and outgoing) on the corresponding edge, and normalization.