Editing Shannon's source coding theorem

{{short description|Establishes the limits to possible data compression}}
{{Information theory}}

{{about|the theory of source coding in data compression|the term in computer programming|Source code}}

In [[information theory]], '''Shannon's source coding theorem''' (or '''noiseless coding theorem''') establishes the statistical limits to possible [[data compression]] for data whose source is an [[independent identically-distributed random variables|independent identically-distributed random variable]], and the operational meaning of the [[Shannon entropy]].

Named after [[Claude Shannon]], the '''source coding theorem''' shows that, in the limit, as the length of a stream of [[independent and identically distributed random variables|independent and identically-distributed random variable (i.i.d.)]] data tends to infinity, it is impossible to compress such data such that the code rate (average number of bits per symbol) is less than the Shannon entropy of the source, without it being virtually certain that information will be lost. However it is possible to get the code rate arbitrarily close to the Shannon entropy, with negligible probability of loss.

The '''source coding theorem for symbol codes''' places an upper and a lower bound on the minimal possible expected length of codewords as a function of the [[Entropy (information theory)|entropy]] of the input word (which is viewed as a [[random variable]]) and of the size of the target alphabet.

Note that, for data that exhibits more dependencies (whose source is not an i.i.d. random variable), the [[Kolmogorov complexity]], which quantifies the minimal description length of an object, is more suitable to describe the limits of data compression. Shannon entropy takes into account only frequency regularities while Kolmogorov complexity takes into account all algorithmic regularities, so in general the latter is smaller. On the other hand, if an object is generated by a random process in such a way that it has only frequency regularities, entropy is close to complexity with high probability (Shen et al. 2017).<ref name="Shen2017"/>

== Statements ==

