View source for Optimal decoding

A decoding which maximizes the exactness of information reproduction (cf. [[Information, exactness of reproducibility of|Information, exactness of reproducibility of]]) for given sources of information, communication channels and coding methods. In case the exactness of information reproduction is characterized by the mean probability of erroneous decoding (cf. [[Erroneous decoding, probability of|Erroneous decoding, probability of]]), optimal decoding minimizes this probability. For example, for a transmission <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684401.png" /> of information represented by the numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684402.png" />, the probabilities of appearance of which are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684403.png" />, respectively, a discrete channel is used with a finite number of input and output signals and with transition function defined by the matrix

<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/o/o068/o068440/o0684404.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684405.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684406.png" /> are the sets of values of the signals of the input <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684407.png" /> and the output <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684408.png" />, respectively, while the coding is defined by the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o0684409.png" /> for which <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844010.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844011.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844013.png" />, is a [[Code|code]], i.e. a choice of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844014.png" /> possible input values. Then an optimal decoding is defined by a function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844015.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844016.png" /> for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844017.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844018.png" /> satisfies the inequality

<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/o/o068/o068440/o06844019.png" /></td> </tr></table>

for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844020.png" />. In particular, if all information has equal probability, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844021.png" />, then the described optimal decoding is also a decoding by the method of  "maximum likelihood"  (which is generally not optimal): The output signal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844022.png" /> has to be decoded in the information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/o/o068/o068440/o06844023.png" /> for which

<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/o/o068/o068440/o06844024.png" /></td> </tr></table>

====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  R. Gallagher,   "Information theory and reliable communication" , Wiley  (1968)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  J.M. Wozencraft,   I.M. Jacobs,   "Principles of communication engineering" , Wiley  (1965)</TD></TR></table>



====Comments====
Cf. also [[Coding and decoding|Coding and decoding]]; [[Information theory|Information theory]].