Error exponent

Formally, it is defined as the limiting ratio of the negative logarithm of the error probability to the block length of the code for large block lengths.

is the block length, the error exponent is

Many of the information-theoretic theorems are of asymptotic nature, for example, the channel coding theorem states that for any rate less than the channel capacity, the probability of the error of the channel code can be made to go to zero as the block length goes to infinity.

In practical situations, there are limitations to the delay of the communication and the block length must be finite.

Therefore, it is important to study how the probability of error drops as the block length go to infinity.

The channel coding theorem states that for any ε > 0 and for any rate less than the channel capacity, there is an encoding and decoding scheme that can be used to ensure that the probability of block error is less than ε > 0 for sufficiently long message block X.

Also, for any rate greater than the channel capacity, the probability of block error at the receiver goes to one as the block length goes to infinity.

is received, the probability that the codeword is incorrectly detected as

Thus, Since there are a total of M messages, and the entries in the codebook are i.i.d., the probability that

in the above formula: Using the independence nature of the elements of the codeword, and the discrete memoryless nature of the channel: Using the fact that each element of codeword is identically distributed and thus stationary: Replacing M by 2nR and defining probability of error becomes Q and

Thus, the error exponent can be defined as The source coding theorem states that for any

and for any rate less than the entropy of the source, there is large enough

binary bits such that the source symbols

Next map each of the possible source output sequences to one of the messages randomly using a uniform distribution and independently from everything else.

This rule is equivalent to finding the source sequence

among the set of source sequences that map to message

This reduction follows from the fact that the messages were assigned randomly and independently of everything else.

Thus, as an example of when an error occurs, supposed that the source sequence

denote the event that the source sequence

Thus, attention can be focused on finding an upper bound to the

denote the event that the source sequence

denote the event that the two source sequences

and is independent of everything else have that A simple upper bound for the term on the left can be established as for some arbitrary real number

because the probabilities of a given input sequence are completely deterministic.

The inequality holds in the other case as well because for all possible source strings.

, have that Where the inequalities follow from a variation on the Union Bound.

Finally applying this upper bound to the summation for

is just a dummy variable in the sum gives the following as an upper bound on the probability of error: The term in the exponent should be maximized over

in order to achieve the highest upper bound on the probability of error.

see that the error exponent for the source coding case is: R. Gallager, Information Theory and Reliable Communication, Wiley 1968