Entropy_coding

  (Redirected from Entropy encoding)

Jump to navigation Jump to search

In information theory, an entropy coding (or entropy encoding) is a lossless data compression scheme that is independent of the specific characteristics of the medium.

One of the main types of entropy coding creates and assigns a unique prefix-free code to each unique symbol that occurs in the input. ^[1] These entropy encoders then compress data by replacing each fixed-length input symbol with the corresponding variable-length prefix-free output codeword. The length of each codeword is approximately proportional to the negative logarithm of the probability of occurrence of that codeword. Therefore, the most common symbols use the shortest codes.^[2]

According to Shannon's source coding theorem, the optimal code length for a symbol is ${\displaystyle -log_{b}(P)}$, where ${\displaystyle b}$ is the number of symbols used to make output codes and ${\displaystyle P}$ is the probability of the input symbol.

Two of the most common entropy coding techniques are Huffman coding and arithmetic coding.^[3] 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. 
   

"Education - Entropy Encoding". www.pcs-ip.eu. Retrieved 2020-10-13.

"What is Entropy Coding | IGI Global". www.igi-global.com. Retrieved 2020-10-13.

3. 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).

	This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please help to improve this article by introducing more precise citations. (December 2013) (Learn how and when to remove this template message)
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 842 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 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 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 Grammar Information theory Timeline Kolmogorov complexity Quantization Rate–distortion Redundancy
Compression formats Compression software (codecs) from https://en.wikipedia.org/wiki/Entropy_coding