Source Entropy

Every information source, whether it is a text file, a sensor output, or a voice signal, produces symbols with certain probabilities. The entropy of a source is the precise mathematical measure of how much uncertainty or information is associated with each symbol produced by that source. It is the single most important quantity in information theory because it establishes the theoretical minimum number of bits needed to represent the source output, serving as the benchmark against which all compression algorithms are evaluated.

Core Concept of Source Entropy

A discrete memoryless source (DMS) is characterized by its alphabet (the set of possible symbols) and the probability of each symbol. The entropy H(X) is defined as the expected value of the self-information across all symbols: H(X) = -sum over all i of P(xi) * log₂(P(xi)) bits per symbol. Each term P(xi) * log₂(P(xi)) represents the contribution of symbol xi to the average uncertainty. The negative sign is needed because log₂(P(xi)) is always non-positive for 0 < P(xi) <= 1, making H(X) always non-negative.

The entropy has a clear physical meaning. If a source produces only one symbol always (P = 1 for one symbol, P = 0 for all others), there is no uncertainty at all and H(X) = 0. If a source produces M symbols each with probability 1/M, the uncertainty is maximum and H(X) = log₂(M). Between these extremes, entropy is a continuous, concave function of the probability distribution. Any deviation from uniform distribution reduces entropy.

The significance of entropy lies in Shannon's source coding theorem: the average number of bits per symbol required to losslessly encode the source output is at least H(X) and can be brought arbitrarily close to H(X) with sufficiently long block codes. This means entropy is not merely an abstract measure but a hard engineering limit for data compression.

Mathematical Expression

The entropy formula H(X) = -sum_{i=1}^{M} P(xi) log₂(P(xi)) has several important properties that are useful in analysis. First, H(X) >= 0 always. Second, H(X) = 0 if and only if one symbol has probability 1. Third, H(X) is maximized at log₂(M) when all M symbols have equal probability 1/M. Fourth, H(X) is a concave function of the probability vector, meaning a mixture of distributions has entropy no less than the weighted sum of their entropies.

The maximum entropy conditions are important for GATE and design problems. The maximum entropy source is the one with the least structure or the most randomness. For a binary source, maximum entropy of 1 bit/symbol occurs when P(0) = P(1) = 0.5. For a ternary source with symbols {0, 1, 2}, maximum entropy of log₂(3) ≈ 1.585 bits/symbol occurs when all three are equally probable. When a constraint is placed on the source (such as a mean value constraint for a continuous source), the maximum entropy distribution under that constraint has a specific form, for example, the Gaussian distribution maximizes differential entropy for a fixed variance.

The entropy of independent sources is additive. If X and Y are statistically independent, then H(X,Y) = H(X) + H(Y). This additivity is the property that makes entropy compatible with the notion of information as something that can be combined and separated. For dependent sources, H(X,Y) < H(X) + H(Y) because knowing one source tells you something about the other, reducing the total uncertainty.

Practical Understanding

In digital communication, entropy determines how compressible a data source is. English text, for example, does not use all 26 letters with equal frequency. The letter E appears far more often than Z. As a result, the entropy of English text per letter is roughly 1.0 to 1.5 bits, far below the theoretical maximum of log₂(26) ≈ 4.7 bits/letter. This gap between actual entropy and the maximum is exactly the redundancy that compression algorithms like Huffman coding exploit to reduce file size.

In GATE examinations, entropy problems typically ask students to compute H(X) from a given probability table, find the maximum entropy for a given alphabet size, compare two sources, or find the minimum average code length. The minimum average code length for lossless coding equals H(X) (achievable only with infinitely long blocks or arithmetic coding), while Huffman coding achieves H(X) <= L_avg < H(X) + 1 for symbol-by-symbol encoding.

Solved Numerical Example

A source produces five symbols with probabilities 0.4, 0.3, 0.15, 0.1, and 0.05. The source entropy is to be computed and compared to the maximum possible entropy for a 5-symbol source. The efficiency of the source is defined as the ratio of actual entropy to maximum entropy.

Given:
Symbols: x1, x2, x3, x4, x5
Probabilities: P(x1)=0.4, P(x2)=0.3, P(x3)=0.15, P(x4)=0.10, P(x5)=0.05
Verification: 0.4+0.3+0.15+0.10+0.05 = 1.00 (valid)

Why this formula applies:
Entropy H = -sum P(xi)*log₂(P(xi)) averages information over all symbols.

Formula:
H(X) = -sum_{i=1}^{5} P(xi) * log₂(P(xi))

Substitution:
H = -[0.4*log₂(0.4) + 0.3*log₂(0.3) + 0.15*log₂(0.15) + 0.10*log₂(0.10) + 0.05*log₂(0.05)]

Calculation:
log₂(0.4)  = -1.322  → 0.4 * (-1.322) = -0.529
log₂(0.3)  = -1.737  → 0.3 * (-1.737) = -0.521
log₂(0.15) = -2.737  → 0.15 * (-2.737) = -0.411
log₂(0.10) = -3.322  → 0.10 * (-3.322) = -0.332
log₂(0.05) = -4.322  → 0.05 * (-4.322) = -0.216
Sum of P*log₂P = -0.529 - 0.521 - 0.411 - 0.332 - 0.216 = -2.009
H(X) = -(-2.009) = 2.009 bits/symbol

Maximum entropy for M=5 symbols:
H_max = log₂(5) = 2.322 bits/symbol

Source efficiency:
η = H(X) / H_max = 2.009 / 2.322 = 86.5%

Final Answer with units:
H(X) = 2.009 bits/symbol
H_max = 2.322 bits/symbol
Source efficiency = 86.5%
Minimum average code length = 2.009 bits/symbol

Exam Tip: GATE often asks for maximum entropy. Always remember H_max = log₂(M) for M symbols. A common mistake is confusing the entropy of a source with code length. Entropy is the theoretical minimum, not the actual code length. Also, by convention, 0*log₂(0) = 0, not undefined.

Mechanism Explained

• Entropy H(X) = -sum P(xi) log₂(P(xi)) computes the probability-weighted average of self-information, giving the average bits of information per source symbol.
• H(X) = 0 when one symbol is certain (probability 1). H(X) = log₂(M) when all M symbols are equally probable. Entropy always lies between these bounds.
• The entropy function is strictly concave in the probability vector, meaning any non-uniform distribution has lower entropy than the uniform distribution over the same alphabet.
• For independent sources X and Y, entropy is additive: H(X,Y) = H(X) + H(Y). For dependent sources, H(X,Y) < H(X) + H(Y) because statistical dependence reduces uncertainty.
• Shannon's source coding theorem directly uses entropy as the compression limit: H(X) bits per symbol is the minimum achievable average code length for lossless encoding.

Quick Revision

• Entropy formula: H(X) = -sum P(xi) log₂(P(xi)) bits/symbol. Convention: 0*log₂(0) = 0.
• Minimum entropy: H = 0 when source is deterministic (one symbol with P=1).
• Maximum entropy: H_max = log₂(M) for M equally probable symbols.
• Source coding bound: H(X) <= L_avg < H(X) + 1 for Huffman coding. L_avg reaches H(X) with arithmetic or long block coding.
• For independent X, Y: H(X,Y) = H(X) + H(Y). Dependent case: H(X,Y) < H(X) + H(Y).
• GATE trap: Higher entropy does NOT mean the source is better. It means the source is more unpredictable and harder to compress. A source with low entropy is more redundant.
• Efficiency of a source: η = H(X) / H_max = H(X) / log₂(M). Maximum efficiency = 1 for uniform source.