''Source coding'' is a mapping from (a sequence of) symbols from an information [[Information theory#Source theory|source]] to a sequence of alphabet symbols (usually bits) such that the source symbols can be exactly recovered from the binary bits (lossless source coding) or recovered within some distortion (lossy source coding). This is one approach to [[data compression]].

=== Source coding theorem ===
In information theory, the source coding theorem (Shannon 1948)<ref name="Shannon"/> informally states that (MacKay 2003, pg. 81,<ref name="MacKay"/> Cover 2006, Chapter 5<ref name="Cover"/>):

<blockquote>{{mvar|N}} [[Independent and identically distributed random variables|i.i.d.]] random variables each with entropy {{math|''H''(''X'')}} can be compressed into more than {{math|''N&thinsp;H''(''X'')}} [[bit]]s with negligible risk of information loss, as {{math|''N'' → ∞}}; but conversely, if they are compressed into fewer than {{math|''N&thinsp;H''(''X'')}} bits it is virtually certain that information will be lost.</blockquote>The <math>NH(X)</math> coded sequence represents the compressed message in a biunivocal way, under the assumption that the decoder knows the source. From a practical point of view, this hypothesis is not always true. Consequently, when the entropy encoding is applied the transmitted message is <math>NH(X)+(inf. source)</math>. Usually, the information that characterizes the source is inserted at the beginning of the transmitted message.

=== Source coding theorem for symbol codes ===
Let {{math|Σ<sub>1</sub>, Σ<sub>2</sub>}} denote two finite alphabets and let {{math|Σ{{su|b=1|p=∗}}}} and {{math|Σ{{su|b=2|p=∗}}}} denote the [[Kleene star|set of all finite words]] from those alphabets (respectively).

Suppose that {{mvar|X}} is a random variable taking values in {{math|Σ<sub>1</sub>}} and let {{math|&thinsp;''f''&thinsp;}} be a [[Variable-length code#Uniquely decodable codes|uniquely decodable]] code from {{math|Σ{{su|b=1|p=∗}}}} to {{math|Σ{{su|b=2|p=∗}}}} where {{math|{{!}}Σ<sub>2</sub>{{!}} {{=}} ''a''}}. Let {{mvar|S}} denote the random variable given by the length of codeword {{math|&thinsp;''f''&thinsp;(''X'')}}.

If {{math|&thinsp;''f''&thinsp;}} is optimal in the sense that it has the minimal expected word length for {{mvar|X}}, then (Shannon 1948):

:<math> \frac{H(X)}{\log_2 a} \leq \mathbb{E}[S] < \frac{H(X)}{\log_2 a} +1 </math>

Where <math>\mathbb{E}</math> denotes the [[expected value]] operator.

== Proof: source coding theorem ==
Given {{mvar|X}} is an [[independent identically-distributed random variables|i.i.d.]] source, its [[time series]] {{math|''X''<sub>1</sub>, ..., ''X<sub>n</sub>''}} is i.i.d. with [[Entropy_(information_theory)|entropy]] {{math|''H''(''X'')}} in the discrete-valued case and [[differential entropy]] in the continuous-valued case. The Source coding theorem states that for any {{math|''ε'' > 0}}, i.e. for any [[information theory#Rate|rate]] {{math|''H''(''X'') + ''ε''}} larger than the [[entropy]] of the source, there is large enough {{mvar|n}} and an encoder that takes {{mvar|n}} i.i.d. repetition of the source, {{math|''X''<sup>1:''n''</sup>}}, and maps it to {{math|''n''(''H''(''X'') + ''ε'')}} binary bits such that the source symbols {{math|''X''<sup>1:''n''</sup>}} are recoverable from the binary bits with probability of at least {{math|1 − ''ε''}}.

'''Proof of Achievability.''' Fix some {{math|''ε'' > 0}}, and let

:<math>p(x_1, \ldots, x_n) = \Pr \left[X_1 = x_1, \cdots, X_n = x_n \right].</math>

The [[typical set]], {{math|''A''{{su|b=''n''|p=''ε''}}}}, is defined as follows:

:<math>A_n^\varepsilon =\left\{(x_1, \cdots, x_n) \ : \ \left|-\frac{1}{n} \log p(x_1, \cdots, x_n) - H_n(X)\right| < \varepsilon \right\}.</math>

The [[Asymptotic equipartition property#AEP for discrete-time i.i.d. sources|asymptotic equipartition property]] (AEP) shows that for large enough {{mvar|n}}, the probability that a sequence generated by the source lies in the typical set, {{math|''A''{{su|b=''n''|p=''ε''}}}}, as defined approaches one. In particular, for sufficiently large {{mvar|n}}, <math>P((X_1,X_2,\cdots,X_n) \in A_n^\varepsilon)</math> can be made arbitrarily close to 1, and specifically, greater than <math>1-\varepsilon</math> (See 
[[Asymptotic equipartition property#AEP for discrete-time i.i.d. sources|AEP]] for a proof).

The definition of typical sets implies that those sequences that lie in the typical set satisfy:

:<math>2^{-n(H(X)+\varepsilon)} \leq p \left (x_1, \cdots, x_n \right ) \leq 2^{-n(H(X)-\varepsilon)}</math>


*The probability of a sequence <math>(X_1,X_2,\cdots X_n)</math> being drawn from {{math|''A''{{su|b=''n''|p=''ε''}}}} is greater than {{math|1 − ''ε''}}.
*<math>\left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}</math>, which follows from the left hand side (lower bound) for <math> p(x_1,x_2,\cdots x_n)</math>.
*<math>\left| A_n^\varepsilon \right| \geq (1-\varepsilon) 2^{n(H(X)-\varepsilon)}</math>, which follows from upper bound for <math> p(x_1,x_2,\cdots x_n)</math>  and the lower bound on the total probability of the whole set {{math|''A''{{su|b=''n''|p=''ε''}}}}.

Since <math>\left| A_n^\varepsilon \right| \leq 2^{n(H(X)+\varepsilon)}, n(H(X)+\varepsilon)</math> bits are enough to point to any string in this set.

The encoding algorithm: the encoder checks if the input sequence lies within the typical set; if yes, it outputs the index of the input sequence within the typical set; if not, the encoder outputs an arbitrary {{math|''n''(''H''(''X'') + ''ε'')}} digit number. As long as the input sequence lies within the typical set (with probability at least {{math|1 − ''ε''}}), the encoder does not make any error. So, the probability of error of the encoder is bounded above by {{mvar|ε}}.

''Proof of converse'': the converse is proved by showing that any set of size smaller than {{math|''A''{{su|b=''n''|p=''ε''}}}} (in the sense of exponent) would cover a set of probability bounded away from {{math|1}}.

== Proof: Source coding theorem for symbol codes ==
For {{math|1 ≤ ''i'' ≤ ''n''}} let {{math|''s<sub>i</sub>''}} denote the word length of each possible {{math|''x<sub>i</sub>''}}. Define <math>q_i = a^{-s_i}/C</math>, where {{mvar|C}} is chosen so that {{math|''q''<sub>1</sub> + ... + ''q<sub>n</sub>'' {{=}} 1}}.  Then

:<math>\begin{align}
H(X) &=    -\sum_{i=1}^n p_i \log_2 p_i \\
     &\leq -\sum_{i=1}^n p_i \log_2 q_i \\
     &=    -\sum_{i=1}^n p_i \log_2 a^{-s_i} + \sum_{i=1}^n p_i \log_2 C \\
     &=    -\sum_{i=1}^n p_i \log_2 a^{-s_i} + \log_2 C \\
     &\leq -\sum_{i=1}^n - s_i p_i \log_2 a \\
     &=  \mathbb{E} S \log_2 a \\
\end{align}</math>

where the second line follows from [[Gibbs' inequality]] and the fifth line follows from [[Kraft's inequality]]:

:<math>C = \sum_{i=1}^n a^{-s_i} \leq 1</math>

so {{math|log ''C'' ≤ 0}}.

For the second inequality we may set

:<math>s_i = \lceil - \log_a p_i \rceil </math>

so that

:<math> - \log_a p_i \leq s_i < -\log_a p_i + 1 </math>

and so

:<math> a^{-s_i} \leq p_i</math>

and

:<math> \sum  a^{-s_i} \leq \sum p_i = 1</math>

and so by Kraft's inequality there exists a prefix-free code having those word lengths. Thus the minimal {{mvar|S}} satisfies

:<math>\begin{align}
\mathbb{E} S & = \sum p_i s_i \\
& < \sum p_i \left( -\log_a p_i +1 \right) \\
& = \sum - p_i \frac{\log_2 p_i}{\log_2 a} +1 \\
& = \frac{H(X)}{\log_2 a} +1 \\
\end{align}</math>

==Extension to non-stationary independent sources ==

=== Fixed rate lossless source coding for discrete time non-stationary independent sources===
Define typical set {{math|''A''{{su|b=''n''|p=''ε''}}}} as:

:<math>A_n^\varepsilon = \left \{x_1^n \ : \ \left|-\frac{1}{n} \log p \left (X_1, \cdots, X_n \right ) - \overline{H_n}(X)\right| < \varepsilon \right \}.</math>

Then, for given {{math|''δ'' > 0}}, for {{mvar|n}} large enough, {{math|Pr(''A''{{su|b=''n''|p=''ε''}}) > 1 − ''δ''}}. Now we just encode the sequences in the typical set, and usual methods in source coding show that the cardinality of this set is smaller than <math>2^{n(\overline{H_n}(X)+\varepsilon)}</math>. Thus, on an average, {{math|{{overline|''H<sub>n</sub>''}}(''X'') + ''ε''}} bits suffice for encoding with probability greater than {{math|1 − ''δ''}}, where {{mvar|ε}} and {{mvar|δ}} can be made arbitrarily small, by making {{mvar|n}} larger.

==See also==
* [[Channel coding]]
* [[Error exponent]]
* [[Noisy-channel coding theorem]]

==References==
{{Reflist|refs=
<ref name="Shen2017">{{cite book | author = Shen, A. and Uspensky, V.A. and Vereshchagin, N. | title = Kolmogorov Complexity and Algorithmic Randomness | chapter = Chapter 7.3. : Complexity and entropy | year = 2017  | publisher = American Mathematical Society | isbn = 9781470431822 |url=https://books.google.com/books?id=IPNOvQEACAAJ | pages=226}}</ref>
<ref name="Shannon">[[C.E. Shannon]], "[http://plan9.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf A Mathematical Theory of Communication] {{Webarchive|url=https://web.archive.org/web/20090216231139/http://plan9.bell-labs.com//cm//ms//what//shannonday//shannon1948.pdf |date=2009-02-16 }}", ''[[Bell System Technical Journal]]'', vol. 27, pp.&nbsp;379–423, 623-656, July, October, 1948</ref>
<ref name="MacKay">David J. C. MacKay. ''[http://www.inference.phy.cam.ac.uk/mackay/itila/book.html Information Theory, Inference, and Learning Algorithms]'' Cambridge: Cambridge University Press, 2003. {{ISBN|0-521-64298-1}}</ref>
<ref name="Cover">{{cite book | last = Cover | first = Thomas M. | title = Elements of Information Theory | chapter = Chapter 5: Data Compression | year = 2006  | publisher = John Wiley & Sons | isbn = 0-471-24195-4|url=https://books.google.com/books?id=VWq5GG6ycxMC|pages=103–142}}</ref>}}


[[Category:Information theory]]
[[Category:Coding theory]]
[[Category:Data compression]]
[[Category:Presentation layer protocols]]
[[Category:Mathematical theorems in theoretical computer science]]
[[Category:Articles containing proofs]]