Entropy and Redundancy

Introduction: The Basis of Lossless Compression

After distinguishing lossless and lossy compression, we can focus on how lossless compression works. A lossless algorithm reconstructs the input exactly, so it does not remove information. It changes the representation by exploiting redundancy in the data. Reconstruction also requires the decoder to know the coding rules or the model used by the compressor.

Redundancy consists of predictable or repeated elements in a data representation. Their description can be shortened without changing the data after decompression. The information content reflects the part associated with uncertainty in the source. Information theory, established in large part by Claude Shannon, gives precise measures for both quantities. Entropy measures average information content, while redundancy describes the difference between an encoding and the limit set by entropy. This relationship determines when and how much lossless compression is possible. A representation with no redundancy has no further shortening available under the same source model.

Entropy: A Measure of Uncertainty and Information

Entropy is the average information content per symbol of a source. For a symbol distribution, it quantifies the uncertainty associated with symbol occurrence. The self-information of one symbol is $I(x_i) = -\log_2 P(x_i)$, so entropy is its expected value. With a base-two logarithm, the unit is bits per symbol. This value describes the symbol distribution; for a sequence with dependencies, the entropy rate can be lower and must account for the context of earlier symbols. For a source $X$ that produces symbols $x_i$ with probabilities $P(x_i)$, the formula is:

Properties of Entropy

The equation gives the following properties of information and uncertainty:

• Maximum Entropy: For a source with a fixed alphabet of $n$ symbols, entropy is maximal when all symbols have equal probabilities. Then $P(x_i) = 1/n$, and the maximum is $H_{ ext{max}}(X) = log_2(n)$. In a memoryless model, this distribution provides no statistical pattern to exploit, so compression is difficult. Dependencies between successive symbols can still reduce the entropy rate of a sequence.
• Minimum Entropy (Zero Entropy):Entropy is zero if and only if one symbol has probability 1 and every other symbol has probability 0. The source is then deterministic, so its next symbol can be predicted without error. For example, a source that produces only the letter 'A' has zero entropy.
• Non-negativity: Entropy is always zero or positive because probabilities lie between zero and one.

Example: An Alphabet of Four Symbols

Consider a source that generates messages from an alphabet of four symbols: A, B, C, and D.

Assume the symbols are independent and each has the same probability of appearing:

The maximum entropy for this four-symbol source is:

A fixed-length code can assign A=00, B=01, C=10, and D=11. Its average length is exactly 2 bits per symbol. It equals the entropy of this source, so the code reaches the theoretical limit for this model. Each symbol requires two bits because four equally likely possibilities carry $\log_2(4) = 2$ bits of information. No redundancy is introduced by this code.

Now assume an unequal probability distribution. Some symbols occur more often, so the source has lower average uncertainty.

The entropy for this biased source is calculated as the weighted average of the self-information of each symbol:

The entropy, 1.75 bits per symbol, is lower than the maximum value of 2 bits per symbol. With the 2-bit code (A=00, B=01, and so on), the average code length remains 2 bits. A variable-length code can assign shorter codewords to frequent symbols while preserving unambiguous decoding. The difference from the entropy, 0.25 bits per symbol, is the redundancy of this code.

Redundancy: The Difference from Entropy

Redundancy describes the predictable and repeated part of a data representation. Entropy gives the source's average information content, while redundancy also depends on the selected code. Quantitatively, it is the difference between the average representation length and the limit set by entropy. Two codes for the same source can therefore have different redundancy values even when they reproduce the same message.

Quantifying Redundancy

Redundancy can be expressed in absolute and relative terms. Consider a source $X$ with entropy $H(X)$ and a code whose average length is $L_{\text{avg}}$ bits per symbol. For a fixed-length code with $n$ symbols, the general value is $L_{\text{avg}} = \lceil \log_2(n) \rceil$. When $n$ is a power of two, $L_{\text{avg}} = \log_2(n)$ and $H_{\text{max}}(X)$ have the same value, so this can be written as $L_{\text{avg}} = \log_2(n) = H_{\text{max}}(X)$. For other values of $n$, some codewords remain unused, so the rounding matters.

• Absolute Redundancy ($R$): This is the average number of bits per symbol above the entropy.
  $R = L_{\text{avg}} - H(X)$
