Namespaces
Variants
Actions

Difference between revisions of "Information, source of"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
An object producing information that could be transmitted over a [[Communication channel|communication channel]]. The information produced by a source of information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511301.png" /> is a [[Random variable|random variable]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511302.png" /> defined on some [[Probability space|probability space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511303.png" />, taking values in some [[Measurable space|measurable space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511304.png" />, and having a probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511305.png" />.
+
<!--
 +
i0511301.png
 +
$#A+1 = 81 n = 0
 +
$#C+1 = 81 : ~/encyclopedia/old_files/data/I051/I.0501130 Information, source of
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
An object producing information that could be transmitted over a [[Communication channel|communication channel]]. The information produced by a source of information $  U $
 +
is a [[Random variable|random variable]] $  \xi $
 +
defined on some [[Probability space|probability space]] $  ( \Omega , \mathfrak A , {\mathsf P} ) $,  
 +
taking values in some [[Measurable space|measurable space]] $  ( \mathfrak X , S _ {\mathfrak X} ) $,  
 +
and having a probability distribution $  p ( \cdot ) $.
  
 
Usually
 
Usually
  
<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/i/i051/i051130/i0511306.png" /></td> </tr></table>
+
$$
 +
( \mathfrak X , S _ {\mathfrak X }  )  = \
 +
\prod _ {t \in \Delta } ( X _ {t} , S _ {X _ {t}  } ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511307.png" /> are copies of one and the same measurable space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511308.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i0511309.png" /> is the direct product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113010.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113011.png" /> runs through a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113012.png" /> 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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113013.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113014.png" />). 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113015.png" /> with values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113016.png" /> represents the information. In applications <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113017.png" /> is treated as the information produced by the source at the moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113018.png" />. The samples of random variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113019.png" /> are called the segments <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113020.png" /> of information.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113021.png" /> produced by the source. E.g., if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113022.png" /> 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.
+
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|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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113023.png" /> be a discrete-time source of information without memory producing information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113024.png" /> with components <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113025.png" /> that take values in some finite set (alphabet) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113026.png" />. Suppose there is another finite set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113027.png" /> (the set of values of the components <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113028.png" /> of the information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113029.png" /> reproduced). An encoding of volume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113030.png" /> of a segment of information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113031.png" /> of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113032.png" /> is a mapping of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113033.png" /> into a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113034.png" /> elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113035.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113036.png" /> be the image of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113037.png" /> under such a mapping (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113038.png" /> is the direct product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113039.png" /> copies of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113040.png" />). Suppose further that the exactness of reproducibility of information (cf. [[Information, exactness of reproducibility of|Information, exactness of reproducibility of]]) is given by a non-negative real-valued function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113042.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113043.png" />, a measure of distortion, for which its average measure of distortion of encoding is given by
+
One of the problems in the theory of information transmission (cf. [[Information, transmission of|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|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
  
<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/i/i051/i051130/i05113044.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
\overline \rho \; _ {L}  = \
 +
 
 +
\frac{1}{L}
 +
 
 +
{\mathsf E} {\rho _ {L} }
 +
( \xi  ^ {L} , \widetilde{x}  {}  ^ {L} ( \xi  ^ {L} ) ) ,
 +
$$
  
 
where
 
where
  
<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/i/i051/i051130/i05113045.png" /></td> </tr></table>
+
$$
 +
\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
  
if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113047.png" />. The quantity
+
$$ \tag{2 }
 +
\overline{H}\; _  \epsilon  ( U )  = \
 +
\inf  I ( \xi _ {1} , \widetilde \xi  _ {1} )
 +
$$
  
<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/i/i051/i051130/i05113048.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
is the [[Epsilon-entropy| $  \epsilon $-
 +
entropy]] of a source of information without memory. Here  $  I ( \cdot , \cdot ) $
 +
is the amount of information (cf. [[Information, amount of|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
  
is the [[Epsilon-entropy|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113049.png" />-entropy]] of a source of information without memory. Here <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113050.png" /> is the amount of information (cf. [[Information, amount of|Information, amount of]]), and the infimum is over all compatible distributions of pairs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113051.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113052.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113053.png" />, for which the distribution of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113054.png" /> coincides with the distributions of the individual components of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113055.png" /> and for which
+
$$
 +
{\mathsf E} \rho ( \xi _ {1} , \widetilde \xi  _ {1} ) \leq  \epsilon .
 +
$$
  
<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/i/i051/i051130/i05113056.png" /></td> </tr></table>
+
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
  
The encoding theorem for a source of information. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113057.png" /> be the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113058.png" />-entropy of a discrete source <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113059.png" /> without memory and with a finite measure of distortion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113060.png" />; let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113061.png" />. Then: 1) for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113062.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113063.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113064.png" />, and all sufficiently large <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113065.png" />, there is an encoding of volume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113066.png" /> of the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113067.png" /> such that the average distortion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113068.png" /> satisfies the inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113069.png" />; 2) if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113070.png" />, then for any encoding of volume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113071.png" /> of segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113072.png" /> the average distortion <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113073.png" /> satisfies the inequality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113074.png" />. This encoding theorem can be generalized to a wide class of sources of information, e.g. to sources for which the space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113075.png" /> of values of the components is continuous. Instead of an encoding of volume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113076.png" /> one speaks in this case of quantization of volume of the source of information. It must be noted that the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113077.png" />-entropy <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113078.png" /> entering in the formulation of the theorem coincides, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113079.png" /> 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}
  
<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/i/i051/i051130/i05113080.png" /></td> </tr></table>
+
\right .$$
  
as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i051/i051130/i05113081.png" />, with the rate of generation of information by the given source (cf. [[Information, rate of generation of|Information, rate of generation of]]).
+
as $  X = \widetilde{X}  $,  
 +
with the rate of generation of information by the given source (cf. [[Information, rate of generation of|Information, rate of generation of]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Shannon,  "A mathematical theory of communication I - II"  ''Bell. Systems Techn. J.'' , '''27'''  (1948)  pp. 379–423; 623–656</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Gallagher,  "Information theory and reliable communication" , Wiley  (1968)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  T. Berger,  "Rate distortion theory" , Prentice-Hall  (1971)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Shannon,  "A mathematical theory of communication I - II"  ''Bell. Systems Techn. J.'' , '''27'''  (1948)  pp. 379–423; 623–656</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  R. Gallagher,  "Information theory and reliable communication" , Wiley  (1968)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  T. Berger,  "Rate distortion theory" , Prentice-Hall  (1971)</TD></TR></table>

Latest revision as of 22:12, 5 June 2020


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)
How to Cite This Entry:
Information, source of. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Information,_source_of&oldid=47352
This article was adapted from an original article by R.L. DobrushinV.V. Prelov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article