- Shannon's source coding theorem
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.
The source coding theorem shows that (in the limit, as the length of a stream of 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.
"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
Source coding theorem
In information theory, the source coding theorem (Shannon 1948) informally states that:
:"N" i.i.d. random variables each with entropy "H(X)" can be compressed into more than "NH(X)"
bitswith negligible risk of information loss, as "N" tends to infinity; but conversely, if they are compressed into fewer than "NH(X)" bits it is virtually certain that information will be lost." (MacKay 2003).
Source coding theorem for symbol codes
Let , denote two finite alphabets and let and denote the set of all finite words from those alphabets (respectively).
Suppose that "X" is a random variable taking values in and let "f" be a decipherable code from to where . Let "S" denote the random variable given by the wordlength "f(X)".
If "f" is optimal in the sense that it has the minimal expected wordlength for "X", then
Proof: Source coding theorem
Given is an i.i.d. source, its
time series"X"1, ..., "X""n" is i.i.d. with entropy"H"("X") in the discrete-valued case and differential entropyin the continuous-valued case. The Source coding theorem states that for any for any rate larger than the entropyof the source, there is large enough and an encoder that takes i.i.d. repetition of the source, , and maps it to binary bits such that the source symbols are recoverable from the binary bits with probability at least .
Proof for achievability
Fix some for any . The typical set,, is defined as follows:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Noisy-channel coding theorem — In information theory, the noisy channel coding theorem (sometimes Shannon s theorem), establishes that for any given degree of noise contamination of a communication channel, it is possible to communicate discrete data (digital information)… … Wikipedia
Distributed source coding — (DSC) is an important problem in information theory and communication. DSC problems regard the compression of multiple correlated information sources that do not communicate with each other. By modeling the correlation between multiple sources … Wikipedia
Shannon–Hartley theorem — In information theory, the Shannon–Hartley theorem tells the maximum rate at which information can be transmitted over a communications channel of a specified bandwidth in the presence of noise. It is an application of the noisy channel coding… … Wikipedia
Claude Shannon — Claude Elwood Shannon (1916 2001) Born April … Wikipedia
Huffman coding — Huffman tree generated from the exact frequencies of the text this is an example of a huffman tree . The frequencies and codes of each character are below. Encoding the sentence with this code requires 135 bits, as opposed of 288 bits if 36… … Wikipedia
Golomb coding — is a data compression scheme invented by Solomon W. Golomb in the 1960s. The scheme is based on entropy encoding and is optimal (in the sense of Shannon s source coding theorem) for alphabets following a geometric distribution, making it highly… … Wikipedia
Adaptive Huffman coding — (also called Dynamic Huffman coding) is an adaptive coding technique based on Huffman coding. It permits building the code as the symbols are being transmitted, having no initial knowledge of source distribution, that allows one pass encoding and … Wikipedia
Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… … Wikipedia
Entropy (information theory) — In information theory, entropy is a measure of the uncertainty associated with a random variable. The term by itself in this context usually refers to the Shannon entropy, which quantifies, in the sense of an expected value, the information… … Wikipedia
Entropy encoding — In information theory an entropy encoding is a lossless data compression scheme that is independent of the specific characteristics of the medium. One of the main types of entropy coding creates and assigns a unique prefix free code to each… … Wikipedia