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


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.
enter image description here

Best Answer

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:

enter image description here

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.