Shannon coding

In the field of data compression, Shannon coding, named after its creator, Claude Shannon, is a lossless data compression technique for constructing a prefix code based on a set of symbols and their probabilities (estimated or measured). It is suboptimal in the sense that it does not achieve the lowest possible expected code word length like Huffman coding, and never better but sometime equal to the Shannon-Fano coding.

The method was the first of its type, The technique was used to prove Shannon's noiseless coding theorem in his 1948 article "A Mathematical Theory of Communication",[1] and is therefore a centerpiece of the information age.

This coding method led rise to the field of information theory and without its contribution, the world would not have any of the many successors; for example Shannon-Fano coding, Huffman coding, or arithmetic coding. Much of our day-to-day lives are significantly influenced by digital data and this would not be possible without Shannon coding and its ongoing evolution of its predecessor coding methods.

In Shannon coding, the symbols are arranged in order from most probable to least probable, and assigned codewords by taking the first digits from the binary expansions of the cumulative probabilities . Here denotes the function which rounds up to the next integer value.

Example

In the table below is shown an example of creating code scheme for symbols a1-6. li represents negative power of 2, which is less than or equal to the current probability. Fifth column represent binary form of sum. The last column is the bit code of each symbol.

ai p(ai) li Sum from pi to i-1 Sum to p(ai) binary Result (truncated significand)
a1 0.36 2 0.0 0.0000 00
a2 0.18 3 0.36 0.0100 010
a3 0.18 3 0.54 0.1000 100
a4 0.12 4 0.72 0.1011 1011
a5 0.09 4 0.84 0.1101 1101
a6 0.07 4 0.93 0.1110 1110

References

External links

This article is issued from Wikipedia - version of the 10/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.