An Introduction to Symbolic Dynamics and Coding
Preface
Symbolic dynamics is a rapidly growing part of dynamical systems. Although it originated as a method to study general dynamical systems, the techniques and ideas have found significant applications in data storage and transmission as well as linear algebra. This is the first general textbook on symbolic dynamics and its applications to coding, and we hope that it will stimulate both engineers and mathematicians to learn and appreciate the subject.
Dynamical systems originally arose in the study of systems of differential equations used to model physical phenomena. The motions of the planets, or of mechanical systems, or of molecules in a gas can be modeled by such systems. One simplification in this study is to discretize time, so that the state of the system is observed only at discrete ticks of a clock, like a motion picture. This leads to the study of the iterates of a single transformation. One is interested in both quantitative behavior, such as the average time spent in a certain region, and also qualitative behavior, such as whether a state eventually becomes periodic or tends to infinity. Symbolic dynamics arose as an attempt to study such systems by means of discretizing space as well as time. The basic idea is to divide up the set of possible states into a finite number of pieces, and keep track of which piece the state of the system lies in at every tick of the clock. Each piece is associated with a “symbol,” and in this way the evolution of the system is described by an infinite sequence of symbols. This leads to a “symbolic” dynamical system that mirrors and helps us to understand the dynamical behavior of the original system.
In their fundamental paper written over fifty years ago, Morse and Hedlund named the subject of symbolic dynamics and described its philosophy as follows.
The methods used in the study of recurrence and transitivity frequently combine classical differential analysis with a more abstract symbolic analysis. This involves a characterization of the ordinary dynamical trajectory by an unending sequence of symbols termed a symbolic trajectory such that the properties of recurrence and transitivity of the dynamical trajectory are reflected in analogous properties of its symbolic trajectory.
One example of this idea that you are very familiar with is the decimal expansion of real numbers in the unit interval \([0,1)\). Here the transformation is given by multiplying a number \(x\) in \([0,1)\) by 10 and keeping its fractional part \(\{10x\}\). We partition \([0,1)\) into ten equal subintervals \([0,1/10)\), \([1/10,2/10)\), …, \([9/10,1)\), and we use the “symbol” \(j\) for the interval \([j/10,(j+1)/10)\). Let \(x\) be a number in \([0,1)\). Using the transformation \(x \mapsto \{10x\}\) and this partition, we write down an infinite sequence of symbols corresponding to any given \(x=.x_1 x_2 \ldots\), as follows. Since \(x\) is in \([x_1/10, (x_1 +1)/10)\), the first symbol is just the first digit \(x_1\) of its decimal expansion. Since \(\{10x\}\) is in \([x_2/10, (x_2 +1)/10)\), the next symbol is the first digit of the decimal expansion of \(\{10x\}\), which is simply the second digit \(x_2\) of the decimal expansion of \(x\). Continuing in this way, we see that the symbolic sequence derived from \(x\) is none other than the sequence of digits from its decimal expansion.
» Continue reading
Symbolic dynamics began when Jacques Hadamard applied this idea in 1898 to more complicated systems called geodesic flows on surfaces of negative curvature. The main point of his work is that there is a simple description of the possible sequences that can arise this way. He showed that there is a finite set of forbidden pairs of symbols, and that the possible sequences are exactly those that do not contain any forbidden pair. This is an example of one of the fundamental objects of study in symbolic dynamics called a shift of finite type. Later discoveries of Morse, Hedlund, and others in the 1920’s, 1930’s, and 1940’s showed that in many circumstances such a finite description of the dynamics is possible. These ideas led in the 1960’s and 1970’s to the development of powerful mathematical tools to investigate a class of extremely interesting mappings called hyperbolic diffeomorphisms. We will see in §6.5 some examples of this.
Another source of inspiration and questions in symbolic dynamics comes from data storage and transmission. As we discuss in §2.5, when information is stored as bits on a magnetic or optical disk, there are physical reasons why it is not stored verbatim. For example, the bits on the surface of a compact audio disk are written in a long sequence obeying the constraint that between successive 1’s there are at least two 0’s but no more than ten 0’s. How can one efficiently transform arbitrary data (such as a computer program or a Beethoven symphony) into sequences that satisfy such kinds of constraints? What are the theoretical limits of this kind of transformation? We are again confronted with a space of sequences having a finite description, and we are asking questions about such spaces and ways to encode and decode data from one space (the space of arbitrary sequences) to another (the space of constrained sequences). One of the main results in this book, the Finite-State Coding Theorem of Chapter 5, tells us when such codes are possible, and gives us an algorithm for finding them. This has led to new codes and a deeper understanding of code constructions. In particular, it has yielded a new and useful technique for code construction called the state-splitting algorithm.
While symbolic dynamics has drawn heavily on other mathematical disciplines such as linear algebra for its tools, it has also contributed new tools for other areas. For example, some deep work of Boyle and Handelman in symbolic dynamics described in Chapter 11 has led to the complete solution of the problem of characterizing the possible sets of nonzero eigenvalues of real nonnegative matrices. This solved a variant of a problem which has been perplexing linear algebraists for decades.
This book is intended to serve as an introduction to symbolic dynamics, its basic ideas, techniques, problems, and spirit. We will focus on symbolic dynamical systems that use just a finite number of symbols, on sequences of such symbols that are infinite in both directions (unlike the decimal expansion above), and spaces of sequences that have finite memory properties. Our aim is to study coding problems for such systems. In particular, we concentrate on the following:
- Find complete sets of necessary and sufficient conditions for the existence of various types of codes from one symbolic dynamical system to another.
- Completely determine the values of certain properties, invariant under a natural notion of “conjugacy,” such as entropy, numbers of periodic sequences, and so on.
- Explore interactions with information and coding theory, linear algebra, and general dynamical systems.
On the other hand, there are many important topics within symbolic dynamics that we do not treat in any depth in this book. Many of these topics are briefly discussed in Chapter 13.
The book is organized as follows. We start in Chapter 1 with the basic notions in symbolic dynamical systems, such as full shifts, shift spaces, irreducibility, and sliding block codes. In Chapter 2 we focus on a special class of shift spaces called shifts of finite type, and in Chapter 3 we study a generalization of these called sofic shifts. Entropy, an important numerical invariant, is treated in Chapter 4, which also includes an introduction to the fundamental Perron-Frobenius theory of nonnegative matrices. Building on the material in the first four chapters, we develop in Chapter 5 the state-splitting algorithm for code construction and prove the Finite-State Coding Theorem. Taken together, the first five chapters form a self-contained introduction to symbolic dynamics and its applications to practical coding problems.
Starting with Chapter 6 we switch gears. This chapter provides some background for the general theory of dynamical systems and the place occupied by symbolic dynamics. We show how certain combinatorial ideas like shift spaces and sliding block codes studied in earlier chapters are natural expressions of fundamental mathematical notions such as compactness and continuity. There is a natural notion of two symbolic systems being “the same,” or conjugate, and Chapter 7 deals with the question of when two shifts of finite type are conjugate. This is followed in Chapters 8 and 9 with the classification of shifts of finite type and sofic shifts using weaker notions, namely finite equivalence and almost conjugacy. Chapters 7, 8, and 9 treat problems of coding between systems with equal entropy. In Chapter 10 we treat the case of unequal entropy and, in particular, determine when one shift of finite type can be embedded in another. The set of numbers which can occur as entropies of shifts of finite type is determined in Chapter 11. Also in that chapter we draw on the results of Chapter 10 to prove a partial result towards characterizing the zeta functions of shifts of finite type (the zeta function is a function which determines the numbers of periodic sequences of all periods). Some of these results in turn are used in Chapter 12 to classify shifts of finite type and sofic shifts up to a notion that sits in between conjugacy and almost conjugacy. The main result of Chapter 12 may be regarded as a generalization of the Finite-State Coding Theorem, and tells us when one sofic shift can be encoded into another in a natural way. Chapter 13 contains a survey of more advanced results and recent literature on the subject. This is a starting point for students wishing to become involved in areas of current research.
The mathematical prerequisites for this book are relatively modest. A reader who has mastered undergraduate courses in linear algebra, abstract algebra, and calculus should be well prepared. This includes upper-division undergraduate mathematics majors, mathematics graduate students, and graduate students studying information and storage systems in computer science and electrical engineering. We have tried to start from scratch with basic material that requires little background. Thus in the first five chapters no more than basic linear algebra and one-variable calculus is needed: matrices, linear transformations, similarity, eigenvalues, eigenvectors, and notions of convergence and continuity (there are also a few references to basic abstract algebra, but these are not crucial). Starting with Chapter 6, the required level of mathematical sophistication increases. We hope that the foundation laid in the first five chapters will inspire students to continue reading. Here the reader should know something more of linear algebra, including the Jordan canonical form, as well as some abstract algebra including groups, rings, fields, and ideals, and some basic notions from the topology of Euclidean space such as open set, closed set, and compact set, which are quickly reviewed.
The book contains over 500 exercises, ranging from simple checks of understanding to much more difficult problems and projects. Those that seem harder have been marked with a *. There is a detailed index as well as a notation index.
The authors have taught courses based on preliminary versions of this material at the University of Washington, Stanford University and the University of California at Berkeley. They have also given lecture series at the Mathematical Sciences Research Institute in Berkeley and the IBM Almaden Research Center. Based on these experiences, here are some suggestions on how to organize the material in this book into courses of different lengths. Chapters 1-5 would constitute a solid one-quarter course introducing symbolic dynamics from scratch and concluding with applications to coding. Chapters 1-7 could form a one-semester course that also includes more theoretical material and finishes with a detailed discussion of the conjugacy problem. The entire book can be covered in a one-year course that would bring students to the frontiers of current research. Of course, the material can be covered more quickly for students with more than the minimum required background.
This book has benefited enormously from suggestions, comments, and corrections made by many people (students, faculty and industrial researchers) on preliminary versions of this manuscript, in lectures on these versions, and in answers to our queries. These include Paul Algoet. Jonathan Ashley, Leslie Badoian, Mignon Belongie, Mike Boyle, Karen Brucks, Elise Cawley, Phil Chou, Wu Chou, Ethan Coven, Jim Fitzpatrick, Dave Forney, Lisa Goldberg, Michael Gormish, Michael Hollander, Danrun Huang, Natasha Jonoska, Sampath Kannan, Bruce Kitchens, Wolfgang Krieger, David Larsen, Nelson Markley, Lee Neuwirth, Kyewon Koh Park, Karl Petersen, Ronny Roth, Paul Siegel, Sylvia Silberger, N. T. Sindhushayana, Serge Troubetzkoy, Paul Trow, Selim Tuncel, Jeff Von Limbach, Jack Wagoner, Peter Walters, Barak Weiss, Susan Williams, and Amy Wilkinson. We are happy to thank Roy Adler, who first suggested the possibility of a textbook on symbolic dynamics, especially one that requires only a minimum amount of mathematical background. Adler’s 1984 set of unpublished lecture notes from Brown University and his notes on Markov partitions were valuable sources. We are also grateful to Elza Erkip, Amos Lapidoth, and Erik Ordentlich, who earned their just desserts by working so many of the exercises in the first five chapters. Special thanks are due to Zhe-xian Wan for very detailed and helpful comments on our manuscript and to Brian Hopkins for clarifying a multitude of murky passages and for eliminating an uncountable number of needless commas. This book is typeset using the LamSTeX extensions to TeX, and we thank Michael Spivak for his help with this. Finally, we wish to express our gratitude to the National Science Foundation (grants DMS-9004252 and DMS-9303240), the University of Washington, and the IBM Corporation for their support of this work.
» Collapse back