text:
# Determining possible avenues of approach using ANTS

## 1 Introduction

Threat assessment is an important part of level 3 data fusion, as defined in . The goal of level 2 data fusion , is to provide an accurate picture of current enemy activity. Given this information about the current time instant, the goal of threat assessment is to extrapolate it into the future to see which own objects are most threatened, and to determine which enemy objects pose the greatest threat. This is a complex task involving modeling the enemy’s units, objectives, estimated knowledge about our forces, and doctrines. The role of threat assessment in level 3 data fusion and its relation to the worst-case risk assessment studied here is discussed further in section 2.1.

The algorithm presented in this paper is designed to give a worst-case scenario of what important locations the enemy objects can reach within certain time limits, given the terrain and the estimated mobility capabilities of the enemy objects. In section 3 we describe how the algorithm works.

Many important optimization problems can not be solved exactly in an efficient way (see, e.g., ). For many problems there are, however, fast, approximate methods that will in most cases give a solution that is “good enough”. One such algorithm, building on ideas from biology, is ant colony optimization (ANTS) . In nature, ants communicate by deploying pheromone (smell) paths that indicate the way between the ant-hill and food supplies. In the ANTS algorithm, ants are simulated agents who move through a search space or energy landscape looking for good locations. When an ant has found a sufficiently good place, it stops and distributes a pheromone along the path it took from its starting position. In our case, ants start from locations of enemy units as given by level 2 data fusion, and their goals are positions of own units. The ants will use the smell in addition to geographical and military-value information to determine where to move. The ANTS algorithm is described in more detail in sections 2.2 and 3. Since we assume that the enemy ants can determine when they have reached an own force-location, the output of our method will be a worst-case result.

Results of the ANTS method for a test scenario are shown in sections 4 and 5, where we give some suggestions for how to present the avenues of approach to a user. Section 6 compares the effective potential determined by ANTS with a calculated potential. Finally, sections 7 to 9 discusses our results and presents some ideas for future extensions of the method.

## 2 Background

### 2.1 Threat versus worst-case risk

Threat assessment is one of the most important and challenging parts of an information fusion system. The method presented in this paper gives a very fast way of obtaining possible avenues of approach given a situation assessment. It does not provide a complete threat analysis. Rather, the output of our algorithm is a map showing an “intelligent guess” as to what areas of the map the enemy may reach. The method will very quickly display a first guess and will then refine this incrementally until it converges to an approximation of the enemy’s avenues of approach. Our algorithm basically simulates many imaginary enemy units doing local searches for own units; this is what makes it a worst-case risk assessment tool. An “exact” threat assessment would assume that the enemy has uncertain information, assign relevant probabilities or beliefs, and produce a ranked list of the enemy’s probable objectives and the paths to them. Such a system could use our ant-based algorithm as a subsystem, combining the output of several runs of this subsystem using, e.g., some sort of Dempster-Shafer  or random set  formalism. Given a Dempster-Shafer belief function describing a situation picture, the ANTS method could be run for each of its focal elements. Attaching the corresponding probability mass to the resulting avenues would then produce a belief function over avenues of approach.

Despite the heuristical nature of ANTS, we argue that this kind of method is an important and indeed necessary part of an operational information fusion system. Our ant-based risk assessor provides a real-time indication of where enemy units might pose the biggest threat. Obtaining a threat analysis that is provably correct or correct with probability $`1ϵ`$ using current methods requires a very large amount of computer resources. Our method, in contrast, runs in real-time and incrementally improves its output. Even in a command and control system that has a complete threat assessment module, an approximate solution such as ours has its place. The output of the fast, approximate algorithm can be used to aid in quick decisions. By comparing the output of this algorithm with the one from a slower but more accurate method, we can find out if the first suggestion was indeed correct. This is very similar to how humans often make a first guess, perhaps without knowing all the facts, and later refine their answer after thinking about the problem. It it also possible that a comparison between the worst-case analysis of ANTS and the action actually taken by the enemy could help us in determining how much the opposite side actually knows.

By having several different subsystems performing the same or nearly the same function, we also gain robustness for the overall system — some parts of it can break down and it will still be able to function. An additional benefit of having two or more subsystems performing the same task is that if the different methods give different results, something extraordinary (e.g., a completely new military strategy is adopted by the enemy) might be taking place and human operators/analysts need to look at the situation in more detail.

Our method can be used for worst-case risk assessment on all levels of force aggregation. It is just as easy to determine where a single tank might be headed as it is to determine where a battalion is going. Note that the geographical/locational information might actually be more accurate for a battalion since there are more restrictions where it can go (e.g., it needs a corridor of certain width).

### 2.2 Ants and Swarm Intelligence

ANTS is a form of collective, intelligent agent system. It is similar to other models for swarm intelligence and crowd behavior (e.g., ). It was first used by Dorigo (e.g., ) to solve the traveling salesperson problem and has later been used for solving problems ranging from graph coloring  to routing and load balancing . The method shares a number of conceptual features with models for describing complex behavior such as Braitenberg vehicles  or Langton’s vant .

ANTS is very similar to random walk or diffusion based methods for solving optimization problems, but adds interaction between the walkers to produce results more quickly. An ant is an agent that moves in the space of all solutions to the problem. The movement is basically a random walk but with one addition. An ant that reaches a good solution to the problem distributes a smell along the path it took to reach this solution. This smell is then sensed by other ants and increases their probability to move to a site with a high smell. This will lead to many ants being attracted to good sites. This process is similar to that used by real ants to communicate paths to food-sources; hence the name “ants” for the agents. ANTS is suited primarily for problems that have a natural representation in a low-dimensional metric space or a graph of not too high connectivity.

Note that the way we use ANTS here is different from traditional optimization. We do not solve an optimization problem. The smell, which gives the ants their ability to solve optimization problems, is here the output of the method. This smell determines avenues of approach, that is, locations where the enemy may move.

It is instructive to compare the ANTS method with tracking methods. The model for how the agents move is similar to that used in for example particle filtering (e.g., ), but adds some extra non-linearity in the form of the use of the smell. This leads to a different, more explicit, kind of interaction between the agents than in tracking models. In a way, we can say that the smell takes the place of observations when we attempt to predict future positions.

Active walker models similar to the ants used here have previously been used to model formation of trails and crowd behavior (e.g., ). One application of this which is somewhat similar to our risk analysis is in urban planning. Another possible application of methods such as these is to crowd-control; here ANTS would be used to predict where a crowd will move.

## 3 The ANTS algorithm

Our method is best explained by examining a situation with one enemy unit. Start by inserting $`N`$ ants at its location. In each time-step, each ant randomly selects a neighbor of its current location and moves there. The probability is not uniform over all neighbors. Instead, the type of the unit represented by the ant and the terrain is taken into account so that, e.g., it is more probable for a tank to move along a road than into a forest. It is also more probable to move into a position that has a high military significance, e.g., with own units nearby, on top of a hill, etc. The probabilities are also modified by smell/pheromone traces left there by other ants. Initially, there is no smell anywhere in the map. As soon as an ant reaches a favorable military position (e.g., one of the target units), it stops and distributes a smell along the way it took to reach its goal.

