Random coding

From Encyclopedia of Mathematics
Revision as of 17:04, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A method of coding (see Coding and decoding) in which to every possible value of a message produced by a source of information (cf. Information, source of) is assigned a randomly chosen value of the signal at the input of the communication channel. On the set of values of the signals at the input of the channel a certain probability distribution is given. It is often assumed that every element of the code (that is, the value of a signal at the input corresponding to a given value of the information) is chosen independently of the others and in accordance with a given probability distribution. Sometimes a random coding is defined in such a way that every realization of it is a group code.

The importance of random coding is related to the fact that the probability of erroneous decoding (cf. Erroneous decoding, probability of), averaged over all realizations, gives a relatively easy to compute upper bound for the probability of erroneously decoding an optimal code.


[1] C.E. Shannon, "A mathematical theory of communication" Bell. System Techn. J. , 27 (1948) pp. 979–423; 623–656
[2] R.L. Dobrushin, "A general formulation of the fundamental theorem of Shannon in information theory" Uspekhi Mat. Nauk , 14 : 6 (1959) pp. 3–104 (In Russian)
[3] R. Gallagher, "Information theory and reliable communication" , Wiley (1968)
How to Cite This Entry:
Random coding. R.L. DobrushinV.V. Prelov (originator), Encyclopedia of Mathematics. URL:
This text originally appeared in Encyclopedia of Mathematics - ISBN 1402006098