COVID-19 Update: We are currently shipping orders daily. However, due to transit disruptions in some geographies, deliveries may be delayed. To provide all customers with timely access to content, we are offering 50% off Science and Technology Print & eBook bundle options. Terms & conditions.
Introduction to Data Compression - 4th Edition - ISBN: 9780124157965, 9780124160002

Introduction to Data Compression

4th Edition

Author: Khalid Sayood
eBook ISBN: 9780124160002
Hardcover ISBN: 9780124157965
Imprint: Morgan Kaufmann
Published Date: 4th October 2012
Page Count: 768
Sales tax will be calculated at check-out Price includes VAT/GST
Price includes VAT/GST

Institutional Subscription

Secure Checkout

Personal information is secured with SSL technology.

Free Shipping

Free global shipping
No minimum order.

Table of Contents

Editor Board



1 Audience

2 Course Use

3 Approach

4 Learning from This Book

5 Content and Organization

6 A Personal View



1.1 Compression Techniques

1.2 Modeling and Coding

1.3 Summary

1.4 Projects and Problems


Mathematical Preliminaries for Lossless Compression

2.1 Overview

2.2 A Brief Introduction to Information Theory

2.3 Models

2.4 Coding

2.5 Algorithmic Information Theory

2.6 Minimum Description Length Principle

2.7 Summary

2.8 Projects and Problems


Huffman Coding

3.1 Overview

3.2 The Huffman Coding Algorithm

3.3 Nonbinary Huffman Codes

3.4 Adaptive Huffman Coding

3.5 Golomb Codes

3.6 Rice Codes

3.7 Tunstall Codes

3.8 Applications of Huffman Coding

3.9 Summary

Further Reading

3.10 Projects and Problems


Arithmetic Coding

4.1 Overview

4.2 Introduction

4.3 Coding a Sequence

4.4 Generating a Binary Code

4.5 Adaptive Arithmetic Coding

4.6 Binary Arithmetic Coding

4.7 Comparison of Huffman and Arithmetic Coding

4.8 Applications

4.9 Summary

4.10 Projects and Problems


Dictionary Techniques

5.1 Overview

5.2 Introduction

5.3 Static Dictionary

5.4 Adaptive Dictionary

5.5 Applications

5.6 Beyond Compression—Lempel-Ziv Complexity

5.7 Summary

5.8 Projects and Problems


Context-Based Compression

6.1 Overview

6.2 Introduction

6.3 Prediction with Partial Match (ppm)

6.4 The Burrows-Wheeler Transform

6.5 Associative Coder of Buyanovsky (ACB)

6.6 Dynamic Markov Compression

6.7 Summary

6.8 Projects and Problems


Lossless Image Compression

7.1 Overview

7.2 Introduction



7.5 Prediction Using Conditional Averages

7.6 Multiresolution Approaches

7.7 Facsimile Encoding

7.8 MRC–T.44

7.9 Summary

7.10 Projects and Problems


Mathematical Preliminaries for Lossy Coding

8.1 Overview

8.2 Introduction

8.3 Distortion Criteria

8.4 Information Theory Revisited

8.5 Rate Distortion Theory

8.6 Models

8.7 Summary

8.8 Projects and Problems


Scalar Quantization

9.1 Overview

9.2 Introduction

9.3 The Quantization Problem

9.4 Uniform Quantizer

9.5 Adaptive Quantization

9.6 Nonuniform Quantization

9.7 Entropy-Coded Quantization

9.8 Summary

9.9 Projects and Problems


Vector Quantization

10.1 Overview

10.2 Introduction

10.3 Advantages of Vector Quantization over Scalar Quantization

10.4 The Linde-Buzo-Gray Algorithm

10.5 Tree-Structured Vector Quantizers

10.6 Structured Vector Quantizers

10.7 Variations on the Theme

10.8 Trellis-Coded Quantization

10.9 Summary

Further Reading

10.10 Projects and Problems


Differential Encoding

11.1 Overview

11.2 Introduction

11.3 The Basic Algorithm

11.4 Prediction in DPCM

11.5 Adaptive DPCM

11.6 Delta Modulation

11.7 Speech Coding

11.8 Image Coding

11.9 Summary

11.10 Projects and Problems


Mathematical Preliminaries for Transforms, Subbands, and Wavelets

12.1 Overview

12.2 Introduction

12.3 Vector Spaces

12.4 Fourier Series

12.5 Fourier Transform

12.6 Linear Systems

12.7 Sampling

12.8 Discrete Fourier Transform

12.9 Z-Transform

12.10 Summary

12.11 Projects and Problems


Transform Coding

13.1 Overview

13.2 Introduction

13.3 The Transform

13.4 Transforms of Interest

13.5 Quantization and Coding of Transform Coefficients

13.6 Application to Image Compression– JPEG

13.7 Application to Audio Compression–The MDCT

13.8 Summary

13.9 Projects and Problems


Subband Coding

14.1 Overview

14.2 Introduction

14.3 Filters

14.4 The Basic Subband Coding Algorithm

14.5 Design of Filter Banks

14.6 Perfect Reconstruction Using Two-Channel Filter Banks

14.7 M-Band QMF Filter Banks

14.8 The Polyphase Decomposition

14.9 Bit Allocation

14.10 Application to Speech Coding—G.722

