Shannon's source coding theorem

Shannon's source coding theorem Information theory EntropyDifferential entropyConditional entropyJoint entropyMutual informationConditional mutual informationRelative entropyEntropy rateLimiting density of discrete points Asymptotic equipartition propertyRate–distortion theory Shannon's source coding theoremChannel capacityNoisy-channel coding theoremShannon–Hartley theorem vte This article is about the theory of source coding in data compression. For the term in computer programming, see Source code.

In information theory, Shannon's source coding theorem (or noiseless coding theorem) establishes the limits to possible data compression, 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 variable (i.i.d.) data tends to infinity) it is impossible to compress the 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 of the input word (which is viewed as a random variable) and of the size of the target alphabet.

Contents 1 Statements 1.1 Source coding theorem 1.2 Source coding theorem for symbol codes 2 Proof: Source coding theorem 3 Proof: Source coding theorem for symbol codes 4 Extension to non-stationary independent sources 4.1 Fixed Rate lossless source coding for discrete time non-stationary independent sources 5 See also 6 References Statements Source coding is a mapping from (a sequence of) symbols from an information 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 the concept behind data compression.

Source coding theorem In information theory, the source coding theorem (Shannon 1948)[1] informally states that (MacKay 2003, pg. 81,[2] Cover 2006, Chapter 5[3]): N i.i.d. random variables each with entropy H(X) can be compressed into more than N H(X) bits with negligible risk of information loss, as N → ∞; but conversely, if they are compressed into fewer than N H(X) bits it is virtually certain that information will be lost.

The {displaystyle NH(X)} 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 {displaystyle NH(X)+(inf.source)} . Usually, the information that characterizes the source is inserted at the beginning of the transmitted message.

Source coding theorem for symbol codes Let Σ1, Σ2 denote two finite alphabets and let Σ∗ 1 and Σ∗ 2 denote the set of all finite words from those alphabets (respectively).

Suppose that X is a random variable taking values in Σ1 and let  f  be a uniquely decodable code from Σ∗ 1 to Σ∗ 2 where |Σ2| = a. Let S denote the random variable given by the length of codeword  f (X).

If  f  is optimal in the sense that it has the minimal expected word length for X, then (Shannon 1948): {displaystyle {frac {H(X)}{log _{2}a}}leq mathbb {E} [S]<{frac {H(X)}{log _{2}a}}+1} Where {displaystyle mathbb {E} } denotes the expected value operator. Proof: Source coding theorem Given X is an i.i.d. source, its time series X1, ..., Xn is i.i.d. with entropy H(X) in the discrete-valued case and differential entropy in the continuous-valued case. The Source coding theorem states that for any ε > 0, i.e. for any rate H(X) + ε larger than the entropy of the source, there is large enough n and an encoder that takes n i.i.d. repetition of the source, X1:n, and maps it to n(H(X) + ε) binary bits such that the source symbols X1:n are recoverable from the binary bits with probability of at least 1 − ε.

Proof of Achievability. Fix some ε > 0, and let {displaystyle p(x_{1},ldots ,x_{n})=Pr left[X_{1}=x_{1},cdots ,X_{n}=x_{n}right].} The typical set, Aε n, is defined as follows: {displaystyle A_{n}^{varepsilon }=left{(x_{1},cdots ,x_{n}) : left|-{frac {1}{n}}log p(x_{1},cdots ,x_{n})-H_{n}(X)right| 0, for n large enough, Pr(Aε n) > 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 {displaystyle 2^{n({overline {H_{n}}}(X)+varepsilon )}} . Thus, on an average, Hn(X) + ε bits suffice for encoding with probability greater than 1 − δ, where ε and δ can be made arbitrarily small, by making n larger.

See also Channel coding Noisy-channel coding theorem Error exponent Asymptotic Equipartition Property (AEP) References ^ C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948 ^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1 ^ Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. pp. 103–142. ISBN 0-471-24195-4. Categories: Information theoryCoding theoryData compressionPresentation layer protocolsMathematical theorems in theoretical computer science