An ant can represent any of several different types of enemy units, from an infantry-squad to a battalion of tanks. The ants basically perform interacting random walks with probabilities that are site-dependent.

An ant at position $`𝐱`$ uses three kinds of information to determine its future position. First, we have geographical information $`T(𝐲,𝐱)`$ that simply says how long it would take the ant to reach each of the neighboring sites of $`𝐱`$. This information is predetermined and comes from a terrain database of the battlefield. It is different for ants that represent different kinds of enemy units. This information is taken as fixed in our current simulations, but it is straightforward to change this in real-time in order to implement changes in accessibility due to war activity (e.g., a bombed bridge should be reflected in this information).

The second component, denoted $`F(𝐲)`$, is related to the strategic importance of different locations $`𝐲`$. This is highest where the targets that the ants try to reach (i.e., our units) are. A human operator could change this field using their intuition and experience of where the important part of the battle will take place.

The third part is the smell distributed by other ants, $`S(𝐲,t)`$. At $`t=0`$, this is initialized to 0 for all $`𝐲`$:

$$S(𝐲,0)=0.$$
(1)
The smell $`S`$ will be updated during the run of the algorithm, see equation 4 below.

The probability to go to a site $`𝐲`$ from $`𝐱`$ at time $`t`$ is thus given by

$$p(𝐲,𝐱,t)=0$$
(2)
if $`𝐱`$ and $`𝐲`$ are not nearest neighbors, and

$$p(𝐲,𝐱,t)\frac{1}{T(𝐲,𝐱)}+\omega _sS(𝐲,t)+\omega _fF(𝐲)$$
(3)
otherwise. In equation 3, $`T(𝐲,𝐱)`$ is the geographical information regarding the time needed for the ant to move from $`𝐱`$ to $`𝐲`$, $`S`$ and $`F`$ are the smell and value fields introduced above, and $`\omega _s=1`$ and $`\omega _f=1`$ are weights determining the relative importances of the different fields. The constant of proportionality is determined by requiring that summing over all $`𝐲`$ gives unit probability.

A possible addition to the $`F`$ field is to include also information on visibility and range of fire at different points, as is done in . The drawback of doing this is that it adds to the storage and/or computation requirements for the background fields, thus destroying the attractive simplicity of the ants model.

In order to avoid loops, we added a small bias against moving back to where the ant came from. If the new position is equal to the ant’s old position, a new random number is drawn and a new position is determined from it. This reduces the probability for the ant to go back in its own track quadratically. We choose not to completely disallow back-moves in order to avoid an ant getting trapped at a location with only one viable exit. The random number generator used in all simulations was Matlab’s rand-function.

All ants are time-evolved in parallel. As soon as an ant reaches a target site it will stop and a trace of smell will be distributed along the way it took to reach this target. If the path that the ant has traveled is given by the sequence $`𝐱_i`$ for $`i=0,\mathrm{},M`$ (with $`𝐱_0`$ equal to the starting position), we change the smell field according to

$$S(𝐱_j,t+1)=S(𝐱_j,t)+\frac{j}{M}.$$
(4)
For sites $`𝐱`$ not visited by the ant, the old value for $`S`$ is propagated to time $`t+1`$. This smell will be used by other ants to determine their future time-evolution (and also displayed to the user as an indication of where the interesting areas in the map are). A number of possible extensions can be made here: the ant could continue from the target when it has distributed its smell or it could be restarted at the start position.

Pseudo-code for the algorithm is shown in figure 1.

The output of the program is not the final positions of the ants but rather the effective potential $`S(𝐱)`$ determined by the distribution of smell on the map. This distribution will of course change as more and more ants reach the targets. This is an important feature of the algorithm: it will run in real-time and provide incrementally better and better approximations to the threat analysis.

## 4 Results

The test scenario presented here takes place on the map shown in figure 2, where we also show the start position (black circle, close to the center of the map) and the positions of five targets (black x:es, one at the middle of each side of the square and one below and to the right of the center). The enemy unit at the black circle is assumed to have different mobilities on the road (light grey), in the field (white) and forests (dark grey). In the simulations presented here, the mobility in the forests is considerably smaller than that in the other types of terrain, leading to almost zero probability of entering such areas.

In figure 3, we present the “smell” left by the ants that is the output of the method. Smells of different strengths are presented using different gray-scales, where white represents the largest amount of smell in the figure and black the lowest. For visibility we chose to map the smell onto a non-linear gray-scale using a histogram equalization method (see, e.g., ) to determine the appropriate mapping from smell to gray-scale. The results of this transformation for the distribution shown in figure 3 is shown in figure 4. (In practice, the transformation works like a logarithmic gray-scale — more smell-values are mapped to the same grayness at large smells than at lower. It works almost like a filter that filters out all smells higher than some threshold. We found that this gave the best representation of the distribution for this medium. )

By comparing figure 4, which shows the smell after convergence, to figures 5 to 7 which show the smell at earlier times, we can see that the convergence is rather quick for most areas of the map. Note however the anomalous behavior near the top target. At times 100 and 200, the distribution of smell indicates that the enemy would take a detour going first left along the road and then up through fields to reach the top. At time 700, the method has discovered the “correct” avenue of approach to this target. This is a clear indication of the heuristic nature of the algorithm showing both the need to run ANTS until convergence and how it incrementally improves its output.

We have also run tests using different numbers of ants. In figure 8, we show the same scenario but using just 30 ants. It is clear that this is too small a number of ants to be able to provide an accurate risk analysis: the upper target can not be found since the ants get stuck near the center.

Figure 9 shows that using too many ants, in this case $`10^3`$, also does not lead to a good convergence of the smell. In this case it is probably due to too much smell being released near the start, which causes many of the ants to get trapped here. After some experimentation, we tentatively recommend using on the order of 100 ants for each simulation. If there are many targets, it is better to divide the targets into sets containing on the order of $`5`$ targets each and run a separate simulation for each set. The results can then be combined for display in the command and control system.

We have also made tests varying the number and locations of the targets and found similar results to those in the scene presented here. As the number of targets and start positions increases, the probability distribution for future locations will be fuzzier and fuzzier. This also means that it will we harder and harder for a human analyst to determine what is happening. The ANTS algorithm provides hints for where the human should concentrate their attention. For analyzing a complex scene with perhaps dozens or hundreds of interesting goals, it is best to use only a few targets (2-5) at a time and instead run several simulations and combine their output. In this way, the ANTS method will be able to provide a rough guide to where the human analyst should focus their attention.

None of the simulations presented here took more than a minute to run using Matlab 6.5 on an 1.4GHz AMD Athlon CPU, and most of the CPU-time was spent in Matlab’s functions for displaying graphics .

