Redundancy (information theory)

In information theory, redundancy measures the fractional difference between the entropy H(X) of an ensemble X, and its maximum possible value log⁡(|𝒜X|).[1][2] Informally, it is the amount of wasted "space" used to transmit certain data. Data compression is a way to reduce or eliminate unwanted redundancy, while forward error correction is a way of adding desired redundancy for purposes of error detection and correction when communicating over a noisy channel of limited capacity.

## Contents

* 1 Quantitative definition
* 2 Other notions
* 2.1 Group redundancy
* 3 See also
* 4 References

## Quantitative definition

In describing the redundancy of raw data, the rate of a source of information is the average entropy per symbol. For memoryless sources, this is merely the entropy of each symbol, while, in the most general case of a stochastic process, it is

r=limn->∞1nH(M1,M2,…Mn),

in the limit, as n goes to infinity, of the joint entropy of the first n symbols divided by n. It is common in information theory to speak of the "rate" or "entropy" of a language. This is appropriate, for example, when the source of information is English prose. The rate of a memoryless source is simply H(M), since by definition there is no interdependence of the successive messages of a memoryless source.[citation needed]

The absolute rate of a language or source is simply

R=log⁡|𝕄|,

the logarithm of the cardinality of the message space, or alphabet. (This formula is sometimes called the Hartley function.) This is the maximum possible rate of information that can be transmitted with that alphabet. (The logarithm should be taken to a base appropriate for the unit of measurement in use.) The absolute rate is equal to the actual rate if the source is memoryless and has a uniform distribution.

The absolute redundancy can then be defined as

D=R−r,

the difference between the absolute rate and the rate.

The quantity DR is called the relative redundancy and gives the maximum possible data compression ratio, when expressed as the percentage by which a file size can be decreased. (When expressed as a ratio of original file size to compressed file size, the quantity R:r gives the maximum compression ratio that can be achieved.) Complementary to the concept of relative redundancy is efficiency, defined as rR, so that rR+DR=1. A memoryless source with a uniform distribution has zero redundancy (and thus 100% efficiency), and cannot be compressed.

## Other notions

A measure of redundancy between two variables is the mutual information or a normalized variant. A measure of redundancy among many variables is given by the total correlation.

Redundancy of compressed data refers to the difference between the expected compressed data length of n messages L(Mn) (or expected data rate L(Mn)/n) and the entropy nr (or entropy rate r). (Here we assume the data is ergodic and stationary, e.g., a memoryless source.) Although the rate difference L(Mn)/n−r can be arbitrarily small as n increased, the actual difference L(Mn)−nr, cannot, although it can be theoretically upper-bounded by 1 in the case of finite-entropy memoryless sources.

Redundancy in an information-theoretic contexts can also refer to the information that is redundant between two mutual informations. For example, given three variables X1, X2, and Y, it is known that the joint mutual information can be less than the sum of the marginal mutual informations: I(X1,X2;Y)<I(X1;Y)+I(X2;Y). In this case, at least some of the information about Y disclosed by X1 or X2 is the same. This formulation of redundancy is complementary to the notion of synergy, which occurs when the joint mutual information is greater than the sum of the marginals, indicating the presence of information that is only disclosed by the joint state and not any simpler collection of sources.[3][4]

### Group redundancy

The above pairwise redundancy measure can be generalized to a set of n variables.

Redundancy=I(X1,X2,...,Xn;Y)−(I(X1;Y)+I(X2;Y)+...I(Xn;Y)). [5] As the pair-wise measure above, if this value is negative, one says the set of variables is redundant.

## See also

* Minimum redundancy coding
* Huffman encoding
* Data compression
* Hartley function
* Negentropy
* Source coding theorem
* Overcompleteness

## References

1. ↑ Here it is assumed 𝒜X are the sets on which the probability distributions are defined.
2. ↑ MacKay, David J.C. (2003). "2.4 Definition of entropy and related functions". Information Theory, Inference, and Learning Algorithms. Cambridge University Press. p. 33. ISBN 0-521-64298-1. http://www.inference.phy.cam.ac.uk/mackay/itila/book.html. "The redundancy measures the fractional difference between H(X) and its maximum possible value, |log⁡(|𝒜X|)"
3. ↑ Williams, Paul L.; Beer, Randall D. (2010). "Nonnegative Decomposition of Multivariate Information". arXiv:1004.2515 [cs.IT].
4. ↑ Gutknecht, A. J.; Wibral, M.; Makkeh, A. (2021). "Bits and pieces: Understanding information decomposition from part-whole relationships and formal logic". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 477 (2251). doi:10.1098/rspa.2021.0110. PMID 35197799. Bibcode: 2021RSPSA.47710110G.
5. ↑ Chechik, Gal; Globerson, Amir; Anderson, M.; Young, E.; Nelken, Israel; Tishby, Naftali (2001). "Group Redundancy Measures Reveal Redundancy Reduction in the Auditory Pathway". Advances in Neural Information Processing Systems (MIT Press) 14. https://proceedings.neurips.cc/paper/2001/hash/05a5cf06982ba7892ed2a6d38fe832d6-Abstract.html.

* Reza, Fazlollah M. (1994). An Introduction to Information Theory. New York: Dover [McGraw-Hill]. ISBN 0-486-68210-2.
* Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: John Wiley & Sons, Inc.. ISBN 0-471-12845-7. https://archive.org/details/Applied_Cryptography_2nd_ed._B._Schneier.
* Auffarth, B; Lopez-Sanchez, M.; Cerquides, J. (2010). "Comparison of Redundancy and Relevance Measures for Feature Selection in Tissue Classification of CT images". Advances in Data Mining. Applications and Theoretical Aspects. Springer. pp. 248–262.

* 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/Redundancy (information theory). Read more

|

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