Introduction to
Information Theory and Data Compression

Darrel Hankerson, Greg A. Harris, and Peter D. Johnson Jr.

Preface

This textbook is aimed at graduate students and upper level undergraduates in mathematics, engineering, and computer science. The material and the approach of the text were developed over several years at Auburn University in two independent courses, Information Theory and Data Compression. Although the material in the two courses is related, we think it unwise for information theory to be a prerequisite for data compression, and have written the data compression section of the text so that it can be read by or presented to students with no prior knowledge of information theory. There are references in the data compression part to results and proofs in the information theory part of the text, and those who are interested may browse over those references, but it is not absolutely necessary to do so. In fact, perhaps the best pedagogical order of approach to these subjects is the reverse of the apparent logical order: students will come to information theory curious and better prepared for having seen some of the definitions and theorems of that subject playing a role in data compression.

Our main aim in the data compression part of the text, as well as in the course it grew from, is to acquaint the students with a number of significant lossless compression techniques, and to discuss two lossy compression methods. Our aim is for the students to emerge competent in and broadly conversant with a large range of techniques. We have striven for a ``practical'' style of presentation: here is what you do, and here is what it is good for. Nonetheless, proofs are provided, sometimes in the text, sometimes in the exercises, so that the instructor may have the option of emphasizing the mathematics of data compression to some degree.

Information theory is of a more theoretical nature than data compression. It provides a vocabulary and a certain abstraction that can bring the power of simplification to many different situations. We thought it reasonable to treat it as a mathematical theory, and to present the fundamental definitions and elementary results of that theory in utter abstraction from the particular problems of communication through noisy channels, which inspired the theory in the first place. We bring the theory to bear on noisy channels in Chapters 3 and 4.

The treatment of information theory given here is extremely elementary. The channels are memoryless and discrete, and the sources are all ``zeroth-order,'' one-state sources (although more complicated source models are discussed in Chapter 7). We feel that this elementary approach is appropriate for the target audience, and that, by leaving more complicated sources and channels out of the picture, we more effectively impart the grasp of Information Theory that we hope our students will take with them.

The exercises range from the routine to somewhat lengthy problems which introduce additional material or establish more difficult results. An asterisk by an exercise or section indicates that the material is off the main road, so to speak, and might reasonably be skipped. In the case of exercises, it may also indicate that the problem is hard and/or unusual.

In the data compression portion of the book, there are a number of projects which require the use of a computer. Appendix A documents Octave and Matlab scripts written by the authors which can be used on some of the exercises and projects involving transform methods and images, and which can also serve as building blocks for other explorations. The software may be obtained from the authors' site, listed in Appendix C. In addition, the site contains information about the book, an on-line version of Appendix A, and links to other sites of interest.

Organization

Here's a brief synopsis of each chapter and appendix.

Chapter 1 contains an introduction to the language and results of probability theory.

Chapter 2 presents the elementary definitions of information theory and the fundamental relations among various sorts of information and entropy.

Chapter 3 is about information flow through discrete memoryless noisy channels.

Chapter 4 is about coding text from a discrete source, transmitting the encoded text through a discrete memoryless noisy channel, and decoding the output.

Chapter 5 begins the material of the data compression portion of this book. Replacement schemes are discussed, and the chapter concludes with the Noiseless Coding Theorem.

Chapter 6 discusses arithmetic coding, which is of considerable interest since it is optimal in a certain way that the replacement schemes are not. Considerations for both an ``ideal'' scheme and for practical implementation on a computer are presented.

Chapter 7 focuses on the modeling aspects of Chapters 5 and 6 (Chapter 8 continues the discussion). Since coding methods such as those presented in Chapter 6 can (in theory) produce optimal-length output for a given model of the source, much of the interest in improving compression in statistical schemes lies in improving the model of the source. Higher-order models attempt to use larger contexts for predictions.

Chapter 8 considers another approach to modeling, using statistics which are updated as the source is read and encoded. These have the advantage that no statistical study needs to be done in advance, and the scheme can also detect changes in the nature of the source.

Chapter 9 discusses popular dictionary methods. These have been widely used, in part due to their simplicity, speed, and relatively good compression. Applications such as Ross Williams' LZRW1 algorithm, Unix compress, and GNU zip (gzip) are examined.

Chapter 10 develops the Fourier, cosine, and wavelet transforms, and discusses their use in compression of signals or images. The lossy scheme in JPEG is presented as a widely-used standard that relies on transform techniques. The chapter concludes with an introduction to wavelet-based compression.

Appendix A documents the use of the ``JPEGtool'' collection of Octave and Matlab scripts in understanding JPEG-like image compression.

Appendix B contains the source listing for Ross Williams' LZRW1-A algorithm, which rather concisely illustrates a viable dictionary compression method.

Appendix C contains material that didn't fit elsewhere. The first section lists sources for information and code for many areas of data compression. The second section contains a few notes on patents affecting the field. The final section contains a semi-famous story illustrating some of the misunderstandings about compression.

Appendix D offers solutions and notes on the exercises.

Acknowledgments

We'd like to thank Ross Williams for permission to reprint his LZRW1-A algorithm, and for notes on his sources. Alistair Moffat provided preprints and alerted us to other information concerning arithemetic coding. Ian H. Witten was kind enough to respond to our questions concerning a detail in Text Compression. We especially wish to acknowledge the help of four reviewers: Jean-loup Gailly offered many important suggestions concerning Chapter 9 and Appendix C, and granted permission to use portions of the ``Frequently Asked Questions'' document that he authors; Tom Lane suggested a number of improvements and clarifications in Chapter 10; we are grateful to James R. Wall and to Isidore Fleischer for reviewing portions of Chapters 1-5.

There are many folks who have made it easier for the community to understand the subject; some of their names are in this book. Others, working on ``GNU Project'' and other freely distributable software, made this book possible. The list of major contributors to this software is lengthy, and includes those involved with AUC TeX, dvips[k], Emacs, Ghostview and Ghostscript, GNU/Linux, the Independent JPEG Group, Info-ZIP, LaTeX, Netpbm, PiCTeX, Portable Network Graphics, TeX, xdvi[k], xfig, xv, Xy-pic, and many GNU utilities such as bash, gawk, gcc and gdb, gzip, and make. We wish to especially thank the principal developer of Octave, John Eaton.

Thanks are due to A. Scottedward Hodel, Alfred Menezes, Stan Reeves, and Greg Roelofs for some early advice on the data compression course. Our students were also generous with their advice, and most of it was valuable, but they are too numerous to mention by name. Douglas Leonard and Luc Teirlinck provided some insightful suggestions and clarifications. Alfred Menezes gets the credit (and the blame) for setting us on the road to a course in data compression and this book.

Some of the computer resources for the course and book were made possible by a grant from the National Science Foundation, for which we are grateful. Our direct contacts at CRC Press were Bob Stern, Nora Konopka, Suzanne Lassandro, Tim Pletscher, and Mimi Williams, and it was a pleasure working with them.

Darrel Hankerson
Greg A. Harris
Peter D. Johnson Jr.

Fall 1997

Information Theory and Data Compression / hankedr@mail.auburn.edu / August 1997