Shannon coding

Lossless data compression technique

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 does, and never better than but sometimes equal to the Shannon–Fano coding (Fano's method).

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.

Shannon–Fano coding methods gave rise to the field of information theory and without its contributions, the world would not have any of the many successors; for example 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-Fano coding and the ongoing evolution of its methods.[2][page needed]

In Shannon coding, the symbols are arranged in order from most probable to least probable, and assigned codewords by taking the first  l i = ⌈ − log 2 ⁡ p i ⌉ {\displaystyle l_{i}=\left\lceil -\log _{2}p_{i}\right\rceil } bits from the binary expansions of the cumulative probabilities  ∑ k = 1 i − 1 p k . {\displaystyle \sum \limits _{k=1}^{i-1}p_{k}.} Here  ⌈ x ⌉ {\displaystyle \lceil x\rceil } denotes the ceiling function (which rounds  x {\displaystyle x} up to the next integer value).

## Example

[edit]

In the table below is an example of creating a code scheme for symbols a1 to a6. The value of li gives the number of bits used to represent the symbol ai. The last column is the bit code of each symbol.

i | pi | li |  ∑ n = 0 i − 1 p n {\displaystyle \sum _{n=0}^{i-1}p_{n}} | Previous value in binary  | Codeword for ai

|
|
|
|
|

1  | 0.36  | 2  | 0.0  | 0.0000  | 00
2  | 0.18  | 3  | 0.36  | 0.0101...  | 010
3  | 0.18  | 3  | 0.54  | 0.1000...  | 100
4  | 0.12  | 4  | 0.72  | 0.1011...  | 1011
5  | 0.09  | 4  | 0.84  | 0.1101...  | 1101
6  | 0.07  | 4  | 0.93  | 0.1110...  | 1110

## References

[edit]

1. ^ Shannon, Claude E. (July 1948). "A Mathematical Theory of Communication [reprint with corrections]" (PDF). Bell System Technical Journal. 27 (3): 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x. hdl:11858/00-001M-0000-002C-4314-2.
2. ^ Ze-Nian Li; Mark S. Drew; Jiangchuan Liu (9 April 2014). Fundamentals of Multimedia. Springer Science & Business Media. ISBN 978-3-319-05290-8.

Shannon, Claude Elwood. "A Mathematical Theory of Communication." ACM SIGMOBILE mobile computing and communications review 5.1 (2001): 3-55.

* v
* t
* e

Data compression methods

Lossless|

| Entropy type|

* Adaptive coding
* Arithmetic
* Asymmetric numeral systems
* Golomb
* Huffman
* Adaptive
* Canonical
* Modified
* Range
* Shannon
* Shannon–Fano
* Shannon–Fano–Elias
* Tunstall
* Unary
* Universal
* Exp-Golomb
* Fibonacci
* Gamma
* Levenshtein

|

Dictionary type|

* Byte pair encoding
* Lempel–Ziv
* 842
* LZ4
* LZJB
* LZO
* LZRW
* LZSS
* LZW
* LZWL
* Snappy

Other types|

* BWT
* CTW
* CM
* Delta
* Incremental
* DMC
* DPCM
* Grammar
* Re-Pair
* Sequitur
* LDCT
* MTF
* PAQ
* PPM
* RLE

Hybrid|

* LZ77 + Huffman
* Deflate
* LZX
* LZS
* LZ77 + ANS
* LZFSE
* LZ77 + Huffman + ANS
* Zstandard
* LZ77 + Huffman + context
* Brotli
* LZSS + Huffman
* LHA/LZH
* LZ77 + Range
* LZMA
* LZHAM
* RLE + BWT + MTF + Huffman
* bzip2

Lossy|

| Transform type|

* Discrete cosine transform
* DCT
* MDCT
* DST
* FFT
* Wavelet
* Daubechies
* DWT
* SPIHT

|

Predictive type|

* DPCM
* ADPCM
* LPC
* ACELP
* CELP
* LAR
* LSP
* WLPC
* Motion
* Compensation
* Estimation
* Vector
* Psychoacoustic

Audio|

| Concepts|

* Bit rate
* ABR
* CBR
* VBR
* Companding
* Convolution
* Dynamic range
* Latency
* Nyquist–Shannon theorem
* Sampling
* Silence compression
* Sound quality
* Speech coding
* Sub-band coding

|

Codec parts|

* A-law
* μ-law
* DPCM
* ADPCM
* DM
* FT
* FFT
* LPC
* ACELP
* CELP
* LAR
* LSP
* WLPC
* MDCT
* Psychoacoustic model

Image|

| Concepts|

* Chroma subsampling
* Coding tree unit
* Color space
* Compression artifact
* Image resolution
* Macroblock
* Pixel
* PSNR
* Quantization
* Standard test image
* Texture compression

|

Methods|

* Chain code
* DCT
* Deflate
* Fractal
* KLT
* LP
* RLE
* Wavelet
* Daubechies
* DWT
* EZW
* SPIHT

Video|

| Concepts|

* Bit rate
* ABR
* CBR
* VBR
* Display resolution
* Frame
* Frame rate
* Frame types
* Interlace
* Video characteristics
* Video quality

|

Codec parts|

* DCT
* DPCM
* Deblocking filter
* Lapped transform
* Motion
* Compensation
* Estimation
* Vector
* Wavelet
* Daubechies
* DWT

Theory|

* Compressed data structures
* Compressed suffix array
* FM-index
* Entropy
* Information theory
* Timeline
* Kolmogorov complexity
* Prefix code
* Quantization
* Rate–distortion
* Redundancy
* Symmetry
* Smallest grammar problem

Community|

* Hutter Prize

People|

* Mark Adler

* Compression formats
* Compression software (codecs)

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template