It has been suggested that this article or section be merged with Entropy encoding. (Discuss)

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. Wikipedia does not have an article with this exact name. ... An entropy encoding is a coding scheme that assigns codes to symbols so as to match code lengths with the probabilities of the symbols. ... Source code (commonly just source or code) is any series of statements written in some human-readable computer programming language. ... A bundle of optical fiber. ... In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ... A bundle of optical fiber. ... In computer science and information theory, data compression or source coding is the process of encoding information using fewer bits (or other information-bearing units) than an unencoded representation would use through use of specific encoding schemes. ...

In information theory, the source coding theorem (Shannon 1948) informally states that: In information theory, the source coding theorem (Shannon 1948) informally states that: N i. ...

"N i.i.d. random variables each with entropy H(X) can be compressed into more than NH(X) bits with 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).

In probability theory, a sequence or other collection of random variables is independent and identically distributed (i. ... Entropy of a Bernoulli trial as a function of success probability, often called the binary entropy function Entropy is a concept in thermodynamics (see entropy), statistical mechanics and information theory. ... BITS may have any of the following meanings: In computer science, bits are binary digits, which may each have the value one or zero. ...

Source Coding Theorem for i.i.d. sources

Fixed Rate -lossless source coding for discrete-time i.i.d. sources

Given X is an i.i.d. source, its time series X₁, ..., X_n 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 for any rate 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, X^1:n, and maps it to n.(H(X) + ε) binary bits such that the source symbols X^1:n are recoverable from the binary bits with probability at least 1 − ε. In probability theory, a sequence or other collection of random variables is independent and identically distributed (i. ... In statistics and signal processing, a time series is a sequence of data points, measured typically at successive times, spaced apart at uniform time intervals. ... Ice melting - classic example of entropy increasing[1] described in 1862 by Rudolf Clausius as an increase in the disgregation of the molecules of the body of ice. ... Differential entropy (also referred to as continuous entropy) is a concept in information theory which tries to extend the idea of (Shannon) entropy, a measure of average surprisal of a random variable, to continuous probability distributions. ... A bundle of optical fiber. ... Ice melting - classic example of entropy increasing[1] described in 1862 by Rudolf Clausius as an increase in the disgregation of the molecules of the body of ice. ...

Proof for achievablity

Fix some for any ε > 0. The typical set,, is defined as follows:

AEP shows that for large enough n, the probability that a sequence generated by the source lies in the typical set,, defined as approaches one. In particular there for large enough n, (See AEP for a proof): The asymptotic equipartition property (AEP) is a general property used extensively in information theory concerning the output samples of a stochastic source. ... The asymptotic equipartition property (AEP) is a general property used extensively in information theory concerning the output samples of a stochastic source. ...

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

Note that:

• The probability of a sequence from X being drawn from is greater than 1 − ε

• since the probability of the whole set is at most one.

• . For the proof, use the upper bound on the probability of each term in typical set and the lower bound on the probability of the whole set .

Since 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 n.(H(X) + ε) digit number. As long as the input sequence lies within the typical set (with probability at least 1 − ε), the encoder doesn't make any error. So, the probability of error of the encoder is bounded above by ε

Proof for converse The converse is proved by showing that any set of size smaller than (in the sense of exponent) would cover a set of probability bounded away from 1.

Variable length perfectly lossless source coding

Main article: Shannon's noiseless coding theorem

A variable length source code maps source symbols to a variable number of bits. This allows sources to be compressed and decompressed with zero error. It is possible to compress an i.i.d. source arbitrarily close to its entropy with variable length codes. In information theory, Shannons noiseless coding theorem 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. ...

Some examples of well-known variable length coding strategies are Huffman coding, Lempel-Ziv coding and Arithmetic coding. In computer science and information theory, Huffman coding is an entropy encoding algorithm used for lossless data compression. ... LZW (Lempel-Ziv-Welch) is a lossless data compression algorithm. ... Arithmetic coding is a method for lossless data compression. ...

The extension of a code is the mapping on finite length source sequences to finite length bit strings that is induced by the original code by applying concatenating the codewords of each symbol.

Variable length codes can be strictly nested in order of decreasing generality as non-singular, uniquely decodable and instantaneous (prefix free). Instantaneous codes are always uniquely decodable, which in turn are always non-singular :

1. A code is non-singular if each source symbol is mapped to a different non-empty bit string, i.e. the mapping from source symbols to bit strings is one-to-one.
   • For example the mapping M1 = {(a,0), (b,0), (c,1)} is not non-singular because both "a" and "b" map to the same bit string "0" ; any extension of this mapping will generate a lossy (non-lossless) coding. Such singular coding may still be useful when some loss of information is acceptable (for example when such code is used in audio or video compression, where a lossy coding becomes equivalent to source quantification).
   • However, the mapping M2 = {(a,0), (b,1), (c,00), (d,01)} is non-singular ; its extension will generate a lossless coding, which will be useful for general data transmission (but this feature is not always required). Note that it is not necessary for the non-singular code to be more compact than the source (and in many applications, a larger code is useful, for example as a way to detect and/or recover from encoding or transmission errors, or in security applications to protect a source from undetectable tamperring).
2. A code is uniquely decodable if its extension is non-singular.
   • The non-singular example mapping M2 in the previous paragraph is not uniquely decodable because (for example) the source sequence "aa" maps to bit string "00" using the extension, exactly like the source sequence "c". However such code is useful when the set of all possible source symbols is completely known and finite, or when there are restrictions (for example a formal syntax) allowing to decide if source elements of this extension are acceptable : such restriction allow to decode the original message by checking which of the possible source symbols mapped to the same symbol are valid under those restrictions.
   • However the mapping M3 = {(a,0), (b,01), (c,011)} is uniquely decodable (this can be demonstrated by looking at the follow-set after each target bit string in the map, because each bitstring is terminated as soon as we see a 0 bit which cannot follow any existing code to create an longer valid code in the map, but unambiguously starts a new code).
3. A code is instantaneous (also said context-free) if no target bit string in the mapping is a prefix of the target bit string of a different source symbol in the same mapping. This means that symbols can be decoded instantaneously after their entire codeword is received.
   • The example mapping M3 in the previous paragraph is not instantaneous because we don't know after reading the bit string "0" if it encodes a "a" source symbol, or if it is the prefix of the encodings of the "b" or "c" symbols.
   • An example of an instantaneous variable length code is shown below.

     

     The source is one of four symbols: a,b,c or d. The binary codeword for each symbol is given.

     The encoding and decoding of a portion of an example source sequence is given below:

     

The advantage of a variable length code is that unlikely source symbols can be assigned longer codewords and likely source symbols can be assigned shorter codewords, thus giving a low expected codeword length. For the above example, if the probabilities of (a, b, c, d) were , the expected number of bits used to represent a source symbol using the code above would be: In language and logic, quantification is a construct that specifies the extent of validity of a predicate, that is the extent to which a predicate holds over a range of things. ... Image File history File links Variablelengthcodeexample. ... Image File history File links Variablelengthcodeexample2. ...

.

As the entropy of this source is 1.75 bits per symbol, this code compresses the source as much as possible so that the source can be recovered with zero error.

Fixed rate lossy source coding for discrete-time i.i.d. sources

Main article: Rate distortion theory

Rate distortion theory is the branch of information theory addressing the problem of determining the minimal amount of entropy (or information) R that should be communicated over a channel such that the source (input signal) can be reconstructed at the receiver (output signal) with given distortion D. As such, rate...

Source Coding Theorem for non-stationary independent sources

=== Fixed Rate lossless source coding for discrete time non-stationary independent sources what?

=

Define typical set as:

Then, for given δ > 0, for n large enough, . 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 . Thus, on an average, bits suffice for encoding with probability greater than 1 − δ, where can be made arbitrarily small, by making n larger.

See also

• Channel coding
• Noisy Channel Coding Theorem
• Error exponent
• Asymptotic Equipartition Property (AEP)
• Shannon's noiseless coding theorem
• Rate distortion theory
• Data compression