Information and Coding Theory Book

	Preface	v
	Notes to the Reader	xiii
1.	Source Coding	1
1.1	Definitions and Examples	1
1.2	Uniquely Decodable Codes	4
1.3	Instantaneous Codes	9
1.4	Constructing Instantaneous Codes	11
1.5	Kraft's Inequality	13
1.6	McMillan's Inequality	14
1.7	Comments on Kraft's and McMillan's Inequalities	16
1.8	Supplementary Exercises	17
2.	Optimal Codes	19
2.1	Optimality	19
2.2	Binary Huffman Codes	22
2.3	Average Word-length of Huffman Codes	26
2.4	Optimality of Binary Huffman Codes	27
2.5	r-ary Huffman Codes	28
2.6	Extensions of Sources	30
2.7	Supplementary Exercises	32
3.	Entropy	35
3.1	Information and Entropy	35
3.2	Properties of the Entropy Function	40
3.3	Entropy and Average Word-length	42
3.4	Shannon-Fano Coding	45
3.5	Entropy of Extensions and Products	47
3.6	Shannon's First Theorem	48
3.7	An Example of Shannon's First Theorem	49
3.8	Supplementary Exercises	51
4.	Information Channels	55
4.1	Notation and Definitions	55
4.2	The Binary Symmetric Channel	60
4.3	System Entropies	62
4.4	System Entropies for the Binary Symmetric Channel	64
4.5	Extension of Shannon's First Theorem to Information Channels	67
4.6	Mutual Information	70
4.7	Mutual Information for the Binary Symmetric Channel	72
4.8	Channel Capacity	73
4.9	Supplementary Exercises	76
5.	Using an Unreliable Channel	79
5.1	Decision Rules	79
5.2	An Example of Improved Reliability	82
5.3	Hamming Distance	85
5.4	Statement and Outline Proof of Shannon's Theorem	88
5.5	The Converse of Shannon's Theorem	90
5.6	Comments on Shannon's Theorem	93
5.7	Supplementary Exercises	94
6.	Error-correcting Codes	97
6.1	Introductory Concepts	97
6.2	Examples of Codes	100
6.3	Minimum Distance	104
6.4	Hamming's Sphere-packing Bound	107
6.5	The Gilbert-Varshamov Bound	111
6.6	Hadamard Matrices and Codes	114
6.7	Supplementary Exercises	118
7.	Linear Codes	121
7.1	Matrix Description of Linear Codes	121
7.2	Equivalence of Linear Codes	127
7.3	Minimum Distance of Linear Codes	131
7.4	The Hamming Codes	133
7.5	The Golay Codes	136
7.6	The Standard Array	141
7.7	Syndrome Decoding	143
7.8	Supplementary Exercises	146
	Suggestions for Further Reading	149
Appendix A.	Proof of the Sardinas-Patterson Theorem	153
Appendix B.	The Law of Large Numbers	157
Appendix C.	Proof of Shannon's Fundamental Theorem	159
	Solutions to Exercises	165
	Bibliography	191
	Index of Symbols and Abbreviations	195
	Index	201