text:
# Critical Noise Levels for LDPC decoding

## I Introduction

The theory of error-correcting codes is based on the efficient introduction of redundancy to given messages for protecting the information content against corruption. The theoretical foundations of this area were laid by Shannon’s seminal work shannon  and have been developing ever since. One of the main results obtained in this field is the celebrated channel coding theorem stating that there exists a code such that the average message error probability $`P_E`$, when maximum likelihood decoding is used, can be made arbitrarily small for sufficiently long messages below the channel capacity; and will approach 1 above it. The channel coding theorem is based on unstructured random codes and impractical decoders such as maximum likelihood viterbi  and typical set decoding Aji . In the case of structured codes, the critical code rate $`R`$ (message information content/length of the encoded transmission) may lie below the channel capacity, commonly termed Shannon’s bound, even if optimal (and typically impractical) decoding methods are being used. The proximity of the critical code rate to Shannon’s limit provides an indication to the theoretical limitations of a given code.

In 1963 Gallager gallager  proposed a coding scheme which involves sparse linear transformations of binary messages that was forgotten soon after, in part due to the success of convolutional codes viterbi  and the computational limitations of the time. Gallager codes have been recently rediscovered by MacKay and Neal (MN), that independently proposed a closely related code MacKay . Variations of this family of codes, known as Low Density Parity Check (LDPC) codes, have displayed performance comparable (and sometimes superior) to other state-of-the-art codes. This family of codes has been thoroughly investigated in the information theory (IT) literature (e.g., MacKay ; Richardson ; Aji ), providing a range of significant theoretical and practical results.

In parallel to studies carried out in the IT community, a different approach has been used to study LDPC codes, using the established methods of statistical physics (SP). This analysis, relying mainly on the replica symmetric analysis of diluted systems MPV ; nishimori\_book , offers an alternative to information theory methods and has yielded some new results and insights us\_prl ; cactus ; montanari . Due to the growing interest in LDPC codes and their successful analysis via the methods of statistical physics, there is growing interest in the relationship between IT and SP methods. As the two communities investigate similar problems, one may expect that standard techniques known in one framework would bring about new developments in the other, and vice versa. Here we present a direct SP method to determine the critical noise level of Gallager and MN error correcting codes, which allows us to focus on the differences between the various decoding criteria and their use for defining the critical noise level for which decoding is theoretically feasible.

The paper is organized as follows: In section II we introduce the general framework, notation and the quantities we focus on, while in section III we will briefly describe the SP calculation. Section IV describes qualitatively the emerging picture of the main quantities calculated for Gallager’s code while the corresponding picture for MN codes will be described in section V. Quantitative results for the critical noise level will be presented in section VI followed by conclusions.

## II Regular Gallager and MN codes

In a general scenario, the $`N`$ dimensional Boolean message $`\stackrel{}{s}^o\{0,1\}^N`$ is encoded to the $`M(>N)`$ dimensional Boolean vector $`\stackrel{}{t}^o`$, and transmitted via a noisy channel, which is taken here to be a Binary Symmetric Channel (BSC) characterized by an independent flip probability $`p`$ per bit; other transmission channels may also be examined within a similar framework. At the other end of the channel, the corrupted codeword is decoded utilizing the structured codeword redundancy.

The first type of error correcting code that we focus on here, is Gallager’s linear code gallager . Gallager’s code is a low density parity check code defined by the a binary $`(MN)\times M`$ matrix $`𝐀=[𝐂_1|𝐂_2]`$, concatenating two very sparse matrices known to both sender and receiver, with the $`(MN)\times (MN)`$ matrix $`𝐂_2`$ being invertible. The matrix $`𝐀`$ has $`K`$ non-zero elements per row and $`C`$ per column, and the code rate is given by $`R=1C/K=1N/M`$. Encoding refers to multiplying the original message $`\stackrel{}{s}^o`$ with the $`(M\times N)`$ matrix $`𝐆^T`$ (where $`𝐆=[\text{ }\text{}_N|𝐂_2^1]`$), yielding the transmitted vector $`\stackrel{}{t}^o`$. Note that all operations are carried out in (mod 2) arithmetic. Upon sending $`\stackrel{}{t}^o`$ through the binary symmetric channel (BSC) with noise level $`p`$, the vector $`\stackrel{}{r}=\stackrel{}{t}^o+\stackrel{}{n}^o`$ is received, where $`\stackrel{}{n}^o`$ is the true noise.

Decoding is carried out by multiplying $`\stackrel{}{r}`$ by $`𝐀`$ to produce the syndrome vector $`\stackrel{}{z}=𝐀\stackrel{}{r}`$ ($`=𝐀\stackrel{}{n}^o`$, since $`\mathrm{𝐀𝐆}^T=\mathrm{𝟎}`$). In order to reconstruct the original message $`\stackrel{}{s}^o`$, one has to obtain an estimate $`\stackrel{}{n}`$ for the true noise $`\stackrel{}{n}^o`$. First we select all $`\stackrel{}{n}`$ that satisfy the parity checks $`𝐀\stackrel{}{n}=𝐀\stackrel{}{n}^o`$:

$$_{\mathrm{pc}}(𝐀,\stackrel{}{n}^o)\{\stackrel{}{n}|𝐀\stackrel{}{n}=\stackrel{}{z}\},\text{and}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{n}^o)\{\stackrel{}{n}_{\mathrm{pc}}(𝐀,\stackrel{}{n}^o)|\stackrel{}{n}\stackrel{}{n}^o\},$$
(1)
the (restricted) parity check set.

