Summary: An introduction to the concept of typical sequences, which lie at the heart of source coding. The idea of typical sequences leads to Shannon's source-coding Theorem.

As mentioned earlier, how much a source can be compressed should be related to its entropy. In 1948, Claude E. Shannon introduced three theorems and developed very rigorous mathematics for digital communications. In one of the three theorems, Shannon relates entropy to the minimum number of bits per second required to represent a source without much loss (or distortion).

Consider a source that is modeled by a discrete-time and discrete-valued
random process

Consider a sequence of length

Therefore,

A typical sequence

For large

Consider a source with alphabet {A,B,C,D} with probabilities {

The number of typical sequences of length 8

The number of nontypical sequences

Examples of typical sequences include those with A appearing

Examples of nontypical sequences of length 8: {D,D,B,C,C,A,B,D},
{C,C,C,C,C,B,C,C} and much more. Indeed, these definitions and
arguments are valid when n is very large. The probability of a
source output to be in the set of typical sequences is 1 when

The essence of source coding or data compression is that as

A source that produced independent and identically
distributed random variables with entropy

The source coding theorem proves existence of source coding techniques that achieve rates close to the entropy but does not provide any algorithms or ways to construct such codes.

If the source is not i.i.d. (independent and identically distributed),
but it is stationary with memory, then a similar theorem applies with
the entropy

In the case of a source with memory, the more the source produces outputs the more one knows about the source and the more one can compress.

The English language has 26 letters, with space it becomes an
alphabet of size 27. If modeled as a memoryless source (no
dependency between letters in a word) then the entropy is

If the dependency between letters in a text is captured in a model
the entropy rate can be derived to be

Although Shannon's results are not constructive, there are a number of source coding algorithms for discrete time discrete valued sources that come close to Shannon's bound. One such algorithm is the Huffman source coding algorithm. Another is the Lempel and Ziv algorithm.

Huffman codes and Lempel and Ziv apply to compression problems where the source produces discrete time and discrete valued outputs. For cases where the source is analog there are powerful compression algorithms that specify all the steps from sampling, quantizations, and binary representation. These are referred to as waveform coders. JPEG, MPEG, vocoders are a few examples for image, video, and voice, respectively.