Diagnosis of Weaknesses in Modern Error Correction Codes: A Physics Approach

One of the main obstacles to the wider use of the modern error-correction codes is that, due to the complex behavior of their decoding algorithms, no systematic method which would allow characterization of the bit-error-rate (BER) is known. This is especially true at the weak noise where many systems operate and where coding performance is difficult to estimate because of the diminishingly small number of errors. We show how the instanton method of physics allows one to solve the problem of BER analysis in the weak noise range by recasting it as a computationally tractable minimization problem.

Figure 1

Parts of the full Tanner graph with nonzero noise for the instantons, corresponding to (a) simple, (b) degenerate, and (c) sign-alternating pseudocode words, are shown in three panels each consisting of three diagrams. In the top left and bottom diagrams bits are numbered according to the (155, 64, 20)-code definition, where the numbering is fixed up to the full symmetry transformation of the code. The numbers appearing on the top right graphs (and areas of the corresponding circles) are (a) $(1-x_i)\times 210/46$, (b) $(1-x_i)\times 79/18$, (c) $(1-x_i)\times 188/44$. For the computational tree (bottom panel) the bits drawn in color participate in the pseudocode word and the shaded bit marks the error position. The marked checks and squares correspond to the points of (b) degeneracy and of (c) sign alternation.

Figure 2

Interpretation of the instanton as a median within a set of pseudocode words. Three panels show the set of pseudocode words for the three instantons described in Fig. 1. Bits on the computational tree painted in white and black correspond to $+1/-1$. Other notations and marks are in accordance with the captions of Fig. 1.