The second type of error correcting code that we focus on here is the MacKay-Neal (MN) code MacKay . An MN code is a low density parity check code defined by a binary $`M\times (N+M)`$ matrix $`𝐀=[𝐂_s|𝐂_n]`$, concatenating two very sparse matrices known to both sender and receiver, with the $`M\times M`$ matrix $`𝐂_n`$ being invertible. The $`M\times N`$ matrix $`𝐂_s`$ has $`K`$ non-zero elements per row and $`C`$ per column, while $`𝐂_n`$ has $`L`$ non-zero elements per row and column. The code rate is given by $`R=K/C=N/M`$. Encoding refers to multiplying the original message $`\stackrel{}{s}^o`$ by the $`(M\times N)`$ dense generator matrix $`𝐆=𝐂_n^1𝐂_s`$, yielding the transmitted vector $`\stackrel{}{t}^o`$. Note that all operations are carried out in (mod2) arithmetic. Upon sending $`\stackrel{}{t}^o`$ through the binary symmetric channel (BSC) with noise level $`p`$, the vector $`\stackrel{}{r}=\stackrel{}{t}^o+\stackrel{}{n}^o`$ is received, where $`\stackrel{}{n}^o`$ is the true noise.

Decoding is carried out by multiplying $`\stackrel{}{r}`$ by $`𝐂_n`$ to produce the syndrome vector $`\stackrel{}{z}=𝐂_s\stackrel{}{s}^o+𝐂_n\stackrel{}{n}^o𝐀\stackrel{}{c}^o`$, where $`\stackrel{}{c}`$ is the concatenated vector $`(\stackrel{}{s},\stackrel{}{n})`$. In order to reconstruct the original message $`\stackrel{}{s}^o`$, one has to obtain estimates $`\stackrel{}{c}`$ for the true signal and noise $`\stackrel{}{c}^o`$. First we select all combinations of signal and noise $`\stackrel{}{c}`$ that satisfy the parity checks $`𝐀\stackrel{}{c}=𝐀\stackrel{}{c}^o`$:

$$_{\mathrm{pc}}(𝐀,\stackrel{}{c}^o)\{\stackrel{}{c}|𝐀\stackrel{}{c}=\stackrel{}{z}\},\text{and}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)\{\stackrel{}{c}_{\mathrm{pc}}(𝐀,\stackrel{}{c}^o)|\stackrel{}{c}\stackrel{}{c}^o\},$$
(2)
the (restricted) parity check set.

To unify notation for Gallager and MN codes, we will adopt the notation $`\stackrel{}{c}^o`$ for the original noise (and signal) vector, and $`\stackrel{}{c}`$ for the estimate of the noise (and signal) vector. Any general decoding scheme then consists of selecting a vector $`\stackrel{}{c}^{}`$ from $`_{\mathrm{pc}}(𝐀,\stackrel{}{c}^o)`$, on the basis of some noise (and signal) statistics criterion. Upon successful decoding $`\stackrel{}{c}^o`$ will be selected, while a decoding error is declared when a vector $`\stackrel{}{c}^{}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)`$ is selected. For each decoding scheme, the average block error probability iba

$$P_e(p_s,p)=\mathrm{\Delta }\left(\text{a vector }\stackrel{}{c}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)\text{ is selected}\right)_{𝐀,\stackrel{}{c}^o}$$
(3)
can be defined as a measure of error correcting ability for a given code ensemble, where $`\mathrm{\Delta }()`$ is an indicator function returning $`1`$ if the proposition of the argument is true and $`0`$, otherwise. For BSC, only the number of non-zero components characterizes the statistics of the noise. On the other hand, the signal bits in general have an equal probability for being 0 and 1 (i.e. $`p_s=\frac{1}{2}`$), which implies that they have no useful prior information for the estimation. In the following, we therefore focus on decoding schemes based on the weight of a vector which is the average sum of the noise components $`w(\stackrel{}{c})\frac{1}{M}_{j=1}^Mn_j`$. To obtain the error probability, one averages the indicator function over all $`\stackrel{}{c}^o`$ vectors drawn from some distribution and the code ensemble $`𝐀`$ as denoted by $`._{𝐀,\stackrel{}{c}^o}`$.

Unfortunately, carrying out averages over the indicator function is difficult. Therefore, the error probability (3) is usually upper-bounded by averaging over the number of vectors $`\stackrel{}{n}`$ obeying a certain condition on the weight $`w(\stackrel{}{n})`$ which characterizes the employed decoding scheme. Alternatively, one can find the average number of vectors with a given weight value $`w`$ from which one can construct a complete weight distribution of noise vectors $`\stackrel{}{n}`$ in $`_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)`$. From this distribution one can, in principle, calculate a bound for $`P_e`$ and derive critical noise values above which successful decoding cannot be carried out.

A natural and direct measure for the average number of states is the entropy of a system under the restrictions described above, that can be calculated via the methods of statistical physics.

