Optimal decoding

A decoding which maximizes the exactness of information reproduction (cf. 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), optimal decoding minimizes this probability. For example, for a transmission $ M $ of information represented by the numbers $ 1 \dots M $, the probabilities of appearance of which are $ p _ {1} \dots p _ {M} $, respectively, a discrete channel is used with a finite number of input and output signals and with transition function defined by the matrix

$$ q( y, \widetilde{y} ) = {\mathsf P} \{ \widetilde \eta = \widetilde{y} \mid \eta = y \} ,\ \ y \in Y ,\ \widetilde{y} \in \widetilde{Y} , $$

where $ Y $, $ \widetilde{Y} $ are the sets of values of the signals of the input $ \eta $ and the output $ \widetilde \eta $, respectively, while the coding is defined by the function $ f( \cdot ) $ for which $ f( m) = y _ {m} $, $ m = 1 \dots M $, where $ y _ {m} \in Y $, $ m = 1 \dots M $, is a code, i.e. a choice of $ M $ possible input values. Then an optimal decoding is defined by a function $ g( \cdot ) $ such that $ g( \widetilde{y} ) = m ^ \prime $ for any $ \widetilde{y} \in \widetilde{Y} $, where $ m ^ \prime $ satisfies the inequality

$$ p _ {m ^ \prime } q( y _ {m ^ \prime } , \widetilde{y} ) \geq p _ {m} q( y _ {m} , \widetilde{y} ) $$

for all $ m \neq m ^ \prime $. In particular, if all information has equal probability, i.e. $ p _ {1} = \dots = p _ {M} = 1/M $, then the described optimal decoding is also a decoding by the method of "maximum likelihood" (which is generally not optimal): The output signal $ \widetilde{y} $ has to be decoded in the information $ m ^ \prime $ for which

$$ q( y _ {m ^ \prime } , \widetilde{y} ) \geq q( y _ {m} , \widetilde{y} ) \ \textrm{ if } m \neq m ^ \prime . $$

References

[1]	R. Gallagher, "Information theory and reliable communication" , Wiley (1968)
[2]	J.M. Wozencraft, I.M. Jacobs, "Principles of communication engineering" , Wiley (1965)

Comments

Cf. also Coding and decoding; Information theory.