# 香农信源编码定理

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.

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.

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.

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.

## 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 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) informally states that (MacKay 2003, pg. 81, Cover 2006, Chapter 5):

In information theory, the source coding theorem (Shannon 1948)

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.

}}

}}

Ni.i.d.每个随机变量都有H(X)可以压缩成超过N H(X)。随着N → ∞的信息丢失风险可以忽略不计；但反过来说，如果它们被压缩成少于N H(X)位，则信息肯定将丢失。

### Source coding theorem for symbol codes

Category:Information theory

Let Σ1, Σ2 denote two finite alphabets and let and denote the set of all finite words from those alphabets (respectively).

Σ1, Σ2表示两个有限字母，并让分别表示这些字母中所有有限词的集合

Category:Coding theory

Category:Data compression

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

Category:Presentation layer protocols

Category:Mathematical theorems in theoretical computer science

If f is optimal in the sense that it has the minimal expected word length for X, then (Shannon 1948):

Category:Articles containing proofs

This page was moved from wikipedia:en:Shannon's source coding theorem. Its edit history can be viewed at 香农信源编码定理/edithistory

1. 引用错误：无效`<ref>`标签；未给name属性为`Shannon`的引用提供文字
2. 引用错误：无效`<ref>`标签；未给name属性为`MacKay`的引用提供文字
3. 引用错误：无效`<ref>`标签；未给name属性为`Cover`的引用提供文字