It was previously shown (see e.g. us\_prl  for technical details) that this problem can be cast into a statistical mechanics formulation, by replacing the field $`(\{0,1\},+\mathrm{mod}(2))`$ by ($`\{1,1\},\times `$), and by adapting the parity checks correspondingly. The statistics of a noise vector $`\stackrel{}{n}`$ is now described by its magnetization $`m(\stackrel{}{n})\frac{1}{M}_{j=1}^Mn_j`$, $`(m(\stackrel{}{n})[1,1])`$, which is inversely linked to the vector weight in the $`[0,1]`$ representation. Similarly, the statistics of a signal vector $`\stackrel{}{s}`$ is now described by its magnetization $`m_s(\stackrel{}{s})\frac{1}{M}_{j=1}^Ms_j`$, $`(m_s(\stackrel{}{s})[1,1])`$. With this in mind, we introduce the conditioned magnetization enumerator, for a given code and noise, measuring the noise vector magnetization distribution in $`_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{n}^o)`$

$$_{𝐀,\stackrel{}{n}^o}(m)\frac{1}{M}\mathrm{ln}\left[\underset{\stackrel{}{n}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{n}^o)}{\text{Tr }}\delta (m(\stackrel{}{n})m)\right].$$
(4)
To obtain the magnetization enumerator $`(m)`$

$$(m)=\frac{}{}_{𝐀,\stackrel{}{c}^o}(m)_{𝐀,\stackrel{}{c}^o},$$
(5)
which is the entropy of the noise vectors in $`_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{n}^0)`$ with a given $`m`$, one carries out uniform explicit averages over all codes $`𝐀`$ with given parameters $`K,C`$ (and $`L`$), and the weighted average over all possible noise vectors generated by the BSC, (and all possible signal vectors) i.e.,

$`P(\stackrel{}{n}^o)={\displaystyle \underset{j}{\overset{M}{}}}\left((1p)\delta (n_j^o1)+p\delta (n_j^o+1)\right),`$ (6)
$`P(\stackrel{}{s}^o)={\displaystyle \underset{j}{\overset{N}{}}}\left((1p_s)\delta (s_j^o1)+p_s\delta (s_j^o+1)\right),`$ (7)
with $`p_s=\frac{1}{2}`$. It is important to note that, in calculating the entropy, the average quantity of interest is the magnetization enumerator rather than the actual number of states. As physicists, this is the natural way to carry out the averages for three main reasons: a) The entropy obtained in this way is believed to be self-averaging, i.e., its average value (over the disorder) coincides with its typical value. b) This quantity is extensive and grows linearly with the system size. c) This averaging distinguishes between annealed variables that are averaged or summed for a given set of quenched variables, that are averaged over later on. In this particular case, summation over all $`\stackrel{}{c}`$ vectors is carried for a fixed choice of code $`𝐀`$ and vector $`\stackrel{}{c}^o`$; averages over these variables are carried out at the next level.

One should point out that in somewhat similar calculations, we showed that this method of carrying out the averages provides more accurate results in comparison to averaging over both sets of variables simultaneously reliability .

A positive magnetization enumerator, $`(m)>0`$ indicates that there is an exponential number of solutions (in $`M`$) with magnetization $`m`$, for typically chosen $`𝐀`$ and $`\stackrel{}{c}^o`$, while $`(m)0`$ indicates that this number vanishes as $`M\mathrm{}`$ (note that negative entropy is unphysical in discrete systems).

Another important indicator for successful decoding is the overlap $`\omega `$ between the selected estimate $`\stackrel{}{n}^{}`$, and the true noise $`\stackrel{}{n}^o`$$`\omega (\stackrel{}{n},\stackrel{}{n}^o)\frac{1}{M}_{j=1}^Mn_jn_j^o`$, $`(\omega (\stackrel{}{n},\stackrel{}{n}^o)[1,1])`$, with $`\omega =1`$ for successful (perfect) decoding. However, this quantity cannot be used for decoding as $`\stackrel{}{n}^o`$ is unknown to the receiver. The (code and noise dependent) noise overlap enumerator is now defined as:

$$𝒲_{𝐀,\stackrel{}{c}^o}(\omega )\frac{1}{M}\mathrm{ln}\left[\underset{\stackrel{}{c}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)}{\text{Tr }}\delta (\omega (\stackrel{}{n},\stackrel{}{n}^o)\omega )\right],$$
(8)
and the average quantity being

$$𝒲(\omega )=\frac{}{}𝒲_{𝐀,\stackrel{}{c}^o}(\omega )_{𝐀,\stackrel{}{c}^o}.$$
(9)
This measure is directly linked to the weight enumerator Aji , although according to our notation, averages are carried out distinguishing between annealed and quenched variables unlike the common definition in the IT literature. However, as we will show below, the two types of averages provide identical results in this particular case.

Similarly, for MN-codes one defines the signal magnetization and weight enumerators as

$`_s(m_s)`$ $``$ $`{\displaystyle \frac{1}{N}}\mathrm{ln}\left[\underset{\stackrel{}{c}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)}{\text{Tr }}\delta (m(\stackrel{}{s})m_s)\right]_{𝐀,\stackrel{}{c}^o}`$ (10)
$`𝒲_s(\omega _s)`$ $``$ $`{\displaystyle \frac{1}{N}}\mathrm{ln}\left[\underset{\stackrel{}{c}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)}{\text{Tr }}\delta (\omega (\stackrel{}{s},\stackrel{}{s}^o)\omega _s)\right]_{𝐀,\stackrel{}{c}^o}`$ (11)
In what follows, we perform all calculations as if both $`m`$ and $`\omega `$ (and $`m_s`$ and $`\omega _s`$ for MN-codes), are constrained to particular values. As we will show, omitting a constraint in the final expressions can then easily be done by assigning the zero value to the corresponding Lagrange multiplier.