## 5 Visualizing possible avenues of approach

In order to show avenues of approach on the map, we converted the map to a gray-scale representation, using darker shades of gray for areas with smaller mobilities. All subsequent figures show what this map looks like using the smell as a filter to change the gray-scale. We used two different ways of combining the map and the smell. In the first (shown in figure 10), the grayness of a pixel is the product of the map’s grayness at that location and the grayness determined by the smell. In practice, this means that areas of the map where no ant has left any smell will be blacked-out, while those areas that have the most smell (i.e, that the ANTS algorithm consider most interesting) will appear normal. The purpose of this is to draw the user’s attention to the avenues of approach, while the black portions require less attention. It is instructive to compare this with the way the map in computer strategy games like Civilization starts out black and then becomes visible only after the area has been explored by the player.

The second way of combination (figure 11) simply displays the maximum of the map-value and the smell-value at each pixel. This is a better representation since it shows more clearly where the ants move and is less influenced by the roads. The combination using multiplication is better for showing what areas the enemy can reach, while the max-combination better shows the relative differences in occupation probability, and can hence be used for determining where to increase surveillance or attack.

Note that the particular way we present the results is of course not a part of the algorithm. A real implementation would use colors and shading to combine these representations and also allow the user to display, e.g., only those places where the smell is larger than some cut-off value.

## 6 An “exact” potential instead of ANTS

An alternative to using ANTS to determine the effective potential induced by the targets on the terrain is to place sources at the target locations and calculate the exact potential at all locations in the map, taking into account also the terrain. Assuming Gaußian sources of strengths $`K_n`$ and with widths $`\sigma _n`$, the potential at location $`𝐱`$ would then be

$$U_0(𝐱)=\{\underset{n}{}K_n\mathrm{exp}(\frac{𝐫_n𝐱^2}{2\sigma _n})\}(1\frac{𝐱𝐫_0^2}{d^2}),$$
(5)
where $`𝐫_n`$ are the goal positions, $`𝐫_0`$ the start position and $`d`$ the diameter of the map. Note that this potential as well as all other fields used in this paper is assumed to live on the set of points $`𝐱`$ of a discretized lattice representation of the area of operations. Note that the exact expression for the potential in equation 5 is of course completely arbitrary — we choose this modified Gaußian for simplicity. It has nothing to do with the ANTS methods presented here.

Calculating any such potential takes time

$$T_dN_tL^2,$$
(6)
where $`N_t`$ is the number of targets and $`L`$ the linear size of the map. The time needed for the ANTS algorithm to determine the effective potential is

$$T_aN_aT_c,$$
(7)
where $`N_a`$ is the number of ants used and $`T_c`$ is the time needed to reach convergence. For diffusion-based methods without interaction, $`T_c`$ would scale as

$$T_c𝐫_t𝐫_s^2_{𝐫_s},$$
(8)
where $`𝐫_s`$ is the starting position and the average is over all target positions $`𝐫_t`$. The presence of the smell in equation 7, however, leads to a behavior more like that of super-diffusive dynamics,

$$T_c\underset{𝐫_s}{\mathrm{max}}\{𝐫_t𝐫_s^\alpha \},$$
(9)
with $`\alpha `$ close to 1. Since

$$\underset{𝐫_s}{\mathrm{max}}\{𝐫_t𝐫_s^\alpha \}L^\alpha ,$$
(10)
it is clear that ANTS gives a large speed-up over calculating the exact potential.

Figure 12 shows the terrain map modified by sources at the target locations, equation 5, using sources of equal strength 4 and with standard deviation 30. Comparing figure 12 to figure 3, it is clear that the effective potential determined by the ANTS method is a good approximation to this $`U_0`$. To get a measure of the speed of convergence of ANTS, we calculated the discrete Kullback-Leibler  distance

$$K[f,g;t]=\underset{𝐱}{}g(𝐱,t)\mathrm{log}\frac{g(𝐱,t)}{f(𝐱)},$$
(11)
using normalized distributions

$$f(𝐱)=\frac{U_0(𝐱)}{_𝐲U_0(𝐲)}$$
(12)
and

$$g(𝐱,t)=\frac{S(𝐱,t)}{_𝐲S(𝐲,t)}.$$
(13)
We found that the Kullback distance decreased exponentially with time, stabilizing after about 500 time-steps at a value about an order of magnitude smaller than at $`t=0`$. Information such as that displayed in figure 12 could be used to help humans focus on the most important areas of the map. The exact appearance of equation 5 is of course completely arbitrary. In addition to being much faster, the ANTS method also does not require us to postulate any such expression for the potential: it only requires the locations of targets and the parameters governing the distribution of smell in equation 4.

## 7 Discussion

Conventional threat analysis takes the current situation and uses our knowledge of where our important assets are to try to predict where the enemy is headed. ANTS, in contrast, flips the sides: we try to predict what the enemy will do by putting ourselves in their position and determining what we would do, without assuming that the enemy has global information about our assets and positions. We argue that using a local-search method in this way gives a more robust threat prediction, since the output is determined by simulating the enemy, not by trying to guess their objectives. The ANTS algorithm can be easily adapted to new information regarding enemy behavior (by changing equation 3). This is important, since potential enemies will also have computer systems to aid them, probably leading to more surprising tactics.

Another goal of using ANTS is to minimize the amount of work needed by humans. Given a terrain map and the locations of enemy forces, humans can often determine possible avenues of approach visually, and then decide where to concentrate own forces and sensors in defense. Our method does not aim to completely replace such human analysis, but can act as a first step by suggesting such avenues to the analyst. The output of our program, together with the output from the situation assessment routines that are used as inputs to our program, help the human operators to focus only on the most important parts of the map. In addition, since the ANTS algorithm is meant to run interactively and provide incrementally better distributions as time goes, it can also be adapted to give an answer to the question of what would happen if the enemy suddenly receives some new information.

## 8 Future extensions

Our current ANTS method can be extended in a number of ways. It is, for instance, possible to add some movement of the targets (i.e., our units) or to include changes in mobility caused by blowing up bridges.

In the simulations presented here, we have used just one type of object to track at all times. It is straightforward to extend the method so that it can handle situations where it is given several different types of objects (e.g., a platoon of tanks at position $`𝐱`$ and a company of infantry at position $`𝐲`$) as input to get the combined threat posed by all of these. Ants with different mobilities should then be started at each of the enemy positions, and the output should be changed so that it gives smells for all types of objects. Ants should here be attracted primarily to smell of its own type, but also to that of other types. This makes it possible to model things like tanks following scout patrols of infantry, or infantry following tanks.

The ANTS method as presented here can also be used for the more interesting problem of “opportunity analysis”, i.e., to determine what possibilities own forces have given an accurate situation picture. We are planning to study these and other extensions to ANTS in future work.

## 9 Conclusions

