Average Redundancy of the Shannon Code for Markov Sources

作者：Merhav Neri^*; Szpankowski Wojciech

来源：IEEE Transactions on Information Theory, 2013, 59(11): 7186-7193.

DOI：10.1109/TIT.2013.2275920

• Analytic information theory
• average redundancy
• Fourier series
• Shannon code
• spectral analysis
• uniform convergence

It is known that for memoryless sources, the average and maximal redundancy of fixed-to-variable length codes, such as the Shannon and Huffman codes, exhibit two modes of behavior for long blocks. It either converges to a limit or it has an oscillatory pattern, depending on the irrationality or rationality, respectively, of certain parameters that depend on the source. In this paper, we extend these findings, concerning the Shannon code, to the case of a Markov source. We provide a precise characterization of the convergent versus oscillatory behavior of the Shannon code redundancy for a class of irreducible, periodic, and aperiodic, Markov sources. These findings are obtained by analytic methods, such as Fourier/Fejer series analysis and spectral analysis of matrices.

• 出版日期2013-11