Random coding

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.

References

[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)