In conclusion, we showed how ANTS can be used to get a quick worst-case risk assessment. By simulating the enemy instead of relying on static assumptions of their objectives, we obtain a method that is more robust if the enemy also uses computer-assisted command and control systems. The ANTS method should be integrated in a command and control system and provide a first, real-time indication of avenues of approach. More thorough analysis methods should also be part of this system and will give an updated more exact picture at some later time. The system should also contain modules that automatically compare the quick picture with the reliable one, and warns the human operators when they differ by too much.

The possible avenues of approach that is the output of the ANTS method can also aid in sensor allocation and management, to help determine which areas should be surveyed by sensors such as UAV’s.

Acknowledgements:  We thank Christian Mårtenson and Johan Schubert for helpful discussions.


format: text

text:
# Average and reliability error exponents in low-density parity-check codes

## 1 Introduction

Low-density parity-check codes (LDPC) have attracted significant interest in recent years due to their simplicity and exceptionally high performance . Their simplicity and inherent randomness make them amenable to analysis using established methods in the area of statistical physics. These have been employed in a number of papers - to gain insight into the properties of LDPC codes and to evaluate their performance.

These studies include the evaluation of critical noise levels for given codes , an exact calculation of weight and magnetisation enumerators , the performance of irregular codes , properties of codes in real-valued channels , and the derivation of bounds for the reliability exponent , to name but a few. These studies also represent the interdisciplinary nature of this research area and illustrate the successful interaction between researchers in the two disciplines.

The evaluation of error exponents has been a long-standing problem in information theory . Efforts to obtain exact expressions and/or bounds to the error exponent resulted in partial success; although tight bounds have been derived in the case of random codes and LDPC with infinite connectivity , only limited results have been obtained for sparely connected codes. Main stream techniques to tackle the problem include sphere-packing and union-bound arguments . Below a certain code-rate value, the estimated bounds also become loose and require using the ‘expurgated exponent’ techniques  for obtaining a tighter bound.

In this paper, we employ methods of statistical physics to evaluate directly the average error exponent and typical reliability exponent in Gallager and MN  LDPC codes. The average error exponent is obtained by carrying out averages over the ensemble of randomly generated LDPC codes of given rate and connectivity; while the reliability exponent is obtained by selecting the best codes in that ensemble. Averages result in the emergence of macroscopic variables, representative of the ensemble properties, that can be obtained numerically and used to calculate the average error exponent (in the current calculation we assume that short loops, which contribute polynomially to the block error probability in LDPC codes , have been removed). Average error exponent solutions have been obtained for both finite and infinite connectivity vector ensembles, while reliability exponent solutions have been obtained only in the case of infinite connectivity.

As a reference point to test our theory, we use known results obtained in the information theory literature for solvable limits (e.g. codes of infinite connectivity), and find that our method reproduces them exactly. Perhaps not surprisingly, we also find that at fixed noise level and code rate, the reliability exponent for codes of finite connectivity is always upper-bounded by that of the infinite-connectivity case.

Before we proceed, the distinction between the typical bounds found previously using methods of statistical physics , and the current calculation should be clarified. In the former, one employs methods of statistical physics to calculate the typical value of a bound based on inequalities introduced by Gallager; while in the current calculation, a direct estimation of the average error exponent, rather than a bound, is sought. An additional advantage of the current approach is that it can be extended to provide reliability exponent values for LDPC codes by restricted averages over codes of high performance.

The paper is organised as follows: In section 2, we introduce the general coding framework and the technique used. In sections 3 and 4 we present an outline of the derivation and the solutions obtained in both finite and infinite connectivity cases respectively. In Section 5 we compare the error exponent results obtained for MN codes to those of Gallager codes in both finite and infinite connectivity cases. Discussion and conclusions are presented in section 6.

## 2 Definitions

A regular ($`k,j`$) Gallager error-correcting code is defined by the binary $`(NK)\times N`$ (parity check) matrix $`A=[C_1|C_2]`$, which is known to both sender and receiver. The $`(NK)\times (NK)`$ matrix $`C_2`$ is taken to be invertible. The number of non-zero elements in each row of $`A`$ is given by $`k`$, while the number of non-zero elements per column is given by $`jk(NK)/N`$.

Gallager’s encoding scheme consists of generating a codeword $`𝒕\{0,1\}^N`$ from an information (message) vector $`𝒔\{0,1\}^K`$ (with $`N>K`$) via the linear operation $`𝒕=G^T𝒔`$ (mod 2) where $`G`$ is the generator matrix defined by $`G=[I|C_2^1C_1]`$ (mod 2). The code rate is then given by $`RK/N=1j/k`$, and measures the information redundancy of the transmitted vector.

Upon transmission of the codeword $`𝒕`$ via a noisy channel, taken here to be a BSC, the vector $`𝒓=𝒕+𝒏^0`$ (mod 2) is received, where $`𝒏^0\{0,1\}^N`$ is the true channel noise. The statistics of the BSC is fully determined by the flip rate $`p[0,1]`$:

$$P(n_i^0)=(1p)\delta _{n_i^0,0}+p\delta _{n_i^0,1}$$
(1)
Decoding is carried out by multiplying $`𝒓`$ by $`A`$ to produce the syndrome vector $`𝒛=A𝒓=A𝒏^0`$, since $`AG^T=0`$ by construction. In order to reconstruct the original message $`𝒔`$, one has to obtain an estimate $`𝒏`$ for the true noise $`𝒏^0`$. First we select the parity check set of $`A`$ and $`𝒏^0`$, i.e. all $`𝒏`$ that satisfy the parity check equations: $`_{pc}(A,𝒏^0)\{𝒏|A𝒏=A𝒏^0\}`$. Since all operations are performed in modulo 2 arithmetic, $`_{pc}(A,𝒏^0)`$ typically contains $`\mathrm{exp}[NR\mathrm{ln}(2)]`$ candidates for the true noise vector $`𝒏^0`$.