## III The statistical physics approach

Quantities of the type $`𝒬(c)=𝒬_y(c)_y`$, with $`𝒬_y(c)=\frac{1}{M}\mathrm{ln}\left[𝒵_y(c)\right]`$ and $`𝒵_y(c)\text{Tr }_x\delta (c(x,y)Mc)`$, are very common in the SP of disordered systems; the macroscopic order parameter $`c(x,y)`$ is fixed to a specific value and may depend both on the disorder $`y`$ and on the microscopic variables $`x`$. Although we will not prove this here, such a quantity is generally believed to be self-averaging in the large system limit, i.e., obeying a probability distribution $`P(𝒬_y(c))=\delta (𝒬_y(c)𝒬(c)))`$. The direct calculation of $`𝒬(c)`$ is known as a quenched average over the disorder, but is typically hard to carry out and requires using the replica method nishimori\_book . The replica method makes use of the identity $`\mathrm{ln}𝒵=lim_{\mathrm{n}0}[𝒵^\mathrm{n}1]/\mathrm{n}`$, by calculating averages over a product of partition function replicas. Employing assumptions about replica symmetries and analytically continuing the variable $`\mathrm{n}`$ to zero, one obtains solutions which enable one to determine the state of the system.

To simplify the calculation, one often employs the so-called annealed approximation, which consists of performing an average over $`𝒬_y(c)`$ first, followed by the logarithm operation. This avoids the replica method and provides (through the convexity of the logarithm function) an upper bound to the quenched quantity:

$$Q_a(c)\frac{1}{M}\mathrm{ln}[𝒵_y(c)_y]Q_q(c)\frac{1}{M}\mathrm{ln}[𝒵_y(c)]_y=\underset{\mathrm{n}0}{lim}\frac{𝒵_y^\mathrm{n}(c)_y1}{\mathrm{n}M}.$$
(12)
The technical details of the calculation are similar to those in us\_prl . It turns out that it is useful to perform the gauge transformation $`c_jc_jc_j^o`$, such that the averages over the code $`𝐀`$ and noise/signal $`\stackrel{}{c}^o`$ can be separated, $`𝒲_{𝐀,\stackrel{}{c}^o}`$ becomes independent of $`\stackrel{}{c}^o`$, leading to an equality between the quenched and annealed results, $`𝒲(m)=_a(m)|_{p=0}=_q(m)|_{p=0}`$. For any finite noise value $`p`$ one should multiply $`\mathrm{exp}[𝒲(\omega )]`$ by the probability that a state obeys all parity checks $`\mathrm{exp}[K(\omega ,p)]`$ given an overlap $`\omega `$ and a noise level $`p`$ Aji . In calculating $`𝒲(\omega )`$ and $`_{a/q}(m)`$, the $`\delta `$-functions fixing $`m`$ and $`\omega `$, are enforced by introducing Lagrange multipliers $`\widehat{m}`$ and $`\widehat{\omega }`$.

Carrying out the averages explicitly one then employs the saddle point method to extremize the averaged quantity with respect to the parameters introduced while carrying out the calculation. These lead, in both quenched and annealed calculations, to a set of saddle point equations that are solved either analytically or numerically to obtain the final expression for the averaged quantity (entropy).

The final expressions for the annealed entropy per noise degree of freedom for Gallager codes, under both overlap ($`\omega `$) and magnetization ($`m`$) constraints, are of the form:

$$𝒬_a=\frac{C}{K}(\mathrm{ln}(2)+(K1)\mathrm{ln}[1+c_1^K])+\mathrm{ln}\underset{n=\pm 1}{\text{Tr }}\mathrm{exp}(n(\widehat{\omega }+\widehat{m}n^o))(1+nc_1^{K1})^C_{n^o}(\widehat{\omega }\omega +\widehat{m}m),$$
(13)
where $`c_1`$ has to be obtained from the saddle point equation $`\frac{𝒬_a}{c_1}=0`$. Similarly, the final expression in the quenched calculation, employing the simplest replica symmetry assumption nishimori\_book , is of the form:

$`𝒬_q`$ $`=`$ $`C{\displaystyle 𝑑x𝑑\widehat{x}\pi (x)\widehat{\pi }(\widehat{x})\mathrm{ln}[1+x\widehat{x}]}+{\displaystyle \frac{C}{K}}{\displaystyle \left\{\underset{k=1}{\overset{K}{}}dx_k\pi (x_k)\right\}\mathrm{ln}\left[\frac{1}{2}\left(1+\underset{k=1}{\overset{K}{}}x_k\right)\right]}`$ (14)
$`+{\displaystyle \left\{\underset{c=1}{\overset{C}{}}d\widehat{x}_c\widehat{\pi }(\widehat{x}_c)\right\}\mathrm{ln}[\underset{n=\pm 1}{\text{Tr }}\mathrm{exp}(n(\widehat{\omega }+\widehat{m}n^o))\underset{c=1}{\overset{C}{}}(1+n\widehat{x}_c)]_{n^o}}(\widehat{\omega }\omega +\widehat{m}m).`$
The probability distributions $`\pi (x)`$ and $`\widehat{\pi }(\widehat{x})`$ emerge from the calculation; the former represents a probability distribution with respect to the noise vector local magnetization TAP\_book , while the latter relates to a field of conjugate variables which emerge from the introduction of $`\delta `$-functions while carrying out the averages (for details see us\_prl ). Their explicit forms are obtained from the functional saddle point equations $`\frac{\delta 𝒬_q}{\delta \pi (x)}`$, $`\frac{\delta 𝒬_q}{\delta \widehat{\pi }(\widehat{x})}=0`$, and all integrals are from $`1`$ to 1.

