Average Redundancy of the Shannon Code for Markov Sources

Neri Merhau; Wojciech Szpankowski

doi:10.1109/isit.2013.6620560

Average Redundancy of the Shannon Code for Markov Sources

Abstrakt

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, which is considerably more involved. While this dichotomy, of convergent vs. oscillatory behavior, is well known in other contexts (including renewal theory, ergodic theory, local limit theorems and large deviations of discrete distributions), in information theory (e.g., in redundancy analysis) it was recognized relatively recently. To the best of our knowledge, no results of this type were reported thus far for Markov sources. We provide a precise characterization of the convergent vs. 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/Fej´er series analysis and spectral analysis of matrices.

Cytowania

0

CrossRef
0

Web of Science
0

Scopus

Autorzy (2)

Neri Merhau
- .. ..
Wojciech Szpankowski prof. dr inż.
- Purdue University Department of Computer Science

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

pełna treść artykułu zobacz w serwisie zewnętrznym otwiera się w nowej karcie

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:: IEEE TRANSACTIONS ON INFORMATION THEORY nr 59, strony 7186 - 7193,
ISSN: 0018-9448
Język:: angielski
Rok wydania:: 2013
Opis bibliograficzny:: Merhau N., Szpankowski W.: Average Redundancy of the Shannon Code for Markov Sources// IEEE TRANSACTIONS ON INFORMATION THEORY. -Vol. 59, nr. 11 (2013), s.7186-7193
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/isit.2013.6620560
Weryfikacja:: Politechnika Gdańska