It was shown (see e.g.  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. From the parity check matrix $`A`$ we construct the binary tensor $`𝒜=\{𝒜_{i_1\mathrm{}i_k},1i_1<i_2\mathrm{}<i_kN\}`$, where $`𝒜_{i_1\mathrm{}i_k}=1`$ if $`A`$ has a row in which the elements $`\{i_c,c=1,\mathrm{},k\}`$ are all 1 (i.e. when the bits $`i_1\mathrm{}i_k`$ are involved in the same parity check), and 0 otherwise. The fact that each bit $`i_1=1,\mathrm{},N`$ is involved in exactly $`j`$ parity checks is then expressed by $`_{i_2<\mathrm{}<i_k}𝒜_{i_1\mathrm{}i_k}=j,i_1=1,\mathrm{},N`$ and the parity check equations become $`_{c=1}^kn_{i_c}=_{c=1}^kn_{i_c}^0`$, $`𝒜_{i_1\mathrm{}i_k}=1`$.

Decoding now consists in selecting an $`𝒏`$ from $`_{pc}(𝒜,𝒏^0)`$, on the basis of its noise statistics, which are fully described by its magnetisation $`m(𝒏)=1/N_in_i`$ (corresponding to the weight in the information theory literature). Note that the number of flipped bits in a candidate noise vector $`𝒏`$ is given by $`N(1m(𝒏))/2`$. Therefore, we introduce a Hamiltonian or cost function for each noise candidate that is negatively proportional to its magnetisation:

$$H(𝒏)=F\underset{i=1}{\overset{N}{}}n_i=FNm(𝒏)$$
(2)
where we take $`F=\frac{1}{2}\mathrm{log}\frac{1p}{p}`$, such that up to normalisation $`\mathrm{exp}(H(𝒏))`$ yields the correct prior for candidate noise vectors generated by the BSC . Then, a vector $`𝒏`$ from $`_{pc}(𝒜,𝒏^0)`$ with the highest magnetisation (lowest weight) is selected as a solution; this corresponds to Maximum A Posteriori (MAP) decoding.

We are now interested in the probability that other candidate noise vectors are selected from the parity check set $`_{pc}(𝒜,𝒏^0)`$, other than the correct (i.e. true) noise vector $`𝒏^0`$, for any given combination $`\{𝒏^0,𝒜\}`$; this is termed the block error probability. In order to calculate this probability, we introduce an indicator function:

$$\mathrm{\Delta }(𝒏^0,𝒜)=\underset{\beta _{1,2}\mathrm{}}{lim}\underset{\lambda _{1,2}\pm \lambda }{lim}\left[Z_1^{\lambda _1}(𝒏^0,𝒜;\beta _1)Z_2^{\lambda _2}(𝒏^0,𝒜;\beta _2)\right]|_{\beta _1=\beta _2=\beta }$$
(3)
where

$$Z_1(𝒏^0,𝒜;\beta _1)=\underset{𝒏_{pc}(𝒏^0,𝒜)\backslash 𝒏^0}{}e^{\beta _1H(𝒏)},Z_2(𝒏^0,𝒜;\beta _2)=\underset{𝒏_{pc}(𝒏^0,𝒜)}{}e^{\beta _2H(𝒏)}.$$
(4)
The partition functions $`Z_1(𝒏^0,𝑨;\beta _1)`$ and $`Z_2(𝒏^0,𝑨;\beta _2)`$ differ only in the exclusion of $`𝒏^0`$ from $`Z_1`$. If the true noise $`𝒏^0`$ has the highest magnetisation of all candidates in the parity check set (decoding success), the Boltzmann factor $`\mathrm{exp}[\beta H(𝒏^0)]`$ will dominate the sum over states in $`Z_2`$ in the limit $`\beta \mathrm{}`$, and $`\mathrm{\Delta }(𝒏^0,𝒜)=0`$. Alternatively, if some other vector $`𝒏𝒏^0`$ has the highest magnetisation of all candidates in the parity check set (decoding failure), its Boltzmann factor will dominate both $`Z_1`$ and $`Z_2`$ and $`\mathrm{\Delta }(𝒏^0,𝒜)=1`$. Note that the separate temperatures $`\beta _1`$ and $`\beta _2`$, which are put to be equal to $`\beta `$ in the end, and the powers $`\lambda _{1,2}`$ which are taken to be $`\pm \lambda `$ in the end, have been introduced in order to allow us to determine whether obtained solutions are physical or not. The power $`\lambda 0`$ have been introduced to restrict the indicator function results to 0/1. In principle, this can be done by taking the limit $`\lambda 0`$; however, in section 3, we show that finite $`0<\lambda <1`$ values will be used due to various constraints.

To derive the average error exponent, we take the logarithm of the indicator function average with respect to all possible realisations of true noise vectors $`𝒏^0`$, and the ensemble of regular $`(k,j)`$ codes $`𝒜`$:

$$Q=\underset{N\mathrm{}}{lim}\frac{1}{N}\mathrm{log}\mathrm{\Delta }(𝒏^0,𝒜)_{𝒏^0}_𝒜$$
(5)
where

$$f(𝒏^0)_{𝒏^0}=\frac{1}{(2\mathrm{cosh}F)^N}\underset{𝒏^0}{}\mathrm{exp}(F\underset{i}{}n_i^0)f(𝒏^0)$$
(6)
and

$$f(𝒜)_𝒜=\frac{_𝒜_{i_1=1}^N\delta [_{i_2<\mathrm{}<i_k}𝒜_{i_1\mathrm{}i_k}j]f(𝒜)}{_𝒜_{i_1=1}^N\delta [_{i_2<\mathrm{}<i_k}𝒜_{i_1\mathrm{}i_k}j]}.$$
(7)
To obtain an expression for the reliability exponent one carries out a similar calculation with one main difference: prior to averaging the indicator function over the ensemble of regular $`(k,j)`$ codes $`𝒜`$, one takes the averaged expression with respect to realisations of true noise vectors $`𝒏^0`$ to a power $`r`$ which favours code constructions with a low average error probability (i.e., $`r<1`$). The logarithm of the expression averaged over the ensemble of codes $`𝒜`$ is then divided by $`r`$ to remove the exponent. The expression calculated is:

$$Q_r=\underset{N\mathrm{}}{lim}\frac{1}{Nr}\mathrm{log}\left[\mathrm{\Delta }(𝒏^0,𝒜)_{𝒏^0}\right]^r_𝒜$$
(8)
Since there are only discrete degrees of freedom, physically meaningful solutions must have a non-negative entropy, requiring the disorder-averaged entropies of the two partition functions (4) to be non-negative. Note that due to the order of taking the logarithm vs the various averages, expressions (5) and (8) are not equivalent to a (quenched) disorder-averaged free energy. Using general principles one can show that for general values of $`\beta _{1,2}`$ and $`\lambda _{1,2}`$, the disordered-averaged entropies (with averages taken over the joint distribution of code-constructions $`\{𝒜\}`$, true- and candidate-noise $`\{𝒏^0,𝒏\}`$ as suggested by (5) and (8)) are given, for both calculations (5) and (8), by

$$S_x=\frac{Q_r}{\lambda _x}\frac{\beta _x}{\lambda _x}\frac{Q_r}{\beta _x}0,x=1,2$$
(9)
which have to be positive.

## 3 Average error exponent - general solution

Using standard statistical physics methods such as in , we perform the gauge transformation $`n_in_in_i^0`$, and the averages over true noise (6) and code constructions (7). In the case of $`r1`$, each quantity carries two indices (a replica index and another index coming from the power $`r`$); however, the two indices factorise unless an explicit, more complex, symmetry breaking structure is introduced. Here, we do not assume a more complex structure that entangles the two types of indices; we also assume the simplest replica symmetric scheme  to arrive at the following expression for the average error exponent ($`r=1`$), and for the reliability exponent (optimised $`r`$):

$$Q_r(\beta _1,\beta _2,\lambda _1,\lambda _2)=\frac{1}{r}\mathrm{Extr}_{\pi ,\widehat{\pi }}\left[\frac{j}{k}\mathrm{log}I_1[\pi ]j\mathrm{log}I_2[\pi ,\widehat{\pi }]+\mathrm{log}I_3[\widehat{\pi }]\right]$$
(10)
where

$$I_1=\underset{c=1}{\overset{k}{}}\left\{d\pi (x_c,y_c)\right\}\left(\frac{1+_{c=1}^kx_c}{2}\right)^{r\lambda _1}\left(\frac{1+_{c=1}^ky_c}{2}\right)^{r\lambda _2}$$
(11)
$$I_2=\left\{d\pi (x,y)d\widehat{\pi }(\widehat{x},\widehat{y})\right\}\left(\frac{1+x\widehat{x}}{2}\right)^{r\lambda _1}\left(\frac{1+y\widehat{y}}{2}\right)^{r\lambda _2}$$
(12)
$`I_3`$ $`=`$ $`{\displaystyle }{\displaystyle \underset{c=1}{\overset{j}{}}}\left\{d\widehat{\pi }(\widehat{x}_c,\widehat{y}_c)\right\}\left[{\displaystyle \underset{u=\pm 1}{}}e^{\beta _1Fn^0u}{\displaystyle \underset{c=1}{\overset{j}{}}}\left({\displaystyle \frac{1+u\widehat{x}_c}{2}}\right)\right]^{\lambda _1}`$ (13)
$`\times \left[{\displaystyle \underset{v=\pm 1}{}}e^{\beta _2Fn^0v}{\displaystyle \underset{c=1}{\overset{j}{}}}\left({\displaystyle \frac{1+v\widehat{y}_c}{2}}\right)\right]^{\lambda _2}_{n^0}^r`$
where we have used the short-hand notation $`df(x,y)`$=$`dxdyf(x,y)`$. For $`r=1`$, functional extremisation of (10) with respect to the densities $`\pi (x,y)`$ and $`\widehat{\pi }(\widehat{x},\widehat{y})`$ results in a closed set of equations (reminiscent of ‘density evolution’ equations ):

$$\widehat{\pi }(\widehat{x},\widehat{y})=\underset{c=1}{\overset{k1}{}}\left\{d\pi (x_c,y_c)\right\}\delta \left[\widehat{x}\underset{c=1}{\overset{k1}{}}x_c\right]\delta \left[\widehat{y}\underset{c=1}{\overset{k1}{}}y_c\right]$$
(14)
$$\pi (x,y)=\frac{\delta \left[x\frac{D_{}(\widehat{𝒙};\beta _1)}{D_+(\widehat{𝒙};\beta _1)}\right]\delta \left[y\frac{D_{}(\widehat{𝒚};\beta _2)}{D_+(\widehat{𝒚};\beta _2)}\right]^{}}{1\frac{}{}^{}}.$$
(15)
where

$`{\displaystyle \frac{}{}}^{}`$ $``$ $`{\displaystyle }{\displaystyle \underset{c=1}{\overset{j1}{}}}\left\{d\widehat{\pi }(\widehat{x}_c,\widehat{y}_c)\right\}D_+^{\lambda _1}(\widehat{𝒙};\beta _1)D_+^{\lambda _2}(\widehat{𝒚};\beta _2)_{n^0},`$ (16)
$`D_\pm (𝒛;\beta )`$ $``$ $`[e^{\beta Fn^0}{\displaystyle \underset{c=1}{\overset{j1}{}}}(1+z_c)]\pm [e^{\beta Fn^0}{\displaystyle \underset{c=1}{\overset{j1}{}}}(1z_c)].`$ (17)
For given $`(\beta _1,\beta _2,\lambda _1,\lambda _2)`$ in general, solutions to (14) and (15) can only be obtained numerically. Inserting these solutions into (10) we then obtain $`Q(\beta _1,\beta _2,\lambda _1,\lambda _2)`$, which becomes the average error exponent for $`\lambda _1=\lambda _2=\lambda >0`$, and for $`\beta _1=\beta _2=\beta \mathrm{}`$.

We must recall, however, that physically meaningful solutions must satisfy the conditions (9) stating that the entropies related to the full and the restricted partition sums are non-negative.

We restrict ourselves to regions below the thermodynamic transition where the average case is dominated by the ferromagnetic solution, such that we can fix the system described by $`Z_2`$ in (4) to the ferromagnetic solution. This dominance is guaranteed if the following constraint is satisfied

$$\frac{Q}{\beta }|_{\lambda _1=\lambda _2=\lambda }0.$$
(18)
It turns out that for given $`\lambda >0`$, the largest value of $`\beta `$ for which (18) is satisfied is given by the simple expression $`\beta =1/(1+\lambda )`$. Hence, in order to maximise $`\beta `$, we must look for the smallest value $`\lambda _{}`$ that satisfies the conditions on the non-negativity of the entropies (9). Unfortunately, in general this value $`\lambda _{}`$ can only be obtained numerically. The value obtained for the average error exponent by this analysis is then given by $`Q(1/(1+\lambda _{}),1/(1+\lambda _{}),\lambda _{},\lambda _{})`$ from (10).

In figure 1 we present the obtained average error exponent as a function of the flip rate for $`(k,j)=(4,3)`$, ($`R=1/3`$) and $`(k,j)=(6,3)`$ ($`R=1/2`$) codes. We observe that the error exponent indeed converges to zero, as it should, when the flip rate approaches its critical value.

Notice the similarity between the equations obtained here and in  in spite of the different starting points. It has been shown in  that the analysis should be refined in low rate regions by considering a more complex bound. The refined analysis resulted in tight bounds of the error exponent even in the region of low code-rates, similar to those obtained using expurgated exponent methods. In the next section we will show that the selection of ’best codes’ through the optimisation of the power $`r`$, in calculating the reliability exponent, provides similar results to those obtained in .

## 4 An exactly solvable limit: $`k,j\mathrm{}`$

Whereas for finite density codes solutions for the average error exponent are obtained numerically, in the limit of $`k,j\mathrm{}`$ (while keeping the rate $`R=1j/k`$ finite) one obtains two types of analytic solutions to equations (14) and (15), which can be verified by substitution. Moreover, in this limit one also obtains solutions in the reliability exponent calculation (8), which are generally difficult to obtain for finite $`k`$ and $`j`$ values.

### 4.1 Average error exponent

Solutions obtained in the average error exponent calculation take the following form:
Type I:

$`\pi (x,y)`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left[\delta (x1)+\delta (x+1)\right]\delta (y1)`$
$`\widehat{\pi }(\widehat{x},\widehat{y})`$ $`=`$ $`{\displaystyle \frac{1}{2}}\left[\delta (\widehat{x}1)+\delta (\widehat{x}+1)\right]\delta (\widehat{y}1)`$ (19)
Type II:

$`\pi (x,y)`$ $`=`$ $`\delta (y1)[G_+(F(1+\beta _2\lambda _1))\delta (x\mathrm{tanh}(\beta _1F))`$
$`+`$ $`G_{}(F(1+\beta _2\lambda _2))\delta (x+\mathrm{tanh}(\beta _1F))]`$
$`\widehat{\pi }(\widehat{x},\widehat{y})`$ $`=`$ $`\delta (\widehat{y}1)\delta (\widehat{x})`$ (20)
with $`G_\pm (x)=\frac{1}{2}[1\pm \mathrm{tanh}(x)]`$.

Taking $`\beta _1=\beta _2=\beta `$ and $`\lambda _1=\lambda _2=\lambda `$, the average error exponent as obtained from the type I solution is given by

$$Q_I=\frac{j}{k}\mathrm{log}2\mathrm{log}\mathrm{cosh}F+\mathrm{log}\mathrm{cosh}(\beta F\lambda )+\mathrm{log}2\mathrm{cosh}(F\beta F\lambda ).$$
(21)
We find that the entropies (9) are always identically zero, and that the constraint (18) requires that $`\beta =1/2`$, such that $`\lambda =1`$ and

$$Q_I=\frac{j}{k}\mathrm{log}2\mathrm{log}[e^F+e^F]+\mathrm{log}[e^F+e^F+2]$$
(22)
which is exactly the Bhattacharyya limit .

The average error exponent as obtained from the type II solution is given by

$$Q_{II}=\lambda \left[\frac{j}{k}\mathrm{log}2+\mathrm{log}2\mathrm{cosh}[\beta F]\right]+\mathrm{log}[2\mathrm{cosh}(F\beta F\lambda )]\mathrm{log}2\mathrm{cosh}F$$
(23)
The condition on the entropy $`S_20`$ is satisfied for all $`\beta >0`$, whereas the condition $`S_10`$ is violated below the critical (freezing) temperature $`1/\beta ^{}`$ obtained from

$$\frac{j}{k}\mathrm{log}2\beta ^{}F\mathrm{tanh}[\beta ^{}F]+\mathrm{log}2\mathrm{cosh}[\beta ^{}F]=0$$
(24)
This negative entropy is an artifact of the assumption about the symmetry between replicas, and is easily remedied by considering a ‘frozen RSB’ ansatz . Using this ansatz and taking into account condition (18), the (frozen) average error exponent obtained from the type II solution, is finally given by

$$Q_{II}^{fr}=F\mathrm{tanh}[\beta ^{}F]+\frac{j}{k}\mathrm{log}2\mathrm{log}2\mathrm{cosh}F$$
(25)
What remains is to determine whether the type I or type II solution is physically dominant, by using $`Q`$ as a generating function for calculating the related free energies (through its derivative with respect to $`\lambda `$). Results for the case of $`k,j\mathrm{}`$ are presented in figure 2 for $`p=0.01`$ and $`p=0.05`$.

### 4.2 Reliability exponent

To obtain the reliability exponent we take equations (10)-(13) and optimise with respect to $`r`$. Deriving a general set of equations similar to (14,15), that can be solved iteratively, is difficult in this case. However, in the limit $`k,j\mathrm{}`$, we observe that we can restrict the possible solutions of $`\widehat{\pi }(\widehat{x},\widehat{y})`$ to two different types:
Type I:

$$\widehat{\pi }(\widehat{x},\widehat{y})=\frac{1}{2}\left[\delta (\widehat{x}1)+\delta (\widehat{x}+1)\right]\delta (\widehat{y}1)$$
(26)
Type II:

$$\widehat{\pi }(\widehat{x},\widehat{y})=\frac{}{}\delta (\widehat{x})\delta (\widehat{y}1)$$
(27)
In this case, knowledge of the solution for $`\widehat{\pi }(\widehat{x},\widehat{y})`$ is sufficient for calculation the reliability exponent (10). Furthermore, the expression obtained from the type II solution turns out to be identical to that of the average error exponent (25).

On the other hand, the reliability exponent obtained from the type I solution is somewhat different, and takes the form:

$$Q_{rI}=\frac{1}{r}\frac{j}{k}\mathrm{log}2\mathrm{log}[\mathrm{cosh}(F)]+\frac{1}{r}\mathrm{log}[\mathrm{cosh}^r(F)+\mathrm{cosh}^r((2\beta \lambda 1)F)].$$
(28)
Given the relation (18) and $`\beta =1/(1+\lambda )`$, one obtains $`\lambda =1`$, $`\beta =1/2`$, and the expression reduces to

$$Q_{rI}=\frac{1}{r}\frac{j}{k}\mathrm{log}2\mathrm{log}[\mathrm{cosh}(F)]+\frac{1}{r}\mathrm{log}[\mathrm{cosh}^r(F)+1].$$
(29)
Optimising the expression with respect to $`r`$, one obtains a similar expression to the expurgated exponent result

$$E_{ex}(r,R)=\underset{r}{max}\left\{\mathrm{ln}2\mathrm{cosh}F\frac{1}{r}\mathrm{ln}\left[(2\mathrm{cosh}F)^r+1\right]+\frac{1}{r}(1R)\mathrm{ln}2\right\},$$
(30)
which is also identical to the result obtained for the average bound of the reliability exponent in .

The reliability exponent is therefore identical to the average error exponent except for very low $`R`$ values as shown in figure 2 for $`p=0.01`$ and $`p=0.05`$ (marked by a dotted line in the two cases considered).

## 5 MN codes

In this section, we extend our treatment of the average error and reliability exponent to regular MN codes , a variant of LDPC codes.

A regular MN code is defined by the binary $`N\times (N+K)`$ matrix $`A=[C_s|C_n]`$, concatenating two sparse matrices with the $`N\times N`$ matrix $`C_n`$ assumed invertible. The $`N\times K`$ matrix $`C_s`$ has $`k`$ non-zero elements per row and $`j`$ per column while $`C_n`$ has $`t`$ non-zero elements per row and per column. The code rate is given by $`RK/N=k/j`$. The encoding scheme consists of generating a codeword $`𝒕^0\{0,1\}^N`$ from an (unbiased) message vector $`𝒔^0\{0,1\}^K`$ via $`𝒕^0=(C_n^1C_s)𝒔^0`$. Upon sending $`𝒕^0`$ through the noisy channel the vector $`𝒓=𝒕^0+𝒏^0`$ is received, where $`𝒏^0`$ is the true channel noise (1).

Decoding is carried out by multiplying the received vector $`𝒓`$ by $`C_n`$ to produce the syndrome vector $`𝒛=C_s𝒔^0+C_n𝒏^0`$. In order to reconstruct the original message, one selects the best estimate $`(𝒔,𝒏)`$, for the true $`(𝒔^0,𝒏^0)`$ from the parity check set $`_{pc}=\{(𝒔,𝒏)|C_s𝒔+C_n𝒏=𝒛\}`$, on the basis of the message/noise statistics. Note that since we take the message vector $`𝒔^0`$ to be unbiased, the selection will only be based on the noise statistics.

Since most calculation steps are completely analogous (although lengthier) to those of Gallager codes, we only state the final general expression for MN codes:

$`Q_r(\beta _1,\beta _2,\lambda _1,\lambda _2)`$ $`=`$ $`{\displaystyle \frac{1}{r}}\mathrm{Extr}_{\pi ,\widehat{\pi },\rho ,\widehat{\rho }}\{{\displaystyle \frac{}{}}`$
$`k\mathrm{log}{\displaystyle \left\{d\pi (x,y)d\widehat{\pi }(\widehat{x},\widehat{y})\right\}\left(\frac{1+x\widehat{x}}{2}\right)^{r\lambda _1}\left(\frac{1+y\widehat{y}}{2}\right)^{r\lambda _2}}`$
$`t\mathrm{log}{\displaystyle \left\{d\rho (x,y)d\widehat{\rho }(\widehat{x},\widehat{y})\right\}\left(\frac{1+x\widehat{x}}{2}\right)^{r\lambda _1}\left(\frac{1+y\widehat{y}}{2}\right)^{r\lambda _2}}`$
$`+\mathrm{log}{\displaystyle \underset{i=1}{\overset{k}{}}\left\{d\pi (x_i,y_i)\right\}\underset{l=1}{\overset{t}{}}\{d\rho (u_l,v_l)\}\left(\frac{1+_ix_i_lu_l}{2}\right)^{r\lambda _1}\left(\frac{1+_iy_i_lv_l}{2}\right)^{r\lambda _2}}`$
$`+{\displaystyle \frac{k}{j}}\mathrm{log}{\displaystyle \underset{c=1}{\overset{j}{}}\left\{d\widehat{\pi }(\widehat{x}_c,\widehat{y}_c)\right\}\left[\underset{\sigma =\pm }{}\underset{c=1}{\overset{j}{}}\left(\frac{1+\sigma \widehat{x}_c}{2}\right)\right]^{r\lambda _1}\left[\underset{\sigma =\pm }{}\underset{c=1}{\overset{j}{}}\left(\frac{1+\sigma \widehat{y}_c}{2}\right)\right]^{r\lambda _2}}`$
$`+\mathrm{log}{\displaystyle }{\displaystyle \underset{l=1}{\overset{t}{}}}\left\{d\widehat{\rho }(\widehat{x}_l,\widehat{y}_l)\right\}\left[{\displaystyle \underset{\tau =\pm }{}}e^{\beta _1\tau Fn^0}{\displaystyle \underset{l=1}{\overset{t}{}}}\left({\displaystyle \frac{1+\tau \widehat{x}_l}{2}}\right)\right]^{\lambda _1}`$
$`\times \left[{\displaystyle \underset{\tau =\pm }{}}e^{\beta _2\tau Fn^0}{\displaystyle \underset{l=1}{\overset{t}{}}}\left({\displaystyle \frac{1+\tau \widehat{y}_l}{2}}\right)\right]^{\lambda _2}_{n^0}^r\}`$
with the short-hand notation $`df(x,y)`$=$`dxdyf(x,y)`$. As for Gallager codes, for $`\beta _1=\beta _2=\beta `$, and $`\lambda _1=\lambda _2=\lambda `$, $`Q_r`$ becomes the average error exponent for $`r=1`$ , while for optimised $`r`$ it becomes the reliability exponent. Furthermore, the conditions (9) and (18) must always be satisfied.

Similarly to the case of Gallager codes one can derive a set of functional equations (reminiscent of ’density evolution’ equations ) for $`\pi ,\widehat{\pi },\rho `$ and $`\widehat{\rho }`$.

### 5.1 Average error exponent - finite $`k,j`$ and $`t`$

The average error exponent can be calculated numerically for finite $`k,j`$ and $`t`$ values; the average error exponent $`Q`$ as function of the flip rate $`p`$ is shown in figure 3.

On the left, we show results for MN codes of fixed rate $`R=1/4`$ with three different sets of parameters $`(k,j,t)=(1,4,2)`$ (circles), $`(2,8,3)`$ (diamonds) and $`k,j\mathrm{}`$ (upper line). It is interesting to notice that average exponents for either $`k>2`$ or $`t>2`$ values coincide with that of the infinite connectivity case (which can be obtained analytically). This complements other interesting properties of MN codes, to do with their critical flip rate values, that have been obtained previously, distinguishing them from Gallager LDPC codes .

On the right, we see a comparison between average error exponents of Gallager and MN codes ($`R=1/2`$). The Gallager code $`(k,j)=(6,3)`$ average error exponent (circles) is significantly below the random code $`k,j\mathrm{}`$ value (thin upper line) and the equivalent MN code $`(k,j,t)=(3,6,3)`$ result (diamonds).

### 5.2 Average and reliability error exponents - $`k,j,t\mathrm{}`$

The case of $`k,j,t\mathrm{}`$ is solvable exactly for all transmission rates, and both average and reliability error exponents can be obtained analytically. The solutions obtained as well as the average and reliability error exponents calculated are identical to those of Gallager LDPC codes. Retrospectively, this is not surprising as both codes become random codes in this limit.

## 6 Discussion

In this paper we suggest a method for direct evaluation of the average and reliability error exponent over the ensemble of LDPC error-correcting codes of given rate and connectivity. An analytical solution has been obtained, for both Gallager and MN codes, using methods of statistical physics, which is in perfect agreement with known results in the limit $`k,j(,t)\mathrm{}`$ (with $`R`$ finite). The results for MN and Gallager codes become identical in this limit as both become random codes.

Average error exponent results obtained by our method for codes of finite $`(k,j)`$ values cannot be obtained using traditional approaches used in the information theory community. As expected, they seem to be upper bounded by the $`k,j\mathrm{}`$ curves, but suggest a profoundly different behaviour for Gallager and MN LDPC codes. Average error exponent results for Gallager codes show a gradually improved performance as the parameters ($`k,j`$) increase, until they finally coincide with the $`k,j\mathrm{}`$ error exponent result. The results for MN codes becomes identical to the $`k,j\mathrm{}`$ error exponent result for all $`k>2`$ or $`t>2`$. To some extent, this is in agreement with previous results obtained for the critical flip rate of MN codes  and is a result of the close-to-random codebook they generate.

An interesting feature of the present study is the similarity of our equations to those obtained in  in spite of the different approaches used. An important advantage offered by the current approach is a potential extension to select high performance codes to obtain reliability exponent values for LDPC codes of finite connectivity; obtaining such solutions remains a difficult task and is currently under study.

Support from EPSRC research grant GR/N63178 (DS,NS), the Royal Society (DS,NS,JvM), Grants-in-aid, MEXT (13680400 and 13780208) and JSPS (YK) is acknowledged.

## Reference