Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-26T01:06:21.940Z Has data issue: false hasContentIssue false
  • English
  • Français

Chains, entropy, coding

Published online by Cambridge University Press:  19 September 2008

Karl Petersen
Karl Petersen
Affiliation:
Department of Mathematics, Phillips Hall 039A, University of North Carolina, Chapel Hill, North Carolina 27514, USA
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Various definitions of the entropy for countable-state topological Markov chains are considered. Concrete examples show that these quantities do not coincide in general and can behave badly under nice maps. Certain restricted random walks which arise in a problem in magnetic recording provide interesting examples of chains. Factors of some of these chains have entropy equal to the growth rate of the number of periodic orbits, even though they contain no subshifts of finite type with positive entropy; others are almost sofic – they contain subshifts of finite type with entropy arbitrarily close to their own. Attempting to find the entropies of such subshifts of finite type motivates the method of entropy computation by loop analysis, in which it is not necessary to write down any matrices or evaluate any determinants. A method for variable-length encoding into these systems is proposed, and some of the smaller subshifts of finite type inside these systems are displayed.

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 6 , Issue 3 , September 1986 , pp. 415 - 448
Copyright
Copyright © Cambridge University Press 1986

References

REFERENCES

[1]Adler, R. L. & Marcus, B.. Topological entropy and equivalence of dynamical systems. Mem. Amer. Math. Soc. 219 (1979).Google Scholar
[2]Adler, R., Coppersmith, D. & Hassner, M.. Algorithms for sliding block codes-an applicationof symbolic dynamics to information theory, IEEE Trans. Inf. Theory 29 (1983), 5–22.Google Scholar
[3]Blanchard, F.. Systémes dynamiques topologiques associés á des automatesrécurrents. Z. Wahr. verw. Geb. 58 (1981), 549–564.CrossRefGoogle Scholar
[4]Blanchard, F. & Hansel, G.. Systémes codés. To appear.Google Scholar
[5]Block, L., Guckenheimer, J.Misiurewicz, M. & Young, L.-S.. Periodic points and topological entropy for one dimensional maps. Lecture Notes in Math. 819, Springer-Verlag, New York, 1980, 18–34.Google Scholar
[6]Bowen, R.. Entropy for group endomorphisms and homogeneous spaces. Trans. Amer. Math. Soc. 153 (1971), 401–414.CrossRefGoogle Scholar
[7]Brudno, A. A.. Entropy and the complexity of the trajectories of a dynamical system. Trans. Moscow Math. Soc. 44 (1982), 127–151.Google Scholar
[8]Denker, M., Grillenberger, C. & Sigmund, K.. Ergodic Theory on Compact Spaces, Lecture Notes in Math. 527, Springer-Verlag, New York, 1976.CrossRefGoogle Scholar
[9]Derriennic, Y.. Quelques applications du théoréme ergodique sous-additif. Soc. Math, de France Astérisque 74 (1980), 183–201.Google Scholar
[10]Dinaburg, E. I.. An example of the computation of topological entropy. Uspehi Mat. Nauk 23 (1968), 249–250.Google Scholar
[11]Franaszek, P. A.. A general method for channel coding. I.B.M. J. Res. and Dev. 24 (1980), 638–691.Google Scholar
[12]Franaszek, P. A.. Construction of bounded delay codes for discrete channels. I.B.M. J. Res. and Dev. 26 (1982), 506–514.Google Scholar
[13]Gould, H. W.. Combinatorial Identities. Morgantown, W. Va., 1972.Google Scholar
[14]Gurevič, B. M.. Topological entropy of enumerable Markov chains. Dokl. Akad. Nauk SSSR 187 (1969).Google Scholar
Soviet Math. Dokl. 10 (1969), 911–915.Google Scholar
[15]Gurevič, B. M.. Shift entropy and Markov measures in the path space of a denumerable graph. Dokl. Akad. Nauk SSSR 192 (1970).Google Scholar
Soviet Math. Dokl. 11 (1970), 744–747.Google Scholar
[16]Lempel, A. & Cohn, M.. Look ahead coding for input restricted channels. IEEE Trans. Inf. Theory 28 (1982), 933–937.Google Scholar
[17]Marcus, B.. Sofic systems and encoding data. IEEE Trans. Inf. Theory 31 (1985), 366–377.Google Scholar
[18]Marcus, B. & Petersen, K.. Balancing ergodic averages. In Ergodic Theory, Lecture Notes in Math. 729, Springer-Verlag, New York, 1979, 126–143.CrossRefGoogle Scholar
[19]Norris, K. & Bloomberg, D. S.. Channel capacity of charge-constrained run-length limited codes. IEEE Trans. Magnetics 17 (1981), 3452–3455.Google Scholar
[20]Parry, W. & Tuncel, S.. Classification Problems in Ergodic Theory. L.M.S. Lecture Note Series 67. Cambridge University Press: Cambridge, 1982.Google Scholar
[21]Patel, A. D.. Zero modulation in magnetic recording. I.B.M. J. Res. and Dev. 19 (1975), 366–388Google Scholar
[22]Salama, I..Topological entropy and classification of countable chains. Ph.D. Dissertation, University of North Carolina, 1984.Google Scholar
[23]Salem, R.. Power series with integral coefficients. Duke Math. J. 12 (1945), 153–171.Google Scholar
[24]Seneta, E., Non-negative Matrices and Markov Chains. Springer-Verlag, New York, 1973 and 1981.Google Scholar
[25]Siegel, P. H.. Modulation codes for magnetic recording. Preprint.Google Scholar
[26]Tang, D. and Bahl, L.. Block codes for a class of constrained noiseless channels. Inf. and Control 7 (1970), 436–461.Google Scholar
[27]Vere-Jones, D.. Geometric ergodicity in denumerable Markov chains. Quarterly J. Math. 13 (1962), 7–28.Google Scholar
[28]Vere-Jones, D.. Ergodic properties of nonnegative matrices, I. Pacific J. Math. 22 (1967), 361–386.Google Scholar
[29]Wagoner, J. B.. Topological Markov chains, C*-algebras, and K 2. To appear.Google Scholar
[30]Weiss, B.. Intrinsically ergodic systems. Bull. Amer. Math. Soc. 76 (1970), 1266–1269.Google Scholar