Belief propagation is a heuristic procedure for computing marginal probabilities of graphical models.
We choose to use a slightly different belief propagation implementation compared to [1]}, as ours seems to be more natural for the bit-flip noise model.
We divide the lattice into \(2\times 2\)  unit cells.
Let \(G\)  be a bipartite graph, where one part corresponds to unit cells, and another part to coarse-grained edges.
Two vertices in \(G\)  is connected when the coarse-grained edge is adjacent to the unit cell.
This later decides how the messages flow in the graph.
However, we assign two variables \(\lbrace x(e_i),x(e_j)\rbrace \)  to each vertex corresponding a coarse-grained edge which \(e_i\)  and \(e_j\)  form.
In this section, the symbol \(e\)  or \(e_i\)  will denote original edges of the lattice (i.e. not coarse-grained).
We define \(E\)  to be the set of all edges \(e\) , \(E_{cg} \subset E\)  to be the set of \(e\)  which are components of coarse-grained edges (i.e. red edges in fig:lattice), and \(\bar{E}_{cg} = E \setminus E_{cg}\) .
Given a syndrome \(S\) , the unnormalized probability of an error configuration \(\vec{x}\equiv \lbrace x(e)\rbrace _{e\in E}\)  can be written as
\(p(\vec{x}) = g(S, \vec{x})\prod _{e\in E} p_e(x(e)) ,\) 
