View source for Erroneous decoding, probability of

One of the possible measures for characterizing the accuracy of information reproduction over a [[Communication channel|communication channel]] (see also [[Information, exactness of reproducibility of|Information, exactness of reproducibility of]]). For the transmission of information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362101.png" /> from a source which has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362102.png" /> different possible values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362103.png" /> with probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362104.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362105.png" />, a certain communication channel is used. Then for fixed methods of [[Coding and decoding|coding and decoding]] (see also [[Information, transmission of|Information, transmission of]]), the probability of erroneous decoding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362106.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362107.png" />, is defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362108.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e0362109.png" /> is the decoded message at the channel output. The variable quantity

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621010.png" /></td> </tr></table>

is called the mean probability of erroneous decoding. The study of the optimal probability of erroneous decoding, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621011.png" />, defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621012.png" /></td> </tr></table>

is of particular interest. The infimum is taken over all possible methods of coding and decoding. Owing to the difficulty of obtaining an accurate expression for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621013.png" />, which is caused by the fact that optimal coding methods are usually unknown, the study of the asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621014.png" /> when the length of the message in the channel increases is of interest. More precisely, the following situation is studied. Let a segment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621015.png" /> in a communication channel with discrete time be used, and put <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621016.png" />. The asymptotic behaviour of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621017.png" /> has to be studied when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621018.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621019.png" /> (this means that the length of the message increases, while its transmission rate remains constant). If the channel is a homogeneous [[Memoryless channel|memoryless channel]] with discrete time and if the spaces <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621020.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621021.png" /> of values of the components of the input and output signals are finite, then the following upper and lower bounds for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621022.png" /> are known:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621023.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621024.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621026.png" /> tend to zero with increasing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621027.png" />, while the functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621029.png" /> are defined as follows:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621030.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621031.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>

where

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621032.png" /></td> </tr></table>

Here, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621033.png" /> is an arbitrary probability distribution on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621035.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621036.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621037.png" />, while <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621040.png" />, are the components of the input and output signals of the memoryless channel being considered. It is known that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621041.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621042.png" />, defined by the formulas (2) and (3), are positive, convex from below, monotone decreasing functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621043.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621044.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621045.png" /> is the transmission rate of the channel (cf. [[Transmission rate of a channel|Transmission rate of a channel]]), and that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621046.png" /> when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621047.png" />; here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621048.png" /> is a quantity defined by the transition matrix of the channel and called the critical speed of the given memoryless channel. Thus, for values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621049.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621050.png" />, the main terms of the upper and lower bounds (1) for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621051.png" /> coincide asymptotically, hence for this range of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621052.png" /> the exact value of the reliability function of the channel, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621053.png" />, defined by

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621054.png" /></td> </tr></table>

is known. For values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621055.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621056.png" />, the exact value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621057.png" /> for arbitrary memoryless channels is still unknown (1983), although the bounds (1) can still be improved. The exponential character of decrease of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e036/e036210/e03621058.png" /> has been proved for a very broad class of channels.

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Gallager,   "Information theory and reliable communication" , '''1–2''' , Wiley  (1968–1972)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Feinstein,   "Foundations of information theory" , McGraw-Hill  (1958)</TD></TR></table>