Abstract: This paper revisits the fundamental theorems of lossless coding, specifically challenging the widely held belief that the expected length of any uniquely decodable block code must be at least as large as the joint entropy of the source symbols ($E[l] \ge H$). By examining sources with memory, the authors demonstrate that this inequality only holds under a restrictive definition of unique decodability. They propose a generalized version of McMillan’s theorem for Markovian sources, showing that for finite-length constrained sources, it is possible to achieve "negative redundancy."
The Gap in McMillan’s Theorem
In introductory information theory, McMillan’s Theorem is a cornerstone. It states that for any uniquely decodable code, the codeword lengths must satisfy Kraft’s inequality, leading to the conclusion that average codeword length cannot be less than source entropy. However, Dalai and Leonardi point out that McMillan’s original proof assumes memoryless sources where any sequence of symbols is possible.
In reality, many sources are constrained (e.g., Markov sources), meaning certain sequences of symbols have zero probability of occurring. The authors argue that the standard definition of "unique decodability" is often applied in a source-independent way, whereas practical decodability is inherently source-dependent. If a source never produces a specific ambiguous sequence, a code that would be ambiguous for a memoryless source remains perfectly decodable for that specific constrained source.
A Counter-Example to the Entropy Bound
To illustrate this, the authors construct a specific 4-state Markov source and a corresponding binary code. The source constraints are defined by transition probabilities that make certain symbol combinations impossible.
As shown in the transition diagram above, the source has restricted movement between states A, B, C, and D. Exploiting these restrictions, the authors propose an encoding scheme that appears ambiguous at first glance but is uniquely decodable given the source's behavior.
In this example, the code maps $A \to 0$, $B \to 1$, $C \to 01$, and $D \to 10$. While a sequence like "01" could represent either the single symbol $C$ or the sequence $AB$, the source constraints might make the sequence $AB$ impossible. Consequently, the decoder can always resolve the ambiguity. For small block lengths $n$, this code achieves an average length strictly less than the joint entropy—a phenomenon described as "negative redundancy."
Generalizing McMillan for Markov Sources
The paper moves beyond counter-examples to provide a formal mathematical extension of coding theory for Markovian sources. The authors introduce a matrix $\mathbf{Q}$, where entries represent codeword lengths weighted by the source's transition possibilities.
Through spectral analysis, they establish Theorem 2: A necessary condition for a code to be uniquely decodable for a Markov source is that the spectral radius (the largest absolute eigenvalue) of the matrix $\mathbf{Q}$ must be less than or equal to 1 ($\rho(\mathbf{Q}) \le 1$). This provides a new "Kraft-like" condition specifically tailored for sources with memory.
Conclusion and Implications
While the authors acknowledge that this "gain" per symbol vanishes as the block length $n$ approaches infinity (aligning with the Asymptotic Equipartition Property), the discovery has significant implications for finite-length coding. It proves that the standard converse to the source coding theorem is not a "strong" converse for constrained sources.
Future work remains in determining whether the condition $\rho(\mathbf{Q}) \le 1$ is sufficient as well as necessary, and in exploring the practical complexities of designing such codes for high-order Markov sources or complex real-world constraints.
Summary updated