Entropy coding

Short description: Lossless data compression scheme

In information theory, an entropy coding (or entropy encoding) is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method must have an expected code length greater than or equal to the entropy of the source.[1]

More precisely, the source coding theorem states that for any source distribution, the expected code length satisfies [math]\displaystyle{ \operatorname E_{x\sim P}[\ell(d(x))] \geq \operatorname E_{x\sim P}[-\log_b(P(x))] }[/math], where [math]\displaystyle{ \ell }[/math] is the number of symbols in a code word, [math]\displaystyle{ d }[/math] is the coding function, [math]\displaystyle{ b }[/math] is the number of symbols used to make output codes and [math]\displaystyle{ P }[/math] is the probability of the source symbol. An entropy coding attempts to approach this lower bound.

Two of the most common entropy coding techniques are Huffman coding and arithmetic coding.[2] If the approximate entropy characteristics of a data stream are known in advance (especially for signal compression), a simpler static code may be useful. These static codes include universal codes (such as Elias gamma coding or Fibonacci coding) and Golomb codes (such as unary coding or Rice coding).

Since 2014, data compressors have started using the asymmetric numeral systems family of entropy coding techniques, which allows combination of the compression ratio of arithmetic coding with a processing cost similar to Huffman coding.

## Contents

* 1 Entropy as a measure of similarity
* 2 See also
* 3 References
* 4 External links

## Entropy as a measure of similarity

Besides using entropy coding as a way to compress digital data, an entropy encoder can also be used to measure the amount of similarity between streams of data and already existing classes of data. This is done by generating an entropy coder/compressor for each class of data; unknown data is then classified by feeding the uncompressed data to each compressor and seeing which compressor yields the highest compression. The coder with the best compression is probably the coder trained on the data that was most similar to the unknown data.

## See also

* Arithmetic coding
* Asymmetric numeral systems (ANS)
* Context-adaptive binary arithmetic coding (CABAC)
* Huffman coding
* Range coding

## References

1. ↑ Duda, Jarek; Tahboub, Khalid; Gadgil, Neeraj J.; Delp, Edward J. (May 2015). "The use of asymmetric numeral systems as an accurate replacement for Huffman coding". 2015 Picture Coding Symposium (PCS). pp. 65–69. doi:10.1109/PCS.2015.7170048. ISBN 978-1-4799-7783-3. https://ieeexplore.ieee.org/document/7170048/;jsessionid=wI8UmMMsBsrAYcNN1Ux2gHW5ReVUf0HhrXFHlaZZVSmlJdKWDIv8!-2026188604.
2. ↑ Huffman, David (1952). "A Method for the Construction of Minimum-Redundancy Codes". Proceedings of the IRE (Institute of Electrical and Electronics Engineers (IEEE)) 40 (9): 1098–1101. doi:10.1109/jrproc.1952.273898. ISSN 0096-8390.

## External links

* Information Theory, Inference, and Learning Algorithms, by David MacKay (2003), gives an introduction to Shannon theory and data compression, including the Huffman coding and arithmetic coding.
* Source Coding, by T. Wiegand and H. Schwarz (2011).

* v
* t
* e

Data compression methods

Lossless|

| Entropy type|

* 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
* Brotli
* DEFLATE
* LZ4
* LZFSE
* LZJB
* LZMA
* LZO
* LZRW
* LZS
* LZSS
* LZW
* LZWL
* LZX
* Snappy
* Zstandard

Other types|

* BWT
* CTW
* Delta
* DMC
* DPCM
* LDCT
* MTF
* PAQ
* PPM
* RLE

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
* Sound quality
* Speech coding
* Sub-band coding

|

Codec parts|

* A-law
* μ-law
* DPCM
* ADPCM
* 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

|

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|

* Entropy
* Information theory
* Timeline
* Kolmogorov complexity
* Quantization
* Rate–distortion
* Redundancy

* Compression formats
* Compression software (codecs)

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Entropy coding. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Entropy_coding&oldid=3433064"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template