• Relative Redundancy ($r$): This expresses the excess as a percentage of the total data size, providing a direct measure of compressibility.
  $r = \frac{R}{L_{\text{avg}}} = \frac{L_{\text{avg}} - H(X)}{L_{\text{avg}}} = 1 - \frac{H(X)}{L_{\text{avg}}}$

A lossless algorithm seeks a representation in which $L_{\text{avg}}$ is as close as possible to $H(X)$, so redundancy $R$ approaches zero. This limit applies to long sequences coded according to the chosen source model. An implementation also carries overhead for headers, dictionaries, code tables, or markers needed by the decoder.

Example: Redundancy in the Four-Symbol Alphabet

Apply the formulas to Scenario 2, where the fixed-length code has 2 bits $(L_{\text{avg}} = 2)$ and the entropy is $H(X) = 1.75$ bits per symbol.

• Absolute Redundancy: $R = 2 - 1.75 = 0.25 \text{ bits/symbol}$. The average redundancy is a quarter of a bit per symbol.
• Relative Redundancy: $r = 1 - \frac{1.75}{2} = 1 - 0.875 = 0.125$, or 12.5%. In this model, 12.5% of the current code represents the difference from entropy. The actual file reduction depends on the source model, data length, and format overhead, while a long sequence can theoretically approach the entropy rate.

Sources and Types of Redundancy in Data

A simple statistical model helps describe the theory. Real data contains dependencies at several levels, so redundancy appears in multiple forms. A codec selects a model according to the data type because dependencies in text, images, and audio have different structures.

Redundancy in Text

• Statistical Redundancy:Letters and words do not occur with equal frequency. In English, common sequences (digrams) such as "th," "he," and "in," together with words such as "the," "and," and "a," can receive shorter codes in a compressor.
• Syntactic Redundancy:Grammar limits the number of valid sequences. Dependencies between neighboring parts of speech let a model predict later characters or words and encode them more briefly. After the word "the," for example, another "the" is uncommon in ordinary prose.
• Semantic Redundancy:Meaning also increases predictability. In "Roses are red, violets are...", the continuation "blue" follows from the familiar context. A probable continuation carries little new information and increases the message's redundancy.

Redundancy in Images and Video

• Spatial Redundancy: Within an image or video frame, neighboring pixels are often correlated. A pixel against a blue sky may have a shade close to the pixels around it. This redundancy can be reduced by RLE in suitable formats and by the predictive filtering applied before DEFLATE in PNG.
• Temporal Redundancy: In video and audio, successive samples or frames are often similar. In a scene with a person talking against a static background, changes may be concentrated around the mouth and eyes. Temporal redundancy is one of the main opportunities for saving data in video, so codecs such as H.264 use motion compensation.
• Spectral Redundancy: In color images, the Red, Green, and Blue (RGB) components are often strongly related. For example, in a grayscale image, $R=G=B$. Knowing the value of one color channel provides a lot of information about the likely values of the others.

The Role of Data Models

Compression algorithms use data models to describe dependencies in the source. A model combines rules and statistics to estimate likely values for subsequent symbols. A more accurate model can exploit more dependencies and produce a shorter representation, but the model description must also be available to the decoder.

• Memoryless Models: The simple entropy calculation assumes that the source is "memoryless," meaning the probability of a symbol does not depend on previous symbols. This model describes basic statistical redundancy.
• Markov Models: These are "sources with memory" that include context. A first-order Markov model estimates the next character from the immediately preceding character. This leads to conditional entropy, the entropy when the context is known. For a context variable, $H(X|Y) \leq H(X)$, so the difference can describe redundancy exposed by the model. Algorithms such as PPM use contexts of different lengths and can achieve high effectiveness on text. The model can therefore replace one frequency table with several conditional distributions, each selected from the observed context. Short messages still include headers and other format overhead in the encoded stream.

Entropy gives the theoretical lower limit for the average length of a lossless code for a defined source model and long sequences. Redundancy is the difference between that limit and the representation in use. The more complex the dependencies, the more accurately a model must describe them for a compressor to exploit them. For short messages, headers and the model description can substantially increase the actual stream size.