Book contents
- Frontmatter
- Contents
- Foreword
- Introduction
- Acknowledgments
- 1 Probability basics
- 2 Probability distributions
- 3 Measuring information
- 4 Entropy
- 5 Mutual information and more entropies
- 6 Differential entropy
- 7 Algorithmic entropy and Kolmogorov complexity
- 8 Information coding
- 9 Optimal coding and compression
- 10 Integer, arithmetic, and adaptive coding
- 11 Error correction
- 12 Channel entropy
- 13 Channel capacity and coding theorem
- 14 Gaussian channel and Shannon–Hartley theorem
- 15 Reversible computation
- 16 Quantum bits and quantum gates
- 17 Quantum measurements
- 18 Qubit measurements, superdense coding, and quantum teleportation
- 19 Deutsch–Jozsa, quantum Fourier transform, and Grover quantum database search algorithms
- 20 Shor's factorization algorithm
- 21 Quantum information theory
- 22 Quantum data compression
- 23 Quantum channel noise and channel capacity
- 24 Quantum error correction
- 25 Classical and quantum cryptography
- Appendix A (Chapter 4) Boltzmann's entropy
- Appendix B (Chapter 4) Shannon's entropy
- Appendix C (Chapter 4) Maximum entropy of discrete sources
- Appendix D (Chapter 5) Markov chains and the second law of thermodynamics
- Appendix E (Chapter 6) From discrete to continuous entropy
- Appendix F (Chapter 8) Kraft–McMillan inequality
- Appendix G (Chapter 9) Overview of data compression standards
- Appendix H (Chapter 10) Arithmetic coding algorithm
- Appendix I (Chapter 10) Lempel–Ziv distinct parsing
- Appendix J (Chapter 11) Error-correction capability of linear block codes
- Appendix K (Chapter 13) Capacity of binary communication channels
- Appendix L (Chapter 13) Converse proof of the channel coding theorem
- Appendix M (Chapter 16) Bloch sphere representation of the qubit
- Appendix N (Chapter 16) Pauli matrices, rotations, and unitary operators
- Appendix O (Chapter 17) Heisenberg uncertainty principle
- Appendix P (Chapter 18) Two-qubit teleportation
- Appendix Q (Chapter 19) Quantum Fourier transform circuit
- Appendix R (Chapter 20) Properties of continued fraction expansion
- Appendix S (Chapter 20) Computation of inverse Fourier transform in the factorization of N = 21 through Shor's algorithm
- Appendix T (Chapter 20) Modular arithmetic and Euler's theorem
- Appendix U (Chapter 21) Klein's inequality
- Appendix V (Chapter 21) Schmidt decomposition of joint pure states
- Appendix W (Chapter 21) State purification
- Appendix X (Chapter 21) Holevo bound
- Appendix Y (Chapter 25) Polynomial byte representation and modular multiplication
- Index
- References
9 - Optimal coding and compression
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Foreword
- Introduction
- Acknowledgments
- 1 Probability basics
- 2 Probability distributions
- 3 Measuring information
- 4 Entropy
- 5 Mutual information and more entropies
- 6 Differential entropy
- 7 Algorithmic entropy and Kolmogorov complexity
- 8 Information coding
- 9 Optimal coding and compression
- 10 Integer, arithmetic, and adaptive coding
- 11 Error correction
- 12 Channel entropy
- 13 Channel capacity and coding theorem
- 14 Gaussian channel and Shannon–Hartley theorem
- 15 Reversible computation
- 16 Quantum bits and quantum gates
- 17 Quantum measurements
- 18 Qubit measurements, superdense coding, and quantum teleportation
- 19 Deutsch–Jozsa, quantum Fourier transform, and Grover quantum database search algorithms
- 20 Shor's factorization algorithm
- 21 Quantum information theory
- 22 Quantum data compression
- 23 Quantum channel noise and channel capacity
- 24 Quantum error correction
- 25 Classical and quantum cryptography
- Appendix A (Chapter 4) Boltzmann's entropy
- Appendix B (Chapter 4) Shannon's entropy
- Appendix C (Chapter 4) Maximum entropy of discrete sources
- Appendix D (Chapter 5) Markov chains and the second law of thermodynamics
- Appendix E (Chapter 6) From discrete to continuous entropy
- Appendix F (Chapter 8) Kraft–McMillan inequality
- Appendix G (Chapter 9) Overview of data compression standards
- Appendix H (Chapter 10) Arithmetic coding algorithm
- Appendix I (Chapter 10) Lempel–Ziv distinct parsing
- Appendix J (Chapter 11) Error-correction capability of linear block codes
- Appendix K (Chapter 13) Capacity of binary communication channels
- Appendix L (Chapter 13) Converse proof of the channel coding theorem
- Appendix M (Chapter 16) Bloch sphere representation of the qubit
- Appendix N (Chapter 16) Pauli matrices, rotations, and unitary operators
- Appendix O (Chapter 17) Heisenberg uncertainty principle
- Appendix P (Chapter 18) Two-qubit teleportation
- Appendix Q (Chapter 19) Quantum Fourier transform circuit
- Appendix R (Chapter 20) Properties of continued fraction expansion
- Appendix S (Chapter 20) Computation of inverse Fourier transform in the factorization of N = 21 through Shor's algorithm
- Appendix T (Chapter 20) Modular arithmetic and Euler's theorem
- Appendix U (Chapter 21) Klein's inequality
- Appendix V (Chapter 21) Schmidt decomposition of joint pure states
- Appendix W (Chapter 21) State purification
- Appendix X (Chapter 21) Holevo bound
- Appendix Y (Chapter 25) Polynomial byte representation and modular multiplication
- Index
- References
Summary
The previous chapter introduced the concept of coding optimality, as based on variable-length codewords. As we have learnt, an optimal code is one for which the mean codeword length closely approaches or is equal to the source entropy. There exist several families of codes that can be called optimal, as based on various types of algorithms. This chapter, and the following, will provide an overview of this rich subject, which finds many applications in communications, in particular in the domain of data compression. In this chapter, I will introduce Huffman codes, and then I will describe how they can be used to perform data compression to the limits predicted by Shannon. I will then introduce the principle of block codes, which also enable data compression.
Huffman codes
As we have learnt earlier, variable-length codes are in the general case more efficient than fixed-length ones. The most frequent source symbols are assigned the shortest codewords, and the reverse for the less frequent ones. The coding-tree method makes it possible to find some heuristic codeword assignment, according to the above rule. Despite the lack of further guidance, the result proved effective, considering that we obtained η = 96.23% with a ternary coding of the English-character source (see Fig. 8.3, Table 8.3). But we have no clue as to whether other coding trees with greater coding efficiencies may ever exist, unless we try out all the possibilities, which is impractical.
- Type
- Chapter
- Information
- Classical and Quantum Information TheoryAn Introduction for the Telecom Scientist, pp. 151 - 178Publisher: Cambridge University PressPrint publication year: 2009