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.

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

probability

## 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:

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:

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.