Error Correction on a Tree: An Instanton Approach

We introduce a method that allows analytical or semianalytical estimating of the post-error correction bit error rate (BER) when a forward-error correction is utilized for transmitting information through a noisy channel. The generic method that applies to a variety of error-correction schemes in the regimes where the BER is low is illustrated using the example of a finite-size code approximated by a treelike structure. Exploring the statistical physics formulation of the problem we find that the BER decreases with the signal-to-noise ratio nonuniformly, i.e., crossing over through a sequence of phases. The higher the signal-to-noise ratio the lower the symmetry of the phase dominating BER.

Figure 1

$m=2,l=3$, and $n=3$. Instantons and bifurcation picture for a complete optimization procedure (no symmetry was a priori assumed). The first line area of a circle surrounding any variable node is proportional to the value of the noise on the node. Different colors correspond to different generations on the tree.

Figure 2

$m=4,l=5$, and $n=4$. Comparative plots of BER (full sum, but the phase volume factors were not counted: $c_p\approx 1$), and individual instanton contributions, calculated within the single-chain approximation, vs SNR.