信息和编码理论

Preface

Notes to the Reader

1. Source Coding

1.1 Definitions and Examples

1.2 Uniquely Decodable Codes

1.3 Instantaneous Codes

1.4 Constructing Instantaneous Codes

1.5 Krafts Inequality

1.6 McMillans Inequality

1.7 Comments on Krafts and McMillans Inequalities

1.8 Supplementary Exercises

2. Optimal Codes

2.1 Optimality

2.2 Binary Huffman Codes

2.3 Average Word-length of Huffman Codes

2.4 Optimality of Binary Huffman Codes

2.5 r-ary Huffman Codes

2.6 Extensions of Sources

2.7 Supplementary Exercises

3. Entropy

3.1 Information and Entropy

3.2 Properties of the Entropy Function

3.3 Entropy and Average Word-length

3.4 Shannon-Fano Coding

3.5 Entropy of Extensions and Products

3.6 Shannons First Theorem

3.7 An Example of Shannons First Theorem

3.8 Supplementary Exercises

4. Information Channels

4.1 Notation and Definitions

4.2 The Binary Symmetric Channel

4.3 System Entropies

4.4 System Entropies for the Binary Symmetric Channel

4.5 Extension of Shannons First Theorem to Information Channels

4.6 Mutual Information

4.7 Mutual Information for the Binary Symmetric Channel

4.8 Channel Capacity

4.9 Supplementary Exercises

5. Using an Unreliable Channel

5.1 Decision Rules

5.2 An Example of Improved Reliability

5.3 Hamming Distance

5.4 Statement and Outline Proof of Shannons Theorem

5.5 The Converse of Shannons Theorem

5.6 Comments on Shannons Theorem

5.7 Supplementary Exercises

6. Error-correcting Codes

6.1 Introductory Concepts

6.2 Examples of Codes

6.3 Minimum Distance

6.4 Hammings Sphere-packing Bound

6.5 The Gilbert-Varshamov Bound

6.6 Hadamard Matrices and Codes

6.7 Supplementary Exercises

7. Linear Codes

7.1 Matrix Description of Linear Codes

7.2 Equivalence of Linear Codes

7.3 Minimum Distance of Linear Codes

7.4 The Hamming Codes

7.5 The Golay Codes

7.6 The Standard Array

7.7 Syndrome Decoding

7.8 Supplementary Exercises

Suggestions for Further Reading

Appendix A. Proof of the Sardinas-Patterson Theorem

Appendix B. The Law of Large Numbers

Appendix C. Proof of Shannons Fundamental Theorem

Solutions to Exercises

Bibliography

Index of Symbols and Abbreviations

Index

信息和代数编码理论足数学、计算机科学和信息科学领域的重要学科。《信息和编码理论》介绍信息理沦、有限域和线性代数的基本知识，起点较低，易于学习；书有大量例子和习题，并附有习题解答或提示。《信息和编码理论》适合用作数学系、计算机科学系和信息科学系本科生高年级必修或选修课程教材或参考书。

《信息和编码理论》以较多篇幅讲述信息论方面的内容，而编码理论方面内容则较为简单（只讲述运用线性代数的线性码，没有讲运用抽象代数的循环码）。目前已有的其他相关书籍则是信息论方面讲得少（甚至不讲），而编码方面讲得多，这两者恰好可以相互补充。