14.11 Application to Audio Coding—MPEG Audio

14.12 Application to Image Compression

14.13 Summary

14.14 Projects and Problems



15.1 Overview

15.2 Introduction

15.3 Wavelets

15.4 Multiresolution Analysis and the Scaling Function

15.5 Implementation Using Filters

15.6 Biorthogonal Wavelets

15.7 Lifting

15.8 Summary

Further Reading

15.9 Projects and Problems


Wavelet-Based Image Compression

16.1 Overview

16.2 Introduction

16.3 Embedded Zerotree Coder

16.4 Set Partitioning in Hierarchical Trees

16.5 JPEG 2000

16.6 Summary

16.7 Projects and Problems


Audio Coding

17.1 Overview

17.2 Introduction

17.3 MPEG Audio Coding

17.4 MPEG Advanced Audio Coding

17.5 Dolby AC-3 (Dolby Digital)

17.6 Other Standards

17.7 Summary


Analysis/Synthesis and Analysis by Synthesis Schemes

18.1 Overview

18.2 Introduction

18.3 Speech Compression

18.4 Wideband Speech Compression—ITU-T G.722.2

18.5 Coding of Speech for Internet Applications

18.6 Image Compression

18.7 Summary

18.8 Projects and Problems


Video Compression

19.1 Overview

19.2 Introduction

19.3 Motion Compensation

19.4 Video Signal Representation

19.5 ITU-T Recommendation H.261

19.6 Model-Based Coding

19.7 Asymmetric Applications

19.8 The MPEG-1 Video Standard

19.9 The MPEG-2 Video Standard—H.262

19.10 ITU-T Recommendation H.263

19.11 ITU-T Recommendation H.264, MPEG-4 Part 10, Advanced Video Coding

19.12 MPEG-4 Part 2

19.13 Packet Video

19.14 Summary

19.15 Projects and Problems


Appendix A. Probability and Random Processes

A.1 Probability

A.2 Random Variables

A.3 Distribution Functions

A.4 Expectation

A.5 Types of Distribution

A.6 Stochastic Process

A.7 Projects and Problems


Appendix B. A Brief Review of Matrix Concepts

B.1 A Matrix

B.2 Matrix Operations


Appendix C. The Root Lattices





Introduction to Data Compression, Fourth Edition, is a concise and comprehensive guide to the art and science of data compression. This new edition includes all the cutting edge updates the reader will need during the work day and in class. It provides an extensive introduction to the theory underlying today’s compression techniques with detailed instruction for their applications using several examples to explain the concepts.

Encompassing the entire field of data compression, this book covers lossless and lossy compression, Huffman coding, arithmetic coding, dictionary techniques, context based compression, scalar and vector quantization. New to this fourth edition is a more detailed description of the JPEG 2000 standard as well as speech coding for internet applications. A source code is also provided via a companion web site that gives readers the opportunity to build their own algorithms, choose and implement techniques in their own applications.

This text will appeal to professionals, software and hardware engineers, students, and anyone interested in digital libraries and multimedia.

Key Features

  • New content added to include a more detailed description of the JPEG 2000 standard
  • New content includes speech coding for internet applications
  • Explains established and emerging standards in depth including JPEG 2000, JPEG-LS, MPEG-2, H.264, JBIG 2, ADPCM, LPC, CELP, MELP, and iLBC
  • Source code provided via companion web site that gives readers the opportunity to build their own algorithms, choose and implement techniques in their own applications


Professionals, software and hardware engineers, students; digital libraries, multimedia


No. of pages:
© Morgan Kaufmann 2012
4th October 2012
Morgan Kaufmann
eBook ISBN:
Hardcover ISBN:


This text is a truly introductory treatment of the entire field of data compression, including lossless coding, speech coding, and audio coding, which are often neglected in other data compression books. Sayood’s book has the very best tutorial treatment of lossless source coding anywhere, with detailed coverage of Lempel-Ziv, arithmetic, Golumb, and Tunstall coding, in addition to treatments of fixed and adaptive Huffman coding and context-based methods. Additionally, the book contains material on M-band quadrature mirror filter banks, the polyphase decomposition, and wavelets beyond what is normally found in any introductory text. I have used Sayood’s book for a reference and as a text for a course on signal compression. I highly recommend it for adoption. --Jerry D. Gibson, Professor of Electrical and Computer Engineering, University of California, Santa Barbara

Khalid Sayood's book has long been the standard academic reference for those interested in Data Compression. I am very pleased to see his ongoing effort to keep the content timely with the release of the fourth edition this fall. If you want to be well versed in state of the art, ranging from simple lossless coding up to complex video compression, this is the only book I know that will stay with you on every step of the journey. --Mark Nelson, Engineer at Cisco Systems, Inc and Senior Member of IEEE

Ratings and Reviews

About the Author

Khalid Sayood

Khalid Sayood

Khalid Sayood received his BS and MS in Electrical Engineering from the University of Rochester in 1977 and 1979, respectively, and his Ph.D. in Electrical Engineering from Texas A&M University in 1982. In 1982, he joined the University of Nebraska, where he is the Heins Professor of Engineering. His research interests include data compression, joint source channel coding, and bioinformatics.

Affiliations and Expertise

Department of Electrical and Computer Engineering, University of Nebraska, Lincoln, Nebraska, USA