The final expressions for the annealed entropy per noise degree of freedom for MN-codes, under both signal and noise overlap ($`\omega ,\omega _s`$) and magnetization ($`m,m_s`$) constraints, are of the form:

$`𝒬_a`$ $`=`$ $`\left(\mathrm{log}(2)+(K+L1)\mathrm{ln}[1+c_1^Kd_1^L]\right)R(\widehat{m}_sm_s+\widehat{\omega }_s\omega _s)(\widehat{m}m+\widehat{\omega }\omega )`$ (15)
$`+R\mathrm{ln}\underset{s=\pm 1}{\text{Tr }}\mathrm{exp}\left(s(\widehat{\omega }_s+\widehat{m}_ss^o)\right)(1+s\widehat{c}_1)^C_{s^o}+\mathrm{ln}\underset{n=\pm 1}{\text{Tr }}\mathrm{exp}\left(n(\widehat{\omega }+\widehat{m}n^o)\right)(1+n\widehat{d}_1)^L_{n^o}`$
where $`c_1,d_1`$ have to be obtained from the saddle point equations $`\frac{𝒬_a}{c_1},\frac{𝒬_a}{d_1}=0`$. Similarly, the final expression in the quenched calculation, employing the simplest replica symmetry assumption nishimori\_book , is of the form:

$`𝒬_q`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{K}{}}dx_k\pi (x_k)\underset{l=1}{\overset{L}{}}dy_l\rho (y_l)\mathrm{ln}\left[\frac{1}{2}\left(1+\underset{k=1}{\overset{K}{}}x_k\underset{l=1}{\overset{L}{}}y_l\right)\right]}R(\widehat{m}_sm_s+\widehat{\omega }_s\omega _s)(\widehat{m}m+\widehat{\omega }\omega )`$ (16)
$`K{\displaystyle 𝑑x𝑑\widehat{x}\pi (x)\widehat{\pi }(\widehat{x})\mathrm{ln}[1+x\widehat{x}]}+R{\displaystyle \underset{c=1}{\overset{C}{}}d\widehat{x}_c\widehat{\pi }(\widehat{x}_c)\mathrm{ln}\left[\underset{s=\pm 1}{\text{Tr }}\mathrm{exp}(s(\widehat{\omega }_s+\widehat{m}_ss^o))\underset{c=1}{\overset{C}{}}(1+s\widehat{x}_c)\right]_{s^o}}`$
$`L{\displaystyle }dyd\widehat{y}\rho (y)\widehat{\rho }(\widehat{y})\mathrm{ln}[1+y\widehat{y}]+{\displaystyle }{\displaystyle \underset{l=1}{\overset{L}{}}}d\widehat{y}_l\widehat{\rho }(\widehat{y}_l)\mathrm{ln}[\underset{n=\pm 1}{\text{Tr }}\mathrm{exp}(n(\widehat{\omega }+\widehat{m}n^o){\displaystyle \underset{l=1}{\overset{L}{}}}(1+n\widehat{y}_l)]_{n^o}`$
The probability distributions $`\pi (x),\rho (y)`$ and $`\widehat{\pi }(\widehat{x}),\widehat{\rho }(\widehat{y})`$ emerge from the calculation; the former represent probability distributions with respect to the signal/noise vector local magnetizations TAP\_book , while the latter relate to fields of conjugate variables which emerge from the introduction of $`\delta `$-functions while carrying out the averages (for details see us\_prl ). Their explicit forms are obtained from the functional saddle point equations $`\frac{\delta 𝒬_q}{\delta \pi (x)},\frac{\delta 𝒬_q}{\delta \widehat{\pi }(\widehat{x})},\frac{\delta 𝒬_q}{\delta \rho (y)},\frac{\delta 𝒬_q}{\delta \widehat{\rho }(\widehat{y})}=0`$, and all integrals are from $`1`$ to 1.

Enforcing a $`\delta `$-function corresponds to taking $`\widehat{\omega },\widehat{m},\widehat{\omega }_s,\widehat{m}_s`$ such that $`\frac{𝒬_{a/q}}{\widehat{\omega }},\frac{𝒬_{a/q}}{\widehat{m}},\frac{𝒬_{a/q}}{\widehat{\omega }_s},\frac{𝒬_{a/q}}{\widehat{m}_s}=0`$, while not enforcing it corresponds to putting $`\widehat{\omega },\widehat{m},\widehat{\omega }_s,\widehat{m}_s`$ to 0. Since $`\omega ,m,\omega _s,m_s`$, follow from $`\frac{𝒬_{a/q}}{\widehat{\omega }},\frac{𝒬_{a/q}}{\widehat{m}},\frac{𝒬_{a/q}}{\widehat{\omega }_s},\frac{𝒬_{a/q}}{\widehat{m}_s}=0`$, all the relevant quantities can be recovered with appropriate choices of $`\widehat{\omega },\widehat{m},\widehat{\omega }_s,\widehat{m}_s`$.

## IV Qualitative picture

We now discuss the qualitative behaviour of $`(m)`$, and the interpretation of the various decoding schemes. To obtain separate results for $`(m)`$ and $`𝒲(m)`$ we calculate the results of Eqs.(13) and (14) (and Eqs. (15) and (16)), corresponding to the annealed and quenched cases respectively, setting $`\widehat{\omega }=0`$ to obtain $`(m)`$ and $`\widehat{m}=0`$ to obtain $`𝒲(\omega )`$ (that becomes $`(m)|_{p=0}`$ after gauging). In Fig. 1, we have qualitatively plotted the resulting function $`(m)`$ for relevant values of $`p`$. $`(m)`$ (solid line) only takes positive values in the interval $`[m_{}(p),m_+(p)]`$; for even $`K`$, $`(m)`$ is an even function of $`m`$ and $`m_{}(p)=m_+(p)`$. The maximum value of $`(m)`$ is always $`(1R)\mathrm{ln}(2)`$ for Gallager codes, and $`R\mathrm{ln}(2)`$ for MN codes. The true noise $`\stackrel{}{n}^o`$ has (with probability 1) the typical magnetization of the BSC: $`m(\stackrel{}{n}^o)=m_0(p)=12p`$ (dashed-dotted line).

The various decoding schemes can be summarized as follows:

* Maximum likelihood (MAP) decoding \- minimizes the block error probability iba  and consists of selecting the $`\stackrel{}{n}`$ from $`_{\mathrm{pc}}(𝐀,\stackrel{}{n}^0)`$ with the highest magnetization. Since the probability of error below $`m_+(p)`$ vanishes, $`P(\stackrel{}{n}_{\mathrm{pc}}^\mathrm{r}:m(\stackrel{}{n})>m_+(p))=0`$, and since $`P(m(\stackrel{}{n}^o)=m_0(p))=1`$, the critical noise level $`p_c`$ is determined by the condition $`m_+(p_c)=m_0(p_c)`$. The selection process is explained in Fig.1(a)-(c).
* Typical pairs decoding \- is based on randomly selecting a $`\stackrel{}{n}`$ from $`_{\mathrm{pc}}`$ with $`m(\stackrel{}{n})=m_0(p)`$ Aji ; an error is declared when $`\stackrel{}{n}^0`$ is not the only element of $`_{\mathrm{pc}}`$. For the same reason as above, the critical noise level $`p_c`$ is determined by the condition $`m_+(p_c)=m_0(p_c)`$.
* Finite temperature (MPM) decoding \- An energy $`Fm(\stackrel{}{n})`$ (with $`F=\frac{1}{2}\mathrm{ln}(\frac{1p}{p})`$) according to Nishimori’s condition (corresponding to the selection of an accurate prior within the Bayesian framework). is attributed to each $`\stackrel{}{n}_{\mathrm{pc}}`$, and a solution is chosen from those with the magnetization that minimizes the free energy us\_prl . This procedure is known to minimize the bit error probability iba . Using the thermodynamic relation $`=𝒰\frac{1}{\beta }𝒮`$, $`\beta `$ being the inverse temperature (Nishimori’s condition corresponds to setting $`\beta =1`$), the free energy of the sub-optimal solutions is given by $`(m)=Fm\frac{1}{\beta }(m)`$ (for $`(m)0`$), while that of the correct solution is given by $`Fm_0(p)`$ (its entropy being 0). The selection process is explained graphically in Fig.1(a)-(c). The free energy differences between sub-optimal solutions relative to that of the correct solution in the current plots, are given by the orthogonal distance between $`(m)`$ and the line with slope $`\beta F`$ through the point $`(m_0(p),0)`$. Solutions with a magnetization $`m`$ for which $`(m)`$ lies above this line, have a lower free energy, while those for which $`(m)`$ lies below, have a higher free energy. Since negative entropy values are unphysical in discrete systems, only sub-optimal solutions with $`(m)0`$ are considered. The lowest $`p`$ value for which there are sub-optimal solutions with a free energy equal to $`Fm_0(p)`$ is the critical noise level $`p_c`$ for MPM decoding. In fact, using the convexity of $`(m)`$ and Nishimori’s condition, one can show that the slope $`(m)/m>\beta F`$ for any value $`m<m_o(p)`$ and any $`p`$, and equals $`\beta F`$ only at $`m=m_o(p)`$; therefore, the critical noise level for MPM decoding $`p=p_c`$ is identical to that of MAP, in agreement with results obtained in the information theory community MacKay\_thrm .

The statistical physics interpretation of finite temperature decoding corresponds to making the specific choice for the Lagrange multiplier $`\widehat{m}=\beta F`$ and considering the free energy instead of the entropy. In earlier work on MPM decoding in the SP framework us\_prl , negative entropy values were treated by adopting different replica symmetry assumptions, which effectively result in changing the inverse temperature, i.e., the Lagrange multiplier $`\widehat{m}`$. This effectively sets $`m=m_+(p)`$, i.e. to the highest value with non-negative entropy. The sub-optimal states with the lowest free energy are then those with $`m=m_+(p)`$.

The central point in all decoding schemes, is to select the correct solution only on the basis of its magnetization. As long as there are no sub-optimal solutions with the same magnetization, this is in principle possible. As shown here, all three decoding schemes discussed above, manage to do so. To find whether at a given $`p`$ there exists a gap between the magnetization of the correct solution and that of the nearest sub-optimal solution, just requires plotting $`(m)(>0)`$ and $`m_0(p)`$, thus allowing a graphical determination of $`p_c`$. Since MPM decoding is done at Nishimori’s temperature, the simplest replica symmetry assumption is sufficient to describe the thermodynamically dominant state nishimori\_book . At $`p_c`$ the states with $`m_+(p_c)=m_0(p_c)`$ are thermodynamically dominant, and the $`p_c`$ values that we obtain under this assumption are exact.

## V MN codes - an alternative view

For MN codes there is a way to obtain the exact expression for $``$, in the case of unbiased messages, by employing a single highly plausible assumption. We first note that every the parity check bit $`z_{<>}=s_{i_1}^o..s_{i_K}^on_{j_1}^o..n_{j_L}^o`$ is made up of a combination of $`K`$ unbiased (i.e. $`p_s=\frac{1}{2}`$) signal bits, and $`L`$ biased (i.e. $`p\frac{1}{2}`$) noise bits. As a result, every syndrome element $`z_{<>}`$ is unbiased independently of the noise bit statistics. It is therefore plausible to assume that the noise bit statistics (i.e. $`p`$) have no influence on the distribution of the parity check bits $`z_{<>}`$, and therefore on $``$ (which only depends on the true noise through the $`z_{<>}`$). If this assumption is satisfied, one can invoke Nishimori’s condition to obtain an exact expression for $``$.
Independently of the assumption, Nishimori’s condition gives the following identity for the thermodynamically dominant state:

$$\frac{(m)}{m}|_{m=m_o(p)}=F(p)=\frac{1}{2}\mathrm{ln}\left(\frac{1p}{p}\right)=\frac{1}{2}\mathrm{ln}\left(\frac{1+m_o}{1m_o}\right).$$
(17)
Since states characterized by any magnetization value $`m<m_0(p_t)`$ will become dominant for an appropriately chosen value of $`p`$, and since we assume that $``$ is independent of $`p`$, the identity

$$\frac{(m)}{m}=\frac{1}{2}\mathrm{ln}\left(\frac{1+m}{1m}\right),$$
(18)
must hold for any value of $`m`$. Furthermore, the maximum of $`(m)`$ is reached at $`m=0`$ with $`(0)=R\mathrm{ln}(2)`$, and we have that

$$(m)=(0)\frac{1}{2}_0^m𝑑u\mathrm{ln}\left(\frac{1+u}{1u}\right)=\mathrm{ln}(2)\left[R1+H_2\left(\frac{1+m}{2}\right)\right],$$
(19)
where $`H_2(p)`$ is the binary entropy per bit for vectors with bias $`p`$. Hence, under this assumption, we do not only obtain the exact expression for $`(m)`$, but we see that the critical noise level $`p_c`$ is given by $`R=1H_2(p_c)`$, saturating Shannon’s bound for this type of codes!

Unfortunately, the assumption can not be verified easily without the replica method. To verify whether indeed $`\frac{(m)}{p}=0`$, we have to take the derivative of expression (16) (setting $`\widehat{\omega }=\widehat{\omega }_s=\widehat{m}_s=0`$) with respect to $`p`$. It turns out that $``$ is only independent of $`p`$, when $`\rho (\widehat{y})`$ is an even function of $`\widehat{y}`$, which in turn requires that $`\rho (y)`$ and $`\pi (x)`$ are even functions of their arguments. Numerical analysis shows, that this is the case for any $`K3`$ or $`K=2,L3`$, while not so for $`K=1`$ or $`K=L=2`$. This result is consistent with those reported in us\_prl , i.e. that typical MN codes with $`K3`$ or $`K=2,L3`$ do saturate Shannon’s bound, while those with $`K=1`$ and $`K=L=2`$ do not.

Intuitively this result can be understood in the following way. There are $`M`$ parity check bits and only $`N(<M)`$ signal bits, such that parity check bits, although individually unbiased, are not uncorrelated. These correlations do seem to have an effect on $`(m)`$ for $`K=1`$ and $`K=L=2`$, while for $`K3`$ and $`K=2,L3`$ the signal bits seem to be “scrambled” enough in the parity checks for the correlations to be insignificant. Note that this argument does not hold for Gallager codes and MN codes with biased messages, where the parity check bits exclusively comprise biased bits, and are therefore biased themselves. They only become unbiased as $`K\mathrm{}`$ for Gallager codes (for which it was already reported in the literature MacKay  that such codes can saturate Shannon’s bound), and for $`K\mathrm{}`$ or $`L\mathrm{}`$ for MN codes.

In fact, numerical analysis reveals that for $`K3`$ and for $`K=2,L3`$ we have that $`\rho (\widehat{y})=\delta (\widehat{y})`$, $`\rho (y)=\delta (y)`$, $`\pi (x)=\delta (x)`$ at least up to $`m_+(p)=m_0(p_t)`$ which is independent of $`p`$. This allows us to calculate $``$ analytically from expression (16), and we recover, as expected, the exact expression (19).

For $`K=1`$ or $`K=L=2`$, like in the case of Gallager codes, one can only obtain $`m_+(p)`$ numerically. The results of this procedure are presented in the next section. Furthermore, for $`K=1`$ and for $`K=L=2`$, we find that spontaneously $`m_s0`$ for some values of $`p<p_c`$, when no restriction is enforced (i.e. for $`\widehat{m}_s=0`$). This implies that one may improve the decoding performance by imposing the condition of unbiased signal (similar to the conditions for typical set decoding), i.e. by adjusting the Lagrange multiplier $`\widehat{m}_s`$ such that $`m_s=0`$. Unfortunately, this only happens for values of $`p`$ for which there is an exponential number of sub-optimal solutions $`\stackrel{}{c}_{\mathrm{pc}}^\mathrm{r}(𝐀,\stackrel{}{c}^o)`$ with the same weight as $`\stackrel{}{c}^o`$, and imposing this constraint on the signal estimator only reduces this number, leaving it nevertheless, exponential.

It was shown book  that MN codes in principle contain sufficient information to saturate Shannon’s bound for unbiased messages. For codes with $`K=1`$, or $`K=L=2`$, some of this information is wasted in a region where errorless decoding is impossible anyway, such that Shannon’s bound is not saturated. For codes with $`K3`$, or $`K=2,L3`$, our analysis indicates that all information is used optimally, and that Shannon’s bound can be theoretically saturated. Our argument also explains the relative importance of the parameters $`K`$ and $`L`$ for the behaviour of the code in comparison with $`C`$.

## VI Critical noise level - results

Some general comments can be made about the critical MAP (or typical set) values obtained via the annealed and quenched calculations. Since $`_q(m)_a(m)`$ (for given values of $`K`$, $`C`$ ($`L`$) and $`p`$), we can derive the general inequality $`p_{c,q}p_{c,a}`$. For all $`K`$, $`C`$ ($`L`$) values that we have numerically analyzed, for both annealed and quenched cases, $`m_+(p)`$ is a non increasing function of $`p`$, and $`p_c`$ is unique. The estimates of the critical noise levels $`p_{c,a/q}`$, based on $`_{a/q}`$, are obtained by numerically calculating $`m_{c,a/q}(p)`$, and by determining their intersection with $`m_0(p)`$. This is explained graphically in Fig.2(a).

As the results for MPM decoding have already been presented elsewhere cactus , we will now concentrate on the critical results $`p_c`$ obtained for typical set and MAP decoding for Gallager codes; these are presented in Fig.2(b), showing the values of $`p_{c,a/q}`$ for various choices of $`K`$ and $`C`$ compared with those reported in the literature.

¿From the table it is clear that the annealed approximation gives a much more pessimistic estimate for $`p_c`$. This is due to the fact that it overestimates $``$ in the following way. $`_a(m)`$ describes the combined entropy of $`\stackrel{}{n}`$ and $`\stackrel{}{n}^o`$ as if $`\stackrel{}{n}^o`$ were thermal variables as well. Therefore, exponentially rare events for $`\stackrel{}{n}^o`$ (i.e. $`m(\stackrel{}{n}^o)m_0(p)`$) still may carry positive entropy due to the addition of a positive entropy term from $`\stackrel{}{n}`$. In a separate study KNM  these effects have been taken care of by the introduction of an extra exponent; this is not necessary in the current formalism as the quenched calculation automatically suppresses such contributions. The similarity between the results reported here and those obtained in reliability  is not surprising as the equations obtained in quenched calculations are similar to those obtained by averaging the upper-bound to the reliability exponent using a methods presented originally by Gallager gallager . Numerical differences between the two sets of results are probably due to the higher numerical precision here.

We have also obtained the critical noise levels for some parameter choices in MN codes. We only present the quenched (exact) values, and compare them only with the highest theoretically achievable critical noise level $`p_t`$ for any code shannon , as we are not aware of values obtained with other methods in the literature. Note that although still strictly below $`p_t`$, the critical noise levels $`p_c`$ for $`K=L=2`$ with increasing values of $`C`$ rapidly approach $`p_t`$ to within the current numerical precision.

## VII Conclusions

In this paper we have shown how both weight and magnetization enumerators can be calculated using the methods of statistical physics in the case of regular LDPC codes. We study the role played by the magnetization enumerator $`(m)`$ in determining the achievable critical noise level for various decoding schemes. The formalism based on the magnetization enumerator $``$ offers a intuitively simple alternative to the weight enumerator formalism used in conjunction with typical pairs decoding in the IT literature Aji ; KNM . The SP based analysis employes the replica method given the very low critical values obtained by the annealed approximation calculation. Furthermore, the powerfull gauge theory as proposed by Nishimori nishimori\_book , proves that the replica symmetric assumption is correct (at least at the critical noise level), and thus that the critical noise levels as obtained by our method are exact. Although we have concentrated here on the critical noise level for the BSC, other channel types as well as other quantities of interest can be treated using a similar formalism. The predictions for the critical noise level are more optimistic than those reported in the IT literature, and are up to numerical precision in agreement with those reported in KNM . We have also shown that the critical noise levels for typical pairs, MAP and MPM decoding must coincide, and we have provided an intuitive explanation to the difference between MAP and MPM decoding. Finally, an extension of this analysis to MN codes reveals the mechanism which allows them to saturate Shannon’s limit for finite $`K3`$ and for $`K=2,L3`$ values (if impractical algorithms such as maximum likelihood are used). This result, which is consistent with previous SP based analyses us\_prl  is considered as surprising in the IT community.

We believe that SP based analysis will provide more insight into the performance and characteristics of random LDPC codes, complementing the analysis provided by the methods of IT.

Support by Grants-in-Aid Nos. 13680400 and 13780208 (YK), The Royal Society and EPSRC-GR/N00562 (DS/JvM) is acknowledged.