Information, source of

An object producing information that could be transmitted over a communication channel. The information produced by a source of information $ U $ is a random variable $ \xi $ defined on some probability space $ ( \Omega , \mathfrak A , {\mathsf P} ) $, taking values in some measurable space $ ( \mathfrak X , S _ {\mathfrak X} ) $, and having a probability distribution $ p ( \cdot ) $.

Usually

$$ ( \mathfrak X , S _ {\mathfrak X } ) = \ \prod _ {t \in \Delta } ( X _ {t} , S _ {X _ {t} } ) , $$

where $ ( X _ {t} , S _ {X _ {t} } ) $ are copies of one and the same measurable space $ ( X , S _ {X} ) $ and $ \prod $ is the direct product of $ ( X _ {t} , S _ {X _ {t} } ) $ as $ t $ runs through a set $ \Delta $ that is, a rule, either a certain interval (finite, infinite to one side, or infinite to both sides) on the real axis, or some discrete subset of this axis (usually, $ \Delta = \{ \dots, - 1 , 0 , 1 ,\dots \} $ or $ \Delta = \{ 1 , 2 ,\dots \} $). In the first of these cases one speaks of a continuous-time source of information, while in the second — of a discrete-time source of information. In other cases, a random variable $ \xi = \{ {\xi ( t) } : {t \in \Delta } \} $ with values in $ ( X , S _ {X} ) $ represents the information. In applications $ \xi ( t) $ is treated as the information produced by the source at the moment of time $ t $. The samples of random variables $ \xi _ {t} ^ {T} = \{ {\xi ( s) } : {t < s \leq T } \} $ are called the segments $ ( t , T ] $ of information.

Sources of information can be divided into various classes, depending on the type of information, i.e. of the random process $ \xi ( t) $ produced by the source. E.g., if $ \xi ( t) $ is a random process with independent identically-distributed values, or if it is a stationary, an ergodic, a Markov, a Gaussian, etc., process, then the source is called a source of information without memory, or a stationary, ergodic, Markov, Gaussian, etc., source.

One of the problems in the theory of information transmission (cf. Information, transmission of) is the problem of encoding a source of information. One distinguishes between, e.g. encoding of a source by codes of fixed length, by codes of variable length, encoding under given accuracy conditions, etc. (in applications some encoding problems are called quantization of information, contraction of information, etc.). E.g., let $ U $ be a discrete-time source of information without memory producing information $ \xi = ( \dots, \xi _ {-} 1 , \xi _ {0} , \xi _ {1} ,\dots) $ with components $ \xi _ {k} $ that take values in some finite set (alphabet) $ X $. Suppose there is another finite set $ \widetilde{X} $( the set of values of the components $ \widetilde \xi _ {k} $ of the information $ \widetilde \xi = ( \dots, \widetilde \xi _ {-} 1 , \widetilde \xi _ {0} , \xi _ {1} ,\dots ) $ reproduced). An encoding of volume $ M $ of a segment of information $ \xi ^ {L} = ( \xi _ {1} \dots \xi _ {L} ) $ of length $ L $ is a mapping of $ X ^ {L} $ into a set of $ M $ elements of $ \widetilde{X} {} ^ {L} $. Let $ \widetilde{x} {} ^ {L} ( x ^ {L} ) $ be the image of $ x ^ {L} \in X ^ {L} $ under such a mapping ( $ X ^ {L} $ is the direct product of $ L $ copies of $ X $). Suppose further that the exactness of reproducibility of information (cf. Information, exactness of reproducibility of) is given by a non-negative real-valued function $ \rho ( x , \widetilde{x} ) $, $ x \in X $, $ \widetilde{x} \in \widetilde{X} $, a measure of distortion, for which its average measure of distortion of encoding is given by

$$ \tag{1 } \overline \rho \; _ {L} = \ \frac{1}{L} {\mathsf E} {\rho _ {L} } ( \xi ^ {L} , \widetilde{x} {} ^ {L} ( \xi ^ {L} ) ) , $$

where

$$ \rho _ {L} ( x ^ {L} , \widetilde{x} {} ^ {L} ) = \sum _ { k= } 1 ^ { L } \rho ( x _ {k} , \widetilde{x} _ {k} ) , $$

if $ x ^ {L} = ( x _ {1} \dots x _ {L} ) $ and $ \widetilde{x} {} ^ {L} = ( \widetilde{x} _ {1} \dots \widetilde{x} _ {L} ) $. The quantity

$$ \tag{2 } \overline{H}\; _ \epsilon ( U ) = \ \inf I ( \xi _ {1} , \widetilde \xi _ {1} ) $$

is the $ \epsilon $- entropy of a source of information without memory. Here $ I ( \cdot , \cdot ) $ is the amount of information (cf. Information, amount of), and the infimum is over all compatible distributions of pairs $ ( \xi _ {1} , \widetilde \xi _ {1} ) $, $ \xi _ {1} \in X $, $ \widetilde \xi _ {1} \in \widetilde{X} $, for which the distribution of $ \xi _ {1} $ coincides with the distributions of the individual components of $ U $ and for which

$$ {\mathsf E} \rho ( \xi _ {1} , \widetilde \xi _ {1} ) \leq \epsilon . $$

The encoding theorem for a source of information. Let $ \overline{H}\; _ \epsilon ( U) $ be the $ \epsilon $- entropy of a discrete source $ U $ without memory and with a finite measure of distortion $ \rho ( \cdot , \cdot ) $; let $ M = e ^ {LR} $. Then: 1) for any $ \epsilon > 0 $, $ \delta > 0 $, $ R > \overline{H}\; _ \epsilon ( U) $, and all sufficiently large $ L $, there is an encoding of volume $ M $ of the segments of length $ L $ such that the average distortion $ \overline \rho \; _ {L} $ satisfies the inequality $ \overline \rho \; _ {L} \leq \epsilon + \delta $; 2) if $ R < \overline{H}\; _ \epsilon ( U) $, then for any encoding of volume $ M $ of segments of length $ L $ the average distortion $ \overline \rho \; _ {L} $ satisfies the inequality $ \overline \rho \; _ {L} > \epsilon $. This encoding theorem can be generalized to a wide class of sources of information, e.g. to sources for which the space $ X $ of values of the components is continuous. Instead of an encoding of volume $ M $ one speaks in this case of quantization of volume of the source of information. It must be noted that the $ \epsilon $- entropy $ \overline{H}\; _ \epsilon ( U) $ entering in the formulation of the theorem coincides, for $ \epsilon = 0 $ and measure of distortion

$$ \rho ( x , \widetilde{x} ) = \ \left \{ \begin{array}{ll} 0 & \textrm{ if } x = \widetilde{x} , \\ 1 & \textrm{ if } x \neq \widetilde{x} , \\ \end{array} \right .$$

as $ X = \widetilde{X} $, with the rate of generation of information by the given source (cf. Information, rate of generation of).

References

[1]	C. Shannon, "A mathematical theory of communication I - II" Bell. Systems Techn. J. , 27 (1948) pp. 379–423; 623–656
[2]	P.L. Dobrushin, "A general formulation of Shannon's fundamental theorem in information theory" Uspekhi Mat. Nauk , 14 : 6 (1959) pp. 3–104 (In Russian)
[3]	R. Gallagher, "Information theory and reliable communication" , Wiley (1968)
[4]	T. Berger, "Rate distortion theory" , Prentice-Hall (1971)