Error exponent

Error exponent

In information theory, the error exponent of a channel code or source code over the block length of the code is the logarithm of the error probability. For example, if the probability of error of a decoder drops as "e"–"n"α, where "n" 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 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 of the code cannot be taken to go to infinity. Therefore it is important to study how the probability of error drops as the block length go to infinity.

Error exponent in channel coding

For time-invariant DMC channels

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.

Assuming a channel coding setup as follows: the channel can transmit any of M = 2^{nR} ; messages, by transmitting the corresponding codeword (which is of length "n"). Each component in the codebook is drawn i.i.d. according to some probability distribution with probability mass function "Q". At the decoding end, ML decoding is done.

Given that y_1^n is received, "X"(1) or first message is transmitted, the probability that "X"(1) is incorrectly detected as "X"(2) is:

:P_{mathrm{error} 1 o 2} = sum_{x_1^n(2)} Q(x_1^n(2))1(p(y_1^n|x_1^n(2))>p(y_1^n|x_1^n(1)))

The function 1(p(y_1^n|x_1^n(2))>p(y_1^n|x_1^n(1)) has upper bound

: left(frac{p(y_1^n|x_1^n(2))}{p(y_1^n|x_1^n(1))} ight)^s

for s > 0 ; Thus,

:P_{mathrm{error} 1 o 2} le sum_{x_1^n(2)} Q(x_1^n(2)) left(frac{p(y_1^n|x_2^n(2))}{p(y_1^n|x_1^n(1))} ight)^s.

Since there are a total of "M" messages, the Probability that "X"(1) is confused with any other message is "M" times the above expression. Since each entry in the codebook is i.i.d., the notation of "X"(2) can be replaced simply by "X". Using the Hokey union bound, the probability of confusing "X"(1) with any message is bounded by:

:P_{mathrm{error} 1 o mathrm{any le M^ ho sum_{x_1^n} Q(x_1^n) left(frac{p(y_1^n|x_2^n)}{p(y_1^n|x_1^n(1))} ight)^{s ho}.

Averaging over all combinations of X_1^n(1), y_1^n :

:P_{mathrm{error} 1 o mathrm{any le M^ ho sum_{y_1^n} left(sum_{x_1^n(1)} Q(x_1^n(1)) [p(y_1^n|x_1^n(1))] ^{1-s ho} ight) left(sum_{x_1^n} Q(x_1^n) [p(y_1^n|x_1^n)] ^s ight)^{ ho}.

Choosing s = 1-s ho and combining the two sums over x_1^n in the above formula:

:P_{mathrm{error} 1 omathrm{any le M^ ho sum_{y_1^n} left(sum_{x_1^n} Q(x_1^n) [p(y_1^n|x_1^n)] ^{frac{1}{1+ ho ight)^{1+ ho}.

Using the independence nature of the elements of the codeword, and the discrete memoryless nature of the channel:

:P_{mathrm{error} 1 omathrm{any le M^ ho prod_{i=1}^n sum_{y_i} left(sum_{x_i} Q_i(x_i) [p_i(y_i|x_i)] ^{frac{1}{1+ ho ight)^{1+ ho}

Using the fact that each element of codeword is identically distributed and thus stationary:

:P_{mathrm{error} 1 omathrm{any le M^ ho left(sum_{y} left(sum_{x} Q(x) [p(y|x)] ^{frac{1}{1+ ho ight)^{1+ ho} ight)^n.

Replacing "M" by 2"nR" and defining

:E_o( ho,Q)= -lnleft(sum_{y} left(sum_{x} Q(x) [p(y|x)] ^{frac{1}{1+ ho ight)^{1+ ho} ight),

probability of error becomes

:P_mathrm{error} le exp(-n(E_o( ho,Q) - ho R)).

"Q" and ho should be chosen so that the bound is tighest. Thus, the error exponent can be defined as

: E_{r}(R) = max_Q max_{ ho varepsilon [0,1] } E_{o}( ho,Q) - ho R. ;

For time variant DMC channels

Error exponent in source coding

For time invariant discrete memoryless sources

The source coding theorem states that for any varepsilon > 0 and any discrete-time i.i.d. source such as X and for any rate less than the entropy of the source, there is large enough n and an encoder that takes n i.i.d. repetition of the source, X^{1:n} , and maps it to n.(H(X)+varepsilon) binary bits such that the source symbols X^{1:n} are recoverable from the binary bits with probability at least 1 - varepsilon .

Let M=e^{nR},! be the total number of possible messages. Next map each of the possible source output sequences to one of the messages randomly using a uniform distribution and independently from everything else. When a source is generated the corresponding message M=m , is then transmitted to the destination. The message gets decoded to one of the possible source strings. In order to minimize the probability of error the decoder will decode to the source sequence X_1^n that maximizes P(X_1^n|A_m) , where A_m, denotes the event that message m was transmitted. This rule is equivalent to finding the source sequence X_1^n among the set of source sequences that map to message m that maximizes P(X_1^n) . 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 X_1^n(1) was mapped to message 1 as was the source sequence X_1^n(2). If X_1^n(1) , was generated at the source, but P(X_1^n(2)) > P(X_1^n(1)) then an error occurs.

Let S_i , denote the event that the source sequence X_1^n(i) was generated at the source, so that P(S_i) = P(X_1^n(i)) ,. Then the probability of error can be broken down as P(E) = sum_i P(E|S_i) P(S_i), . Thus, attention can be focused on finding an upper bound to the P(E|S_i), .

Let A_{i'} , denote the event that the source sequence X_1^n(i') was mapped to the same message as the source sequence X_1^n(i) and that P(X_1^n(i')) geq P(X_1^n(i)) . Thus, letting X_{i,i'}, denote the event that the two source sequences i , and i' , map to the same message, we have that

: P(A_{i'}) = Pleft(X_{i,i'} igcap P(X_1^n(i') ight) geq P(X_1^n(i))),

and using the fact that P(X_{i,i'}) = frac{1}{M}, and is idependent of everything else have that

: P(A_{i'}) = frac{1}{M} P(P(X_1^n(i')) geq P(X_1^n(i))), .

A simple upper bound for the term on the left can be established as

: left [ P(P(X_1^n(i')) geq P(X_1^n(i))) ight ] leq left ( frac{P(X_1^n(i'))}{P(X_1^n(i))} ight ) ^s ,

for some arbitrary real number s>0 ,. This upper bound can be verified by noting that P(P(X_1^n(i')) > P(X_1^n(i))) , either equals 1 , or 0 , because the probabilities of a given input sequence are completely deterministic. Thus, if P(X_1^n(i')) geq P(X_1^n(i)) , , then frac{P(X_1^n(i'))}{P(X_1^n(i))} geq 1 , so that the inequality holds in that case. The inequality holds in the other case as well because

: left ( frac{P(X_1^n(i'))}{P(X_1^n(i))} ight ) ^s geq 0 ,

for all possible source strings. Thus, combining everything and introducing some ho in [0,1] , , have that

: P(E|S_i) leq P(igcup_{i eq i'} A_{i'}) leq left ( sum_{i eq i'} P(A_{i'}) ight ) ^ ho leq left ( frac{1}{M} sum_{i eq i'} left ( frac{P(X_1^n(i'))}{P(X_1^n(i))} ight ) ^s ight ) ^ ho , .

Where the inequalities follow from a variation on the Union Bound. Finally applying this upper bound to the summation for P(E) , have that:

: P(E) = sum_i P(E|S_i) P(S_i) leq sum_i P(X_1^n(i)) left ( frac{1}{M} sum_{i'} left ( frac{P(X_1^n(i'))}{P(X_1^n(i))} ight ) ^s ight ) ^ ho , .

Where the sum can now be taken over all i' , because that will only increase the bound. Ultimately yielding that

: P(E) leq frac{1}{M^ ho} sum_i P(X_1^n(i))^{1-s ho} left ( sum_{i'} P(X_1^n(i'))^s ight ) ^ ho , .

Now for simplicity let 1-s ho = s , so that s= frac{1}{1+ ho} , . Substituting this new value of s , into the above bound on the probability of error and using the fact that i' , is just a dummy variable in the sum gives the following as an upper bound on the probability of error:

: P(E) leq frac{1}{M^ ho} left ( sum_i P(X_1^n(i))^{frac{1}{1+ ho ight ) ^ {1+ ho} , .

: M=e^{nR},! and each of the components of X_1^n(i) , are independent. Thus, simplifying the above equation yields

: P(E) leq exp left( -n left [ ho R - ln left( sum_{x_i} P(x_i)^{frac{1}{1+ ho ight)(1+ ho) ight] ight).

The term in the exponent should be maximized over ho , in order to achieve the tightest upper bound on the probability of error.

Letting E_0( ho) = ln left( sum_{x_i} P(x_i)^{frac{1}{1+ ho ight)(1+ ho) , , see that the error exponent for the source coding case is:

: E_r(R) = max_{ ho in [0,1] } left [ ho R - E_0( ho) ight] . ,

For time-variant DMC sources

See also

* Source coding
* Channel coding

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Exponent (Mathematik) — Das Potenzieren ist wie das Multiplizieren seinem Ursprung nach eine abkürzende Schreibweise für eine wiederholte mathematische Rechenoperation. Wie beim Multiplizieren ein Summand wiederholt addiert wird, so wird beim Potenzieren ein Faktor… …   Deutsch Wikipedia

  • Index error — Index In dex, n.; pl. E. {Indexes}, L. {Indices}(?). [L.: cf. F. index. See {Indicate}, {Diction}.] [1913 Webster] 1. That which points out; that which shows, indicates, manifests, or discloses; as, the increasing unemployment rate is an index of …   The Collaborative International Dictionary of English

  • List of exponential topics — This is a list of exponential topics, by Wikipedia page. See also list of logarithm topics. *Accelerating change *Artin Hasse exponential *Bacterial growth *Baker Campbell Hausdorff formula *Cell growth *Barometric formula *Basic infection number …   Wikipedia

  • Shannon's source coding theorem — In information theory, Shannon s source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, and the operational meaning of the Shannon entropy.The source coding theorem shows that (in the limit, as… …   Wikipedia

  • Channel capacity — In electrical engineering, computer science and information theory, channel capacity is the tightest upper bound on the amount of information that can be reliably transmitted over a communications channel. By the noisy channel coding theorem, the …   Wikipedia

  • Exponentiation — Exponent redirects here. For other uses, see Exponent (disambiguation). Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent (or power) n. When n is a positive integer, exponentiation… …   Wikipedia

  • Floating point — In computing, floating point describes a method of representing real numbers in a way that can support a wide range of values. Numbers are, in general, represented approximately to a fixed number of significant digits and scaled using an exponent …   Wikipedia

  • 2009–2011 Toyota vehicle recalls — Two of the vehicles under recall: the Toyota Camry (top) and the Toyota Corolla Three separate but related recalls of automobiles by Toy …   Wikipedia

  • Rounding — This article is about numerical rounding. For lip rounding in phonetics, see Labialisation. For other uses, see Rounding (disambiguation). Rounding a numerical value means replacing it by another value that is approximately equal but has a… …   Wikipedia

  • Large numbers — This article is about large numbers in the sense of numbers that are significantly larger than those ordinarily used in everyday life, for instance in simple counting or in monetary transactions. The term typically refers to large positive… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”